Computing Large Market Equilibria Using Abstractions

Christian Kroer (), Alexander Peysakhovich (), Eric Sodomka () and Nicolas E. Stier-Moses ()
Additional contact information
Christian Kroer: IEOR Department Columbia University, New York, New York 10027
Alexander Peysakhovich: Facebook AI Research, Menlo Park, California 94025
Eric Sodomka: Facebook Core Data Science, Menlo Park, California 94025
Nicolas E. Stier-Moses: Facebook Core Data Science, Menlo Park, California 94025

Operations Research, 2022, vol. 70, issue 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: Revenue Management and Market Analytics; market equilibrium; abstraction; Eisenberg-Gale; Fisher markets (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2163 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:1:p:329-351

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().