Skip to main content
Springer Nature Link
Log in

Weighted Popular Matchings

  • Conference paper
Automata, Languages and Programming (ICALP 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4051))

Included in the following conference series:

  • 1665 Accesses

Abstract

We study the problem of assigning applicants to jobs. Each applicant has a weight and provides a preference list, which may contain ties, ranking a subset of the jobs. An applicant x may prefer one matching over the other (or be indifferent between them, in case of a tie) based on the jobs x gets in the two matchings and x’s personal preference. A matching M is popular if there is no other matching M′ such that the weight of the applicants who prefer M′ over M exceeds the weight of those who prefer M over M′.

We present two algorithms to find a popular matching, or in case none exists, to establish so. For the case of strict preferences we develop an O(n+m) time algorithm. When ties are allowed a more involved algorithm solves the problem in \(O(\min(k \sqrt{n}, n) m)\) time, where k is the number of distinct weights the applicants are given.

Research supported by NSF Awards CCR 0113192 and CCF 0430650.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abdulkadiroǧlu, A., Sönmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems. Econ. 66(3), 689–701 (1998)

    Google Scholar 

  2. Abraham, D.J., Cechlarova, K., Manlove, D.F., Mehlhorn, K.: Pareto optimality in house allocation problems. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 3–15. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. In: Proc. of SODA, pp. 424–432 (2005)

    Google Scholar 

  4. Abraham, D.J., Kavitha, T.: Dynamic matching markets and voting paths. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  5. Gardenfors, P.: Match making: assignments based on bilateral preferences. Behavioural Sciences 20, 166–173 (1975)

    Article  Google Scholar 

  6. Hylland, A., Zeeckhauser, R.: The efficient allocation of individuals to positions. Journal of Political Economy 87(2), 293–314 (1979)

    Article  Google Scholar 

  7. Irving, R.W., Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: Rank-maximal matchings. In: Proc. of SODA, pp. 68–75 (2004)

    Google Scholar 

  8. Mahdian, M.: Random popular matchings. In: EC (to appear, 2006)

    Google Scholar 

  9. Yuan, Y.: Residence exchange wanted: a stable residence exchange problem. European Journal of Operational Research 90, 536–546 (1996)

    Article  MATH  Google Scholar 

  10. Zhou, L.: On a conjecture by Gale about one-sided matching problems. Journal of Economic Theory 52(1), 123–135 (1990)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Maryland, College Park, MD, 20742, USA

    Julián Mestre

Authors
  1. Julián Mestre
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Informatica, Università Ca’ Foscari, Venice

    Michele Bugliesi

  2. Interdisciplinary Institute for BroadBand Technology (IBBT), Belgium

    Bart Preneel

  3. ECS, University of Southampton, UK

    Vladimiro Sassone

  4. FB Informatik, Univ. Dortmund, LS2, 44221, Dortmund, Germany

    Ingo Wegener

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Mestre, J. (2006). Weighted Popular Matchings. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds) Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, vol 4051. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11786986_62

Download citation

  • DOI: https://doi.org/10.1007/11786986_62

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-35904-3

  • Online ISBN: 978-3-540-35905-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation