16
$\begingroup$

What sort of conjectures and major open problems are the most important in algorithmic game theory (or game theory in general as it relates to CS)? For example, the resolution of NASH as being PPAD-complete would, I think, have been the biggest one up until it was resolved.

(Added: resolving PPAD's relation to P and NP is one good open problem, but others not so deeply entrenched in computational complexity would be nice too.)

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
7
$\begingroup$

Here are several open problems:

1-Major open problem is the problem of computing approximate Nash equilibria.

2- Existence of efficient algorithm for computing pure Nash equilibria in congestion games?

3-finding equilibria with minimum inefficiency?

4-Tim Roughgarden, in Communications of the ACM , posed the following open problem:

to what extent is “incentive-compatible” efficient computation fundamentally less powerful than “classical” efficient computation?

Algorithmic game theory, Communications of the ACM, Volume 53 , Issue 7, (July 2010)

Also, these references contains some open problems: Nisan, Roughgarden, Tardos, and Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.

T. Roughgarden. Algorithmic game theory: Some greatest hits and future directions. In TCS ’08, p. 21–42.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The recent survey is very helpful. I had actually looked at Nisan+++'s book --- a text search for "conjecture" gives only a couple of hits! --- but there are indeed a lot of open problems. Any specific conjectures, or less technical specific open problems, would still be welcomed in my search. $\endgroup$
    – daveagp
    Commented Sep 26, 2010 at 19:40
  • $\begingroup$ Computing a pure Nash equilibrium of a general congestion game is PLS-complete, so an efficient algorithm is unlikely to exist. $\endgroup$
    – Rahul Savani
    Commented Nov 2, 2010 at 23:42
2
$\begingroup$

In this reference, Papadimitriou and Roughgarden pose 6 open problems related to computing correlated equilibria:

Papadimitriou and Tim Roughgarden, Computing Correlated Equilibria in Multi-Player Games

Also, in this paper Papadimitriou poses a several open problems related to Game Theory and the Internet:

Papadimitriou, Algorithms, Games, and the Internet, Proc. STOC 2001

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Papadimitriou's survey is a bit outdated, in that significant progress has been made on most of the open problems since 2001. $\endgroup$
    – Ryan Williams
    Commented Sep 24, 2010 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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