On the problem of assigning PhD grants
Pages 130 - 136
Abstract
In this paper, we study the problem of assigning PhD grants. Master students apply for PhD grants on different topics and the number of available grants is limited. In this problem, students have preferences over topics they applied to and the university has preferences over possible matchings of student/topic that satisfy the limited number of grants. The particularity of this framework is the uncertainty on a student's decision to accept or reject a topic offered to him. Without using probability to model uncertainty, we study the possibility of designing protocols of exchanges between the students and the university in order to construct a matching which is as close as possible to the optimal one i.e., the best achievable matching without uncertainty.
References
[1]
D. Abraham, R. Irving, and D. Manlove. Two algorithms for the student-project allocation problem. J. of Discrete Algo., 5:73-90, 2007.
[2]
A. Abu El-Atta and M. Moussa. Student project allocation with preference lists over (student, project) pairs. In Proc. of ICCEE, pages 375-379, 2009.
[3]
E. Anshelevich and S. Sekar. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proc. of AAAI, pages 390-396, 2016.
[4]
H. Aziz, P. Biró, T. Fleiner, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari. Stable matching with uncertain pairwise preferences. In Proc. of AAMAS, pages 344-352, 2017.
[5]
H. Aziz, R. de Haan, and B. Rastegari. Pareto optimal allocation under uncertain preferences. In Proc. of IJCAI, pages 77-83, 2017.
[6]
P. Biro and J. Gudmondsson. Complexity of finding Pareto-efficient allocations of highest welfare. Working papers, 2019.
[7]
A. Blum, J. Dickerson, N. Haghtalab, A. Procaccia, T. Sandholm, and A. Sharma. Ignorance is almost bliss: Near-optimal stochastic matching with few queries. In Proc. of ACM EC, pages 325-342, 2015.
[8]
D. Bodin, J. Schmidt, R. Lemle, B. Roper, R. Goldberg, K. Hill, C. Parrish, S. Williams, A. Kuemmel, and W. Siegel. Recruitment and selection in health service psychology postdoctoral training: A review of the history and current issues. Training and Education in Professional Psychology, 12, 11 2017.
[9]
H. Chade and L. Smith. Simultaneous search. Econometrica, 74(5):1293-1307, 2006.
[10]
H. Chade, G. Lewis, and L. Smith. Student Portfolios and the College Admissions Problem. The Review of Economic Studies, 81(3):971-1002, 02 2014.
[11]
Y. Che and Y. Koh. Decentralized college admissions. J. of Poly. Eco., 124(5):1295-1338, 2016.
[12]
Y. Deng, D. Panigrahi, and B. Waggoner. The complexity of stable matchings under substitutable preferences. In Proc. of AAAI, pages 480-486, 2017.
[13]
J. Drummond and C. Boutilier. Elicitation and approximately stable matching with partial preferences. In Proc. of IJCAI, pages 97-105, 2013.
[14]
M. Ekmekci and M. Yenmez. Integrating Schools for Centralized Admissions. Working paper, 2014.
[15]
D. Gale and L. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962.
[16]
M. Gondran and M. Minoux. Graphs, dioids and semirings: new models and algorithms. Springer Science & Business Media, 2008.
[17]
M. Goto, A. Iwasaki, Y. Kawasaki, R. Kurata, Y. Yasuda, and M. Yokoo. Strategyproof matching with regional minimum and maximum quotas. Artificial Intelligence, 235:40-57, 2016.
[18]
N. Hamada, C. Hsu, R. Kurata, T. Suzuki, S. Ueda, and M. Yokoo. Strategy-proof school choice mechanisms with minimum quotas and initial endowments. Artificial Intelligence, 249:47-71, 2017.
[19]
R. Hassin and S. Rubinstein. Robust matchings. SIAM J. on Discrete Mathematics, 15:530-537, 2002.
[20]
R. Karp, U. Vazirani, and V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proc. of STOC, pages 352-358, 1990.
[21]
O. Kesten. On two kinds of manipulation for school choice problems. Eco. Theory, 51:677-693, 2012.
[22]
P. Kouvelis and G. Yu. Robust discrete optimization and its applications. Kluwer Academic Publishers Group, 1997.
[23]
D. Manlove. Algorithmics of matching under preferences. World Scientific, 2013.
[24]
M. Niederle, D. Proctor, and A. Roth. What will be needed for the new GI fellowship match to succeed? Gastroenterology, 130:218-24, 02 2006.
[25]
P. Pathak. What Really Matters in Designing School Choice Mechanisms, page 176-214. Econometric Society Monographs. Cambridge University Press, 2017.
[26]
B. Rastegari, A. Condon, N. Immorlica, and K. Leyton-Brown. Two-sided matching with partial information. In ACM EC, pages 733-750, 2013.
[27]
B. Rastegari, A. Condon, N. Immorlica, R. Irving, and K. Leyton-Brown. Reasoning about optimal stable matchings under partial information. In Proc. of ACM EC, pages 431-448, 2014.
[28]
A. Roth and X. Xing. Turnaround time and bottlenecks in market clearing: Decentralized matching in the market for clinical psychologists. J. of Political Economy, 105(2):284-329, 1997.
[29]
A. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. J. of Political Economy, 92(6):991-1016, 1984.
[30]
A. Roth. The college admissions problem is not equivalent to the marriage problem. J. of Economic Theory, 36(2):277-288, 1985.
[31]
A. Roth. What have we learned from market design? The Economic Journal, 118(527):285-310, 2008.
[32]
T. Sönmez. Can pre-arranged matches be avoided in two-sided matching markets? J. of Economic Theory, 86(1):148-156, 1999.
[33]
Vijay V. Vazirani. Approximation algorithms. Springer, 2001.
Recommendations
Identity and access management for the distribution of social grants in South Africa
SAICSIT '07: Proceedings of the 2007 annual research conference of the South African institute of computer scientists and information technologists on IT research in developing countriesIdentity and Access Management (IAM) is an emerging solution for authenticating and authorising individuals. This begins with determining an individual's 'identity' through identification and verification processes. Then it becomes vital for every ...
Speed Up PhD Completion: a Case Study in Curriculum Changes
SIGITE '17: Proceedings of the 18th Annual Conference on Information Technology EducationWhile the discipline has been changing at a furious pace of every 18 months, the average completion time for PhD in Information Technology remains stuck at 4-5 years. The long duration of the PhD program is a complex issue, since the underlying causes ...
Trust-based identity sharing for token grants
ICCSP '19: Proceedings of the 3rd International Conference on Cryptography, Security and PrivacyAuthentication and authorization are two key elements of a software application. In modern day, OAuth 2.0 framework and OpenID Connect protocol are widely adopted standards fulfilling these requirements. These protocols are implemented into ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Sony: Sony Corporation
- Huawei Technologies Co. Ltd.: Huawei Technologies Co. Ltd.
- Baidu Research: Baidu Research
- The International Joint Conferences on Artificial Intelligence, Inc. (IJCAI)
- Lenovo: Lenovo
Publisher
AAAI Press
Publication History
Published: 10 August 2019
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024