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 but the
minimal elements of M. This makes the algorithm search strategy profiles
unnecessarily, but the gain in keeping M small is large enough to justify
this waste.

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 and simulate.c.
Program trivial.c simulates games and finds all equilibria using the trivial
algorithm; simulate.c simulates games and finds all equilibria using the
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 fede@hss.caltech.edu