Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality?

DOI10.1007/978-3-030-85947-3_19zbMATH Open1490.91144arXiv2007.15748OpenAlexW3203116554MaRDI QIDQ2670933FDOQ2670933

Authors: Ndiamé Ndiaye, Serguei Norine, Adrian Vetta 

Publication date: 1 June 2022

Abstract: The set of stable matchings induces a distributive lattice. The supremum of the stable matching lattice is the boy-optimal (girl-pessimal) stable matching and the infimum is the girl-optimal (boy-pessimal) stable matching. The classical boy-proposal deferred-acceptance algorithm returns the supremum of the lattice, that is, the boy-optimal stable matching. In this paper, we study the smallest group of girls, called the {em minimum winning coalition of girls}, that can act strategically, but independently, to force the boy-proposal deferred-acceptance algorithm to output the girl-optimal stable matching. We characterize the minimum winning coalition in terms of stable matching rotations and show that its cardinality can take on any value between $0$ and $leftlfloorfracn2ightfloor$, for instances with $n$ boys and $n$ girls. Our main result is that, for the random matching model, the expected cardinality of the minimum winning coalition is $(frac12+o(1))logn$. This resolves a conjecture of Kupfer cite{Kup18}.

Full work available at URL: https://arxiv.org/abs/2007.15748

Recommendations

• Cheating by Men in the Gale-Shapley Stable Matching Algorithm
• Cheating to Get Better Roommates in a Random Stable Matching
• Stable husbands
• On likely solutions of a stable marriage problem
• Ms. Machiavelli and the Stable Matching Problem

Mathematics Subject Classification ID

Matching models (91B68)

Cites Work

• Title not available (Why is that?)
• Rings of sets
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• Title not available (Why is that?)
• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• Ms. Machiavelli and the Stable Matching Problem
• Machiavelli and the Gale-Shapley Algorithm
• The Economics of Matching: Stability and Incentives
• Title not available (Why is that?)
• The Average Number of Stable Matchings
• Stable husbands
• On likely solutions of a stable marriage problem
• An analysis of the stable marriage assignment algorithm

This page was built for publication: Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670933)