Computing Large Market Equilibria Using Abstractions

References

• Agrawal A, Verschueren R, Diamond S, Boyd S (2018) A rewriting system for convex optimization problems. J. Control Decis. 5(1):42–60.Crossref, Google Scholar
• Andersen M, Dahl J, Vandenberghe L (2013) Cvxopt: A Python package for convex optimization. Accessed April 2021, http://abel.ee.ucla.edu/cvxopt.Google Scholar
• Azevedo EM, Budish E (2018) Strategy-proofness in the large. Rev. Econom. Stud. 86(1):81–116.Google Scholar
• Aziz H, Mackenzie S (2016) A discrete and bounded envy-free cake cutting protocol for any number of agents. Foundations Comput. Sci. (FOCS), 2016 IEEE 57th Annual Symposium, 416–427.Google Scholar
• Aziz H, Ye C (2014) Cake cutting algorithms for piecewise constant and piecewise uniform valuations. Internat. Conf. Web Internet Econom. (Springer), 1–14.Google Scholar
• Baldwin E, Klemperer P (2019) Understanding preferences: “demand types”, and the existence of equilibrium with indivisibilities. Econometrica 87(3):867–932.Crossref, Google Scholar
• Balkanski E, Kurokawa D, Brânzei S, Procaccia AD (2014) Simultaneous cake cutting. Proc. Twenty-Eighth AAAI Conf. Artificial Intelligence (AAAI Press), 566–572.Google Scholar
• Bauckhage C (2015) K-means clustering is matrix factorization. Preprint, submitted December 23, https://arxiv.org/abs/1512.07548.Google Scholar
• Berry S, Levinsohn J, Pakes A (1995) Automobile prices in market equilibrium. Econometrica 63(4):841–890.Crossref, Google Scholar
• Bhojanapalli S, Neyshabur B, Srebro N (2016) Global optimality of local search for low rank matrix recovery. Preprint, submitted May 23, https://arxiv.org/abs/1605.07221.Google Scholar
• Bichler M, Waldherr S (2019) Computing core-stable outcomes in combinatorial exchanges with financially constrained bidders. Proc. 2019 ACM Conf. Econom. Comput., 1–28.Google Scholar
• Bichler M, Fichtl M, Schwarz G (2021) Walrasian equilibria from an optimization perspective: A Guide to the literature. Naval Res. Logist. 68(4):496–513.Crossref, Google Scholar
• Birnbaum B, Devanur NR, Xiao L (2011) Distributed algorithms via gradient descent for Fisher markets. Proc. 12th ACM Conf. Electronic Commerce, 127–136.Google Scholar
• Borgs C, Chayes J, Immorlica N, Jain K, Etesami O, Mahdian M (2007) Dynamics of bid optimization in online advertisement auctions. Proc. 16th Internat. Conf. World Wide Web, 531–540.Google Scholar
• Bottou L, Peters J, Quiñonero-Candela J, Charles DX, Chickering DM, Portugaly E, Ray D, Simard P, Snelson E (2013) Counterfactual reasoning and learning systems: The example of computational advertising. J. Machine Learn. Res. 14(1):3207–3260.Google Scholar
• Brown N, Sandholm T (2018) Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Sci. 359(6374):418–424.Crossref, Google Scholar
• Brown N, Ganzfried S, Sandholm T (2015) Hierarchical abstraction, distributed equilibrium computation, and post-processing, with application to a champion no-limit Texas hold’em agent. Proc. 2015 Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems), 7–15.Google Scholar
• Brown N, Lerer A, Gross S, Sandholm T (2019) Deep counterfactual regret minimization. Chaudhuri K, Salakhutdinov R, eds., Proc. 36th Internat. Conf. Machine Learn., ICML 2019, June 9-15, 2019, Long Beach, California,, vol. 97 Proc. Machine Learn. Res. (PMLR), 793–802.Google Scholar
• Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
• Budish E, Kessler JB (2016) Bringing real market participants’ real preferences into the laboratory: An experiment that changed the course allocation mechanism at Wharton. Working paper, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2016) The unreasonable fairness of maximum Nash welfare. Proc. 2016 ACM Conf. Economics Comput. (ACM), 305–322.Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145.Crossref, Google Scholar
• Chambolle A, Pock T (2016) On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Programming 159(1-2):253–287.Crossref, Google Scholar
• Chawla S, Hartline JD, Nekipelov D (2017) Mechanism redesign. Preprint, submitted August 15, https://arxiv.org/abs/1708.04699.Google Scholar
• Chen X, Teng SH (2009) Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria. Internat. Symposium Algorithms Comput. (Springer), 647–656.Google Scholar
• Chen L, Ye Y, Zhang J (2007) A note on equilibrium pricing as convex optimization. Internat. Workshop Web Internet Econom. (Springer), 7–16.Google Scholar
• Chen X, Dai D, Du Y, Teng SH (2009) Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. 2009 50th Annual IEE Sympos. Foundations Comput. Sci. (IEEE), 273–282.Google Scholar
• Chen Y, Lai JK, Parkes DC, Procaccia AD (2013) Truth, justice, and cake cutting. Games Econom. Behav. 77(1):284–297.Crossref, Google Scholar
• Cole R, Gkatzelis V (2018) Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211–1236.Crossref, Google Scholar
• Cole R, Devanur NR, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. 18th ACM Conf. Economics Computation, EC 2017.Google Scholar
• Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res. Forthcoming.Google Scholar
• Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Sodomka E, Stier-Moses NE, Wilkens C (2022b) Pacing equilibrium in first-price auction markets. Management Sci. Forthcoming.Google Scholar
• Diamond S, Boyd S (2016) CVXPY: A Python-embedded modeling language for convex optimization. J. Machine Learn. Res. 17(83):1–5.Google Scholar
• Domahidi A, Chu E, Boyd S (2013) ECOS: An SOCP solver for embedded systems. Eur. Control Conf. (ECC), 3071–3076.Google Scholar
• Edmonds J, Pruhs K (2011) Cake cutting really is not a piece of cake. ACM Trans. Algorithms 7(4):51.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
• Feng Z, Narasimhan H, Parkes DC (2018) Deep learning for revenue-optimal auctions with budgets. Proc. 17th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems), 354–362.Google Scholar
• Ganzfried S, Sandholm T (2014) Potential-aware imperfect-recall abstraction with earth mover’s distance in imperfect-information games. Proc. Twenty-Eighth AAAI Conf. Artificial Intelligence, 682–690 (AAAI Press).Google Scholar
• Gao Y, Kroer C (2021) Infinite-dimensional Fisher markets: Equilibrium, duality and optimization. Proc. AAAI Conf. Artificial Intelligence.Google Scholar
• Garg N, Goel A, Plaut B (2021) Markets for public decision-making. Soc. Choice Welfare 56:755–801.Crossref, Google Scholar
• Ge R, Lee JD, Ma T (2016) Matrix completion has no spurious local minimum. Proc. 30th Internat. Conf. Neural Inform. Processing Systems (NIPS'16) (Curran Associates Inc., Red Hook, New York), 2981–2989.Google Scholar
• Gilpin A, Sandholm T, Sørensen TB (2007) Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of texas hold’em poker. Proc. 22nd National Conf. Artificial Intelligence-Volume 1 (AAAI Press), 50–57.Google Scholar
• Goldberg K, Roeder T, Gupta D, Perkins C (2001) Eigentaste: A constant time collaborative filtering algorithm. Inform. Retrieval 4(2):133–151.Crossref, Google Scholar
• Goldman J, Procaccia AD (2015) Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges 13(2):41–46.Crossref, Google Scholar
• Golowich N, Narasimhan H, Parkes DC (2018) Deep learning for multi-facility location mechanism design. Proc. 27th Internat. Joint Conf. Artificial Intelligence (AAAI Press), 261–267.Google Scholar
• Harper FM, Konstan JA (2015) The movielens datasets: History and context. ACM Trans. Interactive Intelligence Systems 5(4).Google Scholar
• Hayek FA (1945) The use of knowledge in society. Amer. Econom. Rev. 35(4):519–530.Google Scholar
• Hommes CH (2006) Heterogeneous agent models in economics and finance. Handbook of Computational Economics 2:1109–1186.Crossref, Google Scholar
• Johnson J, Douze M, Jégou H (2021) Billion-scale similarity search with GPUs. IEEE Trans. Big Data 7(3):535–547.Crossref, Google Scholar
• Kantorovich LV (1960) Mathematical methods of organizing and planning production. Management Sci. 6(4):366–422.Google Scholar
• Kantorovich LV (1976) Mathematics in economics: Achievements, difficulties, perspectives. Math. Programming 11:204–211.Google Scholar
• Klemperer P (2018) Auctions: Theory and Practice (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Kroer C, Sandholm T (2014) Extensive-form game abstraction with bounds. Proc. Fifteenth ACM Conf. Econom. Comput. (ACM), 621–638.Google Scholar
• Kroer C, Sandholm T (2016) Imperfect-recall abstractions with bounds in games. Proc. 2016 ACM Conf. Econom. Comput. (ACM), 459–476.Google Scholar
• Kroer C, Sandholm T (2018) A unified framework for extensive-form game abstraction with bounds. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems 31 (NeurIPS 2018), 612–623.Google Scholar
• Lanctot M, Gibson R, Burch N, Zinkevich M, Bowling M (2012) No-regret learning in extensive-form games with imperfect recall. Proc. 29th Internat. Conf. Internat. Conf. Machine Learn. (Omnipress), 1035–1042.Google Scholar
• Leme RP, Wong SC (2020) Computing Walrasian equilibria: Fast algorithms and structural properties. Math. Programming 179(1):343–384.Crossref, Google Scholar
• Lerer A, Peysakhovich A (2017) Maintaining cooperation in complex social dilemmas using deep reinforcement learning. Preprint, submitted July 4, https://arxiv.org/abs/1707.01068.Google Scholar
• Lerer A, Peysakhovich A (2019) Learning social conventions in Markov games. Conf. Artificial Intelligence, Ethics, Society.Google Scholar
• Ljungqvist L, Sargent TJ (2018) Recursive Macroeconomic Theory (MIT Press, Cambridge MA).Google Scholar
• Lu T, Boutilier C (2015) Value-directed compression of large-scale assignment problems. Twenty-Ninth AAAI Conf. Artificial Intelligence.Google Scholar
• Megiddo N, Vazirani VV (2007) Continuity properties of equilibrium prices and allocations in linear Fisher markets. Internat. Workshop Web Internet Econom. (Springer), 362–367.Google Scholar
• Moravčík M, Schmid M, Burch N, Lis V, Morrill D, Bard N, Davis T, Waugh K, Johanson M, Bowling M (2017) Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Sci. 356(6337):508–513.Crossref, Google Scholar
• Murray R, Kroer C, Peysakhovich A, Shah P (2020) Robust market equilibria with uncertain preferences. Proc. Conf. AAAI Artifical Intelligence, vol. 34 (AAAI Press), 2192–2199.Crossref, Google Scholar
• Negishi T (1960) Welfare economics and existence of an equilibrium for a competitive economy. Metroeconomica 12(2-3):92–97.Crossref, Google Scholar
• Nesterov Y, Shikhman V (2018) Computation of Fisher–Gale equilibrium by auction. J. Oper. Res. Soc. China. 6(3):349–389.Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3):1042–1068.Crossref, Google Scholar
• Othman A, Papadimitriou C, Rubinstein A (2016) The complexity of fairness through equilibrium. ACM Trans. Econom. Comput. 4(4):Article 20.Google Scholar
• Paszke A, Gross S, Chintala S, Chanan G, Yang E, DeVito Z, Lin Z, Desmaison A, Antiga L, Lerer A (2017) Automatic differentiation in PyTorch. NIPS 2017 Workshop Autodiff Submission, October 28, 2017.Google Scholar
• Peng F, Sandholm T (2016) Scalable segment abstraction method for advertising campaign admission and inventory allocation optimization. Proc. Twenty-Fifth Internat. Joint Conf. Artificial Intelligence (AAAI Press), 655–661.Google Scholar
• Peysakhovich A, Ugander J (2017) Learning context-dependent preferences from raw data. Proc. 12th Workshop Econom. Networks, Systems Comput. (ACM), 8.Google Scholar
• Peysakhovich A, Kroer C, Lerer A (2019) Robust multi-agent counterfactual prediction. Wallach H, Larochelle H, Beygelzimer A, d'Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform Process Systems 32 (NeurIPS 2019), 3077–3087.Google Scholar
• Porter D, Rassenti S, Roopnarine A, Smith V (2003) Combinatorial auction design. Proc. Natl. Acad. Sci. USA. 100(19):11153–11157.Crossref, Google Scholar
• Recht B (2011) A simpler approach to matrix completion. J. Machine Learn. Res. 12:3413–3430.Google Scholar
• Roth AE (2002) The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica 70(4):1341–1378.Crossref, Google Scholar
• Ruiz FJ, Athey S, Blei DM (2020) Shopper: A probabilistic model of consumer choice with substitutes and complements. Ann. Appl. Statist. 14(1):1–27.Crossref, Google Scholar
• Scarf HE (1967) On the computation of equilibrium prices. Cowles Foundation Discussion Papers 232, Cowles Foundation for Research in Economics, Yale University, New Haven CT.Google Scholar
• Shmyrev VI (2009) An algorithm for finding equilibrium in the linear exchange model with fixed budgets. J. Appl. Indust Math. 3(4):Article 505.Crossref, Google Scholar
• Varian HR (1974) Equity, envy, and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• Walsh WE, Boutilier C, Sandholm T, Shields R, Nemhauser G, Parkes DC (2010) Automated channel abstraction for advertising auctions. Proc. Twenty-Fourth AAAI Conf. Artificial Intelligence (AAAI Press), 887–894.Google Scholar
• Waugh K, Zinkevich M, Johanson M, Kan M, Schnizlein D, Bowling MH (2009) A practical use of imperfect recall. Proc. Eighth Symposium Abstraction, Reformulation, Approximation (SARA’09).Google Scholar