Efficient matching under general constraints

• 成果类型: Article
• 署名作者: Imamura, Kenzo; Kawase, Yasushi
• 署名单位: University of Tokyo
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2024.03.013
• 发表日期: 2024
• 页码: 197-207
• 关键词: Matching with constraints; efficient matching; serial dictatorship; top trading cycles; matroid

摘要

We study indivisible goods allocation problems under constraints and provide algorithms to check whether a given matching is Pareto efficient. We first show that the serial dictatorship algorithm can be used to check Pareto efficiency if the constraints are matroid. To prove this, we develop a generalized top trading cycles algorithm. Moreover, we show that the matroid structure is necessary for obtaining all Pareto efficient matchings by the serial dictatorship algorithm. Second, we provide an extension of the serial dictatorship algorithm to check Pareto efficiency under general constraints. As an application of our results to prioritized allocations, we discuss Pareto improving the deferred acceptance algorithm.