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.


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