This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Fujishige, S. Articles by Tamura, A. Search for Related Content

A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis

Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
Department of Mathematics, Keio University, Yokohama 223-8522, Japan
fujishig{at}kurims.kyoto-u.ac.jp, http://www.kurims.kyoto-u.ac.jp/fujishig
aki-tamura{at}math.keio.ac.jp, http://www.math.keio.ac.jp/local/aki-tamura/

The marriage model due to Gale and Shapley [Gale, D., L. S. Shapley. 1962. College admissions and the stability of marriage. Amer. Math. Monthly 69 9–15] and the assignment model due to Shapley and Shubik [Shapley, L. S., M. Shubik. 1972. The assignment game I: The core. Internat. J. Game Theory 1 111–130] are standard in the theory of two-sided matching markets. We give a common generalization of these models by utilizing discrete-concave functions and considering possibly bounded side payments. We show the existence of a pairwise stable outcome in our model. Our present model is a further natural extension of the model examined in our previous paper [Fujishige, S., A. Tamura. A general two-sided matching market with discrete concave utility functions. Discrete Appl. Math. 154 950–970], and the proof of the existence of a pairwise stable outcome is even simpler than the previous one.

Key Words: marriage model; assignment model; pairwise stability; bounded side payments; discrete convex analysis
History: Received: August 17, 2004; revision received: October 31, 2005;