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:
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
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
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].
Main design ideas
Interface
CE-solver was designed to provide as much freedom to potential modellers as possible. It has two types of interfaces:
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.
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:
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.
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):
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
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".
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.
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
