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

DOI10.1007/978-3-030-85947-3_19MaRDI QIDQ2670933zbMATH OpenOpenAlexFDO

Authors Ndiamé Ndiaye, Serguei Norine, Adrian Vetta

Publication date 1 June 2022

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

Mathematics Subject Classification ID

Matching models (91B68)

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}.

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

Cites work

• scientific article; zbMATH DE number 16479 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• An analysis of the stable marriage assignment algorithm
• College Admissions and the Stability of Marriage
• Machiavelli and the Gale-Shapley Algorithm
• Ms. Machiavelli and the Stable Matching Problem
• On likely solutions of a stable marriage problem
• Rings of sets
• Stable husbands
• The Average Number of Stable Matchings
• The Complexity of Counting Stable Marriages
• The Economics of Matching: Stability and Incentives
• Three Fast Algorithms for Four Problems in Stable Marriage

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)