Note on the size of a stable matching
Consider a one-to-one two-sided matching market with workers on one side and single-position firms on the other, and suppose that the largest individually rational matching contains $n$ pairs. We show that the number of workers employed and positions filled in every stable matching is bounded from below by $\lceil\frac{n}{2}\rceil$ and we characterise the class of preferences that attain the bound.
Code (0)
등록된 구현이 없습니다.
Tasks
PositionSimilar Papers 제목 키워드 기반
A Note on Obvious Manipulations of Quantile Stable Mechanisms
In two-sided matching markets with contracts, quantile (or generalized median) stable mechanisms represent an interesting class that produces stable allocations which can be viewed as compromises between both sides of th…
The Complexity of Interactively Learning a Stable Matching by Trial and Error
In a stable matching setting, we consider a query model that allows for an interactive learning algorithm to make precisely one type of query: proposing a matching, the response to which is either that the proposed match…
BlockingA Tie-breaking based Local Search Algorithm for Stable Matching Problems
The stable marriage problem with incomplete lists and ties (SMTI) and the hospitals/residents problem with ties (HRT) are important in matching theory with broad practical applications. In this paper, we introduce a tie-…
Exploring Strategy-Proofness, Uniqueness, and Pareto Optimality for the Stable Matching Problem with Couples
The Stable Matching Problem with Couples (SMP-C) is a ubiquitous real-world extension of the stable matching problem (SMP) involving complementarities. Although SMP can be solved in polynomial time, SMP-C is NP-Complete.…
On the Equivalence of Two Competing Affirmative Actions in School Choice
This note analyzes the outcome equivalence conditions of two popular affirmative action policies, majority quota and minority reserve, under the student optimal stable mechanism. These two affirmative actions generate an…
Vocal Bursts Valence Prediction