Salarinezhad, Asefeh (2021) Static and Dynamic Theoretical Studies on Improving Matching Design. PhD thesis, Concordia University.
Preview |
Text (application/pdf)
1MBSalarinezhad_PhD_F2021.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
This thesis consists of three independent papers on market design and matching theory. Each paper addresses a different matching model and environment, and together they represent a significant range of real-life matching problems which have not received enough attention.
In the first paper, we consider a new matching model to assign agents and objects on two sides of the market to each other. The new feature is that agents have consecutive acceptance intervals which are based on an exogenously given commonly known ranking of the objects. Each agent finds acceptable a consecutive set of objects with respect to this objective common ranking of the objects. Each agent has an individual preference ranking of the objects in her acceptance interval, which is determined independently of the common ranking of the objects. The main objective is to find new matching rules (algorithms) which are simpler and more efficient than the complicated conventional general algorithms for achieving a maximum matching which is Pareto-optimal, exploiting the special structure of consecutive acceptance intervals which are a common feature of many real-life matching problems.
Our main algorithm, the Block Serial Dictatorship Rule, starts with finding an ordering of agents based only on the acceptance interval structure and thus it is preference profile independent. This ordering is then used as a basis for a Serial Dictatorship which always finds a maximum Pareto-optimal matching, regardless of the agents’ preferences, for the solvable interval profiles that we characterize in the paper. These rules are also group strategy-proof.
In the second paper, I consider a matching model with minimum quotas for one side of the market. The main objective is to find algorithms which respect minimum quotas and find matchings which are both nonwasteful and fair if there exists such a matching. Otherwise, the algorithms find either fair or nonwasteful matchings. My algorithms, CNWF and FCNW (constrained nonwasteful fair and fair constrained nonwasteful), start with finding the range of possible matchings when there are minimum quotas. Then, using an innovative graph, they select the matchings which are both fair and nonwasteful, and if there do not exist such matchings, CNWF selects a constrained nonwasteful matching with a maximum degree of fairness, and FCNW selects a fair matching with a maximum degree of nonwastefulness.
Furthermore, I show that my algorithms are applicable to the case where there are different types of agents, which is a key factor for matching markets that are concerned with diversity. Compared to the existing algorithms my algorithms are unified and more intuitive.
In the third paper, I consider a novel matching model in a dynamic environment. I define a dynamic environment in which the market is open for more than one period. At the beginning of each period new agents enter the market and the matched agents leave at the end. My model is motivated by couple match-making but the results apply to other similar matching markets as well. The main objective is to find an appropriate genderneutral algorithm with nice properties. I introduce a new algorithm which is based on the DA (Deferred Acceptance) algorithm and whose structure provides an opportunity to find two-sided optimal matchings, considering the requirements and characteristics of this dynamic marriage problem.
The novel structure of my algorithm, DM (Dynamic Marriage), allows both sides to make offers simultaneously and selects a matching which is optimal for both sides in a realistic dynamic setup whenever such a matching exists, and otherwise the algorithm finds a matching without favouring either side. This property makes the matching fair in the sense that it gives both sides a fair chance. I also study the dynamic strategy-proofness of the algorithm, as well as its stability and efficiency properties.
Compared to previous algorithms that apply to the marriage problem in a static or dynamic environment, my algorithm is more realistic since it allows for realistic dynamic preferences and for real-life marriage considerations. Furthermore, it is more integrated regarding the optimality of the two sides than other algorithms and avoids some of the common issues of dynamic algorithms.
| Divisions: | Concordia University > Faculty of Arts and Science > Economics |
|---|---|
| Item Type: | Thesis (PhD) |
| Authors: | Salarinezhad, Asefeh |
| Institution: | Concordia University |
| Degree Name: | Ph. D. |
| Program: | Economics |
| Date: | 14 June 2021 |
| Thesis Supervisor(s): | Pápai, Szilvia |
| Keywords: | Mechanism Design, Matching Theory, Pareto-optimal, Maximum Matching, Minimum Quotas, Fairness, Nonwastefulness, Dynamic Matching, Marriage Market |
| ID Code: | 988585 |
| Deposited By: | ASEFEH SALARINEZHAD |
| Deposited On: | 30 Nov 2021 20:54 |
| Last Modified: | 01 Aug 2023 00:00 |
References:
[1] Abdulkadiroˇglu, A., Pathak, P. A., and Roth, A. E. The New York City high school match. American Economic Review, Papers and Proceedings, 95 (2):364–367, 2005.[2] Abdulkadiroˇglu, A. and Sönmez, T. House allocation with existing tenants. Journal of Economic Theory, 88(2):233–260, 1999.
[3] Abdulkadiroˇglu, A. and Sönmez, T. School choice: A mechanism design approach. American Economic Review, 93(3):729–747, 2003.
[4] Afacan, M. O., Bó, I., and Turhan B. Assignment maximization. Working paper arXiv e-prints, arXiv-2012, 2020.
[5] Andersson, T. and Ehlers, L. Assigning refugees to landlords in sweden: Efficient, stable, and maximum matchings. The Scandinavian Journal of Economics, 122(3):937–965, 2020.
[6] Andersson, T., Ehlers, L., and Martinello, A. Dynamic refugee matching. Cahier de recherche, 2018-10.
[7] Grandoni, F. andKrysta, P. and Leonardi, S. andVentre, C. Utilitarian mechanism design for multiobjective optimization. SIAM Journal on Computing, 43(4):1263–1290, 2014.
[8] Arnosti, N. and Shi, P. Design of lotteries and wait-lists for affordable housing allocation. Management Science, 2020.
[9] Balinski, M. and Sönmez, T. Tale of two mechanisms: student placement. Journal of Economic theory, 84(1):73–94, 1999.
[10] Biró, P., Fleiner, T., Irving, R. W., and Manlove, D. F. The college admissions problem with lower and common quotas. Theoretical Computer Science 411, (34-36):3136–3153, 2010.
[11] Bloch, F. and Cantala, D. Dynamic assignment of objects to queuing agents. American Economic Journal: Microeconomics, 9(1):88–122, 2017.
[12] Braun, S., Dwenger, N., Kübler, D., and Westkamp, A. Implementing quotas in university admissions: An experimental analysis. Games and Economic Behavior, 85:232–251, 2014.
[13] Cantala, D. and Pápai, S. Reasonably and securely stable matching. Tech. rep, 2014.
[14] Cormen, T. H., Leiserson, C.E., Rivest, R. L., and Stein, C. Section 26.2: The ford–fulkerson method. Introduction to Algorithms (Second ed.), ISBN 0-262-03293-7:651–664, 2001.
[15] Damiano, E. and Lam, R. Stability in dynamic matching markets. Games and Economic Behavior, 52(1):34–53, 2005.
[16] Doval, L. Dynamically stable matching. Available at SSRN 3411717, 2019.
[17] Du, S. and Livne, Y. Rigidity of transfers and unraveling in matching markets. Available at SSRN 2203910, 2014.
[18] Dubins, L. E. and Freedman, D. Machiavelli and the Gale-Shapley algorithm. Mathematical Monthly, 88(7):485–494, 1981.
[19] Dworczak, P. Deferred acceptance with compensation chains. Operations Research, 69(2):456–468, 2021.
[20] Ehlers, L., Hafalir, I. E., Yenmez, M. B., and Yildirim, M. A. School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory, (153):648–683, 2014.
[21] Erdil, A. and Ergin, H. I. What’s the matter with tie-breaking? improving efficiency in school choice. American Economic Review, 98(3):669–689, 2008.
[22] Ergin, H. I. Efficient resource allocation on the basis of priorities. Econometrica, 70(6):2489–2497, 2002.
[23] Fragiadakis, D. and Troyan, P. Improving matching under hard distributional constraints. Theoretical Economics, (12):863–908, 2017.
[24] Fragiadakis, D., Troyan, P., Iwasaki, A., Ueda, S., and Yokoo, M. Strategyproof matching with minimum quotas. ACM Transactions on Economics and Computation, 4(1):Article 6, 2015.
[25] Gale, D. and Shapley, L. S. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962.
[26] Hafalir, I. E., Yenmez, M. B., and Yildirim, M. A. Effective affirmative action in school choice. Theoretical Economics, 8(2):325–363, 2013.
[27] Hall, P. On representatives of subsets. Journal of the London Mathematical Society, 1:26–30, 1935.
[28] Hamada, K., Iwama, K., and Miyazaki, S. The hospitals/residents problem with lower quotas. Algorithmica, 74(1):440–465, 2016.
[29] Hatfield, J. W. and Milgrom, P. R. Matching with contracts. American Economic Review, 95(4):913–935, 2005.
[30] Herrnstein, R. J. Relative and absolute strength of response as a function of frequency of reinforcement. Journal of the Experimental Analysis of Behavior, 4(3):267, 1961.
[31] Hopcroft, J. E. and Karp, R. M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2:225–231, 1973.
[32] Irving, R. W., Kavitha, T., Mehlhorn, K., Michail, D., and Paluch, K. Rank-maximal matchings. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms, pages 68–75, 2006.
[33] Kahn, A. B. Topological sorting of large networks. Communications of the ACM, 5(11):558–562, 1962.
[34] Kamada, Y. and Kojima, F. Efficient matching under distributional constraints: Theory and applications. American Economic Review, 105(1):67–99, 2015.
[35] Kamada, Y. and Kojima, F. Fair matching under constraints: Theory and applications. Review of Economic Studies, 2018.
[36] Kawagoe, T. and T. Matsubae. Matching with minimal quota: A case study of the japanese university student-supervisor assignment. Available at SSRN 3429626, 2017.
[37] Kelso Jr, A. S. and Crawford, V. P. Job matching, coalition formation, and gross substitutes. Econometrica, pages 1483–1504, 1982.
[38] Kesten, O. Student placement to public schools in the us: Two new solutions. Working paper, University of Rochester, 2004.
[39] Kesten, O. On two competing mechanisms for priority-based allocation problems. Journal of Economic Theory, 127(1):155–171, 2006.
[40] Kesten, O. School choice with consent. The Quarterly Journal of Economics, 125:3, 2010.
[41] Klijn, F., Pais, J., and Vorsatz, M. Static versus dynamic deferred acceptance in school choice: Theory and experiment. Games and Economic Behavior, 113:147–163, 2019.
[42] Kojima, F. School choice: Impossibilities for affirmative action. Games and Economic Behavior, 75(2):685–693, 2012.
[43] Kominers, S. D. and Sönmez, T. Matching with slot-specific priorities: Theory. Theoretical Economics, 11(2):683–710, 2016.
[44] Kotowski, M. H. A perfectly robust approach to multiperiod matching problems. 2019.
[45] Kurino, M. Credibility, efficiency, and stability: A theory of dynamic matching markets. The Japanese Economic Review, 71(1):135–165, 2020.
[46] Kuvalekar, A. A fair procedure in a marriage market. Available at SSRN 2688630, 2014.
[47] Li, S. Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257–87, 2017.
[48] Liu, C. Stability in repeated matching markets. arXiv preprint arXiv:2007, 03794, 2020.
[49] Martínez, R., Massó, J., Neme, A., and Oviedo, J. Single agents and the set of manyto-one stable matchings. Journal of Economic Theory, 91(1):91–105, 2000.
[50] Morrill, T. Making efficient school assignment fairer. Working paper, North Carolina State University.[1311], 2013.
[51] Pápai, S. Strategyproof assignment by hierarchical exchange. Econometrica, 63(6):1403–1433, 2000.
[52] Pápai, S. Strategyproof and nonbossy multiple assignments. Journal of Public Economic Theory, 3:257–271, 2001.
[53] Pápai, S. Matching with minimal priority rights. Working paper, Concordia University, 2013.
[54] Pereyra, J. S. A dynamic school choice model. Games and Economic Behavior, 80:100–114, 2013.
[55] Pycia, M. and Ünver, M. U. Incentive compatible allocation and exchange of discrete resources. Theoretical Economics, 12:287–329, 2017.
[56] Romero-Medina, A. Equitable selection in bilateral matching markets. Theory and Decision, 58(3):305–324, 2005.
[57] Romero-Medina, A. and Kuvalekar, A. V. A fair procedure in a marriage market. Universidad Carlos III de Madrid. Departamento de Economía, (31711), 2021.
[58] Roth, A. E. The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4):617–628, 1982.
[59] Roth, A. E. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6):991–1016, 1984.
[60] Roth, A. E. On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica, 1:425–427, 1986.
[61] Roth, A. E. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 70:1341–1378, 2002.
[62] Roth, A. E. Who gets what—and why: The new economics of matchmaking and market design. Houghton Mifflin Harcourt, 2015.
[63] Roth, A. E. and Peranson, E. The redesign of the matching market for American physicians: Some engineering aspects of economic design. American Economic Review, 89(4):748–780, 1999.
[64] Roth, A. E. and Sotomayor, M. Two-sided matching. Handbook of game theory with economic applications, 1:485–541, 1992.
[65] Roth, A. E., Sönmez, T., and Ünver, M. U. Kidney exchange. The Quarterly Journal of Economics, 119(2):457–4881, 2004.
[66] Satterthwaite M. and Sonnenschein H. Strategy-proof allocation mechanism at differentiable points. Review of Economic Studies, XL VIII:587–597, 1981.
[67] Shapley, L. S. and Scarf, H. On cores and indivisibility. Journal of Mathematical Economics, 1(23), 1974.
[68] Shapley, L. S. and Shubik, M. The assignment game I: The core. International Journal of Game Theory, 1(1):111–130, 1971.
[69] Svensson, L-G. Queue allocation of indivisible goods. Social Choice and Welfare, 11:323–330, 1994.
[70] Svensson, L-G. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16:557–567, 1999.
[71] Teo, C. P. and Sethuraman, J. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 23(4):874–891, 1998.
[72] Tomoeda, K. Finding a stable matching under type-specific minimum quotas. Journal of Economic Theory 176, page 81–117, 2017.
[73] Troyan, P. and Morrill, T. Obvious manipulations. Journal of Economic Theory, 85:104970, 2020.
[74] Westkamp, A. An analysis of the german university admissions system. Economic Theory, 53(3):561–589, 2013.
[75] Yahiro, K., Barrot, N. Zhang, Y., and Yokoo, M. Strategyproof and fair matching mechanism for ratio constraints. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 53(3):59–67, 2018.
Repository Staff Only: item control page
Download Statistics
Download Statistics