The correlated equilibrium is theoretically very easy to implement as a linear programming (LP) task. This problem becomes more complicated when larger games (many players, many strategies) are being solved. Large games generate enormous size of strategic state space (number of strategic profiles) – number of constraints and variables in LP task grows rapidly. Some sort of reduction must be used. The method itself is described in [1], [2], [3] and [4].

Described implementation was created as a part of master's thesis of Stanislav Židek [2].

- N - number of players in the game,
- S_i - strategy set of the i-th player, |S_i| denotes the size of S_i. State space is given by cartesian product of strategy sets, S=S_1 x S_2 x ... x S_N. Members of
*S*are called strategic profiles. - U_i(s) - utility function of the i-th player for a given profile

- representation of N-player games in just two dimensions and
- game minimization by a method following elimination of strictly dominated strategies.

The minimization usually significantly reduces game strategy space and the resulting game can be easily solved as LP problem. For details about exact structure of G-matrix or computing correlated equilibrium as LP problem, please see [1] or [2].

- library interface – CE-solver is used as a library. Game model is created as object with very simple interface (abstract base class).
- tool interface – CE-solver is used as a command line utility, which uses a game stored in file as its input.

Instead, we adopted a new approach that stores only the information that is crucially needed. To represent a G-matrix of a given game, it is enough to store the strategies that have already been eliminated, so we need just B boolean flags, where B = S_1 + ... + S_N.

We do the elimination until no more strategies could be eliminated. Also, we use special structure to store information about where we stopped last time in every row, so we do not compute anything twice or more times.

- players() – returns the number of players
- strategies() – returns a number of strategies of all palyers in structure StrategyProfile
- get(StrategyProfile prof) – returns payoffs of all players when strategy profile prof is being played

Then you can use CESolver object to solve the game:

//game - created model of the game CESolver<true> ces(game); //create CESolver object ces.solve(); //call its method solve() CorrelatedEquilibrium ce = ces.get_solution();

CorrelatedEquilibrium is in fact typedef for std::map of probabilities indexed by strategy profiles.

N |S_1| |S_2| ... |S_N| U_1(s^1) U_2(s^1) ... U_N(s^1) U_1(s^2) U_2(s^2) ... U_N(s^2) ... U_1(s^X) U_2(s^X) ... U_N(s^X)

The profiles {s^1, s^2, ..., s^X}, X=|S| are ordered:

for s_1:=1 to |S_1| do for s_2:=1 to |S_2| do ... for s_N:=1 to |S_N| do import or export the vector of utility functions (U_1(s_1), U_2(s_2), ..., U_N(s_N))

For example, let us have a game:

row/column player | left | right |

top | 1,2 | 3,4 |

bottom | 5,6 | 7,8 |

It can be serialized to:

2 2 2 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0

prompt$ ./cefs game-file

where "game-file" is a name of file with a game for which the CE wants to be computed (in fact, if you omit to specify the file, CEFS will read the game from stdin). You may also specify some additional parameters, which are not so important – for details, run "./cefs -h".

xzidek05@ju:~/cesolver$ ./cefs 3.g File read. Iteration 0: E:0(11) E:0(0) E:0(3) E:0(13) E:4(0) E:4(1) E:4(2) E:4(3) E:4(4) E: 5(0) E:5(1) E:5(2) E:6(0) E:6(1) E:6(2) Iteration 1: E:0(4) E:0(5) E:0(7) E:0(10) Iteration 2: Final forbidden strategies: (100111010011010,000,00,00,111110,1110,1110000,0,0,0 ,0,0,0,0,0,0) Exported reduced game. 0: obj = 0.000000000e+00 infeas = 1.000e+00 (1) * 111: obj = 7.592228675e+10 infeas = 0.000e+00 (0) * 170: obj = 7.675174559e+10 infeas = 1.158e-23 (0) OPTIMAL SOLUTION FOUND Problem solved. [1, 0, 0, 0, 5, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.21 [1, 0, 1, 0, 5, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.10 [1, 1, 0, 0, 5, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.03 [1, 2, 0, 0, 5, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.06 [6, 0, 0, 0, 5, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.39 [6, 0, 0, 0, 5, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.16 [6, 2, 1, 1, 5, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.01 [12, 1, 0, 1, 5, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0] with probability 0.02 Equilibrium payoffs: [2731478528.00, 795184128.00, 2357690624.00, 890539456.00, 1932968960.00, 708174 0288.00, 21284257792.00, 20107910.00, 3274869248.00, 1164744448.00, 4031952128.0 0, 2095142400.00, 1288352384.00, 2965689600.00, 24536121344.00, 300907136.00]

After reading file, minimization takes place. E:i(s) informs that i'th player strategy s has been eliminated. When no more strategy can be eliminated, minimization finishes, flags identifying resulting eliminated strategies are printed and reduced game is exported.

Then, GLPK solves resulting LP problem. Resulting CE is printed (probabilities of strategy profiles). Last item is payoffs of all players in computed equilibrium.

If you want to employ parallelism, you need also OpenMP installed on your system.

It is very important to adjust the Makefile to set the right paths and names. Then it should be easy to build the CE-solver.

[2] Hrubý, M.: Algorithmic Approaches to Game-theoretical Modeling and Simulation, In: AUCO Czech Economic Review, Vol. 2, No. 3, 2008, Praha, CZ, p. 268-300, ISSN 1802-4696, online http://auco.cuni.cz/mag/article/show/id/50

[3] Stanislav Židek: Implementation of Game theory library (Czech), master's thesis, Department of Intelligent Systems, Brno University of Technology, Brno, Czech Republic, 2009

[4] Slides documenting the method: dokum.pdf

e-mail: hrubym at fit.vutbr.cz

www: http://www.fit.vutbr.cz/~hrubym/

working at: FIT BUT

e-mail: xzidek05 at stud.fit.vutbr.cz