Constrained random matching

• 成果类型: Article
• 署名作者: Balbuzanov, Ivan
• 署名单位: University of Melbourne
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2022.105472
• 发表日期: 2022
• 关键词: Constrained random assignment; probabilistic serial mechanism; sd-efficiency; fairness

摘要

This paper generalizes the Probabilistic Serial (PS) mechanism of Bogomolnaia and Moulin (2001) to matching markets with arbitrary constraints. The constraints are modeled as a set of permissible ex post allocations. A result of independent interest gives a simple geometric characterization of all lotteries over the set of permissible allocations: they are the ones that satisfy a collection of simple and tractable linear inequalities determined by the constraints. The inequalities correspond to the hyperplanes defining a convex polytope that is intuitively constructed from the given set. When a general version of the PS algorithm is executed under these inequalities, the outcome is an efficient and fair lottery over the set of permissible allocations. The method is general, can be applied to both one-sided and two-sided matching markets, and allows for multi-unit demand. (c) 2022 Elsevier Inc. All rights reserved.