Gross substitutes (indivisible items)

For other uses, see Gross substitutes.

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)
$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: {apple,bread}. 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.

Definitions

The GS condition has many equivalent definitions.

Gross Substitutes (GS)

The original GS definition[1] is based on a price vector and a demand set.

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 and such that , and any , there is a such that (Y contains all items in X whose price remained constant).

Single Improvement (SI)

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 and bundle , there exists a bundle such that , and .

No Complementaries (NC)

The NC condition[2] says that every subset of a demanded bundle has a substitute. Formally: for any price vector and demanded bundles , and for every subset , there is a subset such that:

If the valuation function is monotone, then GS implies SI and SI implies NC and NC implies GS,[2]:117–120 so these three conditions are equivalent.

M# Concave (MX)

The MX condition[3] comes from convex analysis. It says that for all sets and for every item , at least one of the following must be true:

The M#-concavity property is also called M#-exchange property.[4] It has the following interpretation. Suppose Alice and Bob both have utility function , and are endowed with bundles and respectively. 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.

SI implies MX and MX implies SI,[3] so they are equivalent.

Strong No Complementaries (SNC)

The SNC condition[2] says that, for all sets and and for every subset , there is a subset such that:

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 , and are endowed with bundles and respectively. For every subset 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 and . And for these cases, we only need to search among bundles .

Kazuo Murota proved[4] that MX implies SNC.

It is obvious that SNC implies NC.[2] Proof: Fix an SNC utility function and a price-vector . Let be two bundles in the demand-set . This means that they have the same net-utility, E.g, , and all other bundles have a net-utility of at most . By the SNC condition, for every , there exists such that . But and are both at most . Hence, both must be exactly . Hence, both are also in .

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).

Downward Demand Flow (DDF)

The DDF condition[5] is reltaed 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 increase 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 be two price-vectors and let be the price-increase vector. If an item is demanded under and not demanded under , then there is another item with that is not demanded under and is demanded under .

It is easy to see that DDF implies GS (GS is a special case of DDF in which has only zero or positive values). [5] prove that MX implies DDF, so these conditions are all equivalent.

Preservation

The GS condition is preserved under price-changes. I.e, a utility function has GS, if-and-only-if for every price-vector , the net-utility function also has GS. This is easiest to see through the MC or SNC conditions, since it is evident that these conditions are invariant to price.

Properties

Submodularity

Submodular which is not GS
Bundle Value ($)
0
x 40
y 40
z 66
x,y 80
x,z 75
y,z 75
x,y,z 80

Every GS valuation is a submodular set function.[2] 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:

References

  1. 1 2 Kelso, A. S.; Crawford, V. P. (1982). "Job Matching, Coalition Formation, and Gross Substitutes". Econometrica. 50 (6): 1483. doi:10.2307/1913392. JSTOR 1913392.
  2. 1 2 3 4 5 6 7 8 Gul, F.; Stacchetti, E. (1999). "Walrasian Equilibrium with Gross Substitutes". Journal of Economic Theory. 87: 95. doi:10.1006/jeth.1999.2531.
  3. 1 2 3 Fujishige, Satoru; Yang, Zaifu (2003). "A Note on Kelso and Crawford's Gross Substitutes Condition". Mathematics of Operations Research. 28 (3): 463. doi:10.1287/moor.28.3.463.16393.
  4. 1 2 3 4 Kazuo Murota (2016). "Multiple Exchange Property for M#-concave Functions and Valuated Matroids". arXiv:1608.07021Freely accessible.
  5. 1 2 Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "Demand-flow of agents with gross-substitute valuations". Operations Research Letters. 44 (6): 757. arXiv:1607.01989Freely accessible. doi:10.1016/j.orl.2016.09.012.
  6. Ben-Zwi, Oren; Lavi, Ron; Newman, Ilan (2013). "Ascending auctions and Walrasian equilibrium". arXiv:1301.1153Freely accessible [cs.GT].
This article is issued from Wikipedia - version of the 10/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.