Computing large market equilibria using abstractions
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Multi-Agent Reinforcement Learning for Greenhouse Gas Offset Credit Markets
Climate change is a major threat to the future of humanity, and its impacts are being intensified by excess man-made greenhouse gas emissions. One method governments can employ to control these emissions is to provide fi…
Multi-agent Reinforcement Learningreinforcement-learningReinforcement LearningA Unified Framework for Extensive-Form Game Abstraction with Bounds
Abstraction has long been a key component in the practical solving of large-scale extensive-form games. Despite this, abstraction remains poorly understood. There have been some recent theoretical results but they have b…
FormSubgame Perfect Nash Equilibria in Large Reinsurance Markets
We consider a model of a reinsurance market consisting of multiple insurers on the demand side and multiple reinsurers on the supply side, thereby providing a unifying framework and extension of the recent literature on …
Convex-Concave Min-Max Stackelberg Games
Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made …
Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
Computing Nash equilibria of zero-sum games in classical and quantum settings is extensively studied. For general-sum games, computing Nash equilibria is PPAD-hard and the computing of a more general concept called corre…