 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
 |
Matching schemes in Europe
References: M. Baïou and M. Balinski. Admissions and recruitment. American Mathematical Monthly, 110(5):386-399, 2003. M. Baïou and M. Balinski. Student admissions and faculty recruitment. Theoretical Computer Science, 322:245-265, 2004.
References: S. Braun, N. Dwenger. Success in the University Admission Process in Germany: Regional Provenance Matters. DIW Berlin Discussion Paper, German Institute for Economic Research, Berlin, 2008. S. Braun, N. Dwenger, D. Kübler. Telling the Truth May Not Pay Off: An Empirical Study of Centralised University Admissions in Germany. SBF 759 Discussion Paper, Hunbold University, Berlin, 2007. A. Westkamp. An analysis of the German university admissions system, working paper (2010)
Short description of the program: The program was established in 2000, the number of applicants was 116672 in 2007. The program uses the original model and algorithm of Gale and Shapley (the applicant-oriented version).
Description was given by Péter Biró.
Reference:P. Biró. Student Admissions in Hungary as Gale and Shapley Envisaged. Technical Report. Dept of Computing Science, University of Glasgow, TR-2008-291.
Further information: a recent survey in Hungarian
Description was given by Péter Biró.
Reference:
Further information: a recent survey in Hungarian
Webpage: National Higher Education Information Centre
Short description of the program: The program was established in 1985, the number of applicants is between 100000 and 170000 every year. The students apply for studies rather than to institutions (but here we refer to the studies as colleges for simplicity). The program uses a special Gale-Shapley algorithm, the college-oriented version was replaced with the applicant-oriented version in 2007. The main special features of the program are the following:
1. Ties can occur, since students are ranked according to their scores, and two students may have the same score at a particular college. The attempted solution is a so-called stable score-limit, which satisfies the condition that no overdemanded college can decrease its score-limit without violating its quota. See related results in [1].
2. Beside the upper quotas some colleges may have lower quotas as well. This feature is studied in [2].
3. Some sets of colleges may have common upper quotas. This feature is studied in [2].
4. Teachers can apply for pair of studies, which is like having couples in the Hospitals Residents problem.
Description was given by Péter Biró.
Another description of the program in Hungarian and further links: Felsőoktatási MŰHELY
References:[1] P. Biró. Student Admissions in Hungary as Gale and Shapley Envisaged. Technical Report. Dept of Computing Science, University of Glasgow, TR-2008-291. [2] P. Biró, T.Fleiner, R.W. Irving and D.F. Manlove. The College Admissions problem with lower and common quotas. Theoretical Computer Science 411, 3136-3153 (2010).
The full version of this paper is available as Technical Report no. TR-2009-303 of the Computing Science Department of Glasgow University, 2009. [3] L.Á. Kóczy, A magyarországi felvételi rendszerek sajátosságai. Közgazdasági Szemle 57:(2) pp. 142-164. (2010), in Hungarian.
Short description of the program: The program was established in 1985, the number of applicants is between 100000 and 170000 every year. The students apply for studies rather than to institutions (but here we refer to the studies as colleges for simplicity). The program uses a special Gale-Shapley algorithm, the college-oriented version was replaced with the applicant-oriented version in 2007. The main special features of the program are the following:
1. Ties can occur, since students are ranked according to their scores, and two students may have the same score at a particular college. The attempted solution is a so-called stable score-limit, which satisfies the condition that no overdemanded college can decrease its score-limit without violating its quota. See related results in [1].
2. Beside the upper quotas some colleges may have lower quotas as well. This feature is studied in [2].
3. Some sets of colleges may have common upper quotas. This feature is studied in [2].
4. Teachers can apply for pair of studies, which is like having couples in the Hospitals Residents problem.
Description was given by Péter Biró.
Another description of the program in Hungarian and further links: Felsőoktatási MŰHELY
References:
The full version of this paper is available as Technical Report no. TR-2009-303 of the Computing Science Department of Glasgow University, 2009.
Reference: N. Perach, J. Polak, U.G. Rothblum. A case study on the assignment of students to dormitories using a stable matching model with an entrance criterion. International Journal of Game Theory, 36 p:519-535.
References: Karin M. Keizer, Marry de Klerk, Bernadette J.J.M. Haase-Kromwijk and Willern Weimar. The Dutch Algorithm for Allocation in Living Donor Kidney Exchange. Transplantation Proceedings, 37:589-591, 2005. Marry de Klerk, Karin M. Keizer, Frans H. J. Claas, Marian Witvliet, Bernadette J.J.M. Haase-Kromwijk and Willern Weimar. The Dutch National Living Donor Kidney Exchange Program. American Journal of Transplantation, 5:2302-2305, 2005.
Reference: A. Romero-Medina. Implementation of stable solutions in a restricted matching market. Review of Economic Design, 3:137-147, 1998.
A description in Spanish: Programa National De Donatión Renal Cruzada en Espana
References: M. Balinski, T. Sonmez. A Tale of Two Mechanisms: Student Placement. Journal of Economic Theory, 84:73-94, 1999. M. Baïou and M. Balinski. Admissions and recruitment. American Mathematical Monthly, 110(5):386-399, 2003. M. Baiou and M. Balinski. Student admissions and faculty recruitment. Theoretical Computer Science, 322:245-265, 2004.
Webpage: Scottish Foundation Allocation Scheme
Short description of the program:
The four main medical schools in Scotland (Glasgow, Edinburgh, Aberdeen and Dundee) produce around 800 graduates per year. The allocation of these graduates to their first positions has been carried out by a centralized matching scheme since 2000. Initially, when the allocation was to Pre-Registration House Officer posts, or PRHOs, the scheme was known as SPA (Scottish PRHO Allocations). SPA ran for six years, but since 2006 the allocation has been to so-called Foundation Programmes, and the scheme has been changed and renamed SFAS (Scottish Foundation Allocation Scheme).
SPA (2000 -- 2005)
In the SPA scheme, the requirement was that each applicant be allocated to two six-month positions, a medical post and a surgical post (except for a small number of applicants who required only one of these.) Applicants were required to rank their preferred n medical posts and preferred n surgical posts separately, in strict order of preference, and these rankings were submitted to the central body. (The value of n varied from year to year, in the range from 3 to 6.) Applicants were also invited to indicate whether they wished their medical post or their surgical post to come first chronologically (their so-called seasonal preference). Consultants in charge of each medical and each surgical unit were then sent the names of those applicants who had listed them, and were in turn required to submit strictly ranked preferences over their applicants, together with the number of posts on offer. The matching program was based primarily on the classical Gale-Shapley applicant-oriented algorithm. This was used to find the applicant-optimal stable matchings to medical and surgical posts separately. Following this, the two matchings were combined , using a network-flow based approach, to ensure that each candidate's allocation was to two different six-month periods, and that no unit's capacity was exceeded during any six-month period, at the same time maximizing the number of applicants whose seasonal preference was satisfied. Technical details of the algorithm appear in the webpage. Typically some 90-95% of positions were allocated by this first round of matching. Subsequently, details of unfilled positions were circulated to unmatched or partially matched applicants, and these applicants were matched in a second, somewhat ad hoc, round.
SFAS (2006 -- )
The current arrangements for medical training involve the allocation of each graduate to an integrated two-year Foundation Programme, which involves a range of medical disciplines. From the point of view of the matching algorithm, all that is required is an allocation of each applicant to (at most) one programme, respecting the capacities of the programmes. So, on the surface this appears to be an instance of the classical Hospitals-Residents problem. However, two factors combined to add extra interest to this process.
Firstly, as a matter of policy, programme directors are no longer asked to rank their applicants in order of preference. Instead, applicants are ranked in a so-called master list, in order of score – each applicant has a numerical score allocated partly on the basis of academic performance and partly as a result of the assessment of their application form. (Application forms are complex, and require detailed responses to challenging questions.) The range of possible scores (approximately 40 – 100) is much smaller than the number of applicants (around 750 each year), so there are inevitably ties of substantial length in the master list. The individual programme preference lists are constructed from the master list, so these also typically contain ties. It turns out that, even in the presence of a master list, random or arbitrary tie-breaking can lead to variations in the size of the stable matching produced by the Gale-Shapley algorithm. Finding a maximum size stable matching in these circumstances is known to be an NP-hard problem [2].) Discussion of a range of heuristics that are applicable in this context, together with an empirical evaluation of their performance relative to random tie-breaking, appears in [3].
Secondly, pairs of applicants to SFAS may declare themselves to be a couple, with a view to being assigned to geographically compatible positions. Such applicants are required to submit individual preference lists, just like single applicants. These are then combined in a pre-specified way to form a joint preference list for the couple, omitting any incompatible allocations. (A complete compatibility matrix for all pairs of programmes is available to applicants.) Under a natural extension of the stability concept, it is well known that a stable matching may not exist in the presence of couples, and that it is an NP-complete problem to determine whether such a matching exists. These results continue to hold in the presence of a master list [4]. The current SFAS program uses a heuristic that attempts to find a stable matching that allocates as many applicants as possible. Simulations reported in [4] suggest that, as long as the proportion of couples is relatively low, it is highly likely that a stable matching can be found, and this has so far been borne out in practice.
Description was given by Robert W. Irving.
References:[1] Robert W. Irving. Matching medical students to pairs of hospitals: a new variation on a well-known theme, in Proceedings of ESA'98, the Sixth Annual European Symposium on Algorithms, Venice Italy, 1998, Lecture Notes in Computer Science, vol. 1461 (Springer 1998), pp. 381-392. [2] R.W. Irving, D.F. Manlove and S. Scott. The stable marriage problem with master preference lists, Discrete Applied Mathematics vol. 156 (2008), pp. 2959-2977. Postprint. [3] R. W. Irving and D. F. Manlove, Finding large stable matchings. ACM Journal of Experimental Algorithmics vol. 14 (2009), section 1 article no. 2, 30 pages. Postprint. P. Biro, R.W. Irving and I. Schlotter, Stable matching with couples: Theory and Practice, Technical Report. Dept of Computing Science, University of Glasgow, TR-2011-324. To appear in ACM Journal of Experimental Algorithmics.
Short description of the program:
The four main medical schools in Scotland (Glasgow, Edinburgh, Aberdeen and Dundee) produce around 800 graduates per year. The allocation of these graduates to their first positions has been carried out by a centralized matching scheme since 2000. Initially, when the allocation was to Pre-Registration House Officer posts, or PRHOs, the scheme was known as SPA (Scottish PRHO Allocations). SPA ran for six years, but since 2006 the allocation has been to so-called Foundation Programmes, and the scheme has been changed and renamed SFAS (Scottish Foundation Allocation Scheme).
SPA (2000 -- 2005)
In the SPA scheme, the requirement was that each applicant be allocated to two six-month positions, a medical post and a surgical post (except for a small number of applicants who required only one of these.) Applicants were required to rank their preferred n medical posts and preferred n surgical posts separately, in strict order of preference, and these rankings were submitted to the central body. (The value of n varied from year to year, in the range from 3 to 6.) Applicants were also invited to indicate whether they wished their medical post or their surgical post to come first chronologically (their so-called seasonal preference). Consultants in charge of each medical and each surgical unit were then sent the names of those applicants who had listed them, and were in turn required to submit strictly ranked preferences over their applicants, together with the number of posts on offer. The matching program was based primarily on the classical Gale-Shapley applicant-oriented algorithm. This was used to find the applicant-optimal stable matchings to medical and surgical posts separately. Following this, the two matchings were combined , using a network-flow based approach, to ensure that each candidate's allocation was to two different six-month periods, and that no unit's capacity was exceeded during any six-month period, at the same time maximizing the number of applicants whose seasonal preference was satisfied. Technical details of the algorithm appear in the webpage. Typically some 90-95% of positions were allocated by this first round of matching. Subsequently, details of unfilled positions were circulated to unmatched or partially matched applicants, and these applicants were matched in a second, somewhat ad hoc, round.
SFAS (2006 -- )
The current arrangements for medical training involve the allocation of each graduate to an integrated two-year Foundation Programme, which involves a range of medical disciplines. From the point of view of the matching algorithm, all that is required is an allocation of each applicant to (at most) one programme, respecting the capacities of the programmes. So, on the surface this appears to be an instance of the classical Hospitals-Residents problem. However, two factors combined to add extra interest to this process.
Firstly, as a matter of policy, programme directors are no longer asked to rank their applicants in order of preference. Instead, applicants are ranked in a so-called master list, in order of score – each applicant has a numerical score allocated partly on the basis of academic performance and partly as a result of the assessment of their application form. (Application forms are complex, and require detailed responses to challenging questions.) The range of possible scores (approximately 40 – 100) is much smaller than the number of applicants (around 750 each year), so there are inevitably ties of substantial length in the master list. The individual programme preference lists are constructed from the master list, so these also typically contain ties. It turns out that, even in the presence of a master list, random or arbitrary tie-breaking can lead to variations in the size of the stable matching produced by the Gale-Shapley algorithm. Finding a maximum size stable matching in these circumstances is known to be an NP-hard problem [2].) Discussion of a range of heuristics that are applicable in this context, together with an empirical evaluation of their performance relative to random tie-breaking, appears in [3].
Secondly, pairs of applicants to SFAS may declare themselves to be a couple, with a view to being assigned to geographically compatible positions. Such applicants are required to submit individual preference lists, just like single applicants. These are then combined in a pre-specified way to form a joint preference list for the couple, omitting any incompatible allocations. (A complete compatibility matrix for all pairs of programmes is available to applicants.) Under a natural extension of the stability concept, it is well known that a stable matching may not exist in the presence of couples, and that it is an NP-complete problem to determine whether such a matching exists. These results continue to hold in the presence of a master list [4]. The current SFAS program uses a heuristic that attempts to find a stable matching that allocates as many applicants as possible. Simulations reported in [4] suggest that, as long as the proportion of couples is relatively low, it is highly likely that a stable matching can be found, and this has so far been borne out in practice.
Description was given by Robert W. Irving.
References:
Webpage: Teacher Induction Scheme
Webpage: National Matching Scheme for Paired and Pooled (kidney) Donation
Short description of the program: NHS Blood and Transplant run the National Matching Scheme for Paired and Pooled (kidney) Donation in the UK. They maintain a database of incompatible (donor,patient) pairs who would be willing to participate in a live-donor kidney exchange with one or more other (donor,patient) pairs. Every three months a matching run is carried out in an attempt to construct an optimal set of exchanges. At present paired (2-way) and pooled (3-way) exchanges are sought, though an exchange involving 3 or more couples has yet to be carried out in the UK. The term "optimal" refers to the fact that the overriding constraint is to maximise the number of transplants that can be carried out, and subject to this, to maximise the overall score of the exchange. The score of an exchange is based on the points system that NHS Blood and Transplant employs for couples involved in the process - see the above webpage for more details. A number of paired kidney donations have been carried out in the UK as a result of this matching scheme, and these have generated much interest in the media - see an article from The Guardian, for example.
Description was given by David F. Manlove.
Recent news: A BBC article and the corresponding video on the first successful 3-way exchange in the UK. A report by the Human Tissue Authority, and a summary about the involvement of the Glasgow algorithm and complexity research group.
References:Johnson, Rachel J.; Allen, Joanne E.; Fuggle, Susan V.; Bradley, J Andrew; Rudge, Chris; on behalf of the Kidney Advisory Group. Early Experience of Paired Living Kidney Donation in the United Kingdom. Transplantation, 86(12) : 1672-1677, 2008. P. Biró, D.F. Manlove and Romeo Rizzi. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1 (4) : 499-517, 2009. An earlier version of this paper is available as Technical Report no. TR-2009-298, Department of Computing Science, University of Glasgow, 2009. D.F. Manlove and G. O'Malley. Paired and altruistic kidney donation in the UK: Algorithms and experimentation. In Proceedings of SEA 2012, vol. 7276 of LNCS, pp 271-282. Postprint.
Short description of the program: NHS Blood and Transplant run the National Matching Scheme for Paired and Pooled (kidney) Donation in the UK. They maintain a database of incompatible (donor,patient) pairs who would be willing to participate in a live-donor kidney exchange with one or more other (donor,patient) pairs. Every three months a matching run is carried out in an attempt to construct an optimal set of exchanges. At present paired (2-way) and pooled (3-way) exchanges are sought, though an exchange involving 3 or more couples has yet to be carried out in the UK. The term "optimal" refers to the fact that the overriding constraint is to maximise the number of transplants that can be carried out, and subject to this, to maximise the overall score of the exchange. The score of an exchange is based on the points system that NHS Blood and Transplant employs for couples involved in the process - see the above webpage for more details. A number of paired kidney donations have been carried out in the UK as a result of this matching scheme, and these have generated much interest in the media - see an article from The Guardian, for example.
Description was given by David F. Manlove.
Recent news: A BBC article and the corresponding video on the first successful 3-way exchange in the UK. A report by the Human Tissue Authority, and a summary about the involvement of the Glasgow algorithm and complexity research group.
References:
Matching schemes in America
See more about school choice mechanisms at Al Roth's webpage!
New York City high schools
References:A. Abdulkadiroglu, P.A. Pathak and A.E. Roth The New York City High School Match. American Economic Review, 84, September, 2004, 992-1044. A. Abdulkadiroglu, P.A. Pathak and A.E. Roth Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match. November, 2008 (to appear in American Economic Review).
Boston high schools
References:A. Abdulkadiroglu, P.A. Pathak, A.E. Roth and Tayfun Sonmez The Boston Public School Match. American Economic Review, Papers and Proceedings, 95,2, May, 2005, 368-371. A. Abdulkadiroglu, P.A. Pathak, A.E. Roth and Tajfun Sonmez Changing the Boston School Choice Mechanism. January, 2006, this revision May 2006.
New York City high schools
References:
Boston high schools
References:
Other interesting links:
A non-profit institute has been established recently: The Institute for Innovation in Public School Choice
A non-profit institute has been established recently: The Institute for Innovation in Public School Choice
See more about medical and health care labor markets at Al Roth's webpage!
Reference:Alvin E. Roth. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92, 1984, 991-1016.
Alvin E. Roth. Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. International Journal of Game Theory, Special Issue in Honor of David Gale on his 85th birthday, 36, March, 2008, 537-569.
A company that provides matching services: National Matching Services Inc.
Reference:
A recent summary with a list of further applications (on page 27):
A company that provides matching services: National Matching Services Inc.
See more about kidney exchange at Al Roth's webpage!
Reference:Alvin E. Roth, Tayfun Sonmez and M. Utku Unver. A Kidney Exchange Clearinghouse in New England. American Economic Review, Papers and Proceedings, 95,2, May, 2005, 376-380.
Alliance for Paired Donation Paired Donation Network
Reference:
Other programs:
References: Melissa M. Short. Analysis of the Current Navy Enlisted Detailing Process. Masters' Thesis, Naval Postgraduate School Monterey CA, Dec 2000. Paul A. Robards. Applying Two-Sided Matching Processes to the United States Navy Enlisted Assignment Process. Masters' Thesis, Naval Postgraduate School Monterey CA, March, 2001. W. Yang, J.A. Giampapa and K. Sycaratech. Two-Sided Matching for the U.S. Navy Detailing Process with Market Complication. report CMU-RI-TR-03-49, Robotics Institute, Carnegie Mellon University, November, 2003.
Webpage: Canadian Resident Matching Service
At the wikipedia: Canadian Resident Matching Service
At the wikipedia: Canadian Resident Matching Service
Matching schemes in Asia
Webpage: Japanese Resident Matching Program
Reference:Yuichiro Kamada, Fuhito Kojima. Improving Efficiency in Matching Markets with Regional Caps: The Case of the Japan Residency Matching Program working paper(2010)
Reference:
Reference: Chung-Piaw Teo, Jay Sethuraman and Wee-Peng Tan. Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications. Management Science 47(9), 2001, p:1252--1267.
Worldwide applications
AdWords auction
Description: at the Google website, with a talk speach by Hal Varian
Reference:Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, Martin Pál. General Auction Mechanism for Search Advertising. In proceedings of WWW2009: The 18th International World Wide Web Conference.
TV ad auction
Reference:N. Nisan et al. Google's auction for TV ads Invited talk in EURO 2009, ICALP 2009, SAGT 2009, SODA 2010, and COLT 2010. Paper appeared in proceedings of ICALP 2009. Here are the talk slides (ppt).
Description: at the Google website, with a talk speach by Hal Varian
Reference:
TV ad auction
Reference:
 |
Intézményünk országos és nemzetközi hálózati kapcsolatát az NIIF program biztosítja |
 |
MTA Magyar Tudományos Akadémia |
Utolsó módosítás: 2016. 05. 02. |