tag:blogger.com,1999:blog-3722233.post110907832035551965..comments2021-01-22T21:11:37.799-06:00Comments on Computational Complexity: The Complexity of the Nash EquilibriumLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-1109286869958065912005-02-24T17:14:00.000-06:002005-02-24T17:14:00.000-06:00There are 2 surveys on algorithms for Nash equilib...There are 2 surveys on algorithms for Nash equilibria:<br />1. R. McKelvey, A. McLennan. Computation of equilibria in finite games, in Handbook of Computational Economics, 1996.<br />2. B. von Stengel. Computing equilibria for 2-person games, in Handbook of Game Theory, 2002.<br /><br />However little is mentioned about the complexity of the problem.<br />Another reference in which the problem is shown to be in some class between FP and FNP is:<br /><br />C. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence, JCSS 1994.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109250139844560412005-02-24T07:02:00.000-06:002005-02-24T07:02:00.000-06:00E. Koutsoupias. Coordination mechanisms for conges...E. Koutsoupias. Coordination mechanisms for congestion games. Sigact News, December 2004.<br /><br /><br />http://cgi.di.uoa.gr/~elias/publications/paper-kou04.abs.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109224442090501722005-02-23T23:54:00.000-06:002005-02-23T23:54:00.000-06:00Re. Eric's second formulation, it is known to be N...Re. Eric's second formulation, it is known to be NP-hard. I think so is the first one. (See <A HREF="http://www-2.cs.cmu.edu/~sandholm/Nash_complexity.ijcai03.pdf" REL="nofollow"> this</A> paper by Conitzer and Sandholm and the references therein.)<br /><br />The 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.<br /><br />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.<br /><br />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.)<br /><br />--kunalAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109203886817116982005-02-23T18:11:00.000-06:002005-02-23T18:11:00.000-06:00Unfortunately, no one has taken up Lance's suggest...Unfortunately, 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)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109196456020785412005-02-23T16:07:00.000-06:002005-02-23T16:07:00.000-06:00For two player games it is known that there exists...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109194307508009392005-02-23T15:31:00.000-06:002005-02-23T15:31:00.000-06:00Is it clear that a "nice" Nash equilibrium exists?...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?<br /><br />Also, are the entries of the matrix boolean or integers or what?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109189133901179822005-02-23T14:05:00.000-06:002005-02-23T14:05:00.000-06:00For a natural decision problem version of this, wh...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)?<br /><br />Or, 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?<br /><br />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.<br /><br />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.<br /><br />EricAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109126365790356972005-02-22T20:39:00.000-06:002005-02-22T20:39:00.000-06:00In response to Siva's question.
There are a few pr...In response to Siva's question.<br />There are a few problems for which<br />we know quasi-polynomial time<br />approximation algorithms but no <br />polynomial time approximation algorithms with a comparable ratio.<br />A good example is the directed <br />Steiner tree problem. A different example is the problem of counting <br />the number of strings of a <br />particular length accepted by an NFA <br />or CFG(context free grammar). It is <br />hard to know what to make of these<br />problems because the quasi-poly<br />time algorithm is not too<br />difficult in both cases but a<br />poly time algorithm seems difficult.<br /><br />ChandraAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109109246587886572005-02-22T15:54:00.000-06:002005-02-22T15:54:00.000-06:00David:
1. Since the expected payoff when playing \...David:<br />1. 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.<br /><br />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.<br /><br />---<br /><br />Another natural problem between P and NPC is the Anne Condon game.<br /><br />--kunalAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109088698075200882005-02-22T10:11:00.001-06:002005-02-22T10:11:00.001-06:00It is also known that it is NP-hard to optimize ov...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109088689891738452005-02-22T10:11:00.000-06:002005-02-22T10:11:00.000-06:00Shouldn't the statement be "there is no $sigma'$ t...Shouldn't the statement be "there is no $sigma'$ that gives better results against $tau$ and no $tau'$ that gives better results against $sigma$?<br /><br />Also, as stated this is a search problem rather than a decision problem. What is the corresponding open decision problem?<br /><br />I ask because I'm looking for good open problems to list in my revived NP-completeness columnAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109087575422336712005-02-22T09:52:00.000-06:002005-02-22T09:52:00.000-06:00Not to mention the turnpike problem (another fairl...Not to mention the turnpike problem (another fairly natural problem that has unknown complexity, and appears to be somehow connected to factoring)Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1109085927323502852005-02-22T09:25:00.000-06:002005-02-22T09:25:00.000-06:00Of course, the list between P and NPC also include...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. <br /><br />SivaAnonymousnoreply@blogger.com