On the Construction of Substitutes

• 成果类型: Article
• 署名作者: Balkanski, Eric; Leme, Renato Paes
• 署名单位: Harvard University; Alphabet Inc.; Google Incorporated
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.0991
• 发表日期: 2020
• 页码: 272-291
• 关键词: stability; equilibrium; MAPS

摘要

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.