A modified deferred acceptance algorithm for many-to-one matching markets with externalities among firms.

*(English)*Zbl 1297.91096Summary: We consider a many-to-one matching market with externalities among firms where each firm’s preferences satisfy substitutability, increasing choice and no external effect by unchosen workers, which are defined by the author [J. Math. Econ. 48, No. 1, 14–20 (2012; Zbl 1236.91096)]. We first illustrate that a sequential version of the deferred acceptance (DA) algorithm with worker-proposing may not find a worker-optimal quasi stable matching. Then, we provide a modified DA algorithm in which (i) each worker simultaneously proposes to his most preferred firm that has not rejected him and (ii) each firm chooses its acceptable workers from the cumulative set of workers who have ever proposed to it, assuming that the other workers proposing to its rival firms are hired. We show that this algorithm finds a worker-optimal quasi stable matching. We also show that this algorithm can be generalized into a fixed point algorithm.

##### MSC:

91B40 | Labor market, contracts (MSC2010) |

91B68 | Matching models |

##### Keywords:

many-to-one matching market; externalities; stability; deferred acceptance algorithm; fixed point algorithm
Full Text:
DOI

##### References:

[1] | Adachi, H., On a characterization of stable matchings, Econom. Lett., 68, 43-49, (2000) · Zbl 0953.91048 |

[2] | Bando, K., Many-to-one matching with externalities among firms, J. Math. Econom., 48, 14-20, (2012) · Zbl 1236.91096 |

[3] | Blair, C., The lattice structure of the set of stable matchings with multiple partners, Math. Oper. Res., 13, 619-628, (1988) · Zbl 0664.90075 |

[4] | Blum, Y.; Roth, A. E.; Rothblum, U., Vacancy chains and equilibration in senior-level labor markets, J. Econom. Theory, 76, 362-411, (1997) · Zbl 0892.90047 |

[5] | Dubins, L. E.; Freedman, D. A., Machiavelli and the gale-Shapley algorithm, Amer. Math. Monthly, 88, 485-494, (1981) · Zbl 0449.92024 |

[6] | Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15, (1962) · Zbl 0109.24403 |

[7] | Echenique, F.; Oviedo, J., Core many-to-one matchings by fixed-point methods, J. Econom. Theory, 115, 358-376, (2004) · Zbl 1094.91049 |

[8] | Echenique, F.; Oviedo, J., A theory of stability in many-to-many matching markets, Theoret. Econom., 1, 233-273, (2006) |

[9] | Echenique, F.; Yenmez, B., A solution to matching with preferences over colleagues, Games Econom. Behav., 59, 46-71, (2007) · Zbl 1271.91084 |

[10] | Fleiner, T., A fixed point approach to stable matchings and some applications, Math. Oper. Res., 28, 103-126, (2003) · Zbl 1082.90096 |

[11] | Hafalir, I. E., Stability of marriage with externalities, Internat. J. Game Theory, 37, 353-369, (2008) · Zbl 1153.91689 |

[12] | Hatfield, J. W.; Milgrom, P., Matching with contracts, Amer. Econom. Rev., 95, 913-935, (2005) |

[13] | Hatfield, J. W; Kojima, F., Substitutes and stability for matching with contracts, J. Econom. Theory, 145, 1704-1723, (2010) · Zbl 1245.91068 |

[14] | Kelso, A.; Crawford, V., Job matching, coalition formation, and Gross substitutes, Econometrica, 50, 1483-1504, (1982) · Zbl 0503.90019 |

[15] | Mumcu, A.; Saglam, I., Stable one-to-one matchings with externalities, Math. Social Sci., 60, 154-159, (2010) · Zbl 1232.91534 |

[16] | Ostrovsky, M., Stability in supply chain networks, Amer. Econom. Rev., 98, 897-923, (2008) |

[17] | Roth, A. E., Stability and polarization of interests in job matching, Econometrica, 52, 47-58, (1984) · Zbl 0526.90012 |

[18] | Roth, A. E., The economics of matching: stability and incentives, Math. Oper. Res., 7, 617-628, (1982) · Zbl 0496.90008 |

[19] | Roth, A. E.; Sotomayor, M. A.O., Two-sided matching: A study in game theoretic modeling and analysis, (1990), Cambridge Univ. Press Cambridge, UK · Zbl 0726.90003 |

[20] | Sasaki, H.; Toda, M., Two-sided matching problems with externalities, J. Econom. Theory, 70, 93-108, (1996) · Zbl 0859.90011 |

[21] | Sotomayor, M., A non-constructive elementary proof of the existence of stable marriage, Games Econom. Behav., 13, 135-137, (1996) · Zbl 0853.90003 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.