Xu, Xinkai (2015) Two-sided matching algorithms for dynamic labor markets. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
946kBthesis.pdf - Accepted Version |
Abstract
Temporary recruitment is a fast growing labor market with candidates, usually professionals, looking for contract positions in today’s fast evolving and dynamic economy. While two-sided matching algorithms have been applied to some labor markets during the past decades, they usually assume a static environment in which the strategic interactions between candidates and employers are designed without considering dynamic changes in market participants. In recent years, the advance of Internet and mobile technologies has enabled the implementation of large scale online labor markets which can capture the dynamics of the participants in a near real time manner.
In this thesis, I study how to improve the effectiveness and the efficiency of recruitment processes in the context of temporary labor markets. The key challenge is how to design two-sided matching algorithms to accommodate dynamic changes in market participants. To have a better understanding of the challenge and possible solutions, I first analyzed the problem using the Environment-Based Design (EBD) methodology. The analyzing results show that two aspects need to by improved in the proposed two sided matching algorithm: the efficiency, which is the responsiveness of the algorithm, and the effectiveness, which is measured by the consistency of solutions generated by the algorithm when dynamics are introduced.
Based on the results derived from EBD analysis, I designed two algorithms to improve the efficiency and the effectiveness. For the efficiency, I designed a request-accumulated deferred acceptance algorithm, which is a modification of the classical deferred acceptance algorithm. In addition, I designed a repair-based two-sided matching algorithm to improve solution consistency when changes are introduced to the market. The performance of the proposed algorithms are evaluated through a computational study. The results show that the efficiency and the effectiveness design requirements are satisfied.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Xu, Xinkai |
| Institution: | Concordia University |
| Degree Name: | M.A. Sc. |
| Program: | Information Systems Security |
| Date: | 10 August 2015 |
| Thesis Supervisor(s): | Wang, Chun and Zeng, Yong |
| Keywords: | two-sided matching dynamic responsiveness result consistency repair-based algorithm |
| ID Code: | 980265 |
| Deposited By: | XINKAI XU |
| Deposited On: | 03 Nov 2015 15:51 |
| Last Modified: | 18 Jan 2018 17:51 |
References:
[1] JHV Vate AE Roth. Random paths to stability in two-sided matching. Econometrica:Journal of the Econometric Society, pages 1475–1480, 1990.
[2] MAO Sotomayor AE Roth. Two-sided matching: A study in game-theoretic modeling
and analysis. Number 18. Cambridge University Press, 1992.
[3] VP Crawford AS Kelso Jr. Job matching, coalition formation, and gross substitutes.
Econometrica: Journal of the Econometric Society, pages 1483–1504, 1982.
[4] J Massó B Dutta. Stability of matchings when individuals have preferences over
colleagues. Journal of Economic Theory, 75(2):464–475, 1997.
[5] K Iwama S Miyazaki DF Manlove, RW Irving. Hard variants of stable marriage.
Theoretical Computer Science, 276(1):261–279, 2002.
[6] LBWilson DG McVitie. The application of the stable marriage assignment to university
admissions. Operational Research Quarterly, pages 425–433, 1970.
[7] LBWilson DG McVitie. The stable marriage problem. Communications of the ACM,
14(7):486–490, 1971.
[8] PJ Dolton. The â˘AŸmarriage gameâ˘A ´ Z: An assignment problem with indivisibilities.
Theory and Decision, 14(4):373–389, 1982.
81
[9] David Gale and Lloyd S Shapley. College admissions and the stability of marriage.
American mathematical monthly, pages 9–15, 1962.
[10] P Gärdenfors. Match making: assignments based on bilateral preferences. Behavioral
Science, 20(3):166–173, 1975.
[11] G Isaak H Abeledo. A characterization of graphs that ensure the existence of stable
matchings. Mathematical social sciences, 22(1):93–96, 1991.
[12] SY Itoga. The upper bound for the stable marriage problem. Journal of the Operational
Research Society, pages 811–814, 1978.
[13] SY Itoga. A generalization of the stable marriage problem. Journal of the Operational
Research Society, pages 1069–1074, 1981.
[14] L Lovász J Csima. A matching algorithm for regular bipartite graphs. Discrete applied
mathematics, 35(3):197–203, 1992.
[15] RF Kirby. A preferencing model for trip distribution. Transportation Science, 4(1):1–
35, 1970.
[16] AE Roth. The economics of matching: Stability and incentives. Mathematics of
operations research, 7(4):617–628, 1982.
[17] AE Roth. Stability and polarization of interests in job matching. Econometrica:
Journal of the Econometric Society, pages 47–57, 1984.
[18] AE Roth. The college admissions problem is not equivalent to the marriage problem.
Journal of economic Theory, 36(2):277–288, 1985.
[19] D Gusfield RW Irving, P Leather. An efficient algorithm for the â ˘ AIJoptimalâ˘A
˙I
stable marriage. Journal of the ACM (JACM), 34(3):532–543, 1987.
82
[20] RCT Lee SS Tseng. A parallel algorithm to solve the stable marriage problem. BIT
Numerical Mathematics, 24(3):308–316, 1984.
[21] A Tamura. Transformation from arbitrary matchings to stable matchings. Journal of
Combinatorial Theory, Series A, 62(2):310–323, 1993.
[22] LB Wilson. An analysis of the stable marriage assignment algorithm. BIT Numerical
Mathematics, 12(4):569–575, 1972.
[23] Y. Zeng. Axiomatic theory of design modeling. Journal of Integrated Design and
Process Science, pages 1–28, 2002.
[24] Y. Zeng. Axiomatic theory of design modeling. Environment-based formulation of
design problem, pages 45–63, 2004.
[25] L Zhou. Stable matchings and equilibrium outcomes of the gale-shapley’s algorithm
for the marriage problem. Economics Letters, 36(1):25–29, 1991.
Repository Staff Only: item control page
Download Statistics
Download Statistics