Lecture Notes in Computer Science, 2003, Volume 2906/2003, 495-504, DOI: 10.1007/978-3-540-24587-2_51

A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model

Akinobu Eguchi, Satoru Fujishige and Akihisa Tamura

View Related Documents

Abstract

The stable marriage model due to Gale and Shapley is one of the most fundamental two-sided matching models. Recently, Fleiner generalized the model in terms of matroids, and Eguchi and Fujishige extended the matroidal model to the framework of discrete convex analysis. In this paper, we extend their model to a vector version in which indifference on preferences is allowed, and show the existence of a stable solution by a generalization of the Gale-Shapley algorithm.
This work is supported by a Grant-in-Aid of the Ministry of Education, Culture, Sports, Science and Technology of Japan.

Fulltext Preview

Image of the first page of the fulltext document