Outstanding conjectures and open problems in (algorithmic) game theory? 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.)
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.