Simultaneous Games
In this class, we use a Linear Complementarity Problem (LCP) to solve a simultaneous non-cooperative game among \(n\) players (aka Nash Games in the optimization community).
Specifically, each player solves Parametrized Quadratic Program – stored in an instance of MathOpt::QP_Param – where the parameters are the other players’ decisions the variables are the player’s decision variables.
We will use members of the class Game::NashGame to model the game. This class will extensively invoke MathOpt::LCP to find the Nash equilibria.
A theory primer
Assume we have a simultaneous non-cooperative game among \(n\) players, so that each of them solves a convex Parametrized Quadratic Program such as:
Then, one can compute a Nash equilibrium for this game by considering the KKT conditions of each player and grouping them. For each player, the KKT conditions are equivalent to the following LCP problem.
As a standard game-theory notation, let the operator \((\cdot)^i\) refer 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})\). The \(y\) variables for player \(i\) are then just the vector \(x^{-i}\), namely the variables of other players. By renaming each player’s \(i\) variables \(y\) to \(x^i\), and parameters \(x\) to \(x^{-i}\), a Nash equilibrium for the game corresponds to a solution to following LCP:
Modeling the problem
We now model a simple simultaneous game among two players. Their two optimization problem are as follows.
Player 1
Player 2
The above problem corresponds to a Cournot Competition where the demand curve is given by \(P = a-BQ\) where P is the market price and Q is the quantity in the market. A convex quadratic function gives the cost of production of both the producers in the quantity they produce. The solution to the problem is to find a Nash Equilibrium from which neither producer can deviate.
To handle this problem, first, we create two objects of MathOpt::QP_Param to model each player’s optimization problem, as parameterized by the other.
#include "zero.h"
//[...] Your other code here
GRBEnv env;
arma::sp_mat Q(1, 1), A(0, 1), B(0, 1), C(1, 1);
arma::vec b, c(1), d(1);
b.set_size(0);
Q(0, 0) = 2 * 1.1;
C(0, 0) = 1;
c(0) = -90;
auto q1 = std::make_shared<MathOpt::QP_Param>(Q, C, A, B, c, b, d, &env);
Q(0, 0) = 2 * 1.2;
c(0) = -95;
auto q2 = std::make_shared<MathOpt::QP_Param>(Q, C, A, B, c, b, d, &env);
// We create a vector with the two QP_Params
std::vector<shared_ptr<MathOpt::QP_Param>> q{q1, q2};
/ /Cast to abstract MP_Param
std::shared_ptr<MathOpt::MP_Param>> MPCasted=std::dynamic_cast<MathOpt::MP_Param>(q);
Since we do not have any Market clearing constraints (more mathematical details), we set empty matrices for them. If the problem does not have market-clearing constraints, the matrices must be input with zero rows and the appropriate number of columns.
arma::sp_mat MC(0, 2);
arma::vec MCRHS;
MCRHS.set_size(0);
Finally, we can instantiate the Game::NashGame object by invoking the constructor.
Game::NashGame Nash = Game::NashGame(&env, MPCasted, MC, MCRHS);
The LCP problem to solve this nash game is then:
The method Game::NashGame::FormulateLCP() formulates the above LCP.
arma::sp_mat M;
arma::vec q;
// Stores the complementarity pairs relationships
perps Compl;
// Compute the LCP conditions
Nash.FormulateLCP(M, q, Compl);
M.print();
q.print();
Here M and q are such that the solution to the LCP \(0 \le x \perp Mx + q \ge 0\) solves the Nash Game. These matrices can be written to a file and solved externally now.
Alternatively, one can pass it to the Game::LCP class, and solve it natively. To achieve this, one can pass the above matrices to the constructor of the Game::LCP class.
Game::LCP lcp = Game::LCP(&env, M, q, 1, 0);
More concisely, the class Game::LCP offers a constructor with a NashGame as an argument. This way, one need not explicitly compute M, q.
Game::LCP lcp2 = Game::LCP(&env, Nash);
Computing solutions
We can now solve the instance of Game::LCP.
auto model = lcp.LCPasMIP();
model.optimize();
As was the case with MathOpt::QP_Param::solveFixed(), the above function returns a
unique_ptr to GRBModel.
Checking solutions
The solution to this problem is \(q_1=28.271028, q_2=27.803728\). In order to verify the solution, one can create a solution vector and solve each player’s MathOpt::QP_Param and check that the solution indeed matches.
arma::vec Nashsol(2);
Nashsol(0) = model->getVarByName("x_0").get(GRB_DoubleAttr_X); // This is 28.271028
Nashsol(1) = model->getVarByName("x_1").get(GRB_DoubleAttr_X); // This is 27.803728
auto nashResp1 = Nash.respond(0, Nashsol);
auto nashResp2 = Nash.respond(1, Nashsol);
cout<<nashResp1->getVarByName("y_0").get(GRB_DoubleAttr_X)<<endl; // Should print 28.271028
cout<<nashResp2->getVarByName("y_0").get(GRB_DoubleAttr_X)<<endl; // Should print 27.803728
If only one does not want the individual GRBModel handles but just wants to confirm that the problem is solved or provide a player with profitable deviation, one can just use cpp:func:Game::NashGame::isSolved function as follow.
unsigned int temp1 ; arma::vec temp2;
// This should be true.
cout<<Nash.isSolved(Nashsol, temp1, temp2);
If the Game::NashGame::isSolved() function returns false, then temp1 and temp2 respectively contain the player with profitable deviation and the more profitable strategy of the player.
Furthermore, note that just like MathOpt::QP_Param, Game::NashGame can also be saved and loaded from an external file.
Nash.save("dat/Nash.dat");
Game::NashGame Nash2(&env);
Nash2.load("dat/Nash.dat");