10
$\begingroup$

I searched the forum to see if this has been asked before, and while algorithmic game theory is discussed, I couldn't find this particular issue addressed. I am trying to figure out what the best known algorithm is for computing approximate (mixed-strategy) Nash equilibria in a finite n-person game. Of course, this algorithm would be PPAD. I am more interested in speed/efficiency than perfect accuracy of the algorithm.

Thanks, Philip

$\endgroup$
  • $\begingroup$ We can help you better if you give more details. For example what value of $n$ do you have in mind? Do you have any special structure of the payoff function in mind? Do you really need a Nash equilibrium or would a correlated equilibrium suffice? Are you looking for something with good provable bounds or something with good practical performance? $\endgroup$ – Warren Schudy Oct 20 '10 at 21:32
7
$\begingroup$

The short answer is that although there are some polynomial time algorithms for provably finding approximate Nash equilibria, they all find relatively poor approximations -- probably not good enough if you are actually trying to find an algorithm to play a game. More is known for 2 player games than for n player games.

If what you are trying to do is actually find an (approximate) Nash equilibrium, one easy to code thing you might try is simulating game play, with each player using the randomized weighted majority algorithm (http://en.wikipedia.org/wiki/Randomized_weighted_majority_algorithm). This isn't guaranteed to work, but in many cases will (And is guaranteed to in certain classes of games, like zero-sum games). In particular, if this process converges at all, it is guaranteed to converge to a Nash equilibrium. The danger is that it will not converge, and cycle forever -- but even in this case, the empirical history of game play will converge to the set of coarse correlated equilibria.

$\endgroup$
  • $\begingroup$ I started taking a look at the paper mentioned in the answer above. I didn't understand all of it (or much of it at first glance)...can you explain why the approximation is "relatively poor?" Also, could you explain briefly what a "coarse correlated equilibrium" is? I know what a correlated equilibrium is, but what it means for such an eq. to be coarse. Finally, what do you mean by "the empirical history of game play will converge...[etc.]"? How can something that never converges converge to a set of CCE's? Thanks for your answer, I'm looking up the Wikipedia article now. $\endgroup$ – Philip White Oct 7 '10 at 2:22
  • $\begingroup$ For some background on algorithms that produce distributions that converge to coarse correlated equilibria or correlated equilibria, I'd start here: cs.cmu.edu/~avrim/Papers/regret-chapter.pdf $\endgroup$ – Aaron Roth Oct 7 '10 at 2:37
  • $\begingroup$ If you want a correlated equilibria rather than a coarse correlated equilibria you can use a no-internal-regret learner. For example (shameless plug) cs.brown.edu/~ws/papers/regret.pdf . There are also algorithms for computing correlated equilibria directly in polynomial time. $\endgroup$ – Warren Schudy Oct 20 '10 at 21:29
10
$\begingroup$

Perhaps the 2008 paper presented at the Symposium on Algorithmic Game Theory by Hémon, Rougemont, and Santha, "Approximate Nash Equilibria for Multi-player Games" could help? They "exhibit polynomial-time algorithms for additive approximation" for $n$-player games.

$\endgroup$
4
$\begingroup$

If you are interested in algorithms that are actually implemented in software, there are several that I know of:

  1. the GAMBIT package (http://www.gambit-project.org/doc/index.html) implements several Nash equilibrium algorithms for 2-player & n-player normal form, and in some cases extensive form games.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) implements Govindan & Wilson's GNM and IPA algorithms for n-player normal form games.

  3. For large games, the normal form representation is problematic as size grows exponentially in the number of players. Instead, if your game's utility function has certain kinds of structure, you can use a "concise representation" (e.g. graphical games, symmetric games, action-graph games) to express it using much less space; and furthermore the structure can often be exploited for computational speedups. In terms of software, the AGG Solver (http://agg.cs.ubc.ca) adapts GameTracer's GNM algorithm and GAMBIT's simpdiv algorithm to the action-graph game (AGG) representation. (Disclaimer: I am involved in the development of this software pacakge.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.