A Polynomial-Time Algorithm to Find von Neumann-Morgenstern Stable Matchings in Marriage Games |
| |
Authors: | Jun Wako |
| |
Affiliation: | (1) Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, New York;(2) Department of Industrial Engineering, Bilkent University, 06800 Bilkent, Ankara, Turkey;(3) On leave from the Department of Applied Mathematics and Statistics at Stony Brook University, Stony Brook, NY, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|