[1]   Kenneth J. Arrow and Gérard Debreu: Existence of an equilibrium for a competitive economy. Econometrica, 22(3):265–290, 1954. [doi:10.2307/1907353]

[2]   Andrei A. Bulatov: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66–120, 2006. Preliminary version in FOCS’02. [doi:10.1145/1120582.1120584]

[3]   Xi Chen: Guest column: Complexity dichotomies of counting problems. ACM SIGACT News, 42(4):54–76, 2011. [doi:10.1145/2078162.2078177]

[4]   Xi Chen, Decheng Dai, Ye Du, and Shang-Hua Teng: Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. In Proc. 50th FOCS, pp. 273–282. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.29, arXiv:0904.0644]

[5]   Xi Chen, Xiaotie Deng, and Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14:1–14:57, 2009. Preliminary version in FOCS’06. [doi:10.1145/1516512.1516516, arXiv:0704.1678]

[6]   Xi Chen, Dimitris Paparas, and Mihalis Yannakakis: The complexity of non-monotone markets. In Proc. 45th STOC, pp. 181–190. ACM Press, 2013. [doi:10.1145/2488608.2488632, arXiv:1211.4918]

[7]   Bruno Codenotti, Sriram V. Pemmaraju, and Kasturi R. Varadarajan: On the polynomial time computation of equilibria for certain exchange economies. In Proc. 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’05), pp. 72–81. ACM Press, 2005. ACM DL.

[8]   Vincent Conitzer and Tuomas Sandholm: New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621–641, 2008. [doi:10.1016/j.geb.2008.02.015, arXiv:cs/0205074]

[9]   Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone: The Linear Complementarity Problem. Academic Press, 1992.

[10]   Nadia Creignou: A dichotomy theorem for maximum generalized satisfiability problems. J. Comput. System Sci., 51(3):511–522, 1995. [doi:10.1006/jcss.1995.1087]

[11]   George B. Dantzig: Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Produciton and Allocation, Cowles Commission Monograph, pp. 339–347. John Wiley & Sons, 1951.

[12]   Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. SIAM J. Comput., 39(1):195–259, 2009. Preliminary version in STOC’06. [doi:10.1137/070699652]

[13]   Nikhil R. Devanur and Ravi Kannan: Market equilibria in polynomial time for fixed number of goods or agents. In Proc. 49th FOCS, pp. 45–53. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.30]

[14]   Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay V. Vazirani: Market equilibrium via a primal–dual algorithm for a convex program. J. ACM, 55(5):22:1–22:18, 2008. Preliminary version in FOCS’02. [doi:10.1145/1411509.1411512]

[15]   B. Curtis Eaves: A finite algorithm for the linear exchange model. Journal of Mathematical Economics, 3(2):197–203, 1976. [doi:10.1016/0304-4068(76)90028-8]

[16]   Kousha Etessami and Mihalis Yannakakis: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput., 39(6):2531–2597, 2010. Preliminary version in FOCS’07. [doi:10.1137/080720826]

[17]   Jugal Garg and Ravi Kannan: Markets with production: A polynomial time algorithm and a reduction to pure exchange. In Proc. 16th ACM Conf. on Economics and Comput. (EC’15), pp. 733–749. ACM Press, 2015. [doi:10.1145/2764468.2764517]

[18]   Jugal Garg, Ruta Mehta, Milind A. Sohoni, and Vijay V. Vazirani: A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. SIAM J. Comput., 44(6):1820–1847, 2015. Preliminary version in STOC’12. [doi:10.1137/140971002]

[19]   Jugal Garg, Ruta Mehta, and Vijay V. Vazirani: Substitution with satiation: A new class of non-separable utility functions and a complementary pivot algorithm for computing market equilibrium. Math. of Operations Res., to appear. Preliminary version in STOC’14.

[20]   Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod: ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In Proc. 42nd Internat. Colloq. on Automata, Languages and Programming (ICALP’15), volume 9134 of LNCS, pp. 554–566. Springer, 2015. [doi:10.1007/978-3-662-47672-7_45]

[21]   Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod: Leontief markets can solve multivariate polynomials yeilding FIXP and ETR hardness. 2015. [arXiv:1411.5060]

[22]   Jugal Garg and Vijay V. Vazirani: On computability of equilibria in markets with production. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1329–1340. ACM Press, 2014. [doi:10.1137/1.9781611973402.98, arXiv:1308.5272]

[23]   Itzhak Gilboa and Eitan Zemel: Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav., 1(1):80–93, 1989. [doi:10.1016/0899-8256(89)90006-7]

[24]   Victor Klee and George J. Minty: How good is the simplex algorithm? In Proc. 3rd Symp. on Inequalities, pp. 159–175. Academic Press, 1972.

[25]   Carlton E. Lemke: Bimatrix equilibrium points and mathematical programming. Management Science, 11(7):681–689, 1965. [doi:10.1287/mnsc.11.7.681]

[26]   Carlton E. Lemke and J. T. Howson, Jr.: Equilibrium points of bimatrix games. SIAM J. on Applied Mathematics, 12(2):413–423, 1964. [doi:10.1137/0112033]

[27]   Robert R. Maxfield: General equilibrium and the theory of directed graphs. Journal of Mathematical Economics, 27(1):23–51, 1997. [doi:10.1016/0304-4068(95)00763-6]

[28]   Nimrod Megiddo and Christos H. Papadimitriou: On total functions, existence theorems and computational complexity. Theoret. Comput. Sci., 81(2):317–324, 1991. [doi:10.1016/0304-3975(91)90200-L]

[29]   Katta G. Murty: Linear Complementarity, Linear and Non-linear Programming. Heldermann Verlag, 1988.

[30]   John F. Nash: Non-cooperative games. Ann. of Math., 54(2):286–295, 1951. [doi:10.2307/1969529]

[31]   Christos H. Papadimitriou: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci., 48(3):498–532, 1994. [doi:10.1016/S0022-0000(05)80063-7]

[32]   Rahul Savani and Bernhard von Stengel: Hard-to-solve bimatrix games. Econometrica, 74(2):397–429, 2006. Preliminary version in FOCS’04. [doi:10.1111/j.1468-0262.2006.00667.x]

[33]   Marcus Schaefer and Daniel Štefankovič: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Sys., pp. 1–22, 2015. [doi:10.1007/s00224-015-9662-0]

[34]   Lloyd S. Shapley: A note on the Lemke-Howson algorithm. In Math. Programming Studies, pp. 175–189. Springer, 1974. [doi:10.1007/BFb0121248]

[35]   Daniel A. Spielman and Shang-Hua Teng: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385–463, 2004. Preliminary version in STOC’01. [doi:10.1145/990308.990310, arXiv:cs/0111050]

[36]   Michael J. Todd: Orientation in complementary pivot algorithms. Math. Oper. Res., 1(1):54–66, 1976. [doi:10.1287/moor.1.1.54]

[37]   Vijay V. Vazirani and Mihalis Yannakakis: Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM, 58(3):10:1–10:25, 2011. Preliminary version in ICS’10. [doi:10.1145/1970392.1970394]

[38]   Mihalis Yannakakis: Personal communication, 2013.