Saturday, September 15, 2018

Envy free (not quite stable) matchings

It's hard for decentralized markets to achieve stable matchings (i.e. matchings with no blocking pairs) in the way that centralized clearinghouses can (and this is why we see some markets organized by clearinghouses).  So it's worthwhile looking at larger sets of outcomes, and in this paper we look at matchings such that any blocking pairs must involve an unfilled position--i.e. they are envy free in the sense that there are no blocking pairs in which some worker can take the job presently held by another worker.

Wu, Qingyun and Alvin E. Roth, “The Lattice of Envy-free Matchings,” Games and Economic Behavior, May 2018, 109, 201-211

The lattice of envy-free matchings


Envy-free matchings are matchings that can only be unstable with respect to a blocking pair of a worker with a firm that has some unfilled positions.
These envy-free but unstable matchings may arise in the course of filling “vacancy chains” following a worker's retirement.
The set of envy free matchings is a lattice under the partial ordering of the common preferences of the workers.


In a many-to-one matching model, we show that the set of envy-free matchings is a lattice. A Tarski operator on this lattice, which can be interpreted as modeling vacancy chains, has the set of stable matchings as its fixed points.
Here's an ungated version of the paper.

No comments: