考虑稳定匹配条件的双边满意匹配决策方法

中国管理科学 ›› 2014, Vol. 22 ›› Issue (4): 112-118.

考虑稳定匹配条件的双边满意匹配决策方法

樊治平¹, 李铭洋^1,2, 乐琦³

1. 东北大学工商管理学院, 辽宁沈阳 110819;
2. 沈阳化工大学数理系, 辽宁沈阳 110142;
3. 江西财经大学信息管理学院, 江西南昌 330013

收稿日期:2012-02-15 修回日期:2013-01-22 出版日期:2014-04-20 发布日期:2014-04-23
作者简介:樊治平（1961- ），男（汉族），江苏镇江人，东北大学工商管理学院教授，博士生导师，研究方向：运作管理与决策分析.
基金资助:
国家自然科学基金资助项目（71271051，71371002）；辽宁省高等学校创新团队支持计划项目（WT2013004）；中央高校基本科研业务费专项资金资助项目（N110706001）

Decision Analysis Method for Two-Sided Satisfied Matching Considering Stable Matching Condition

FAN Zhi-ping¹, LI Ming-yang^1,2, YUE Qi³

1. School of Business Administration, Northeastern University, Shenyang 110819, China;
2. Department of Science, Shenyang University of Chemical Technology, Shenyang 110142, China;
3. School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, China

Received:2012-02-15 Revised:2013-01-22 Online:2014-04-20 Published:2014-04-23

摘要/Abstract

摘要： 双边匹配问题是指如何在两个不相交的主体集合中依据各主体针对潜在匹配对象给出的偏好信息来确定合适的匹配结果，其在经济管理领域中存在着大量的实际背景，是许多学者关注的研究课题。在本文中，针对双边主体给出偏好序值信息的双边匹配问题，给出了一种考虑稳定匹配条件的双边满意匹配决策方法。首先给出了双边匹配、稳定匹配和满意匹配的相关概念；然后考虑到稳定匹配条件，并以双边主体满意度最大为目标，构建了多目标双边匹配优化模型；进一步地，采用线性加权法将多目标优化模型转换为单目标优化模型，并通过求解优化模型来获得最优匹配结果。最后，通过一个算例说明了本文提出方法的实用性和有效性。

关键词: 双边匹配, 序值, 稳定匹配, 满意度, 满意匹配, 优化模型

Abstract: Two-sided matching problem refers to how to obtain proper matching result from two disjoint sets of agents according to the preference information of each agent for potential partners from the opposite set. It is a research topic with extensive practical backgrounds in the field of economic management and attracts the attention of many scholars. In this paper, a decision analysis method for two-sided satisfied matching considering stable matching condition is proposed to solve the two-sided matching problem, in which the preference ordinal numbers are provided by agents on both sides. Firstly, the related concepts on two-sided matching, stable matching and satisfied matching are given. Then, considering the stable matching condition, a multi-objective two-sided matching optimization model which maximizes the satisfaction degrees of two-sided agents is constructed. Furthermore, the linear weighted method is used to convert the multi-objective optimization model into a single-objective optimization model, and the optimal matching result can be obtained by solving the model. Finally, a numerical example is given to illustrate the practicality and effectiveness of the method proposed in this paper.

Key words: two-sided matching, ordinal number, stable matching, satisfaction degree, satisfied matching, optimization model

中图分类号:

C934

樊治平, 李铭洋, 乐琦. 考虑稳定匹配条件的双边满意匹配决策方法[J]. 中国管理科学, 2014, 22(4): 112-118.

FAN Zhi-ping, LI Ming-yang, YUE Qi. Decision Analysis Method for Two-Sided Satisfied Matching Considering Stable Matching Condition[J]. Chinese Journal of Management Science, 2014, 22(4): 112-118.

参考文献

[1] Gale D, Shapley L. College admissions and the stability of marriage[J]. American Mathematical Monthly, 1962, 69(1): 9-15.

[2] Janssen M, Verbraeck A. Comparing the strengths and weaknesses of Internet-based matching mechanisms for the transport market[J]. Transportation Research Part E, 2008, 44(3): 475-490.

[3] Sarne D, Kraus S. Managing parallel inquiries in agents' two-sided search[J]. Artificial Intelligence, 2008, 172 (4-5): 541-569.

[4] Lin H T. A job placement intervention using fuzzy approach for two-way choice[J]. Expert Systems with Applications, 2009, 36(2): 2543-2553.

[5] Huang D K, Chiu H N, Yeh R H, et al. A fuzzy multi-criteria decision making approach for solving a bi-objective personnel assignment problem[J]. Computers & Industrial Engineering, 2009, 56(1): 1-10.

[6] Kaiser U, Wright J. Price structure in two-sided markets: Evidence from the magazine industry[J]. International Journal of Industrial Organization, 2006, 24(1): 1-28.

[7] Elitzur R, Gavious A. A multi-period game theoretic model of venture capitalists and entrepreneurs[J]. European Journal of Operational Research, 2003, 144(2): 440-453.

[8] Roth A E. Common and conflicting interests in two-sided matching markets[J]. European Economic Review, 1985, 27(1): 75-96.

[9] McVitie D G, Wilson L B. The stable marriage problem[J]. Communications of the Association for Computing Machinery, 1971, 14(7): 486-492.

[10] Mcvitie D G, Wilson L B.Stable marriage assignment for unequal sets[J]. Bit Numerical mathematics, 1970, 10(3): 295-309.

[11] Halldórsson M M, Iwama K, Miyazaki S, et al. Randomized approximation of the stable marriage problem[J]. Theoretical Computer Science, 2004, 325(3), 439-465.

[12] Vate V, John H.Linear programming brings marital bliss[J]. Operations Research Letters, 1989, 8(3): 1-23.

[13] Roth A E, Rothblum U G, John H, et al. Stable matchings, optimal assignments and linear programming[J]. Mathematics of Operations Research, 1993, 18(4): 803-828.

[14] Iwama K, Manlove D, Miyazaki S, et al. Stable marriage with incomplete lists and ties[C]// Giorgio A, Mariangiola D C, Simonetha R. Proceedings ICALP '99: The 26th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Springer, Berlin, 1999, 1644: 443-452.

[15] Manlove D F, Irving R W, Iwama K, et al. Hard variants of stable marriage[J]. Theoretical Computer Science, 2002, 276(1-2): 261-279.

[16] Iwama K, Miyazaki S, Yamauchi N. A (2-c/√N)-approximation algorithm for the stable marriage problem[J]. Algorithmica, 2008, 51(3): 342-356.

[17] Teo C P, Sethuraman J, Tan W P.Gale-Shapley stable marriage problem revisited strategic issues and applications[J]. Management Science, 2001, 47(9): 1252-1267.

[18] Gale D. The two-sided matching problem: Origin, development and current issues[J]. International Game Theory Review, 2001, 3(2-3): 237-252.

[19] Echenique F.What matchings can be stable? The testable implications of matching theory[J]. Mathematics of Operations Research, 2008, 33(3): 757-768.

[20] 党兴华, 贾卫峰. GS匹配算法在企业技术创新网络结构形成中的应用[J]. 系统工程, 2009, 27(4): 31-36.

[21] Clark S, Kanbur R. Stable partnerships, matching, and local public goods[J]. European Economic Review, 2004, 48(4): 905-925.

[22] Alkan A, Gale D. Stable schedule matching under revealed preference[J]. Journal of Economic Theory, 2003, 112(2): 289-306.

[23] Cohon J L. Multiobjective programming and planning[M]// Mustoe L R, Barry M D J. Mathematics in Science and Engineering, New York: Academic Press, 1978.

[24] 钱颂迪.运筹学[M]. 北京:清华大学出版社, 1996.