Additional information on "Finding All Equilibria"
By Federico Echenique
1. A C-program implementing Algorithm 2 in the paper is here.
I have very little experience programming, so I hope that someone
who actually knows anything about C will take the program
and do a better job.
The main problem in implementing the algorithm is dealing with
"large states." A state M is large if it contains many strategy profiles.
Large states will slow down the algorithm considerably. In my program
I kept down the size of the states by discarding, in each iteration, all
minimal elements of M. This makes the algorithm search strategy profiles
unnecessarily, but the gain in keeping M small is large enough to justify
My program is for two-player games. It is not difficult to do it for n-player
games, but I made a bad choice when I started writing the program
(I had one pointer for each player, instead of using an array), and
then I was locked in.
One could try to implement the algorithm using MATLAB, Gauss,
or something like that. Its probably slower, I haven't tried.
2. HERE you can find
the data produced
by the simulations that I report in the paper.
The C-programs I used for doing the simulations are trivial.c
Program trivial.c simulates games and finds all equilibria using
algorithm; simulate.c simulates games and finds all equilibria using
algorithm I propose in the paper. Note that the seed is set in the programs
so that both algorithms work on the same set of games---this is crucial
for making the comparison between the algorithms, and to check that
my algorithm is actually working!
Please send any feedback to firstname.lastname@example.org