Computing large market equilibria using abstractions
From MaRDI portal
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, (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.
Recommendations
Cites work
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A simpler approach to matrix completion
- Algorithmic Game Theory
- Approximating the Nash Social Welfare with Indivisible Items
- Automobile Prices in Market Equilibrium
- Cake cutting algorithms for piecewise constant and piecewise uniform valuations
- Cake cutting really is not a piece of cake
- Combinatorial auction design
- Computation of Fisher-Gale equilibrium by auction
- Computing Walrasian equilibria: fast algorithms and structural properties
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Consensus of Subjective Probabilities: The Pari-Mutuel Method
- Counterfactual reasoning and learning systems: the example of computational advertising
- CVXPY: a Python-embedded modeling language for convex optimization
- DeepStack: expert-level artificial intelligence in heads-up no-limit poker
- Eigentaste: A constant time collaborative filtering algorithm
- Markets for public decision-making
- Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
- Mathematics in economics: Achievements, difficulties, perspectives
- Multiplicative Pacing Equilibria in Auction Markets
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
- SHOPPER: a probabilistic model of consumer choice with substitutes and complements
- Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
- Strategy-proofness in the large
- Superhuman AI for heads-up no-limit poker: Libratus beats top professionals
- The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics
- Truth, justice, and cake cutting
- Understanding preferences: ``demand types, and the existence of equilibrium with indivisibilities
- Walrasian equilibria from an optimization perspective: A guide to the literature
- WELFARE ECONOMICS AND EXISTENCE OF AN EQUILIBRIUM FOR A COMPETITIVE ECONOMY
Describes a project that uses
Uses Software
This page was built for publication: Computing large market equilibria using abstractions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5031015)
