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 Integer Programming Game for this example is a Knapsack Game.

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