More Web Proxy on the site http://driver.im/

research-article

Weighted popular matchings

Author:

Juliań MestreAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 10, Issue 1

Article No.: 2, Pages 1 - 16

https://doi.org/10.1145/2556951

Published: 01 January 2014 Publication History

Abstract

We study the problem of assigning jobs to applicants. 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 to another (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′ to M exceeds the weight of those who prefer M to M′.

We present algorithms to find a popular matching, or if none exists, to establish so. For instances with strict preference lists, we give an O(n+m time algorithm. For preference lists with ties, we give a more involved algorithm that solves the problem in O(min (k √n;, n) m) time, where k is the number of distinct weights the applicants are given.

References

[1]

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

[2]

D. Abraham, N. Chen, V. Kumar, and V. S. Mirrokni. 2006. Assignment problems in rRental markets. In Proceedings of the 2th International Workshop on Internet and Network Economics (WINE). 198--213.

Digital Library

[3]

D. J. Abraham, K. Cechlarova, D. F. Manlove, and K. Mehlhorn. 2004. Pareto optimality in house allocation problems. In Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC). 3--15.

Digital Library

[4]

D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. 2007. Popular matchings. SIAM J. Comput. 37, 4 (2007), 1030--1045.

Digital Library

[5]

D. J. Abraham and T. Kavitha. 2006. Dynamic matching markets and voting paths. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT). 65--76.

Digital Library

[6]

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

[7]

J. E. Hopcroft and R. M. Karp. 1973. An n^5/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput. 2, 4 (1973), 225--231.

[8]

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

[9]

R. W. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch. 2006. Rank-maximal matchings. ACM Transactions on Algorithms 2, 4 (2006), 602--610.

Digital Library

[10]

T. Itoh and O. Watanabe. 2010. Weighted random popular matchings. Random Struct. Algorithms 37, 4 (2010), 477--494.

Digital Library

[11]

T. Kavitha and C. D. Shah. 2006. Efficient algorithms for weighted rank-maximal matchings and related problems. In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC). 153--162.

Digital Library

[12]

M. Mahdian. 2006. Random popular matchings. In Proceedings of the 7th ACM Conference on Electronic Commerce (EC). 238--242.

Digital Library

[13]

D. Manlove and C. Sng. 2006. Popular matchings in the Capacitated House Allocation problem. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA). 492--503.

Digital Library

[14]

J. Mestre. 2006. Weighted popular matchings. In Proceedings of the 33th International Colloquium on Automata, Languages and Programming. 715--726.

Digital Library

[15]

C. H. Papadimitriou and K. Steiglitz. 1998. Combinatorial Optimization. Dover Publications, Inc.

[16]

A. Schrijver. 2003. Combinatorial Optimization. Springer-Verlag.

[17]

C. T. S. Sng and D. Manlove. 2010. Popular matchings in the weighted capacitated house allocation problem. Journal on Discrete Algorithms 8, 2 (2010), 102--116.

Digital Library

[18]

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

[19]

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

Cited By

Kavitha T(2024)Popular Matchings with One-Sided BiasACM Transactions on Algorithms10.1145/363876420:1(1-22)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3638764
Heeger KCseh Á(2024)Popular matchings with weighted votersGames and Economic Behavior10.1016/j.geb.2024.01.015144(300-328)Online publication date: Mar-2024
https://doi.org/10.1016/j.geb.2024.01.015
Natsui KTakazawa K(2023)Finding popular branchings in vertex-weighted directed graphsTheoretical Computer Science10.1016/j.tcs.2023.113799953(113799)Online publication date: Apr-2023
https://doi.org/10.1016/j.tcs.2023.113799
Show More Cited By

Index Terms

Weighted popular matchings
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Popular and clan-popular b-matchings

Suppose that each member of a set of agents has a preference list of a subset of houses, possibly involving ties, and each agent and house has their capacity denoting the maximum number of houses/agents (respectively) that can be matched to him/her/it. ...
Popular edges and dominant matchings

Given a bipartite graph $$G = (A \cup B,E)$$G=(AýB,E) with strict preference lists and given an edge $$e^* \in E$$eýýE, we ask if there exists a popular matching in G that contains $$e^*$$eý. We call this the popular edge problem. A matching M is ...
Dynamic rank-maximal and popular matchings

We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph $$G=(\mathcal {A}\cup \mathcal {P},E)$$G=(AýP,E), where $$\mathcal {A}$$A denotes a set of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 10, Issue 1

January 2014

73 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2578701

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2014

Accepted: 01 August 2013

Revised: 01 December 2012

Received: 01 April 2008

Published in TALG Volume 10, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
328
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kavitha T(2024)Popular Matchings with One-Sided BiasACM Transactions on Algorithms10.1145/363876420:1(1-22)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3638764
Heeger KCseh Á(2024)Popular matchings with weighted votersGames and Economic Behavior10.1016/j.geb.2024.01.015144(300-328)Online publication date: Mar-2024
https://doi.org/10.1016/j.geb.2024.01.015
Natsui KTakazawa K(2023)Finding popular branchings in vertex-weighted directed graphsTheoretical Computer Science10.1016/j.tcs.2023.113799953(113799)Online publication date: Apr-2023
https://doi.org/10.1016/j.tcs.2023.113799
Afacan MBó I(2022)Strategy-proof popular mechanismsJournal of Mathematical Economics10.1016/j.jmateco.2022.102734102(102734)Online publication date: Oct-2022
https://doi.org/10.1016/j.jmateco.2022.102734
Kondratev ANesterov A(2022)Minimal envy and popular matchingsEuropean Journal of Operational Research10.1016/j.ejor.2021.03.060296:3(776-787)Online publication date: Feb-2022
https://doi.org/10.1016/j.ejor.2021.03.060
Natsui KTakazawa K(2022)Finding Popular Branchings in Vertex-Weighted DigraphsWALCOM: Algorithms and Computation10.1007/978-3-030-96731-4_25(303-314)Online publication date: 16-Mar-2022
https://doi.org/10.1007/978-3-030-96731-4_25
Kamiyama N(2019)Popular matchings with two-sided preference lists and matroid constraintsTheoretical Computer Science10.1016/j.tcs.2019.12.017Online publication date: Dec-2019
https://doi.org/10.1016/j.tcs.2019.12.017
Kamiyama N(2018)A CHARACTERIZATION OF WEIGHTED POPULAR MATCHINGS UNDER MATROID CONSTRAINTSJournal of the Operations Research Society of Japan10.15807/jorsj.61.261:1(2-17)Online publication date: 2018
https://doi.org/10.15807/jorsj.61.2
Kamiyama N(2018)The popular matching and condensation problems under matroid constraintsJournal of Combinatorial Optimization10.1007/s10878-015-9965-832:4(1305-1326)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1007/s10878-015-9965-8
Cseh ÁHuang CKavitha T(2017)Popular Matchings with Two-Sided Preferences and One-Sided TiesSIAM Journal on Discrete Mathematics10.1137/16M107616231:4(2348-2377)Online publication date: Jan-2017
https://doi.org/10.1137/16M1076162
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents