# What is an RBG?

A Reciprocally Bilinear Game is a simultaneous non-cooperative game among $$n$$ players with each player $$i=1,2,\dots,n$$ solving the optimization problem

$\begin{split}\min{x^i} (c^i)^\top x^i + (x^{-i})^\top C^ix^i \\ \text{s.t.} \quad x^i \in \mathcal{X}^i\end{split}$

where $$\mathcal{X}^i$$ is a set (not necessarily closed), $$C$$ and $$c$$ are a matrix and a vector of appropriate dimensions. An RBG is polyhedrally representable if $$\text{cl conv}(\mathcal{X}^i)$$ is a polyhedron for every $$i$$, and one can optimize an arbitrary linear funciton on $$\mathcal{X}^i$$. As a standard game-theory notation, the operator $$(\cdot)^i$$ refers to an object of player $$i$$ with $$i \in \{ 1,2,\dots,n\}$$, and $$(\cdot)^{-i}$$ be $$(\cdot^1,\dots, \cdot^{i-1},\cdot^{i+1},\dots,\cdot^{n})$$.

From the definition, the following properties hold for each player $$i$$:

• its objective function is reciprocally bilinear, namely, it is linear in its variables $$x^i$$, and bilinear in the other players’ ones $$x^{-i}$$

• its constraint set $$\mathcal{X}^i$$ is not parametrized in $$x^{-i}$$, i.e., the interaction takes place at the objective level thus the problem is not a generalized Nash equilibrium problem.

The set $$\text{cl conv}(\mathcal{X}^i)$$ as it represents the set of all mixed strategies that the player can adopt. We refer to [CNP] for a detailed review on the mathematics.

CNP

Margarida Carvalho, Gabriele Dragotto, Andrea Lodi, Sriram Sankaranarayanan. The Cut and Play Algorithm: Computing Nash Equilibria via Outer Approximations.