• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Summer School of DeCAn. Day 3

Speaker: Peter Biro (Research fellow, Hungarian Academy of Sciences, Hungary)
Title: Game theoretical aspects of matching problems under preferences

Summer School of DeCAn. Day 3

Abstract

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. 


Additional materials:

 Slides (PDF, 8.54 Мб)






References:

  1. 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
  2. P. Biro and T. Fleiner, Fractional solutions for NTU-games, with applications to stable matchings. Discrete Optimization, forthcoming (2015)
  3. 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
  4. 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
  5. P. Biro, W. Kern and D. Paulusma, Computing solutions for matching games. International Journal of Game Theory, 41 (2012) pp:75-90
  6. 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)
  7. P. Biro and F. Klijn, Matching with Couples: a Multidisciplinary Survey. International Game Theory Review, 15(2), 1340008 (2013)