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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Gale-Shapley Algorithm Revisited: Semistability

  • Vladimir Danilov,
  • Gleb Koshevoy

摘要

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.