Computing Large Market Equilibria using Abstractions
Computing Large Market Equilibria using Abstractions
复制标题
DOI：
10.1145/3328526.3329553
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Christian Kroer;A. Peysakhovich;Eric Sodomka;N. Stier-Moses
中科院分区：
文献类型：
--
作者：
Christian Kroer;A. Peysakhovich;Eric Sodomka;N. Stier-Moses
计算市场均衡是市场设计（如公平分割、物品分配）的一个重要实际问题。然而，计算均衡需要大量的信息（例如，所有物品的所有买家的所有估价）和计算能力。我们考虑通过应用用于解决复杂博弈的方法来改善这些问题：构建给定市场的粗糙抽象，求解抽象中的均衡，并将价格和分配提升回原始市场。我们展示了如何约束重要的数量，如遗憾，嫉妒，纳什社会福利，帕累托最优，最大化份额时，抽象的价格和分配的地方使用的真实的均衡。然后，我们研究了两个抽象的从业者感兴趣的方法：1）填写在未知的估值使用矩阵完成技术，2）减少问题的规模，通过聚合组的买家/项目成较小数量的代表性买家/项目，并解决在这个粗化的市场均衡。我们发现，在真实的数据分配/价格是相对接近均衡，可以计算出甚至非常粗糙的抽象。
Computing market equilibria is an important practical problem for market design (e.g. fair division, item allocation). However, computing equilibria requires large amounts of information (e.g. all valuations for all buyers for all items) and compute 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 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.