Working Paper
[UTMD-032] Impossibility of weakly stable and strategy-proof mechanism (by Sung-Ho Cho, Miyuki Koshimura, Pinaki Mandal, Kentaro Yahiro, Makoto Yokoo)
Author
Sung-Ho Cho, Miyuki Koshimura, Pinaki Mandal, Kentaro Yahiro, Makoto Yokoo
Abstract
Many real matching markets are subject to distributional constraints. When the set of feasible matchings is restricted by some distributional constraints, a stable matching may not exist. In contrast, a weakly stable matching is guaranteed to exist under a very general class of constraints that satisfies a condition called heredity. However, it has been an open question whether a weakly stable matching can be obtained by a strategy-proof mechanism. We negatively answer this open question; no weakly stable and strategy-proof mechanism exists under any heredity feasibility constraint in general.