Approximate Random Allocation Mechanisms

• 成果类型: Article
• 署名作者: Akbarpour, Mohammad; Nikzad, Afshin
• 署名单位: Stanford University; University of Southern California
• 刊物名称: REVIEW OF ECONOMIC STUDIES
• ISSN/ISSBN: 0034-6527
• DOI: 10.1093/restud/rdz066
• 发表日期: 2020
• 页码: 2473-2510
• 关键词: reduced-form auctions; random assignment; school choice; equilibrium; efficient; serial; EQUIVALENCE; economies

摘要

We generalize the scope of random allocation mechanisms, in which the mechanism first identifies a feasible expected allocation and then implements it by randomizing over nearby feasible integer allocations. The previous literature has shown that the cases in which this is possible are sharply limited. We show that if some of the feasibility constraints can be treated as goals rather than hard constraints, then, subject to weak conditions that we identify, any expected allocation that satisfies all the constraints and goals can be implemented by randomizing among nearby integer allocations that satisfy all the hard constraints exactly and the goals approximately. By defining ex post utilities as goals, we are able to improve the ex post properties of several classic assignment mechanisms, such as the random serial dictatorship. We use the same approach to prove the existence of epsilon-competitive equilibrium in large markets with indivisible items and feasibility constraints.