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.
Bundle | Alice's valuation (GS) | Bob's valuation (not GS) | |
---|---|---|---|
\emptyset | $0 | $0 | |
apple | $5 | $5 | |
bread | $7 | $7 | |
apple+bread | $9 | $15 |
An example is shown on the right. The table shows the valuations (in dollars) of Alice and Bob to the four possible subsets of the set of two items: . Alice's valuation is GS, but Bob's valuation is not GS. 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. Now, the price of bread increases to $10. Now, Bob's optimal bundle is the empty bundle, since all other bundles give him negative net value. 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.[2] Since then it has found many applications, mainly in auction theory and competitive equilibrium theory.
The GS condition has many equivalent definitions.
The original GS definition[1] is based on a price vector and a demand set.
p
u
p
X
u(X)-p ⋅ X
D(u,p)
The GS property means that when the price of some items increases, the demand for other items does not decrease. Formally, for any two price vectors
q
p
q\geqp
X\inD(u,p)
Y\inD(u,q)
Y\supseteq\{x\inX|px=qx\}
The SI condition[2] says that a non-optimal set can be improved by adding, removing or substituting a single item. Formally, for any price vector
p
X\notinD(u,p)
Y
u(Y)-p ⋅ Y>u(X)-p ⋅ X
|X\setminusY|\leq1
|Y\setminusX|\leq1
The NC condition[2] says that every subset of a demanded bundle has a substitute. Formally: for any price vector
p
X,Y\inD(u,p)
X'\subseteqX
Y'\subseteqY
X\setminusX'\cupY'\inD(u,p)
If the valuation function is monotone, then GS implies SI and SI implies NC and NC implies GS,[2] so these three conditions are equivalent.
The M♮-condition[3] comes from convex analysis (the symbol is the "natural" symbol similar to its use in music). It says that for all sets
X,Y
x\inX
u(X)+u(Y)\lequ(X\setminus\{x\})+u(Y\cup\{x\})
y\inY
u(X)+u(Y)\lequ(X\setminus\{x\}\cup\{y\})+u(Y\setminus\{y\}\cup\{x\})
The M♮-concavity property is also called M♮-exchange property.[4] It has the following interpretation. Suppose Alice and Bob both have utility function
u
X
Y
SI implies MX and MX implies SI,[3] so they are equivalent.
The SNC condition[2] says that, for all sets
X
Y
X'\subseteqX
Y'\subseteqY
u(X)+u(Y)\lequ(X\setminusX'\cupY')+u(Y\setminusY'\cupX')
The SNC property is also called M♮-multiple-exchange property.[4] It has the following interpretation.[2] Suppose Alice and Bob both have utility function
u
X
Y
X'
Y'
Note: to check whether u has SNC, it is sufficient to consider the cases in which
X'\subseteqX\setminusY
X' ≠ \emptyset
X' ≠ X\setminusY
Y'\subseteqY\setminusX
Kazuo Murota proved[4] that MX implies SNC.
It is obvious that SNC implies NC.[2] Proof: Fix an SNC utility function
u
p
A,B
D(u,p)
Up:=up(A)=up(B)
Up
A'\subsetA
B'\subseteqB
up(A\setminusA'\cupB)+up(B\setminusB'\cupA)\gequp(A)+up(B)=2 ⋅ Up
up(A\setminusA'\cupB)
up(B\setminusB'\cupA)
Up
Up
D(u,p)
We already said that NC implies GS which implies SI, and that[3] SI implies MX. 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. If we order the items by an ascending order of their price-increase, then the demand of a GS agents flows only downwards – from items whose price increased more to items whose price increased less, or from items whose price increased to items whose price decreased, or from items whose price decreased less to items whose price decreased more.
Formally, let
p,q
\Delta:=q-p
x
p
q
y
\Deltay<\Deltax
p
q
It is easy to see that DDF implies GS (GS is a special case of DDF in which
\Delta
The GS condition is preserved under price-changes. I.e, a utility function
u
p
u-p
Bundle | Value ($) | |
---|---|---|
\emptyset | 0 | |
x | 40 | |
y | 40 | |
z | 66 | |
x,y | 80 | |
x,z | 75 | |
y,z | 75 | |
x,y,z | 80 |
The converse is not necessarily true.[6] This is shown by the example on the right. 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:
px=py=10
pz=6
px=py=pz=10
px
px
px=py=pz=10
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:
for all integers
kx,ky
kx'\leqkx
ky'\leqky
u(kx)+u(ky)\lequ(kx-kx'+ky')+u(ky-ky'+kx')
kx'\leqky
ky'=kx'
kx'>ky
ky'=ky
u(kx)+u(ky)\lequ(ky+kx-kx')+u(kx')
u(kx'+[kx-kx'])-u(kx')\lequ(ky+[kx-kx'])-u(ky)
kx'>ky