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 HighWire Citing Articles via Google Scholar Google Scholar Articles by Fujishige, S. Articles by Yang, Z. Search for Related Content

A Note on Kelso and Crawford's Gross Substitutes Condition

Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
Cowles Foundation for Research in Economics, Yale University, New Haven, CT 06520-8281, USA
fujishig{at}sys.es.osaka-u.ac.jp
zaifu.yang{at}yale.edu

In their 1982 article, Kelso and Crawford proposed a gross substitutes condition for the existence of core (and equilibrium) in a two-sided matching model. Since then, this condition has often been used in the literature on matching models and equilibrium models in the presence of indivisibilities. In this paper we prove that a reservation value (or utility) function satisfies the gross substitutes condition if and only if it is an M-concave function defined on the unit-hypercube, which is a discrete concave function recently introduced by Murota and Shioura (1999).

Key Words: Indivisibility; gross substitutes; equilibrium; M-concave function; generalized polymatroid; submodular function
History: Received: June 25, 2001; revision received: May 14, 2002;

This article has been cited by other articles:

				Z. Yang On the Solutions of Discrete Nonlinear Complementarity and Related Problems Mathematics of Operations Research, November 1, 2008; 33(4): 976 - 990. [Abstract] [PDF]

				S. Fujishige and A. Tamura A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis Mathematics of Operations Research, February 1, 2007; 32(1): 136 - 155. [Abstract] [PDF]