research-article

Matchings under Preferences: Strength of Stability and Trade-Offs

Authors:

Manuel SorgeAuthors Info & Claims

EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation

Pages 41 - 59

https://doi.org/10.1145/3328526.3329555

Published: 17 June 2019 Publication History

Abstract

We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classic definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classic sense, even if the agents slightly change their preferences. Near stability, on the other hand, imposes that a matching must become stable (again, in the classic sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative; together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of trade-offs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined trade-offs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching, and we prove that finding a socially optimal and nearly stable matching is computationally hard.

Supplementary Material

MP4 File (p41-chen.mp4)

Download
1552.53 MB

References

[1]

Elliot Anshelevich, Sanmay Das, and Yonatan Naamad. 2013. Anarchy, Stability, and Utopia: Creating Better Matchings. Autonomous Agents and Multi-Agent Systems, Vol. 26, 1 (2013), 120--140.

Digital Library

[2]

Haris Aziz, Pé ter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. 2016. Stable Matching with Uncertain Linear Preferences. In Proc. SAGT-16. 195--206.

[3]

Pé ter Biró, David Manlove, and Eric McDermid. 2012. “Almost stable” matchings in the Roommates problem with bounded preference lists. Theoretical Computer Science, Vol. 432 (2012), 10--20.

Digital Library

[4]

James Boudreau and Vicki Knoblauch. 2013. Preferences and the price of stability in matching markets. Theory and Decision, Vol. 74, 4 (2013), 565--589.

[5]

Robert Bredereck, Jiehua Chen, Ugo P. Finnendahl, and Rolf Niedermeier. 2017. Stable Roommate with Narcissistic, Single-Peaked, and Single-Crossing Preferences. In Proc. ADT-17. 315--330.

[6]

Paul Camion. 1965. Characterization of Totally Unimodular Matrices. Proc. Amer. Math. Soc., Vol. 16, 5 (1965), 1068--1073.

[7]

Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. 2018a. How hard is it to satisfy (almost) all roommates?. In Proc. ICALP-18. 35:1--35:15.

[8]

Jiehua Chen, Rolf Niedermeier, and Piotr Skowron. 2018b. Stable Marriage with Multi-Modal Preferences. In Proc. EC-18. 269--286.

Digital Library

[9]

Jiehua Chen, Piotr Skowron, and Manuel Sorge. 2019. Matchings under Preferences: Strength of Stability and Trade-Offs . Technical Report. arXiv:1902.10535 {cs.GT}.

[10]

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms .Springer.

Digital Library

[11]

Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity .Springer.

Digital Library

[12]

Joanna Drummond and Craig Boutilier. 2013. Elicitation and Approximately Stable Matching with Partial Preferences. In Proc. IJCAI-13 . 97--105.

Digital Library

[13]

Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory .Springer.

[14]

David Gale and Lloyd S. Shapley. 1962. College Admissions and the Stability of Marriage. The American Mathematical Monthly, Vol. 120, 5 (1962), 386--391.

[15]

Begum Genc, Mohamed Siala, Gilles Simonin, and Barry O'Sullivan. 2017a. On the Complexity of Robust Stable Marriage. In Proc. COCOA-17. 441--448.

Digital Library

[16]

B. Genc, M. Siala, G. Simonin, and B. O'Sullivan. 2017b. Robust Stable Marriage. In Proc. AAAI-17. 4925--4926.

Digital Library

[17]

Dan Gusfield and Robert W. Irving. 1989. The Stable Marriage Problem--Structure and Algorithms .MIT Press.

Digital Library

[18]

Robert W. Irving. 1994. Stable marriage and indifference. Discrete Applied Mathematics, Vol. 48, 3 (1994), 261--272.

Digital Library

[19]

R. W. Irving, P. Leather, and D. Gusfield. 1987. An efficient algorithm for the 'optimal' stable marriage. J. ACM, Vol. 34, 3 (1987), 532--543.

Digital Library

[20]

Maurice Kendall. 1948. A New Measure of Rank Correlation. Biometrika, Vol. 30 (1948), 81--89.

[21]

Donald Knuth. 1976. Mariages Stables .Les Presses de L'Université de Montréal.

[22]

Tung Mai and Vijay V. Vazirani. 2018a. Finding Stable Matchings That Are Robust to Errors in the Input. In Proc. ESA-18 . 60:1--60:11.

[23]

Tung Mai and Vijay V. Vazirani. 2018b. A Generalization of Birkhoff's Theorem for Distributive Lattices, with Applications to Robust Stable Matchings . Technical Report. arXiv:1804.05537 {cs.DM}.

[24]

David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. 2002. Hard variants of stable marriage. Theoretical Computer Science, Vol. 276, 1--2 (2002), 261--279.

Digital Library

[25]

David F. Manlove. 2013. Algorithmics of Matching Under Preferences. Vol. 2. WorldScientific.

[26]

Vijay Menon and Kate Larson. 2018. Robust and Approximately Stable Marriages under Partial Information. In Proc. WINE-18 . 341--355.

Digital Library

[27]

Shuichi Miyazaki and Kazuya Okamoto. 2017. Jointly Stable Matchings. In Proc. ISAAC-17. 56:1--56:12.

[28]

Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms .Oxford University Press.

[29]

Christos H. Papadimitriou. 2007. The Complexity of Finding Nash Equilibria. In Algorithmic Game Theory . Cambridge University Press, 29--51.

[30]

Maria Silvia Pini, Francesca Rossi, K. Brent Venable, and Toby Walsh. 2013. Stability, Optimality and Manipulation in Matching Problems with Weighted Preferences. Algorithms, Vol. 6, 4 (2013), 782--804.

Cited By

Gupta SJain P(2024)Manipulation With(out) Money in Matching MarketAlgorithmic Decision Theory10.1007/978-3-031-73903-3_18(273-287)Online publication date: 16-Oct-2024
https://doi.org/10.1007/978-3-031-73903-3_18
Xu ZZhang JXu ZZhang J(2022)Algorithmic ThinkingComputational Thinking: A Perspective on Computer Science10.1007/978-981-16-3848-0_4(131-182)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-981-16-3848-0_4
Boehmer NBredereck RHeeger KNiedermeier R(2021)Bribery and Control in Stable MarriageJournal of Artificial Intelligence Research10.1613/jair.1.1275571(993-1048)Online publication date: 24-Aug-2021
https://dl.acm.org/doi/10.1613/jair.1.12755
Show More Cited By

Index Terms

Matchings under Preferences: Strength of Stability and Trade-Offs
1. Theory of computation

Recommendations

Matchings under Preferences: Strength of Stability and Tradeoffs
We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classical definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires ...
Stable Marriage with Multi-Modal Preferences
EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation

We thoroughly study a generalized version of the famous Stable Marriage problem, now based on multi-modal preference lists. The central twist herein is to allow each agent to rank its potentially matching counterparts based on more than one "evaluation ...
Stable Matchings with Restricted Preferences: Structure and Complexity
In the stable marriage (SM) problem, there are two sets of agents—traditionally referred to as men and women—and each agent has a preference list that ranks (a subset of) agents of the opposite sex. The goal is to find a matching between men and women ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation

June 2019

947 pages

ISBN:9781450367929

DOI:10.1145/3328526

General Chair:
Anna Karlin
University of Washington, USA
,
Program Chairs:
Nicole Immorlica
Microsoft Research, USA
,
Ramesh Johari
Stanford University, USA

Copyright © 2019 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 the author(s) 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].

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

H2020 European Research Council

Conference

EC '19

Sponsor:

SIGecom

EC '19: ACM Conference on Economics and Computation

June 24 - 28, 2019

AZ, Phoenix, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
195
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gupta SJain P(2024)Manipulation With(out) Money in Matching MarketAlgorithmic Decision Theory10.1007/978-3-031-73903-3_18(273-287)Online publication date: 16-Oct-2024
https://doi.org/10.1007/978-3-031-73903-3_18
Xu ZZhang JXu ZZhang J(2022)Algorithmic ThinkingComputational Thinking: A Perspective on Computer Science10.1007/978-981-16-3848-0_4(131-182)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-981-16-3848-0_4
Boehmer NBredereck RHeeger KNiedermeier R(2021)Bribery and Control in Stable MarriageJournal of Artificial Intelligence Research10.1613/jair.1.1275571(993-1048)Online publication date: 24-Aug-2021
https://dl.acm.org/doi/10.1613/jair.1.12755
Bredereck RChen JFinnendahl UNiedermeier R(2020)Stable roommates with narcissistic, single-peaked, and single-crossing preferencesAutonomous Agents and Multi-Agent Systems10.1007/s10458-020-09470-x34:2Online publication date: 11-Sep-2020
https://doi.org/10.1007/s10458-020-09470-x
Boehmer NBredereck RHeeger KNiedermeier R(2020)Bribery and Control in Stable MarriageAlgorithmic Game Theory10.1007/978-3-030-57980-7_11(163-177)Online publication date: 8-Sep-2020
https://doi.org/10.1007/978-3-030-57980-7_11

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents