Lattice structure of the random stable set in many-to-many matching markets

Abstract

We study the lattice structure of the set of random stable matchings for a many-to-many matching market. We define a partial order on the random stable set and present two natural binary operations for computing the least upper bound and the greatest lower bound for each side of the matching market. Then we prove that with these binary operations the set of random stable matchings forms two distributive lattices for the appropriate partial order, one for each side of the market. Moreover, these lattices are dual.