Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Matchings under Preferences: Strength of Stability and Trade-Offs

Uproszczony widok
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryStany Zjednoczone
dc.conference.datefinish2019-06-28
dc.conference.datestart2019-06-24
dc.conference.placePhoenix
dc.conference.seriesACM Conference on Economics and Computation
dc.conference.seriesACM Conference on Economics and Computation
dc.conference.seriesshortcutEC
dc.conference.shortcutEC
dc.conference.weblinkhttp://www.sigecom.org/ec19/
dc.contributor.authorSorge, Manuel
dc.contributor.authorSkowron, Piotr
dc.contributor.authorChen, Jiehua
dc.date.accessioned2024-01-25T05:34:01Z
dc.date.available2024-01-25T05:34:01Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.identifier.doi10.1145/3328526.3329555
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111901
dc.identifier.weblinkhttps://dl.acm.org/doi/pdf/10.1145/3328526.3329555
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages41–59
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleMatchings under Preferences: Strength of Stability and Trade-Offs
dc.typeJournalArticle
dspace.entity.typePublication