A satisfaction and fairness based matching approach for mutual selection problem

作     者：Lixia Li Lichen Zhang Sui Yu A’na Wang Lizong Zhang 

作者机构：Key Laboratory of Modern Teaching Technology Ministry of Education Xi’an 710119 China School of Computer Science Shaanxi Normal University Xi’an 710119 China School of Computer Science and Engineering University of Electronic Science and Technology of China Chengdu 610054 China 

出 版 物：《Procedia Computer Science》 

年 卷 期：2019年第147卷

页      面：422-427页

主　　题：Satisfaction Relative Fairness Mutual Selection Problem Dynamic Programming 

摘      要：In colleges and universities, bidirectional selection of students and supervisors is very common to determine the supervisor-student pairs. However, the most bidirectional selection methods only focus on the maximization of the number of matching pairs, while not considering the specific satisfaction and fairness of each person. To deal with such issue, in this paper, we introduce two novel metrics of satisfaction and fairness for each person, and then formulate the bidirectional selection problem to an integer linear programming problem with the predefined relative fairness. Due to the NP-hardness of the problem, we propose three heuristic algorithms, respectively named by the Satisfaction-based Greedy (SG) algorithm, the Weight-based Greedy (WG) algorithm and the Satisfaction-based Dynamic Programming (SDP) algorithm. We evaluate the performance of the three algorithms in terms of total satisfaction, average satisfaction and matching ratio. The experimental results show that the SDP can achieve the maximized satisfaction and a higher matching ratio.