Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm

References

• Adsul B, Garg J, Mehta R, Sohoni MA (2011) Rank-1 bimatrix games: A homeomorphism and a polynomial time algorithm. Fortnow L, Vadhan SP, eds. Proc. 43rd Sympos. Theory Comput. Conf., STOC ’12 (ACM, New York), 195–204.Google Scholar
• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms and Applications (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Arrow K, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290.Crossref, Google Scholar
• Bazarra MS, Sherali HD, Shetty CM (2006) Nonlinear Programming: Theory and Algorithms (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Boyd S, Vandenberghe L (2009) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chen X, Teng SH (2009) Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria. Proc. 20th Intl.Symp. Algorithms Comput. (ISAAC), 647–656.Google Scholar
• Chen X, Deng X, Teng S (2009b) Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3):14:1–14:57.Crossref, Google Scholar
• Chen X, Paparas D, Yannakakis M (2013) The complexity of nonmonotone markets. Boneh D, Roughgarden T, Feigenbaum J, eds. Proc. 45th Sympos. Theory Comput. Conf., STOC ’13 (ACM, New York), 181–190.Google Scholar
• Chen X, Dai D, Du Y, Teng S (2009a) Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. Proc. 50th IEEE Sympos. Foundations Comput. Sci. (FOCS), 273–282.Google Scholar
• Codenotti B, Varadarajan K (2007) Computation of market equilibria by convex programming. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Campridge, UK), 135–158.Crossref, Google Scholar
• Codenotti B, McCune B, Penumatcha S, Varadarajan KR (2005) Market equilibrium for CES exchange economies: Existence, multiplicity, and computation. Ramanujam R, Sen S, eds. Proc. 25th Internat. Conf. Foundations of Software Tech. Theoret. Comp. Sci., FSTTCS ’05 (Springer, Berlin), 505–516.Google Scholar
• Codenotti B, Saberi A, Varadarajan K, Ye Y (2006) Leontief economies encode two-player zero-sum games. Proc. 17th Annual ACM-SIAM Annual Sympos. Discrete Algorithms, SODA ’06 (ACM, New York), 659–667.Google Scholar
• Conitzer V, Sandholm T (2008) New complexity results about Nash equilibria. Games Econom. Behav. 63(2):621–641.Crossref, Google Scholar
• Cottle RW, Pang JS, Stone RE (1992) The Linear Complementarity Problem (Academic Press, San Diego).Google Scholar
• Dantzig GB (1951) Maximization of a linear function of variables subject to linear inequalities. Koopmans TC, ed. Activity Analysis of Production and Allocation, (John Wiley & Sons, Hoboken, NJ) 339–347.Google Scholar
• Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• Debreu G (1974) Excess demand functions. J. Math. Econom. 1(1):15–22.Crossref, Google Scholar
• Devanur N, Kannan R (2008) Market equilibria in polynomial time for fixed number of goods or agents. Proc. 49th Annual IEEE Sympos. Foundations Comput. Sci., FOCS ’08 (IEEE Computer Society, Washington, DC), 45–53.Google Scholar
• Devanur N, Papadimitriou CH, Saberi A, Vazirani VV (2008) Market equilibrium via a primal-dual algorithm for a convex program. J. ACM 55(5):22:1–22:18.Crossref, Google Scholar
• Dixon PB, (editors) DWJ (2013) Handbook of Computable General Equilibrium Modeling SET, Vols. 1A and 1B (Elsevier, Amsterdam).Google Scholar
• Eaves BC (1975) A finite algorithm for the linear exchange model. Cowles Foundation for Research in Economics, Paper 389, Yale University.Google Scholar
• Eaves BC (1976) A finite algorithm for the linear exchange model. J. Math. Econom. 3(2):197–203.Crossref, Google Scholar
• Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The Pari-Mutuel method. Ann. Math. Statist. 30(1):165–168.Crossref, Google Scholar
• Etessami K, Yannakakis M (2010) On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6):2531–2597.Crossref, Google Scholar
• Garg J, Vazirani VV (2014) On equilibrium computation in markets with production. Proc. 25th Annual ACM-SIAM Annual Sympos. Discrete Algorithms, SODA ’14 (SIAM, Philadelphia), 1329–1340.Google Scholar
• Garg J, Mehta R, Vazirani VV (2016) Dichotomies in equilibrium computation, and membership of PLC markets in FIXP. Theory Comput. 12(20):1–25.Crossref, Google Scholar
• Garg J, Mehta R, Sohoni MA, Vazirani VV (2012) A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities. Karloff HJ, Pitassi T, eds. Proc. 44th Sympos. Theory Comput. STOC ’12 (ACM, New York), 1003–1016.Google Scholar
• Garg J, Mehta R, Vazirani VV, Yazdanbod S (2015) ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. Halldórsson MM, Iwama K, Kobayashi N, Speckmann B, eds. Proc. 42nd Internat. Colloquium on Automata, Languages, and Programming, ICALP ’15 (Springer, Berlin), 554–566.Google Scholar
• Garg J, Mehta R, Vazirani VV, Yazdanbod S (2017) Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput., STOC ’’17 (ACM, New York), To appear.Google Scholar
• Gilboa I, Zemel E (1989) Nash and correlated equilibria: Some complexity considerations. Games Econom. Behav. 1(1):80–93.Crossref, Google Scholar
• Hochbaum DS, Shanthikumar JG (1990) Convex separable optimization is not much harder than linear optimization. J. ACM 37(4):843–862.Crossref, Google Scholar
• Jain K (2007) A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. SIAM J. Comput. 37(1):306–318.Crossref, Google Scholar
• Klee V, Minty GJ (1972) How good is the simplex algorithm? Shisha O, ed. Inequalities, III (Academic Press, New York), 159–175.Google Scholar
• Lemke CE (1965) Bimatrix equilibrium points and mathematical programming. Management Sci. 11(7):681–689.Link, Google Scholar
• Lemke CE, Howson JT (1964) Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12(2):413–423.Crossref, Google Scholar
• Mantel R (1974) On the characterization of excess demand. J. Econom. Theory 7(3):348–353.Crossref, Google Scholar
• Maxfield RR (1997) General equilibrium and the theory of directed graphs. J. Math. Econom. 27(1):23–51.Crossref, Google Scholar
• Minoux M (1986) Solving integer minimum cost flows with separable convex cost objective polynomially. Gallo G, Sandi C, eds. Netflow at Pisa. Mathematical Programming Studies, Vol. 26, (Springer, Berlin), 237–239.Crossref, Google Scholar
• Murota K (1999) Submodular flow problem with a nonseparable cost function. Combinatorica 19(1):87–109.Crossref, Google Scholar
• Nash JF (1951) Noncooperatie games. Annals of Mathematics 54(2):286–295.Crossref, Google Scholar
• Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3):498–532.Crossref, Google Scholar
• Savani R, von Stengel B (2006) Hard-to-solve bimatrix games. Econometrica 74(2):397–429.Crossref, Google Scholar
• Scarf H (1967) The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15(1):1328–1343.Crossref, Google Scholar
• Scarf HE (1960) Some examples of global instability of competitive equilibria. Internat. Econom. Rev. 1(3):157–172.Crossref, Google Scholar
• Schaefer M, Štefankovič D (2017) Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Systems 60(2):172–193.Crossref, Google Scholar
• Shapley LS (1974) A note on the Lemke-Howson algorithm. Balinski, ML, ed. Pivoting and Extensions Mathematical Programming Studies, Vol. 1 (Springer, Berlin), 175–189.Crossref, Google Scholar
• Shoven J, Whalley J (1992) Applying General Equilibrium (Cambridge University Press, Cambridge, UK).Google Scholar
• Smale S (1976) A convergent process of price adjustment and global Newton methods. J. Math. Econom. 3(2):107–120.Crossref, Google Scholar
• Sonnenschein H (1973) Do Walras’ identity and continuity characterize the class of community excess demand functions? J. Econom. Theory 6(4):345–354.Crossref, Google Scholar
• Spielman DA, Teng SH (2004) Smoothed analysis: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3):385–463.Crossref, Google Scholar
• Todd MJ (1976) Orientation in complementary pivot algorithms. Math. Oper. Res. 1(1):54–66.Link, Google Scholar
• Vazirani VV (2013) Nonseparable, concave utilities are easy—In a perfect price discrimination market model. SIAM J. Discrete Math. 27(1):266–273.Crossref, Google Scholar
• Vazirani VV, Yannakakis M (2011) Market equilibrium under separable, piecewise-linear, concave utilities. J. ACM 58(3):10:1–10:25.Crossref, Google Scholar
• Walras L (1874) Éléments d’économie politique pure ou théorie de la richesse sociale (Elements of Pure Economics, or the Theory of Social Wealth) (Lausanne, Paris). [1899, 4th ed.; 1926, rev ed., 1954, Engl. transl.]Google Scholar
• Yannakakis M (2013) Personal communication.Google Scholar