View this PageEdit this PageAttachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide

CE-Solver Swiki - A very efficient implementation of Aumann's Correlated Equilibrium

Introduction

This web page introduces CE-solver, a C++ library/tool for computing the Correlated Equilibrium for a given N-player strategic game. CE-Solver can be used for experimenting with the correlated equilibrium or can be included in various computer models employing game theory.

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].

Used symbols:


Theoretical description of the method

CE-solver uses a very elegant method of game minimization developed by Martin Hrubý, which is generally described in [1]. The most important idea of this method is employing so called G-matrix. This structure is well suited for

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].

Main design ideas

Interface

CE-solver was designed to provide as much freedom to potential modellers as possible. It has two types of interfaces:

G-matrix storage

Previous prototype version of CE-solver created by Martin Hrubý used explicit representation of whole G-matrix, that is table with |S| columns (|S| is a product |S_1| x ... x |S_N|) and R rows (R is a sum of |S_i|!/(|S_i|-2)! for all players i). This approach consumes much memory and slows down the computation by accessing data scattered among large memory area (along with swapping to disk).

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.

Iterative elimination

Prototype CE-solver did always only one traverse through G-matrix. However, eliminating some strategy might cause another strategy to become dominated, so passing the G-matrix again might eliminate strategies that could not have been eliminated before.

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.

Payoff cache

Computing payoffs is consedered to be computationally hardest task in real-world models. During minimization, we almost always need to know particular payoff several times. To avoid unnecessary repeated computation, we store computed payoffs in special cache. (Using this cache is optional.)

Parallelization

CE-solver was designed with special respect to parallelization. It is possible to significantly speed up computation if payoff computation takes the majority of time and can be done in parallel.

Usage

Library interface

To use CE-solver as a library, you just need to create child of abstract base class Game and implement three methods:

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.

Tool interface

Correlated Equilibrium File Solver (CEFS) was created as a simple command line utility to solve games stored in files.

Input format of the files

Games must be formatted in the following manner (N and S_1,S_2,...,S_N are integers, U_i(s) are floats):
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 playerleftright
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


Remark CEFS also accepts file format for normal games used in Gambit library (NFG). However, we strongly discourage using this format, because we found a lot of incopatibilities even in example Gambit games, which do not respect the specification.

CEFS invocation

CEFS is invoked by:
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".

CEFS output

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.

Download and licence

CE-solver is released under GNU General Public License. Authors would be grateful for any comment, testing or whatever.

Download link: cesolver.zip

Installation

The library has been developed on GNU/Linux operating system and GNU C++ compiler (version 4.3.2). CE-solver itself requires GNU Linear Programming Toolkit library.

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.

References

[1] Hrubý Martin, Čambala Petr: Efficient Computing of Correlated Equilibria in Multi-Player Games, In: Proceedings of 12th IASTED Conference on Artificial Intelligence and Soft Computing, Calgery, CA, ACTA Press, 2008, p. 100-106, http://www.fit.vutbr.cz/research/view_pub.php?id=8645
[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

Contact to the authors

Martin Hrubý
e-mail: hrubym at fit.vutbr.cz
www: http://www.fit.vutbr.cz/~hrubym/
working at: FIT BUT

Stanislav Židek
e-mail: xzidek05 at stud.fit.vutbr.cz