A Polynomial-Time Algorithm to Find von Neumann-Morgenstern Stable Matchings in Marriage Games

作者：Wako Jun^*

来源：Algorithmica, 2010, 58(1): 188-220.

DOI：10.1007/s00453-010-9388-y

• Matching problem
• Stable matching
• von Neumann-Morgenstern stable set

This paper considers von Neumann-Morgenstern (vNM) stable sets in marriage games. Ehlers (Journal of Economic Theory 134: 537-547, 2007) showed that if a vNM stable set exists in a marriage game, the set is a maximal distributive lattice of matchings that includes all core matchings. To determine what matchings form a vNM stable set, we propose a polynomial-time algorithm that finds a man-optimal matching and a woman-optimal matching in a vNM stable set of a given marriage game. This algorithm also generates a modified preference profile such that a vNM stable set is obtained as the core of a marriage game with the modified preference profile. It is well known that cores of marriage games are nonempty. However, the nonemptiness of cores does not imply the existence of a vNM stable set. It is proved using our algorithm that there exists a unique vNM stable set for any marriage game.

• 出版日期2010-9