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, often the valuation of every buyer for every item, and computing power. In “Computing Large Market Equilibria Using Abstractions,” the authors study abstraction methods for ameliorating these issues. The basic abstraction idea is as follows. First, construct a coarsened abstraction of a given market, then solve for the equilibrium in the abstraction, and finally, lift the prices and allocations back to the original market. The authors show theoretical guarantees on the solution quality obtained via this approach. Then, two abstraction methods of interest for practitioners are introduced: (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.