Language: 日本語 English


Fuhito Kojima
Wed, 2009-01-21
This paper proposes a new stability concept in matching markets
between schools and students, robust stability. A mechanism is ro-
bustly stable if it is stable, strategy-proof and also immune to a com-
bined manipulation, where a student first misreports her preferences
and then blocks the matching that is produced by the mechanism.
First, we show an impossibility result: Even when school priorities
are publicly known and only students can behave strategically, there
is no robustly stable mechanism. Our main result characterizes the
market conditions under which a robustly stable mechanism exists.
Specifically, we show that there exists a robustly stable mechanism if
and only if the priority structure of schools is acyclic (Ergin 2002),
and in that case, the student-optimal stable mechanism is the unique
robustly stable mechanism.