conitzer_sandholm_nash.bbl
\begin{thebibliography}{10}

\bibitem{Abreu88:Structure}
Dilip Abreu and Ariel Rubinstein.
\newblock The structure of {N}ash equilibrium in repeated games with finite
  automata.
\newblock {\em Econometrica}, 56(6):1259--1281, 1988.

\bibitem{Bartholdi91:Single}
John~J. Bartholdi, III and James~B. Orlin.
\newblock Single transferable vote resists strategic voting.
\newblock {\em Social Choice and Welfare}, 8(4):341--354, 1991.

\bibitem{Bartholdi89:Computational}
John~J. Bartholdi, III, Craig~A. Tovey, and Michael~A. Trick.
\newblock The computational difficulty of manipulating an election.
\newblock {\em Social Choice and Welfare}, 6(3):227--241, 1989.

\bibitem{Bartholdi89:Voting}
John~J. Bartholdi, III, Craig~A. Tovey, and Michael~A. Trick.
\newblock Voting schemes for which it can be difficult to tell who won the
  election.
\newblock {\em Social Choice and Welfare}, 6:157--165, 1989.

\bibitem{BenPorath:Complexity}
E.~Ben-Porath.
\newblock The complexity of computing a best response automaton in repeated
  games with mixed strategies.
\newblock {\em Games and Economic Behavior}, pages 1--12, 1990.

\bibitem{Chu02:NP}
Francis Chu and Joseph Halpern.
\newblock On the {NP}-completeness of finding an optimal strategy in games with
  common payoffs.
\newblock {\em International Journal of Game Theory}.
\newblock To appear.

\bibitem{Conen01:Preference}
Wolfram Conen and Tuomas Sandholm.
\newblock Preference elicitation in combinatorial auctions: Extended abstract.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 256--259, Tampa, FL, October 2001.
\newblock A more detailed description of the algorithmic aspects appeared in
  the IJCAI-2001 Workshop on Economic Agents, Models, and Mechanisms, pp.
  71--80.

\bibitem{Conen02:Partial}
Wolfram Conen and Tuomas Sandholm.
\newblock Partial-revelation {VCG} mechanism for combinatorial auctions.
\newblock In {\em Proceedings of the National Conference on Artificial
  Intelligence (AAAI)}, Edmonton, Canada, 2002.

\bibitem{Conitzer02:Complexity}
Vincent Conitzer and Tuomas Sandholm.
\newblock Complexity of manipulating elections with few candidates.
\newblock In {\em Proceedings of the National Conference on Artificial
  Intelligence (AAAI)}, Edmonton, Canada, 2002.

\bibitem{Conitzer02:Mechanism_noUAI}
Vincent Conitzer and Tuomas Sandholm.
\newblock Complexity of mechanism design.
\newblock 2002.
\newblock Under review.

\bibitem{Conitzer02:Elicitation}
Vincent Conitzer and Tuomas Sandholm.
\newblock Vote elicitation: Complexity and strategy-proofness.
\newblock In {\em Proceedings of the National Conference on Artificial
  Intelligence (AAAI)}, Edmonton, Canada, 2002.

\bibitem{Fudenberg91:Game_theory}
Drew Fudenberg and Jean Tirole.
\newblock {\em Game Theory}.
\newblock MIT Press, 1991.

\bibitem{Gilboa:Nash}
I.~Gilboa and E.~Zemel.
\newblock Nash and correlated equilibria: Some complexity considerations.
\newblock {\em Games and Economic Behavior}, 1989.

\bibitem{Gilboa89:Bounded}
Itzhak Gilboa and Dov Samet.
\newblock Bounded versus unbounded rationality: The tyranny of the weak.
\newblock {\em Games and Economic Behavior}, pages 213--221, 1989.

\bibitem{Harsanyi67}
John Harsanyi.
\newblock Game with incomplete information played by {B}ayesian players.
\newblock {\em Management Science}, 14:159--182; 320--334; 486--502, 1967--68.

\bibitem{Hershberger01:Vickrey}
John Hershberger and Subhash Suri.
\newblock Vickrey prices and shortest paths: {W}hat is an edge worth?
\newblock In {\em Proceedings of the Symposium on Foundations of Computer
  Science (FOCS)}, 2001.

\bibitem{Hudson02:Elicitation}
Benoit Hudson and Tuomas Sandholm.
\newblock Effectiveness of preference elicitation in combinatorial auctions.
\newblock Technical report, Carnegie Mellon Computer Science, CMU-CS-02-124,
  March, 2002.
\newblock Also accepted to the Stanford Institute for Theoretical Economics
  workshop (SITE), June, 2002.

\bibitem{Kearns01:Graphical}
Michael Kearns, Michael Littman, and Satinder Singh.
\newblock Graphical models for game theory.
\newblock In {\em Proceedings of the Uncertainty in Artificial Intelligence
  Conference (UAI)}, 2001.

\bibitem{Kfir-Dahav00:Mechanism}
Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz.
\newblock Mechanism design for resource bounded agents.
\newblock In {\em Proceedings of the Fourth International Conference on
  Multi-Agent Systems (ICMAS)}, 2000.

\bibitem{Koller:Twoperson}
D.~Koller and N.~Megiddo.
\newblock The complexity of twoperson zero-sum games in extensive form.
\newblock {\em Games and Economic Behavior}, pages 4:528--552, 1992.

\bibitem{Koller96:Efficient}
Daphne Koller, Nimrod Megiddo, and {Bernhard von} Stengel.
\newblock Efficient computation of equilibria for extensive two-person games.
\newblock {\em Games and Economic Behavior}, 14(2):247--259, 1996.

\bibitem{Koller01:Multi-agent}
Daphne Koller and B~Milch.
\newblock Multi-agent influence diagrams for representing and solving games.
\newblock In {\em Proceedings of the Seventeenth International Joint Conference
  on Artificial Intelligence (IJCAI)}, pages 1027--1034, Seattle, WA, 2001.

\bibitem{Larson01:Bargaining}
Kate Larson and Tuomas Sandholm.
\newblock Bargaining with limited computation: Deliberation equilibrium.
\newblock {\em Artificial Intelligence}, 132(2):183--217, 2001.
\newblock Short early version appeared in the Proceedings of the National
  Conference on Artificial Intelligence (AAAI), pp. 48--55, Austin, TX, 2000.

\bibitem{Larson01:Costly}
Kate Larson and Tuomas Sandholm.
\newblock Costly valuation computation in auctions.
\newblock In {\em Theoretical Aspects of Rationality and Knowledge (TARK
  VIII)}, pages 169--182, Sienna, Italy, July 2001.

\bibitem{Lehmann99:Truth}
Daniel Lehmann, Lidian~Ita O'{C}allaghan, and Yoav Shoham.
\newblock Truth revelation in rapid, approximately efficient combinatorial
  auctions.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 96--102, Denver, CO, November 1999.

\bibitem{Lichtenstein80:Go}
D~Lichtenstein and M~Sipser.
\newblock {GO} is polynomial-space hard.
\newblock {\em Journal of the ACM}, 27:393--401, 1980.

\bibitem{Luce57:Games}
R.~Duncan Luce and Howard Raiffa.
\newblock {\em Games and Decisions}.
\newblock John Wiley and Sons, New York, 1957.
\newblock Dover republication 1989.

\bibitem{Mas-Colell95:Microeconomic}
Andreu Mas-Colell, Michael Whinston, and Jerry~R. Green.
\newblock {\em Microeconomic Theory}.
\newblock Oxford University Press, 1995.

\bibitem{McLennan:Expected}
Andrew McLennan.
\newblock On the expected number of nash equilibria of a normal form game.
\newblock 1997.

\bibitem{McLennan:Generic}
Andrew McLennan and In-Uck Park.
\newblock Generic 4x4 two person games have at most 15 nash equilibria.
\newblock 1997.

\bibitem{Nash50:Eq}
John Nash.
\newblock Equilibrium points in n-person games.
\newblock {\em Proc. of the National Academy of Sciences}, 36:48--49, 1950.

\bibitem{Neyman85:Bounded}
A~Neyman.
\newblock Bounded complexity justifies cooperation in finitely repeated
  prisoner's dilemma.
\newblock {\em Economic Letters}, pages 227--229, 1985.

\bibitem{Nisan99:Algorithmic}
Noam Nisan and Amir Ronen.
\newblock Algorithmic mechanism design.
\newblock In {\em Proceedings of the Annual ACM Symposium on the Theory of
  Computing (STOC)}, pages 129--140, 1999.

\bibitem{Nisan00:Computationally}
Noam Nisan and Amir Ronen.
\newblock Computationally feasible {VCG} mechanisms.
\newblock In {\em Proceedings of the ACM Conference on Electronic Commerce
  (ACM-EC)}, pages 242--252, Minneapolis, MN, 2000.

\bibitem{Nisan02:Segal}
Noam Nisan and Ilya Segal.
\newblock The communication complexity of efficient allocation problems, 2002.
\newblock Draft. Second version March 5th.

\bibitem{Orlin81:Complexity}
J~Orlin.
\newblock The complexity of dynamic languages and dynamic optimization
  problems.
\newblock In {\em Proceedings of the Annual ACM Symposium on the Theory of
  Computing (STOC)}, pages 218--227, 1981.

\bibitem{Papadimitriou:Players}
C.~H. Papadimitriou.
\newblock On players with a bounded number of states.
\newblock {\em Games and Economic Behavior}, pages 122--131, 1992.

\bibitem{Papadimitriou01:Algorithms}
Christos Papadimitriou.
\newblock Algorithms, games and the {I}nternet.
\newblock In {\em Proceedings of the 33rd Annual ACM Symposium on the Theory of
  Computing}, pages 749--253, 2001.

\bibitem{Papadimitriou94:Complexity}
Christos~H. Papadimitriou and Mihalis Yannakakis.
\newblock On complexity as bounded rationality.
\newblock In {\em Proceedings of the Annual ACM Symposium on the Theory of
  Computing (STOC)}, pages 726--733, 1994.

\bibitem{Roughgarden01:Designing}
Tim Roughgarden and Eva Tardos.
\newblock Designing networks for selfish users is hard.
\newblock In {\em Proceedings of the Symposium on Foundations of Computer
  Science (FOCS)}, 2001.

\bibitem{Rubinstein86:Finite}
Ariel Rubinstein.
\newblock Finite automata play the repeated prisoner's dilemma.
\newblock {\em Journal of Economic Theory}, 39:83--96, 1986.

\bibitem{Sandholm02:Algorithm}
Tuomas Sandholm.
\newblock Algorithm for optimal winner determination in combinatorial auctions.
\newblock {\em Artificial Intelligence}, 135:1--54, January 2002.
\newblock First appeared as an invited talk at the First International
  Conference on Information and Computation Economies, Charleston, SC, Oct.
  25--28, 1998. Extended version appeared as Washington Univ., Dept. of
  Computer Science, tech report WUCS-99-01, January 28th, 1999. Conference
  version appeared at the International Joint Conference on Artificial
  Intelligence (IJCAI), pp. 542--547, Stockholm, Sweden, 1999.

\bibitem{Sandholm01:Market}
Tuomas Sandholm and Subhash Suri.
\newblock Market clearability.
\newblock In {\em Proceedings of the Seventeenth International Joint Conference
  on Artificial Intelligence (IJCAI)}, pages 1145--1151, Seattle, WA, 2001.

\bibitem{Sandholm99:ConstructingTR}
Tuomas Sandholm and Fredrik Ygge.
\newblock Constructing speculative demand functions in equilibrium markets.
\newblock Technical Report WUCS-99-26, Washington University, Department of
  Computer Science, October 1999.
\newblock Short early version appeared at the International Joint Conference on
  Artificial Intelligence (IJCAI), pp. 632--638, Nagoya, Japan, 1997.

\bibitem{Shapley53:Stochastic}
Lloyd~S Shapley.
\newblock Stochastic games.
\newblock {\em Proc. of the National Academy of Sciences}, 39:1095--1100, 1953.

\bibitem{Sobel71:Noncooperative}
M~Sobel.
\newblock Noncooperative stochastic games.
\newblock {\em Annals of Mathematical Statistics}, 42:1930--1935, 1971.

\bibitem{Stengel02:Computing}
{Bernhard von} Stengel.
\newblock Computing equilibria for two-person games.
\newblock In Robert Aumann and Sergiu Hart, editors, {\em Handbook of game
  theory}, volume~3. North Holland, Amsterdam, 2002.
\newblock Forthcoming.

\bibitem{Stockmeyer73:Word}
L~Stockmeyer and A~Meyer.
\newblock Word problems requiring exponential time.
\newblock In {\em Proceedings of the Annual ACM Symposium on the Theory of
  Computing (STOC)}, pages 1--9, 1973.

\bibitem{Valiant79:Complexity}
Leslie Valiant.
\newblock The complexity of computing the permanent.
\newblock {\em Theoretical Computer Science}, 8:189--201, 1979.

\bibitem{Papadimitriou02:Complexity}
Deng Xiaotie, Christos Papadimitriou, and Muli Safra.
\newblock On the complexity of equilibria.
\newblock In {\em Proceedings of the Annual ACM Symposium on the Theory of
  Computing (STOC)}, 2002.

\bibitem{Nachbar:Noncomputable}
William~R. Zame and John~H. Nachbar.
\newblock Non-computable strategies and discounted repeated games.
\newblock {\em Economic Theory}, pages (1)103--122, 1996.

\end{thebibliography}
