On the Construction of Substitutes
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. Since 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 4 items.