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

<p>Papadimitriou and Tim Roughgarden, 
<a href="http://theory.stanford.edu/~tim/papers/cor.pdf" rel="nofollow">Computing Correlated Equilibria in Multi-Player Games</a>
<a href="http://theory.stanford.edu/~tim/papers/cor.pdf" rel="nofollow"></a></p>

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

<p><a href="http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/stoc01.pdf" rel="nofollow">Papadimitriou, Algorithms, Games, and the Internet,  </a>
<a href="http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/stoc01.pdf" rel="nofollow">Proc. STOC 2001 </a></p>

CC BY-SA 2.5
2010-09-24T19:54:03.617Z
Papadimitriou's survey is a bit outdated, in that significant progress has been made on most of the open problems since 2001.
Ryan Williams
CC BY-SA 2.5
2010-09-24T17:40:50.957Z
2010-09-24T18:29:57.463Z
2010-09-24T18:29:57.463Z
Mohammad Al-Turkistany
<p>Here are several open problems:</p>

<p>1-Major open problem is the problem of computing approximate Nash equilibria.</p>

<p>2- Existence of efficient algorithm for computing pure Nash equilibria in congestion
games?</p>

<p>3-finding equilibria with minimum inefficiency?</p>

<p>4-Tim Roughgarden, in Communications of the ACM , posed the following open problem:</p>

<blockquote>
  <p>to what extent is “incentive-compatible” efficient computation fundamentally less powerful
  than “classical” efficient computation?</p>
</blockquote>

<p><a href="http://portal.acm.org/citation.cfm?id=1785439&amp;dl=GUIDE&amp;coll=GUIDE">Algorithmic game theory,</a>
<a href="http://portal.acm.org/citation.cfm?id=1785439&amp;dl=GUIDE&amp;coll=GUIDE"></a>Communications of the ACM, Volume 53 , Issue 7,  (July 2010)</p>

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

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

CC BY-SA 2.5
2010-09-26T19:40:23.230Z
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.
daveagp
CC BY-SA 2.5
2010-11-02T23:42:48.887Z
Computing a pure Nash equilibrium of a general congestion game is PLS-complete, so an efficient algorithm is unlikely to exist.
Rahul Savani
CC BY-SA 2.5
2010-09-25T06:22:19.673Z
2010-09-25T07:17:49.807Z
2010-09-25T07:17:49.807Z
Mohammad Al-Turkistany
<p>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. </p>

<p>(Added: <a href="https://cstheory.stackexchange.com/questions/314/evidence-that-ppad-is-hard/319#319">resolving PPAD's relation to P and NP</a> is one good open problem, but others not so deeply entrenched in computational complexity would be nice too.)</p>

CC BY-SA 2.5
2010-09-24T14:46:55.983Z
This question would work better if you flagged it as CW (Community Wiki). See here: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/239#239
Daniel Apon
CC BY-SA 2.5
2010-09-24T17:48:17.587Z
I agree. please mark it CW.
Suresh Venkat
<big-list><gt.game-theory>
Outstanding conjectures and open problems in (algorithmic) game theory?
daveagp
# Outstanding conjectures and open problems in (algorithmic) game theory?

(Asked by: username_0 on 2010-09-24)

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](https://cstheory.stackexchange.com/questions/314/evidence-that-ppad-is-hard/319#319) is one good open problem, but others not so deeply entrenched in computational complexity would be nice too.)

**Tags:** big-list, gt.game-theory

> **Comments:**
> **username_1**: This question would work better if you flagged it as CW (Community Wiki). See here: http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/239#239  
> **username_2**: I agree. please mark it CW.  

---

## 2 answers

### Answer by username_3 on 2010-09-25. Score: 7 | Accepted answer

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,](http://portal.acm.org/citation.cfm?id=1785439&dl=GUIDE&coll=GUIDE)
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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: Computing a pure Nash equilibrium of a general congestion game is PLS-complete, so an efficient algorithm is unlikely to exist.  

---

### Answer by username_3 on 2010-09-24. Score: 2

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](http://theory.stanford.edu/~tim/papers/cor.pdf)

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

[Papadimitriou, Algorithms, Games, and the Internet,](http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/stoc01.pdf) 
[Proc. STOC 2001](http://www.eecs.harvard.edu/~parkes/cs286r/spring02/papers/stoc01.pdf)

> **Comments:**
> **username_4**: Papadimitriou's survey is a bit outdated, in that significant progress has been made on most of the open problems since 2001.  

---

