A computational approach to the multi-period many-to-one matching with ties

Xinsheng Xiong (), Yong Zhao and Yang Chen
Additional contact information
Xinsheng Xiong: Huazhong University of Science and Technology
Yong Zhao: Huazhong University of Science and Technology
Yang Chen: Huazhong University of Science and Technology

Journal of Combinatorial Optimization, 2017, vol. 33, issue 1, No 13, 183-201

Abstract: Abstract The many-to-one matching problem is commonly referred as the hospitals/residents problem which assigns each resident a hospital in an efficient and fair way. This paper considers a multi-period hospitals/residents problem that consists of assigning positions to overlapping generations of residents. From one period to another, residents can either retain their current positions or can choose a more preferred one. In this situation, a fairness criterion is introduced with the condition of the individual rationality for the matching. Moreover, it has been proven that the matching satisfying such criterion always exists and can be obtained by iteratively eliminating Pareto improvement cycles and unjustified claim cycles from any acceptable matching. This paper presents a novel algorithm to compute a matching with minimal unjustified claims under the premise of satisfying the individual rationality and the Pareto efficiency. The complexity of the proposed algorithm is bounded by $$O(Q^{3}n^{3})$$ O ( Q 3 n 3 ) in each period, where n and Q are the number of the residents and the total number of positions of the hospitals in the corresponding period, respectively.

Keywords: Many-to-one matching; Multi-period; Individual rationality; Pareto efficiency; Fairness (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9944-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:1:d:10.1007_s10878-015-9944-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9944-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().