On the Construction of Substitutes

Eric Balkanski () and Renato Paes Leme ()
Additional contact information
Eric Balkanski: School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts 02138;
Renato Paes Leme: Google Research NYC, New York, New York 10011

Mathematics of Operations Research, 2020, vol. 45, issue 1, 272–291

Abstract: Gross substitutability is a central concept in economics and is connected to important notions in discrete convex analysis, number theory, and the analysis of greedy algorithms in computer science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Because gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability, and fully describe all substitutes with at most four items.

Keywords: gross substitutes; matroid rank functions; constructive description (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2019.0991 (application/pdf)

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:inm:ormoor:v:45:y:2020:i:1:p:272-291

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().