Летняя школа МЛАВР. День 3
Докладчик: Peter Biro (Research fellow, Hungarian Academy of Sciences, Hungary)
Тема доклада: Game theoretical aspects of matching problems under preferences
Certain stable matching problems with and without payments can be interpreted as TU and NTU games, where the core corresponds to the set of stable solutions. Scarf's lemma provides a fractional solution for NTU-games, even when players have capacities and a cooperation may require different contributions from the players. This result can serve as the base of a heuristic for solving challenging matching problems, such as the problem of allocating residents in the presence of couples, as we demonstrate. Regarding the models with payments, we show that graph theoretical results can be used to compute stable solutions efficiently in matching games and also in the case where players may have capacities.
![]() | ![]() | ![]() |
Презентация (PDF, 8.54 Мб)
Список рекомендуемой литературы:
- P. Biro, M. Bomhoff, P.A. Golovach, W. Kern and D. Paulusma, Solutions for the Stable Roommates Problem with Payments. Theoretical Computer Science, 540-541 (2014) pp:53-61
- P. Biro and T. Fleiner, Fractional solutions for NTU-games, with applications to stable matchings. Discrete Optimization, forthcoming (2015)
- P. Biro, T. Fleiner and R.W. Irving, Matching couples with Scarf's algorithm. In the Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, (2013) pp:55-64
- P. Biro, R.W. Irving and I. Schlotter, Stable matching with couples – an empirical study. ACM Journal of Experimental Algorithmics, 16 (2011) Article No.: 1.2
- P. Biro, W. Kern and D. Paulusma, Computing solutions for matching games. International Journal of Game Theory, 41 (2012) pp:75-90
- P. Biro, W. Kern, D. Paulusma and P. Wojuteczky, Stable Fixtures Problem with Payments. To appear in the proceedings of the 41th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science, Springer-Verlag, (2015)
- P. Biro and F. Klijn, Matching with Couples: a Multidisciplinary Survey. International Game Theory Review, 15(2), 1340008 (2013)