Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUnique Stable Matchings
106
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We provide necessary and sufficient conditions on the preferences of market participants for a unique stable matching in models of two-sided matching with non-transferable utility. We use the process of iterated deletion of unattractive alternatives (IDUA), a formalisation of the reduction procedure in Balinski and Ratier (1997), and we show that an instance of the matching problem possesses a unique stable matching if and only if IDUA collapses each participant preference list to a singleton. (This is in a sense the matching problem analog of a strategic game being dominance solvable.)
rate research
Read More
In a many-to-one matching model in which firms preferences satisfy substitutability, we study the set of worker-quasi-stable matchings. Worker-quasi-stability is a relaxation of stability that allows blocking pairs involving a firm and an unemployed worker. We show that this set has a lattice structure and define a Tarski operator on this lattice that models a re-equilibration process and has the set of stable matchings as its fixed points.
We highlight the tension between stability and equality in non transferable utility matching. We consider many to one matchings and refer to the two sides of the market as students and schools. The latter have aligned preferences, which in this context means that a schools utility is the sum of its students utilities. We show that the unique stable allocation displays extreme inequality between matched pairs.
We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose--accept rounds executed by the Gale--Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. This holds even if ties are present in the preference lists. We apply our results to give a distributed $(2+epsilon)$-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.
We study conditions for the existence of stable and group-strategy-proof mechanisms in a many-to-one matching model with contracts if students preferences are monotone in contract terms. We show that equivalence, properly defined, to a choice profile under which contracts are substitutes and the law of aggregate holds is a necessary and sufficient condition for the existence of a stable and group-strategy-proof mechanism. Our result can be interpreted as a (weak) embedding result for choice functions under which contracts are observable substitutes and the observable law of aggregate demand holds.
We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference list over the agents of the next type. We consider the open problem of the existence of three-dimensional matchings in which no triple of agents prefer each other to their partners. Such matchings are said to be weakly stable. We show that contrary to published conjectures, weakly stable three-dimensional matchings need not exist. Furthermore, we show that it is NP-complete to determine whether a weakly stable three-dimensional matchings exists. We achieve this by reducing from the variant of the problem where preference lists are allowed to be incomplete. Our results can be generalized to the $k$-dimensional stable matching problem with cyclic preferences for $k geq 3$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
