Université de Lausanne
Faculté des
HEC
Département d'économétrie
et d'économie politique
Cahier de recherches économiques du DEEP No. 13.14
Bettina Klaus and Frédéric Payot
Paths to Stability in the Assignment Problem
September 2013
Abstract
We study a labor market with finitely many heterogeneous workers and firms to
illustrate the decentralized (myopic) blocking dynamics in two-sided one-to-one
matching markets with continuous side payments (assignment problems, Shapley
and Shubik, 1971).
A labor market is unstable if there is at least one blocking pair, that is,
a worker and a firm who would prefer to be matched to each other in order to
obtain higher payoffs than the payoffs they obtain by being matched to their
current partners. A blocking path is a sequence of outcomes (specifying matchings
and payoffs) such that each outcome is obtained from the previous one by satisfying
a blocking pair (i.e., by matching the two blocking agents and assigning new
payoffs to them that are higher than the ones they received before).
We are interested in the question if starting from any (unstable) outcome, there
always exists a blocking path that will lead to a stable outcome. In contrast
to discrete versions of the model (i.e., for marriage markets, one-to-one matching,
or discretized assignment problems), the existence of blocking paths to stability
cannot always be guaranteed. We identify a necessary and sufficient condition
for an assignment problem (the existence of a stable outcome such that all matched
agents receive positive payoffs) to guarantee the existence of paths to stability
and show how to construct such a path whenever this is possible.
Keywords: Assignment problem; competitive equilibria; core; decentralized market; random path; stability
JEL classification: C71 ; C78 ; D63