Journal of Dynamics and Games (JDG)

Paths to stability in the assignment problem

Pages: 257 - 287, Volume 2, Issue 3/4, July/October 2015      doi:10.3934/jdg.2015004

       Abstract        References        Full Text (538.5K)       Related Articles       

Bettina Klaus - Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland (email)
Frédéric Payot - Federal Department of Economic A airs, Education and Research, SECO, CH-3003 Bern, Switzerland (email)

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 [24]).
    Assuming individual rationality, 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) individually rational 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.
Mathematics Subject Classification:  Primary: 91A80; Secondary: 91A12.

Received: February 2015;      Revised: May 2015;      Available Online: November 25 2015.