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
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.