Computing Large Market Equilibria Using Abstractions
- 1 January 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 70 (1) , 329-351
Abstract
Computing market equilibria is an important practical problem for market design, for example, in fair division of items. However, computing equilibria requires large amounts of information (typically the valuation of every buyer for every item) and computing power. We consider ameliorating these issues by applying a method used for solving complex games: constructing a coarsened abstraction of a given market, solving for the equilibrium in the abstraction, and lifting the prices and allocations back to the original market. We show how to bound important quantities such as regret, envy, Nash social welfare, Pareto optimality, and maximin share/proportionality when the abstracted prices and allocations are used in place of the real equilibrium. We then study two abstraction methods of interest for practitioners: (1) filling in unknown valuations using techniques from matrix completion and (2) reducing the problem size by aggregating groups of buyers/items into smaller numbers of representative buyers/items and solving for equilibrium in this coarsened market. We find that in real data allocations/prices that are relatively close to equilibria can be computed from even very coarse abstractions.Keywords
This publication has 31 references indexed in Scilit:
- Truth, justice, and cake cuttingGames and Economic Behavior, 2013
- The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal IncomesJournal of Political Economy, 2011
- Cake cutting really is not a piece of cakeACM Transactions on Algorithms, 2011
- An algorithm for finding equilibrium in the linear exchange model with fixed budgetsJournal of Applied and Industrial Mathematics, 2009
- Chapter 23 Heterogeneous Agent Models in Economics and Finance2006
- The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design EconomicsEconometrica, 2002
- Automobile Prices in Market EquilibriumEconometrica, 1995
- Equity, envy, and efficiencyJournal of Economic Theory, 1974
- WELFARE ECONOMICS AND EXISTENCE OF AN EQUILIBRIUM FOR A COMPETITIVE ECONOMYMetroeconomica, 1960
- Consensus of Subjective Probabilities: The Pari-Mutuel MethodThe Annals of Mathematical Statistics, 1959