# 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:

$\begin{split}\min_{x^i} (c^i) ^\top x^i + (x^{-i})^\top C^ix^i \\ \text{s.t.} \quad A^ix^i\le b^i \\ \quad \quad x^i \ge 0 \\ \quad \quad x^i_j \in \mathbb{N} \quad \forall j \in \mathcal{I}^i\end{split}$

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

\begin{align}\begin{aligned}\max_{x_1, x_2} x_1 + 2x_2 - 2x_1y_1 -3x_2y_2\\\text{s.t.} \quad 3x_1+4x_2 &\le 5\\\quad \quad x_1, x_2 &\in \{0,1\}\end{aligned}\end{align}

While the y player’s optimization problem is:

\begin{align}\begin{aligned}\max_{y_1, y_2} 3y_1 + 5y_2 - 5y_1x_1 -4y_2x_2\\\text{s.t.} \quad 2y_1+5y_2 &\le 5\\\quad \quad y_1, y_2 &\in \{0,1\}\end{aligned}\end{align}

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
// 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.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);
}
}