Implementation of the sampled generation method (SGM) for equilibria computation of integer programming games (IPGs). See:
A game is any list of players. To define a player, you must define the strategy space and the payoff function. The strategy space is handled through JuMP models, while payoff functions are handled by our structures (see Bilateral payoff games below for examples). Additionally, we need to keep track of references for the decision variables and the index of each player in the game.
The following illustrates the necessary steps to define the players:
using IPG
p1 = Player(); ... ; pn = Player()
# variable definition
@variable(p1.X, x1[1:5], Int)
@variable(p1.X, y1 >= 0)
@constraint(p1.X, ...) # add your constraints
... # the same for players 2..n
# set payoff function
set_payoff!(p1, c' * x1 + 0.5 * x1' * x2)
...The payoff is defined as a JuMP expression. Thus far, any quadratic jump expression is supported. In the (near) future, we expect to support nonlinear expressions as well, which could be handled by the SGM for two-player games.
The following is based on Example 5.3, from Carvalho, Lodi, and Pedroso (2020).
julia> using IPG, SCIP
julia> P1 = Player(); P2 = Player();
julia> @variable(P1.X, x1, start=10)
x1
julia> @constraint(P1.X, x1 >= 0)
x1 ≥ 0
julia> @variable(P2.X, x2 >= 0, start=10)
x2
julia> set_payoff!(P1, -x1*x1 + x1*x2)
-x1² + x1*x2
julia> set_payoff!(P2, -x2*x2 + x1*x2);
julia> Σ, payoff_improvements = SGM([P1, P2], SCIP.Optimizer, max_iter=5);
julia> Σ[end]
2-element Vector{DiscreteMixedStrategy}:
DiscreteMixedStrategy([1.0], [[0.625]])
DiscreteMixedStrategy([1.0], [[1.25]])
Further details in example_5_3.jl. In fact, check out examples/.
Many components of the algorithm can be modified, as is already discussed in the original work (Table 1 and Section 6.2, Carvalho, Lodi, and Pedroso, 2020). To choose between different options, you have only to assign different implementations to the baseline pointer. Note that those different implementations can be custom, local functions as well.
A practical example is shown in example_5_3.jl, at section Customization. Below, we detail the customizable parts and the available options.
A initial strategy for each player is necessary to start the SGM algorithm. If all player's variables are assigned start values through JuMP's interface, that will be used as the initial strategy.
Otherwise, the default procedure is to solve the feasibility problem for each player (see initialize_strategies_feasibility).
We have also implemented the initialization procedure that solves the best strategy for each player when she is alone (other strategies set to zero).
To change to this alternative approach, you just need to add IPG.initialize_strategies = IPG.initialize_strategies_player_alone before calling the SGM method.
By default, we solve the sampled games using NormalGames.jl, which has not been published (yet). Ask for permission and follow the installation instructions at https://github.com/mxmmargarida/Normal-form-games. Any nash equilibria method can be used. By default, we have wrapped NormalGames' implentation of Porter, Nudelman and Shoham's method in solve_PNS. We also provide a wrapper for the Big-M formulation of Sandholm et al. (2005) in solve_Sandholm1. To choose the latter instead of the former, just assign it to IPG.solve.
SGM iterates over the players until a deviation from the current candidate equilibrium is found. The order in which this iteration happens can deeply impact the performance and the equilibrium found. The default approach is to order the players in a descending order of the number of iterations since that player found a deviation (get_player_order_by_last_deviation). Other simples methods are also implemented. To choose between them or to simply use your own, assign a different method to IPG.get_player_order.
A deviation from the candidate equilibrium is found by computing a player's best response. This is implemented in find_deviation_best_response, and any solver can be used to solve these optimization problems, as is going to be discussed below. To use a custom method, assign it to IPG.find_deviation.
MIP solvers are used (in the default methods) for the initialization of strategies and for computing a deviation (best response, by default) from the candidate equilibrium. Any JuMP-supported MIP solver that can handle the players' problem can be used in SGM. For example, it may be that your players have quadratic constraints, so you will need a MIQCP solver. Your call will look like SGM(my_players, MySolver.Optimizer).
The algorithm also supports using a different solver for each player. You just need to initialize each player's strategy space with that optimizer factory or use JuMP's method, e.g., set_optimizer(player, MySolver.Optimizer). It is important to note that the optimizer_factory that is provided to SGM will not overwrite any player's optimizer. It will be set as the player's optimizer only if no optimizer has been set.