IPG
An Integer Programming Game is a simultaneous game among \(n\) players solving a parameterized (mixed) Integer Program. In ZERO, we support IPGs where each player \(i\) solves the following problem:
Where \(\mathcal{I}\) is the set of indices of integer variables. In other words, the objective function takes a specific bi-linear form.
A quick example
Consider the following Integer Programming Game: The first player is the x player, whose decision variables are \(x\). The second player is the y player where its variables are \(y\).
Note
We slightly change the notation with respect to ZERO’s arguments for the exposition of this game. For instance, here for \(x\), we point to the first player’s variables instead of the parameters of a IP_Param
. The example below should clarify any doubt.

The x player’s optimization problem is as follows
While the y player’s optimization problem is:
The problem has two pure Nash equilibria \((x_1, x_2, y_1, y_2) = (0, 1, 1, 0)\), and \((x_1, x_2, y_1, y_2) = (1, 0, 0, 1)\), and a mixed Equilibrium \((x_1, x_2, y_1, y_2) = (2/9, 7/9, 2/5, 3/5)\).
Modeling and solving the problem
The first step in modeling this Integer Programming Game is to include zero.h and create a derived class of Game::IPG
. The minimal constructor for Game::IPG
involves passing a pointer to GRBEnv (Check Gurobi’s C++ reference manual
). The derived class should indeed instantiate the base class (Game::IPG) using such a constructor. The code below gives an example.
#include <zero.h>
int main(int argc, char **argv) {
GRBEnv GurobiEnv;
try {
Models::IPG::IPGInstance IPG_Instance;
int numItems = 2;
int numPlayers = 2;
// Objective terms
arma::vec c(numItems);
arma::sp_mat C(numPlayers * (numItems - 1), numItems);
// Constraints
arma::sp_mat a(1, numItems);
arma::vec b(1);
// The index of the integer variables
arma::vec IntegerIndexes(numItems);
// Implicit bounds on variables. Could be omitted
VariableBounds VarBounds = {{0, 1}, {0, 1}};
for (unsigned int i = 0; i < numItems; ++i)
IntegerIndexes.at(i) = i;
C(0, 0) = 2;
C(1, 1) = 3;
a(0, 0) = 3;
a(0, 1) = 4;
b(0) = 5;
// The standard is minimization.
c(0) = -1;
c(1) = -2;
// Create a parametrized Integer Program
MathOpt::IP_Param PlayerOne(C, a, b, c, IntegerIndexes, VarBounds, &GurobiEnv);
// Let's create another parametrized Integer Program for the second player.
// We'll reuse the previously created matrices and vectors
C(0, 0) = 5;
C(1, 1) = 4;
a(0, 0) = 2;
a(0, 1) = 5;
c(0) = -3;
c(1) = -5;
MathOpt::IP_Param PlayerTwo(C, a, b, c, IntegerIndexes, VarBounds, &GurobiEnv);
// Add the players to the instance. We also specify a file path to write the instance
IPG_Instance.addIPParam(PlayerOne, "A_Parametrized_KnapsackProblem1");
IPG_Instance.addIPParam(PlayerTwo, "A_Parametrized_KnapsackProblem2");
// Save the instance with the standardize format
IPG_Instance.save("A_Knapsack_Game");
// Create a model from the instance
Models::IPG::IPG IPG_Model(&GurobiEnv, IPG_Instance);
// Select the equilibrium to compute a Nash Equilibrium
IPG_Model.setAlgorithm(Data::IPG::Algorithms::CutAndPlay);
// Extra parameters
IPG_Model.setDeviationTolerance(3e-4);
IPG_Model.setNumThreads(4);
IPG_Model.setLCPAlgorithm(Data::LCP::Algorithms::PATH);
IPG_Model.setGameObjective(Data::IPG::Objectives::Feasibility);
IPG_Model.setTimeLimit(600);
// Lock the model
IPG_Model.finalize();
// Run!
IPG_Model.findNashEq();
// Print the solution
IPG_Model.getX().at(0).print("Player 1:");
IPG_Model.getX().at(1).print("\n Player 2:");
} catch (ZEROException &e) {
throw ZEROException(e);
}
}
With the method setAlgorithm of
Game::IPG
, we set the algorithm to solve the Integer Programming Game. So far, onlyAlgorithms::IPG::CutAndPlay
is available.The method setLCPAlgorithm specifies the algorithm used to solve the LCPs. It can be either
Data::LCP::Algorithms::MIP
,Data::LCP::Algorithms::PATH
, orData::LCP::Algorithms::MINLP
.The game’s objective (not supported by PATH) forces an objective into the LCP problem as to increase the chances of finding a good equilibrium given the objective. Values can be
Data::IPG::Objectives::Quadratic
Data::IPG::Objectives::Linear
Data::IPG::Objectives::Feasibility
.Other options can be found in the documentation of
Game::IPG