Summer School of DeCAn. Day 1

Speaker: Peter Biro (Research fellow, Hungarian Academy of Sciences, Hungary)
Title: Computational aspect of matching problems under preferences

Abstract

School choice, college admissions, entry-labour markets, and organ exchanges are all examples for matching markets, where money does not necessary has a role. The task of a market designer is to set rules and construct allocation mechanisms so that the resulting solution is fair and in some sense optimal with regard to the true preferences of the participants. Since the collection of the preferences became simple by web-based applications, it is now up to the computational tools to obtain the desired solutions in the large scale centralised matching schemes that have been established in the past decades across the world. However, even just one special feature of the application can make the underlying matching problem computationally hard. In this talk we will present some examples for such challenging computational problems which are motivated by real applications, such as the Scottish resident allocation program, the Hungarian higher education scheme and the UK kidney exchange program.

Besides discussing the computational complexity of these problems, we also present different type of  solutions methods, some of which having been implemented and used in the applications.

Additional materials:

 Slides (PDF, 5.88 Мб)

 

References

P. Biro, T. Fleiner, R.W. Irving and D.F. Manlove, The College Admissions problem with lower and common quotas. Theoretical Computer Science, 411 (2010) pp:3136-3153

P. Biro and S. Kiselgof, College admissions with stable score-limits. Central European Journal of Operations Research, forthcoming (2015)

P. Biro, D.F. Manlove and R. Rizzi, Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1/4 (2009) pp:499-517

P. Biro and I. McBride, Integer programming methods for special college admissions problems. In Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA), volume 8881 of Lecture Notes in Computer Science, Springer-Verlag, (2014) pp:429-443

P. Biro and E.J. McDermid, Three-sided stable matchings with cyclic preferences. Algorithmica, 58 (2010) pp:5-18

P. Biro and E.J. McDermid, Matching with sizes (or scheduling with processing set restrictions). Discrete Applied Mathematics, 164(1), (2014) pp:61-67