Gale-Shapley Algorithm Revisited: Semistability
摘要
We consider the broader problem of the existence of stable systems of contracts (we are not limited to the assumption of finite sets of contracts) between agents of two complementary groups, say workers and firms. To do this, we introduce the concept of semistable pairs. We define a dynamic process (a lá Gale-Shapley algorithm) on the set of semistable pairs and show that for agents’s preferences defined by path-independent choice functions, the steady states yield stable sets of contracts. In addition to existence, this process makes it possible to show that the set of stable sets forms a complete lattice. In the Appendix, we discuss Lehmann hyper-orders and establish a bijection between a set of Lehmann hyper-orders and a set of path-independent choice functions.