考虑双边主体公平性的稳定匹配决策方法

doi:F 270；C 934

系统管理学报 ›› 2015, Vol. 24 ›› Issue (3): 397-404.DOI: F 270；C 934

考虑双边主体公平性的稳定匹配决策方法

孔德财，姜艳萍，梁海明

东北大学工商管理学院，沈阳110819

收稿日期:2014-01-13 修回日期:2014-09-22
作者简介:孔德财(1984-)，男，博士生。研究方向为管理决策分析。E-mail: ypjiang@mail.neu.edu.cn
基金资助:
国家自然科学基金资助项目(71271050)；高等学校博士学科点专项科研基金资助课题(20110042110011)

Stable Matching with Fairness for Two-sided Agents

KONG De-cai，JIANG Yan-ping，LIANG Hai-ming

School of Business Administration, Northeastern University, Shenyang 110819，China

Received:2014-01-13 Revised:2014-09-22

摘要/Abstract

摘要： 针对一对一双边匹配决策问题，依据双边主体给出的多指标评价信息提出了一种新的双边匹配决策方法。给出了稳定匹配和公平匹配的相关概念，并给出了双边主体满意度的计算方法；建立了考虑稳定性、公平性和满意性的多目标优化模型，并设计了一个多目标遗传算法用于求解模型；最后，通过教育服务机构中学生与老师的双边匹配实例验证了方法的实用性和有效性。

关键词: 双边匹配, 稳定匹配, 公平匹配, 满意度, 多目标优化模型

Abstract: For the one to one two-sided matching problem, a new two-sided matching method based on multiple criteria information of two-sided agents is proposed. Firstly, the concept of stable matching and fair matching in two-sided matching are introduced, and the computing method of two-sided matching agents’ satisfaction is developed. Secondly, a mathematical model of two-sided matching considering stability, fairness and satisfaction is constructed. A multi-objective genetic algorithm is designed to solve the model. An example of students and teachers matching in educational institution is used to illustrate feasibility and validity of the proposed method.

Key words: two-sided matching, stable matching, fair matching, satisfaction, multiple-objective optimization model

孔德财，姜艳萍，梁海明. 考虑双边主体公平性的稳定匹配决策方法[J]. 系统管理学报, 2015, 24(3): 397-404.

参考文献

[1]      Gale D, Shapley L S. College admissions and the stability of marriage [J]. The American Mathematical Monthly, 1962, 69(1): 9-15.
[2]      Korkmaz ?, Gökçen H, Çetinyoku? T. An analytic hierarchy process and two-sided matching based decision support system for military personnel assignment [J]. Information Sciences, 2008, 178(14): 2915-2927.
[3]      陈希,樊治平,韩菁.考虑关联性指标的双边匹配决策方法[J].运筹与管理,2012,21(6):94:99.
[4]      陈希,樊治平,李玉花. IT服务供需双边匹配的模糊多目标决策方法[J].管理学报,2011,8(7):1097-1101.
[5]      蒋忠中,喻海飞, 盛莹. 电子中介中多数量的多属性商品交易匹配模型与算法[J].系统管理学报,2010,19(5):593-600.
[6]      Zhang Z, Guo C H. A hybrid multiple attributes two-sided matching decision making method with incomplete weight information [M]. New York: Springer Berlin Heidelberg, 2011:272-283.
[7]    Gusfield D, Irving R W. The stable marriage problem: structure and algorithms [M]. Cambridge: MIT press, 1989.
[8]      Kato A. Complexity of the sex-equal stable marriage problem [J]. Japan Journal of Industrial and Applied Mathematics, 1993, 10(1): 1-19.
[9]      Iwama K, Miyazaki S, Yanagisawa H. Approximation algorithms for the sex-equal stable marriage problem [M]. Algorithms and Data Structures. New York: Springer Berlin Heidelberg, 2007: 201-213.
[10] McDermid E, Irving R W. Sex-equal stable matchings: Complexity and exact algorithms [J]. Algorithmica, 2012: 1-26.
[11] Cheng C T. Understanding the generalized median stable matchings[J]. Algorithmica, 2010, 58(1): 34-51.
[12] Roth A E, Rothblum U G, Vate J H V. Stable matchings, optimal assignments, and linear programming[J]. Mathematics of Operations Research, 1993, 18(4): 803-828.
[13] Vande Vate J H. Linear programming brings marital bliss [J]. Operations Research Letters, 1989, 8(3): 147-153.
[14] Vohra R V. Stable matchings and linear programming [J]. Current Science (Bangalore), 2012, 103(9): 1051-1055.
[15] Herrera F, López E, Mendaña C, et al. Solving an assignment–selection problem with verbal information and using genetic algorithms [J]. European Journal of Operational Research, 1999, 119(2): 326-337.
Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II [J] IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.