Given two n x m matrices A and B, consider the game where simultaneously player I picks a row i and player II picks a column j. Player I's payoff is A(i,j) and player II's payoff is B(i,j).
Nash proved that for all A and B there are probability distributions σ on the rows and τ on the columns so that if the player I plays according to σ and player II plays according to τ
- There is no i such that if player I chooses row i his expected payoff will increase with player II still playing according to τ.
- There is no j such that if player II chooses column j her expected payoff will increase with player I still playing according to σ.
Using linear programming we can find Nash Equilibrium in a zero-sum game (A(i,j)=-B(i,j) for all i,j) or if we know the set of i where σ(i)=0 and the j where τ(j)=0.
We can also find a correlated equilibrium in polynomial-time which is a distribution on pairs (i,j). However to implement a correlated equilibrium you need either a third trusted party or use some cryptographic techniques.
I don't know a good survey on the complexity of Nash Equilibrium but perhaps my readers will have some good references.
Of course, the list between P and NPC also includes all optimization problems whose approximability isn't completely understood -- for example, the problem of coloring a 3-colorable graph with 6 colors. Somewhat strangely, (I think) many people believe that factoring (and perhaps Nash equilibrium, Minkowski short vectors in lattices)is probably not NP-Hard but hard in a different, imprecise, sense. I don't know if people hold such views about approximation problems.
ReplyDeleteSiva
Not to mention the turnpike problem (another fairly natural problem that has unknown complexity, and appears to be somehow connected to factoring)
ReplyDeleteShouldn't the statement be "there is no $sigma'$ that gives better results against $tau$ and no $tau'$ that gives better results against $sigma$?
ReplyDeleteAlso, as stated this is a search problem rather than a decision problem. What is the corresponding open decision problem?
I ask because I'm looking for good open problems to list in my revived NP-completeness column
It is also known that it is NP-hard to optimize over Nash Equilibria, e.g. find a Nash Equilibrium that maximizes payoffs to player 1, or maximizes the sum of the payoffs, etc. This is hard even in a 2-player case.
ReplyDeleteDavid:
ReplyDelete1. Since the expected payoff when playing \sigma is a convex combination of the expected payoffs corresponding to strategies in its support, all strategies in the support of an NE must give the same expected payoff. Thus the stronger requirement you state is in fact equivalent.
2. Since, as Nash showed, NE always exist, there is no obvious decision version. Several related decision versions (such as Is there an NE with player 1 payoff at least c? Are there at least k NE? Is there an NE where \sigma(i) is zero?) are known to be NP-hard. However, none of these results rule out a polytime algorithm for the search problem.
---
Another natural problem between P and NPC is the Anne Condon game.
--kunal
In response to Siva's question.
ReplyDeleteThere are a few problems for which
we know quasi-polynomial time
approximation algorithms but no
polynomial time approximation algorithms with a comparable ratio.
A good example is the directed
Steiner tree problem. A different example is the problem of counting
the number of strings of a
particular length accepted by an NFA
or CFG(context free grammar). It is
hard to know what to make of these
problems because the quasi-poly
time algorithm is not too
difficult in both cases but a
poly time algorithm seems difficult.
Chandra
For a natural decision problem version of this, what's wrong with trying to find the nth bit of the lexicographically first NE (under some nice system of describing NEs)?
ReplyDeleteOr, if you don't like this, how about determining the existence of a NE where each strategy satisfies a set of linear constraints (i.e. player 1's strategy chooses option 3 with probability between 1/10 and 3/10), so as to allow something like binary search?
Now that I've asked, I can see that the first is not clearly equivalent to the problem of finding ANY Nash Equilibrium, although it seems that the second should be.
I've puzzled over this a little bit since Christos Papadimitriou spoke last year at the UW, but I haven't looked hard for the answer, so forgive me if I'm missing something obvious.
Eric
Is it clear that a "nice" Nash equilibrium exists? I.e., that the probability distributions can be described by a vector of *rational* probabilities for each strategy, where the numerator/denominator of these rationals is of polynomial size?
ReplyDeleteAlso, are the entries of the matrix boolean or integers or what?
For two player games it is known that there exists a "nice" Nash equilibrium (rationals with polynomially bounded numerator and denominator). For three and more players it is also known that there are games with no "nice" Nash Equilibria. In that case what we aim for is for an algorithm that produces the vector of probabilities up to d digits of precision in time polynomial on d.
ReplyDeleteUnfortunately, no one has taken up Lance's suggestion to post refrences...are there any good surveys available? How about references for the last result mentioned (about existence of "nice" equilibria)?
ReplyDeleteRe. Eric's second formulation, it is known to be NP-hard. I think so is the first one. (See this paper by Conitzer and Sandholm and the references therein.)
ReplyDeleteThe reason there is always a small-description NE in the two player case is that given the supports of the two players' strategies, the NE can be computed as a solution to a system of linear equations.
Moreover for multiplayer games, there is always an NE that has a finite representation (more precisely, each probability is an algebraic number; see the paper by Lipton and Markakis). Its not known if there is always one with polynomial representation.
BTW, the matrix is usually assumed to have integer entries. (Which raises the question: what if the entries are 0-1? I don't know if this has been looked at.)
--kunal
E. Koutsoupias. Coordination mechanisms for congestion games. Sigact News, December 2004.
ReplyDeletehttp://cgi.di.uoa.gr/~elias/publications/paper-kou04.abs.html
There are 2 surveys on algorithms for Nash equilibria:
ReplyDelete1. R. McKelvey, A. McLennan. Computation of equilibria in finite games, in Handbook of Computational Economics, 1996.
2. B. von Stengel. Computing equilibria for 2-person games, in Handbook of Game Theory, 2002.
However little is mentioned about the complexity of the problem.
Another reference in which the problem is shown to be in some class between FP and FNP is:
C. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence, JCSS 1994.