In economics, gross substitutes (GS) is a class of utility functions on indivisible goods.
An agent is said to have a GS valuation if, whenever the prices of some items increase and the prices of other items remain constant, the agent's demand for the items whose price remain constant weakly increases.
The table shows the valuations (in dollars) of Alice and Bob to the four possible subsets of the set of two items: {apple, bread}.
To see this, suppose that initially both apple and bread are priced at $6.
Bob's optimal bundle is apple+bread, since it gives him a net value of $3.
So Bob's demand to apple has decreased, although only the price of bread has increased.
The GS condition was introduced by Kelso and Crawford in 1982[1] and was greatly publicized by Gul and Stacchetti.
The original GS definition[1] is based on a price vector and a demand set.
The SI condition[2] says that a non-optimal set can be improved by adding, removing or substituting a single item.
The NC condition[2] says that every subset of a demanded bundle has a substitute.
Suppose Alice and Bob both have utility function
For every item that Alice hands Bob, Bob can hand at most one item to Alice, such that their total utility after the exchange is preserved or increased.
[2] Suppose Alice and Bob both have utility function
that Alice hands Bob, there is an equivalent subset
that Bob can handle Alice, such that their total utility after the exchange is preserved or increased.
Note that it is very similar to the MC condition - the only difference is that in MC, Alice hands Bob exactly one item and Bob returns Alice at most one item.
Note: to check whether u has SNC, it is sufficient to consider the cases in which
And it is sufficient to check the non-trivial subsets, i.e., the cases in which
Kazuo Murota proved[4] that MX implies SNC.
It is obvious that SNC implies NC.
[2] Proof: Fix an SNC utility function
This closes the loop and shows that all these properties are equivalent (there is also a direct proof[4] that SNC implies MX).
The DDF condition[5] is related to changes in the price-vector.
[5] prove that MX implies DDF, so these conditions are all equivalent.
The GS condition is preserved under price-changes.
Every GS valuation is a submodular set function.
The utility is submodular since it satisfies the decreasing-marginal-utility property: the marginal-utility of an item is 40–66 when added to an empty set, 9--40 when added to a single item and 0--5 when added to a pair of items.
But it violates the equivalent conditions of the GS family: Submodularity does imply GS in the special case in which there is a single item-type, so that the value of a bundle depends only on the number of items in the bundle.
This is easiest to see using the SNC characterization, which in this case translates to: Indeed, if
which makes the inequality: which is equivalent to: This follows from submodularity because