Gross substitutability: An algorithmic survey

Renato Paes Leme

Games and Economic Behavior, 2017, vol. 106, issue C, 294-316

Abstract: The concept of gross substitute valuations was introduced by Kelso and Crawford as a sufficient conditions for the existence of Walrasian equilibria in economies with indivisible goods. The proof is algorithmic in nature: gross substitutes is exactly the condition that enables a natural price adjustment procedure – known as Walrasian tatônnement – to converge to equilibrium. The same concept was also introduced independently in other communities with different names: M♮-concave functions (Murota and Shioura), Matroidal and Well-Layered maps (Dress and Terhalle) and valuated matroids (Dress and Wenzel). Here we survey various definitions of gross substitutability and show their equivalence. We focus on algorithmic aspects of the various definitions. In particular, we highlight that gross substitutes are the exact class of valuations for which demand oracles can be computed via an ascending greedy algorithm. It also corresponds to a natural discrete analogue of concave functions: local maximizers correspond to global maximizers.

Keywords: Gross substitutes; Discrete convexity; Walrasian equilibrium (search for similar items in EconPapers)
JEL-codes: C78 D44 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899825617301884
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:106:y:2017:i:c:p:294-316

DOI: 10.1016/j.geb.2017.10.016

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().