A New Approach to the Pareto Stable Matching Problem

• 成果类型: Article
• 署名作者: Kamiyama, Naoyuki
• 署名单位: Kyushu University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0627
• 发表日期: 2014
• 页码: 851-862
• 关键词: rank-maximal matchings; school choice; EFFICIENCY; STABILITY; marriage

摘要

In two-sided matching markets, the concept of stability proposed by Gale and Shapley is one of the most important solution concepts. In this paper, we consider a problem related to stability of a matching in a two-sided matching market with indifferences. It is known that stability does not guarantee Pareto efficiency in a two-sided matching market with indifferences. However, Erdil and Ergin proved that there always exists a stable and Pareto efficient matching in a many-to-one matching market with indifferences and gave a polynomial-time algorithm for finding it. Later on, Chen proved that there always exists a stable and Pareto efficient matching in a many-to-many matching market with indifferences and gave a polynomial-time algorithm for finding it. In this paper, we propose a new approach to the problem of finding a stable and Pareto efficient matching in a many-to-many matching market with indifferences. Our algorithm is an alternative proof of the existence of a stable and Pareto efficient matching in a many-to-many matching market with indifferences.