Substitute Goods, Auctions, and Equilibrium ∗Paul Milgrom†

Bruno Strulovici‡

April 22, 2008

Abstract
This paper identifies two notions of substitutes for auction and equilibrium analysis. Weak substitutes, which is the usual price-theory notion, guarantees monotonicity of tâtonnement processes and convergence of clock auctions to a pseudoequilibrium, but only strong substitutes, which treats each unit traded as a distinct
good with its own price, guarantees that every pseudo-equilibrium is a Walrasianequilibrium, that the Vickrey outcome is in the core, and that the “law of aggregate
demand” is satisfied. The paper provides several primal and dual characterizations
and properties of weak and strong substitutes. When goods are divisible, weak
substitutes along with concavity guarantees all of the above properties, except for
the law of aggregate demand.

Keywords: Gross substitutes, tâtonnement, Pseudo-Equilibrium, Law of Aggregate Demand.
JEL Classification: D44, C62.

∗

We are grateful to John Quah and all participants of the Nuffield College Theory Workshop for usefulcomments. All remaining errors are our own. Financial support for Milgrom’s research was provided by
the National Science Foundation under grant ITR-0427770.
†
Department of Economics, Stanford University. Email: milgrom@stanford.edu.
‡
Nuffield College and Department of Economics,
Oxford University.
bruno.strulovici@economics.ox.ac.uk.

1

Email:

1

Introduction

Recent years have seen the growing use of simultaneous auctions for substitute goods likeelectrical power, natural gas, and certain agricultural contracts. Products available atdifferent but nearby times and places or with slightly different specifications are sometimes
included in a single product category to achieve a thicker market. Once categories of goods
are defined, the neoclassical model with its standard definitions can be applied: roughly,
two goods are substitutes in demand if increasing the price of one does not reduce thedemand for the other.
It can turn out, however, that small changes in the inclusiveness of a product definition
affects whether the various goods are substitutes according to the standard definition.
It is convenient to say that goods are weak substitutes when the substitutes condition issatisfied given a classification of the goods with a single price for each type of good andstrong substitutes when each item is regarded as distinct, potentially having its own price.
The biggest surprises in our analysis are that even in very ordinary-looking problems, thetwo notions of substitutes have very different implications for the analysis of auctions andequilibrium. It can even happen that identical goods fail to be price-theoretic substitutes
for one another.
We illustrate the possibilities with some simple examples. Consider a firm producing an
output whose price is normalized to one. Suppose that the firm’s output f (x, y) is afunction of two types of discrete inputs x ∈ {0, 1} and y ∈ {0, 1, 2}, as follows:f

y=0 y=1 y=2
√
x=0
0
1
2
√
x=1
1
1
2

In this example, the two inputs are substitutes (because f is submodular in its twoarguments) and there are nonincreasing marginal returns of each type of input. The firmchooses x and y to maximize f (x, y)−rx−wy. That the inputs are substitutes means thatwhen comparing any two price vectors p and p0 for which the firm’s optimum is unique,if p ≥ p0 and pi = p0i , then the demand for good i is weakly higher at prices p.
2

Next, consider an alternative formulation in which the two units of input y are treatedas distinct. Let y = y1 + y2 and suppose y1 , y2 ∈ {0, 1}. In this formulation, the prices
are also potentially distinct, so the firm maximizes f (x, y1 + y2 ) − rx − w1 y1 − w2 y2 .
It is as if we had distinguished blue and red versions of the input, where the color isdevoid of any consequences for production. It is easy to check that if the input prices
are (r, w1 , w2 ) = (0.2, 0.3, 0.2), then the firm’s unique profit-maximizing input vector is(0,1,1), but if (r, w1 , w2 ) = (0.2, 0.3, 0.7), then the profit-maximizing choice is (1,0,0).
This demonstrates that an increase in the price of input y2 reduces the demand for input
y1 : different units of the same type of good may fail to be substitutes.
Examples of this sort are hardly rare. For instance, an airline that is acquiring landing
slots at a hub airport may wish to have some number N of slots, for illustration N=2,
within a particular period, say from 2:00pm to 2:15pm or from 3:00pm to 3:15pm, so thatpassengers traveling on the same continuing flight can be scheduled to arrive at that flightat about the same time. Landing slots in the two time periods are weak substitutes ifwhen slots at 2-2:15 are expensive, the airline will substitute slots at 3-3:15. Slots withina given time period, however, need not be substitutes. As in our example, the airline
may demand both or neither. As in our example, this can happen even with diminishingreturns to additional slots in the same time period. Because clock auctions have been
proposed for just this sort of application, it is important to investigate how these auctions
perform in settings where slots are weak substitutes but not strong substitutes.
Despite the practical significance of the weak substitutes condition for applications likelanding slots, previous studies of ascending clock auctions, which have focused exclusively
on the strong substitutes case. Ausubel (2006, p. 617) mentions that his clock auction
design, which applies when goods are distinct and substitutes, can also be applied when
there are multiple units of each good.1 Gul and Stacchetti (2000) restrict their auction
design to nonidentical goods, in effect assuming strong substitutes.
One important difference between the weak and strong substitutes arises when studying
the existence of market-clearing prices. Using models in which goods are priced individu1

Bikhchandani and Mamer (1997, p. 391) go further: “In case there are multiple units of some objects,

one can expand the commodity space by treating each unit of an object as a different commodity. It may
be verified that market clearing prices exist in the original economy with multiple units per object if andonly if market clearing prices exist in the new economy with one unit per object. Moreover, the sets ofmarket allocations supported by equilibrium prices in the two economies (which may be empty sets) are
identical, except for relabelling.”3

ally, Gul and Stacchetti (2000) and Milgrom (2000) display monotonic auction processes
that converge to exact or approximate market-clearing prices.2 In those formulations,substitutes means strong substitutes: the equilibrium existence results do not extend tothe case of weak substitutes.
To illustrate the problem using our example, suppose that good y is treated as a single
class and that the available supply for the two classes of goods is given by the vector (1, 2).
Suppose that firm 1 has production function f as before, and that there is a second firmwith production function g(x, y) = 1y≥1 (thus, firm 2 is only interested in getting one unitof good y). At the efficient allocation, firm 2 uses one unit of y and firm 1 uses one unitof x. To induce firm 1 to make this choice, the price of input y must be strictly positive,
but then the total demand for good y will be only one unit: there is no market clearing.
Market clearing prices do not exist.
In our example, if the supply vector is anything else besides (1, 2), then not only does amarket clearing price vector exist, but more is true. First, the set of market clearing pricevectors is a sublattice. Second, a continuous tâtonnement or clock auction process beginning with low prices converges monotonically upward to the minimum market clearing
price vector. A similar process beginning with high prices converges monotonically downward to the maximum market clearing price vector. Similar conclusions have been derived
in the past using strong substitutes, but not for the weak substitutes of this example.
How does the clock auction perform when there are no market clearing prices? Supposethat firm 1 has valuation f as above, firm 2 has valuation v(x, y) = 0.05 × 1y≥1 , supply is(1, 1) and we initially set the input price vector to (0, 0). At that price there is strict excess
demand for good y but not for good x. The price of good y is gradually increased. Whenpy passes 0.05, firm 2’s demand drops to 0 units of good y, but firm 1 still demands 2 unitsof y, so there is still excess demand in y. Eventually, the price for y reaches a level p̄y at
which firm 1 is indifferent between buying one unit of x or two units of y, as determined√by the equation 1 = 2 − 2p̄y . At that price, firm 2 is indifferent between 0 and 1 unitof good x (since px = 0). Aggregate demand thus consists of the bundles (2, 1), (2, 0),(0, 1) and (0, 2), hence contains supply (1, 1) in its convex hull. This is an example ofa pseudo-equilibrium — a concept that can play an important role in both theory andpractice.3
2

These analyses are descendants of the Kelso and Crawford (1982) analysis of strict core allocations

in a labor market.
3
See Definition 11. As a matter of theory, pseudo-equilibrium characterizes the outcome of certain

4

Examples of this sort are also potentially significant for the design of activity rules in
auctions. These are rules that typically prevent a bidder from increasing its overall demand as prices increase.4 In our example, at prices (px , p1 , p2 ) = (.4, .4, .41), firm 1
demands (x, y1 , y2 ) = (0, 1, 1) while at prices (px , p1 , p2 ) = (.4, .5, .41), firm 1 demands(x, y1 , y2 ) = (1, 0, 0). Suppose these two price vectors represent successive prices in an ascending auction and that the next price vector is (.5, .5, .41). The firm’s demand now shifts
to (0, 1, 1): its total demand rises from 1 unit to 2 units. Hatfield and Milgrom (2005)
had shown that the strong substitutes property implies that, for a profit-maximizing firm,
the sum of the quantities of goods demanded does not increase as prices rise, a result theycalled the law of aggregate demand. Our example shows that activity rules can blockstraightforward bidding when goods are weak substitutes (but not when they are strong
substitutes).
These several observations herald more general results, which are the subject of this paper.
Section 2 defines weak-substitute valuations and strong-substitute valuations. Section 3
gives a useful characterization of these properties of valuations in terms of the firm’s dual
profit function. Section 4 further studies the two concepts of substitutes and how they
are related to each other and to other properties of demand.
Section 5 treats the implications of weak and strong substitutes for aggregate demand.
We show that the strong substitutes condition is sufficient and necessary (in a quantified
sense) for the robust existence of market-clearing prices and for Vickrey payoffs to be in
the core. The weak substitutes condition implies that the set of pseudo-equilibrium pricevectors is a non-empty sublattice, that this set coincides with the set of equilibrium prices
whenever an equilibrium exists
Section 6 presents our analysis of clock auctions when bidders have weak-substitute valuations. We first introduce a continuous-time model and show that weak substitutes isnecessary and sufficient for the monotonicity of a certain continuous tâtonnement-likeclock auction and implies that a continuous descending or ascending clock auctions terminates at a pseudo-equilibrium. We then show how the analysis can be applied to thecase in which prices follow small bid increments and bidders only need to announce one
ascending auctions. We will also find that the set of pseudo-equilibria coincides with the equilibrium set
when the latter is non-empty. In practice, pseudo-equilibria represent the closest one can come to fullmarket clearing. As in the example, small supply adjustments can sometimes be sufficient to convert apseudo-equilibrium to a real equilibrium, and real sellers are sometimes willing and able to adjust supply
to accomplish just that.
4
An exception is the revealed-preference activity rule of Ausubel and Milgrom (2002).

5

optimal bundle, rather than their entire indifference set of optimal bundles. Section 7
analyzes the case of divisible goods and finds a sharp contrast with the case of discrete
goods. Section 8 concludes.

2

Definitions

Consider an economy with K goods, in which good k is available in Nk units. Let X =Πk∈K {0, 1, . . . , Nk } and X̃ = Πk∈K {0, 1}Nk represent the space of possible bundles of theexchange economy in its multi-unit and binary formulations. The multi-unit formulation
only considers the aggregate quantity of each good, while the binary formulation treats
each unit of each good as a distinct good available in binary (0 or 1) amount. To any
bundle of the binary formulation, we can associate a bundle in the multi-unit formulation.
P kThis correspondence ϕ is defined formally as xk = ϕk (x̃) = N
j=1 x̃kj , i.e. by counting all
items in the binary vector x̃ corresponding to good k.
Definition 1 (Multi-Unit Valuation) A multi-unit valuation v is a mapping from
X into R.
Definition 2 (Binary Valuation) A binary valuation ṽ is a mapping from X̃ into R.
The binary valuation ṽ corresponds to the multi-unit valuation v, if for every x̃, ṽ(x̃) =v(ϕ(x̃)). We denote by V the space of multi-unit valuations and Ṽ the space of corresponding binary valuations. Corresponding binary valuation treat all units of any given goodsymmetrically, and hence Ṽ is strictly included in the set of all binary valuations. SimiNk
larly, let P = RK
+ and P̃ = Πk∈K R+ denote the respective price spaces of the multi-unit

and binary economies. The first price space permits only linear prices for each categoryof goods, while the second allows nonlinear prices for each class of goods. With nonlinear
prices, an agent who buys x units of some good will buy the x cheapest ones. Consequently, the marginal price faced by such agent is weakly increasing. Throughout the
paper, we assume that agents have quasi-linear utilities.
Assumption 1 (Quasi-linearity) The utility of an agent with multi-unit valuation v
acquiring a bundle x at price p is u(x, p) = v(x) − px. Similarly, the utility of an agent
with binary valuation ṽ acquiring a bundle x̃ at price p̃ is ũ(x̃, p̃) = ṽ(x̃) − p̃x̃.

6

Given a binary valuation ṽ and a price vector p̃ ∈ P̃, define the demand of the agent at
price p̃ by D̃(p̃) = arg maxx̃∈X̃ {ṽ(x̃) − p̃x̃}.
Similarly, we define the multi-unit demand D of an agent with valuation v as D(p) =arg maxx∈X {v(x) − px}.
With quasi-linear preferences, there is no distinction to be made between gross and net
substitutes, so we drop the modifier and make the following definitions.
Definition 3 (Strong-Substitute Valuation) A multi-unit valuation v is a strongsubstitute valuation if its binary form ṽ satisfies the binary substitutes property: for any
prices p̃ and q̃ in P̃ such that p̃ ≤ q̃, and x ∈ D̃(p̃), there exists a bundle x̃0 ∈ D̃(q̃) suchthat x̃0kj ≥ x̃kj for all (k, j) such that p̃kj = q̃kj .
Definition 4 (Weak-Substitute Valuation) A multi-unit valuation v is a weaksubstitute valuation if it satisfies the multi-unit substitutes property: for all prices pand q in P such that p ≤ q and x ∈ D(p), there exists a bundle x0 ∈ D(q) such thatx0k ≥ xk for all k in K = {κ ∈ K : pκ = qκ }.
The strong substitutes condition is at least weakly more restrictive than the weak substitutes condition, because the latter applies only for linear prices while the former applies
also for nonlinear prices. Moreover, the weak substitutes condition only compares unitsof distinct goods, while the strong substitutes condition requires that units of the same
good be substitutes. Section 1 illustrates that the two conditions are not equivalent. In
particular, weak-substitute valuations can violate the law of aggregate demand, but strong
substitute valuations cannot. An even simpler illustration of the difference is the case ofmultiple units of a single good. In that case, the weak substitutes condition is vacuous,
while strong substitutes imposes concavity, as shown by Theorem 9.

3Duality Results

To any multi-unit valuation v we associate the dual profit function π : P → R such that
π(p) = maxx∈X {u(x, p) = v(x) − px}. Similarly, to any binary valuation ṽ we associate
the dual profit function π̃(p̃) = maxx̃∈X̃ {ũ(x̃, p̃) = ṽ(x̃) − p̃x̃}.
Definition 5 (Multi-Unit Concavity) A multi-unit valuation is concave if it can beextended to a concave function on RK .
7

Theorem 1 Let v be a multi-unit valuation and π be its dual profit function. Then, forall x ∈ X , v(x) ≤ minp∈P {π(p) + px}. Moreover, v is concave if and only ifv(x) = min{π(p) + px} for all x ∈ X .
p∈P

Proof.

(1)

The first claim follows from the definition of π. The second claim is proved byapplying the separating-hyperplane theorem.



Ausubel’s and Milgrom’s dual characterization of strong substitute valuations extends
straightforwardly to the cases treated here.
Theorem 2 (Ausubel and Milgrom (2002)) v is a weak-substitute valuation if andonly if π is submodular, and this holds if and only if the dual profit function π̃ of thecorresponding binary form ṽ = φ(v) is submodular on the restricted domain where goodsof the same type have equal prices. In addition, v is a strong-substitute valuation if andonly if the dual profit function π̃ of its binary form ṽ = φ(v) is submodular.
Proof. The proofs of the two statements follow the proof of Theorem 10 in Ausubel and
Milgrom (2002).



The preceding theorem relies on the idea that one can characterize weak substitutes byfocusing on the subset PL of the price space in the binary formulation P̃ in which goods ofthe same type have the same price. This subset is isomorphic to the set P of linear prices
used in the multi-unit economy. The weak-substitute property then corresponds to therequirement that the dual profit function is submodular on PL , while the strong-substituteproperty requires submodularity on the whole price space. An immediate consequence of
this alternative formulation is the following:
Theorem 3 Any strong-substitute valuation is also a weak-substitute valuation.
The converse is not true. For example, suppose there is only one type of good, so thatevery valuation v is a weak-substitute valuation. Let v(0) = 0, v(1) = 1 and v(2) = 3
and suppose prices are (p1 , p2 ) = (1.4, 1.4), at which both units are demanded. Increasing
p1 to 1.7 would reduce demand to 0, thus violating the strong-substitute property. The
same example establishes that a multi-unit valuation can be submodular even when therelated binary valuation is not.
We have seen than weak-substitute valuations need not be submodular. The following
result shows that adding the requirement that v is concave does yield submodularity.
8

Theorem 4 Any concave weak-substitute valuation is submodular.
Proof.

From Theorem 1 v(x) = minp∈P {π(p) + px} = maxp {−π(p) − px}. From

Theorem 2, π is submodular. Therefore, v is the maximum over p of a function that issupermodular in p and −x, which implies that v is supermodular in −x or, equivalently,
submodular in x.



Theorem 5 Let ṽ be a strong-substitute valuation. Then ṽ(x̃) = minp̃∈P̃ {π̃(p̃) + p̃x̃}.
Proof.

Given x̃, define p̃ as p̃a = 0 if x̃a = 1 and p̃a = ∞ if x̃a = 0. Clearly, x̃ ∈ D̃(p̃).

The rest of the proof is identical to the proof of Theorem 1.

Underlying Theorem 4 is the fact that concavity allows v to be expressed by formula (1).
As Theorem 5 shows, concavity is not required in the binary form to obtain that equation.
Combining this observation with the same argument as in the proof of Theorem 4, provides
a direct explanation of why strong substitutes valuations are submodular.

4

Relations between Concepts of Substitutes

Gul and Stacchetti (1999) introduced the single-improvement property for binary valuations, which requires that if some vector x is not demanded at price vector p, then there
is a vector y that is strictly preferred to x and entails increasing the demand for at mostone good and decreasing the demand for at most one other good, as follows.
Definition 6 (Binary Single-Improvement Property) A binary valuation ṽ satisfies the single-improvement property if for any price vector p̃ and x̃ ∈/ D̃(p̃), there existsỹ such that u(ỹ, p̃) > u(x̃, p̃), k(ỹ − x̃)+ k1 ≤ 1, and k(x̃ − ỹ)+ k1 ≤ 1.
Gul and Stacchetti also showed that this single-improvement property is equivalent to thestrong substitutes property:
Theorem 6 (Gul and Stacchetti (1999)) A monotonic valuation is a strong-substitutevaluation if and only if it satisfies the binary single-improvement property.
We now extend these results to multi-unit economies.

9Definition 7 (Multi-Unit Single-Improvement Property) A valuation v satisfies the multi-unit single-improvement property if for any p and x ∈/ D(p), there exists x0
such that u(x0 , p) > u(x, p), k(x0 − x)+ k1 ≤ 1, and5 k(x − x0 )+ k1 ≤ 1.
The only difference in the definitions of binary and multi-unit single-improvement properties resides in the price domain where the property has to hold.
Throughout the paper, we will denote by ek the vector of RK whose k th component equals
one and whose other components equal zero.
Theorem 7 If v satisfies the multi-unit single-improvement property then it is a weaksubstitute valuation.
Proof.

Suppose by contradiction that the weak-substitute property is violated: there

exist p, k, a small positive constant ε, and a bundle x such that x ∈ D(p) and for ally ∈ D(p + εek ), there exists j 6= k such that yj < xj . Set p̂ = p + εek . We havex∈
/ D(p̂) and yk < xk for all y ∈ D(p̂) (since D(p) clearly contains bundles with strictly
less than xk units of good k). Therefore x is only dominated by bundles y that havestrictly less units of at least two goods, implying that k(x − y)+ k1 ≥ 2, which violates the
single-improvement property.



The converse in not true. In the first example of Section 1, the valuation is submodular
in a two-good economy, thus satisfies the weak substitutes property. However, for r = 0.2
and w = 0.3, the bundle (1, 0) is only dominated by the bundle (0, 2), which violates the
single-improvement property.
Definition 8 (Multi-Unit Submodularity) A multi-unit valuation v is submodular
if for any vectors x and x0 of X , v(x) + v(x0 ) ≥ v(x ∧ x0 ) + v(x ∨ x0 ).
The next theorem contains a key result for the existence of Walrasian equilibria in multiunit economies. The proof uses Gul and Stacchetti’s characterization theorem (Theorem 6) and thus requires monotonicity of v. Throughout the rest of the paper, we assume
that v is nondecreasing.
Assumption 2 Agent valuations are nondecreasing.
5

Here the norm is defined on RK , whereas it was defined on R

10

P

k Nk

in the binary setting.

Theorem 8 If v is a strong-substitute valuation, then any bundle x is optimal at somelinear price.
Proof.
Let x be any bundle, and x̃ be a binary representation of this bundle. From Theorem 5,
we have
v(x) = ṽ(x̃) = min{π̃(p̃) + p̃x̃}.
p̃

(2)

Since v is a strong substitutes valuation, π̃ is submodular, so the objective in (2) is
submodular. By a theorem of Topkis (1998), the set M of minimizers of a submodular
function is a sublattice and, since the objective is continuous, the sublattice is closed.
Therefore, it has a largest element p̃. We will first show that for any good k consumed inpositive amount (i.e. xk ≥ 1), p̃ki = p̃kj whenever x̃ki = x̃kj = 1. That is, the restriction
to good k of p̃ must be linear for the xk cheapest units of that good. We will then showthat this price linearity can be extended to the entire supply of good k without affecting
optimality of the bundle.
To show the first claim, suppose by contradiction that p̃ki 6= p̃kj for some units i, j ofsome good k such that x̃ki = x̃kj = 1. Then the price vector p̃0 equal to p̃ except for units
i and j of good k, where p̃ki and p̃kj are swapped, is also a minimizer of (2). Thereforep̃ ∨ p̃0 > p̃ is also in M , which contradicts maximality of p̃. We have thus shown that p̃ islinear on the “support” of x̃: for each good k there exists a price pk such that p̃ki = pk for
all i such that x̃ki = 1. Obviously, p̃kl = +∞ whenever x̃kl = 0, so the p̃ is not linear on
the whole supply. To prove the theorem, therefore, we need to show that price linearity
can be extended to those units of good k that are not consumed.
We now prove that x is optimal for the linear price vector p = (pk )k∈K , where pk = +∞when xk = 0, pk = 0 when xk = Nk , and pk is defined as above when 1 ≤ xk ≤ Nk − 1.
That is, we can impose p̃kl = pk for all units, including those for which x̃kl = 0, andpreserve optimality of x.
To show this, we first observe that for any good k such that xk ∈ {1, Nk − 1}, the firmmust be indifferent, at p̃, between x and some bundle y k such that ykk < xk , otherwise it
would be possible to increase pk , which would contradict maximality of p̃. We can choosey k so that it is optimal if we slightly increase the price of some particular unit of good k.
Since ṽ is a strong substitute valuation, we can choose y such that ykk = xk − 1, andyjk ≥ xj for all j. Since p̃kl = +∞ outside of the support of x̃, we necessarily have yjk = xj
11

for j 6= k. This shows that y k = x − ek . Such indifference bundles exist for all goods ksuch that 1 ≤ xk ≤ Nk − 1.
Now, for all goods such that xk ∈ [1, Nk − 1], reset all unit prices outside the support of x̃
from +∞ to pk . This change does not affect optimality of x among bundles z such thatz ≤ x, and it does not affect indifference between x and the bundles y k . For any good k,
consider the bundle z k = x + ek . Since ṽ is submodular, Theorem 11 implies that v iscomponent-wise concave (see p. 14). Therefore, v(z k ) − v(x) ≤ v(x) − v(y k ) = pk , which
implies that z k is weakly dominated by x. Now for two goods k 6= j such that xk ≥ 1 andxj < Nj , consider the bundle z kj = x − ek + ej . We claim that z is also weakly dominatedby x. To see this, we use the following Lemma, whose proof is in the Appendix.6
Lemma 1 If v is a strong-substitute valuation, k and j are two goods and x is a bundle
such that xk ≤ Nk −1 and xj ≤ Nj −2, then v(x+ek +ej )−v(x+ek ) ≥ v(x+2ej )−v(x+ej ).
Applying Lemma 1 to the bundle x − ej − ek yields v(x) − v(y j ) ≥ v(z kj ) − v(y k ), which
implies, along with v(x) = v(y j ) + pj = v(y k ) + pk , that v(x) − pk ≥ v(z kj ) − pj . Thus,x weakly dominates z. This shows that x̃ has no single improvement. From Theorem 6,ṽ satisfies the single-improvement property. Therefore, x̃ must be optimal at the linear
price p̃ such that p̃kl = pk for all l ∈ {1, . . . , Nk }. Equivalently, the bundle x is optimal
at price p = (pk ), which concludes the proof.



We can now state the properties of strong-substitute valuations in linear-pricing economies.
Theorem 9 Suppose that v is a strong-substitute valuation. Then it satisfies the following properties:[Concavity] v is concave.
[Weak-Substitute Property.] For any p ∈ P, k ∈ K, ε > 0, and x ∈ D(p), there exists
x0 ∈ D(p + εek ) such that x0j ≥ xj for all j 6= k.
[Law of Aggregate Demand.] For any p ∈ P, k ∈ K, ε > 0, and x ∈ D(p), there exists
x0 ∈ D(p + εek ) such that kx0 k1 ≤ kxk1 .
[Consecutive-Integer Property.] For any p ∈ P and k ∈ K, the set Dk (p) = {zk : z ∈D(p)} consists of consecutive integers.
6

As can be easily checked, the proof of Lemma 1 is independent of the proof of the present theorem.

12

Proof.

Theorem 3 implies that v satisfies the weak-substitute property, and Hatfieldand Milgrom (2005) show that v must satisfy the law of aggregate demand. Therefore, itremains to show that v is concave and satisfies the consecutive-integer property.
We first show that v is concave. Theorem 8 implies that for any x there exists p such that
π(p) = v(x) − px, where π is the dual profit function defined in Section 3. From the firstpart of Theorem 1, v(x) ≤ minp π(p) + px. Combining the two equations above yields
v(x) = minp π(p) + px for all x. Applying the second part of Theorem 1 then proves thatv is concave.7
Last, we show the consecutive-integer property. Suppose by contradiction that there exist
p, k, and two bundles x and y in D(p) such that xk ≥ yk +2 and z ∈ D(p) ⇒ zk ∈/ (yk , xk ).
Consider the binary price vector p̃ that is linear and equal to pj for all good j 6= k, andthat equals pk for the first xk units of good k and +∞ for the remaining units of good k.
Clearly, there exist binary forms x̃ and ỹ of x and y that belong to D̃(p̃), and there isno bundle z̃ in D̃(p̃) such that zk ∈ (yk , xk ). If the price of one unit of good k is slightly
increased, the demand for good k thus falls directly below zk , implying that the demandof another unit of good k, whose price had not increased, has strictly decreased, which
violates the strong-substitute property for ṽ.



The consecutive-integer property is not implied by concavity of v. For example, in a(multi-unit) two-good economy, concavity is compatible with the demand set D(p) ={(1, 0), (0, 2)}. However, this demand set violates the consecutive-integer property: theset D2 (p) = {0, 2} does not consist of consecutive integers. The consecutive-integer
property rules out valuations causing a sudden decrease in the consumption of a good(independently of the consumption of other goods). For example, there are no prices atwhich the firm is indifferent between bundles containing, say, 5 and 10 units of a good,but strictly prefers these bundles to any bundle containing between 6 and 9 units of that
good. In that sense, there are no “holes” in the demand set with respect to any good. In
terms of demand, the property implies a progressive reaction to price movements: as theprice of a good increases, the optimal demand of that good decreases unit by unit. By
contrast, concavity is not required for the law of aggregate demand.
Theorem 10 If v is a weak-substitute valuation that satisfies the consecutive-integer
property, then it satisfies the law of aggregate demand.
7

As can be easily verified, the proof of Theorem 1 is independent of the present proof.

13

Proof. See the Appendix.
The weak-substitute property and the law of aggregate demand do not imply the consecutiveinteger property. For example, in an economy with one good available in two units,
consider the non-concave valuation v(0) = 0, v(1) = 1, and v(2) = 4. v is trivially asubstitutes valuation, and satisfies the law of aggregate demand. However, at price p = 2,
the demand set is {0, 2}, which violates the consecutive-integer property. This is also an
example of a weak-substitute valuation that is not concave.
To obtain sharp results, we consider the concept of component-wise concavity, which
is weaker than concavity and entails diminishing marginal returns in each component
separately.
Definition 9 (Component-wise Concavity) A multi-unit valuation v is componentwise concave if for all x and k, v(xk + 1, x−k ) − v(x) ≥ v(xk + 2, x−k ) − v(xk + 1, x−k ).
Theorem 11 A multi-unit valuation v is submodular and component-wise concave if andonly if its binary form ṽ = φ(v) is submodular.
Proof. By a theorem of Topkis (1998), it is sufficient to consider binary bundles x and ythat differ in just two components. If the two components represent the same good, thensubmodularity of the binary form is the same as component-wise concavity. If the twocomponents represent different goods, then submodularity of the binary form is impliedby submodularity of the multi-unit form (and conversely).



The last three properties listed in Theorem 9 describe the demands corresponding to astrong-substitute valuation in linear-pricing economies. Even though strong-substitutevaluations are defined by their demands in response to nonlinear prices, the identified
properties turn out to be sufficient to characterize strong substitutes. That is the essential
content of Theorem 12 below.
Before proving this theorem, we state a new “minimax” result, in which one of the choice
set is a lattice and the other choice set consists of nonlinear prices. The proof of thisresult is in the Appendix.
If x is a multi-unit bundle and p̃ is a nonlinear price vector, let (p̃, x) denote the cost of
acquiring bundle x under p̃. That is,(p̃, x) =xkXXk∈K i=114p̃k(i) ,where p̃k(i) is the price of the ith cheapest unit of good k.
Proposition 1 (Minimax) Suppose that v is a concave weak-substitute valuation satisfying the consecutive-integer property, and let p̃ be a nonlinear price vector. Then,max min{π(p) + px − (p̃, x)} = min max{π(p) + px − (p̃, x)}
x

p

p

x

Theorem 12 Let v be a multi-unit valuation. The following properties are equivalent.
(i) v is a strong-substitute valuation.
(ii) v is a concave weak-substitute valuation, and satisfies the consecutive-integer property.

Proof. We know from Theorem 9 that (i) implies (ii). We now show that (ii) implies (i).
From Theorem 2, it is enough to show that π̃ is submodular. Consider any nonlinear pricevector p̃. We haveπ̃(p̃) = max{ṽ(x̃) − p̃x̃} = max{v(x) − (p̃, x)}.
xx̃Since v is concave, Theorem 1 implies thatπ̃(p̃) = max{min{π(p) + px} − (p̃, x)} = max{min{π(p) + px − (p̃, x)}}.
x

p

x

p

From Proposition 1, the max and min operators can be swapped:π̃(p̃) = min{max{π(p) + px − (p̃, x)}} = min{π(p) + max{px − (p̃, x)}}.
p

x

p

x

As can be easily verified, the inner maximum equals
NkXX(pk − p̃ki )+ .

k∈K i=1

Therefore,(π̃(p̃) = min π(p) +
p

Nk
XX

)
(pk − p̃ki )+.

k∈K i=1

Since v is a weak-substitute valuation, π is submodular by Theorem 2. Moreover, thefunction (x, y) → (x − y)+ is submodular as a convex function of the difference x − y.
Therefore, π̃(p̃) is the minimum over p of an objective function that is submodular in p
and p̃, which shows that it is submodular in p̃.8
8

See Topkis (1968).

15It turns out that, given concavity and the weak-substitute property, the law of aggregate
demand is equivalent to the consecutive integer property. Some of the main results above
are combined and extended in the following theorem.
Theorem 13 (Equivalence of Substitute Concepts) Let v be a multi-unit valuation. The following statements are equivalent.

(i) v satisfies the binary single-improvement property.
(ii) v is a strong-substitute valuation.
(iii) v is a concave weak-substitute valuation and satisfies the consecutive-integer property.
(iv) v is a concave weak-substitute valuation and satisfies the law of aggregate demand.
(v) v is concave and satisfies the multi-unit single-improvement property.

Proof.

(i) ⇔ (ii) is Gul and Stacchetti’s theorem (see Theorem 6). (ii) ⇔ (iii) is a

restatement of Theorem 12. Theorem 10 shows that (iii) implies (iv). For the converse,
the weak-substitute property implies9 for all p that any edge E of D(p) has direction ei or
ei − αej for some goods i, j. In the first case, concavity implies that all integral bundles on
the edge belong to the demand. In the second case, α = 1. Otherwise, slightly modifying
the price would reduce demand to that edge, and increasing pi if α > 1 or pj if α < 1would violate the law of aggregate demand. This, along with concavity, implies that theconsecutive-integer property holds along all edges, and thus for D(p). (i)−(iv) implies (v):(i) clearly implies the multi-unit single-improvement property, and (iii) implies concavity.
We conclude by showing that (v) implies (iii). We already know from Theorem 7 that
if v satisfies (v), then it is a weak-substitute valuation. Therefore, there only remains toshow that v satisfies the consecutive-integer property. Suppose it doesn’t. There exists
a price vector p, a good k, and a unit number d such that Dk = {zk : z ∈ D(p)} is splitby d: the sets Dk− = Dk ∩ [0, d − 1] and Dk+ = Dk ∩ [d + 1, Nk ] are disjoint and cover
Dk . Now slightly increase pk . The new demand set D0 is such that Dk0 ⊂ Dk− . Pick any
bundle y that is optimal under the new price within the set {x ∈ X : xk ≥ d}. Thenyk > d, because pk has only been slightly increased and any bundle with d units of goodk was strictly dominated by Dk+ . At the new price, y is dominated but cannot be strictly
9

See the proof of Proposition 1.

16

improved upon with reducing the amount of good k by at least two units, which violates
the single-improvement property.



The multi-unit single-improvement property alone is not equivalent to strong substitutes.
For example, in an economy with two goods available in two units, consider the valuation
v defined by v(x) = kxk1 − .1r(x), where r(x) equals 1 if x contains exactly one unitof each good, and 0 otherwise. The valuation is not concave, and therefore cannot be astrong-substitute valuation. However, one can easily verify that v satisfies the multi-unit
single-improvement property.
We conclude this section with a property of concave, weak-substitute valuations. For any(multi-unit) bundle x, let P(x) denote the set of price vectors such that x ∈ D(p).
Theorem 14 If v is a weak-substitute valuation, then for all x, P(x) is either the empty
set or the complete sublattice of P given by P(x) = arg min{π(p) + px}.
Proof. Fix x ∈ X . From Theorem 5, v(x) ≤ minp {π(p)+px}. Suppose that the inequality
is strict. Then v(x) − px < π(p) for all p, so P(x) is the empty set. Now suppose thatv(x) = minp {π(p) + px}. Then, for all p ∈ arg min{π(p) + px}, v(x) − px = π(p), sox ∈ D(p). Conversely, if x ∈ D(p̄) for some price p̄, then arg min{π(p) + px} = v(x) =π(p̄) + p̄x. Therefore, P(x) = arg min{π(p) + px}. From Theorem 2, π(p) is submodular.
Therefore P(x) is the set of minimizers of a submodular function over a sublattice P;
hence, it is a sublattice of P. Completeness is obtained by a standard limit argument. In the binary formulation, all bundles can be achieved through nonlinear pricing, bysetting some unit prices to zero and others to infinity. Therefore, Theorem 14 takes asimpler form. For any binary bundle x̃, let P̃(x̃) denote the set of price vectors such thatx̃ ∈ D̃(p̃).
Theorem 15 If ṽ is a binary valuation satisfying the strong substitutes, then P̃(x̃) is acomplete, non-empty lattice for all x̃ ∈ X̃ .
Proof.

For any bundle x̃, there exists a price p̃ such that x̃ ∈ D̃(p̃). Therefore, P̃(x̃) isnonempty. The rest of the proof is similar to the proof of Theorem 14.

17



5

Aggregate Demand and Equilibrium Analysis

The first theorem of this section extends results by Gul and Stacchetti and by Milgrom
asserting necessary conditions for the existence of Walrasian equilibrium in the binary
formulation. These theorems assume that individual valuations are drawn from a set that
includes all unit-demand valuations (Gul and Stacchetti), which are defined next, or all
additive valuations (Milgrom).10 They establish that if the set of valuations includes any
that are not strong substitutes, then there is a profile of valuations to be drawn from theset such that no competitive equilibrium exists.
These results are unsatisfactory for our multi-unit context, because they allow preferences
to vary among identical items and the constructions used in those papers hinge on that
freedom. The next theorem extends the earlier results by including the restriction thatfirms’ binary valuations are consistent with some multi-unit valuation, that is, that firms
treat all units of the same good symmetrically.
Definition 10 A unit-demand valuation is such that for all price p and x ∈ D(p),kxk1 ≤ 1.
Let N =P

k Nk denote the total number of units in the economy.

Theorem 16 Consider a multi-unit endowment X and a firm having a concave, weaksubstitute valuation v1 on X that is not a strong-substitute valuation. Then there exist I firms, I ≤ N , with unit-demand valuations {vi }i∈I , such that the economy E =(X , v1 , . . . , vI+1 ) has no Walrasian equilibrium.
Proof. See the Appendix.
Since preferences are assumed to be quasi-linear, one can conveniently analyze equilibrium prices and allocations in terms of the solutions to certain optimization problems.
With that objective in mind, consider an economy consisting of n firms with valuations{vi }1≤i≤n . The valuations vi are defined for {x ∈ NK : xk ≤ Nk ∀k ∈ K}. It is convenient
to extend the domain of vi by setting v(x) = v(min{x1 , N1 }, min{x2 , N2 }, . . . min{xk , NK })for all x in NK , where ∧ denotes the “meet” operator for the lattice structure induced by
10

An additive valuation is a valuation with the property that the value of any set is equal to the sumof the values of the singletons in the set.

18

the usual order. We now define the market-valuation v of the economy bynXoXKv(x) = maxvi (xi ) :xi = x and xi ∈ N.
and the market dual profit function of the economy by π(p) = maxx∈NK {v(x) − px}. The
function π is convex, as can be checked easily.
Theorem 17 For all p ∈ P, π(p) =P1≤i≤n πi (p).

Proof.
PP
π(p) = maxx {max{ i vi (xi ) : i xi = x} − px}P= maxx1 ,...,xn i {vi (xi ) − pxi }P= i πi (xi ),which concludes the proof.



Theorem 17 cannot be extended to nonlinear prices. To see this we observe, for example,
that the cheapest unit of a given good can only be allocated to a single firm when computing the market dual profit function, whereas it is included in all individual dual profit
functions involving at least one unit of this good. It is thus easy to construct examples
where the market dual profit function is strictly lower than the sum of individual dual
profit functions, the latter allowing each firm to use the cheapest units.
Corollary 1 If all firms have weak-substitute valuations, then the market valuation v
is also a weak-substitute valuation.
Proof. If individual firms have weak substitute valuations, Theorem 2 implies that individual profit functions are submodular. By Theorem 17, the market dual profit functionis therefore a sum of submodular functions, and so itself submodular. Theorem 2 thenallows us to conclude that v is a substitute valuation.

Definition 11 A price vector p is a pseudo-equilibrium price of the economy with endowment x̄ if p ∈ arg min{π(p) + px̄}.
Section 6 uses the following characterization of pseudo-equilibrium prices.
Proposition 2 p is a pseudo-equilibrium price if and only if the supply vector x̄ is in
the convex hull Co(D(p)) of D(p).

19

Proof.

By definition p minimizes the convex function f : p → π(p) + px̄. Therefore,

0 is in the subdifferential of f at p.11 That is, 0 ∈ ∂π(p) + x̄. The extreme points of−∂π(p) are bundles that are demanded at price p. Moreover, −D(p) ⊂ ∂π(p). Therefore−Co(D(p)) = ∂π(p). Combining these results yields x̄ ∈ Co(D(p)).

Let P(x̄) denote the set of pseudo-equilibrium prices.
Proposition 3 If all firms have weak-substitute valuations, then P(x̄) is a complete
sublattice of P.
Proof.

Individual weak-substitute valuations imply that πi is submodular for all i by

Theorem 2. Therefore, π is submodular. The proof is then identical to the proof of
Theorem 14.



Theorem 18 The economy with endowment x̄ has a Walrasian equilibrium if and only
if v(x̄) = minp {π(p) + px̄}. Moreover, if the economy with endowment x̄ has a Walrasianequilibrium, then the set of Walrasian equilibrium prices is exactly the set P (x̄) of pseudoequilibrium prices.
Proof. Theorem 1 implies that v(x̄) ≤ minp {π(x)+px̄}. Suppose that v(x̄) = π(p)+px forsome p. Let x̄i denote the bundle received by firm i for some fixed allocation maximizing
the objective in the definition of v. For all i, vi (x̄i ) − px̄i ≤ πi (p). Summing theseinequalities yields v(x̄) ≤ π(p) − px̄. By assumption, the last inequality holds as anequality, which can only occur if vi (x̄i ) − px̄i = π(p) for all i, implying that (p, x̄1 , ..., x̄n )is a Walrasian equilibrium. To prove the second claim, suppose that ({x̄i }1≤i≤n , p) is a
Walrasian equilibrium. Then, vi (x̄i ) = πi (p) + px̄i for all i. Summing these equalities
yields v(x̄) = π(p) + px̄, which implies that v(x̄) = minp {π(p) + px̄} (since the minimum
is always above v(x̄)). It is clear from the first part of the proof that if the economy has a
Walrasian equilibrium, the set of Walrasian prices is exactly the set of pseudo-equilibrium
prices.



Theorem 18 shows that whenever a Walrasian equilibrium exists, the concepts of pseudoequilibrium and equilibrium coincide. In binary economies, where nonlinear pricing isavailable, the question of the existence of a Walrasian equilibrium have been solved by
Gul and Stacchetti (1999) and Milgrom (2000), who both show that equilibrium exists in
11

See for example Rockafellar (1970).

20

the binary formulation when goods are strong substitutes and establish the two partial
converses described above.
For the multi-unit formulation, we have already established the partial converse in Theorem 16. We now consider the other direction: we prove that strong substitutes implies theexistence of a Walrasian equilibrium with linear pricing. This result is then used to prove
the stronger theorem that strong-substitute valuations are closed under aggregation: if
all valuations satisfy strong-substitutes, then so does the market valuation.
Theorem 19 (Linear-Pricing Walrasian Equilibrium) In a multi-unit exchange
economy with individual strong-substitute valuations, there exists a Walrasian equilibriumwith linear prices.
Proof. Considering the binary form of the economy, Gul and Stacchetti (1999, Corollary1) have shown that the set of (nonlinear pricing) Walrasian equilibria is a complete lattice.
In particular, it has smallest and largest elements. We now prove that these two elements
consist of linear prices, which proves the result. Suppose by contradiction that the largest
element p̃ is such that p̃ki 6= p̃kj for some units i, j of some good k. Then the price vectorp̃0 equal to p̃ except for units i and j of good k, where p̃ki and p̃kj are swapped, is alsoa Walrasian equilibrium. Therefore p̃ ∨ p̃0 > p̃ is also a Walrasian equilibrium, which
contradicts maximality of p̃. Linearity of the smallest element is proved similarly.

Corollary 2 (Concavity of Aggregate Demand) In a multi-unit exchange economy with individual strong-substitute valuations, the market valuation is concave.
Proof.

Denote by x the total endowment of the economy, and n the number of firms.

We show that for all y such that 0 ≤ y ≤ x, there exists a linear price vector p suchthat y is in the demand set of the market valuation. From Theorem 19, we already knowthat the result is true if y = x. Thus suppose that y < x. Consider an additional firmwith valuation vn+1 (z) = Kz ∧ (x − y), where K is a large constant, greater than the
total value of other firms for the whole endowment x. One can easily check that vn+1
is an assignment valuation, and therefore a strong-substitute valuation (see Hatfield andMilgrom (2004)). Applying Theorem 19 to the economy with (n + 1) firms, there exists a
Walrasian equilibrium with linear price vector p. At this price, the additional firm obtains
the bundle x−y since its marginal utility dominates all other firms’ for any unit up to thisbundle, and vanishes beyond this bundle. This implies that the remaining firms ask for yat price p, or equivalently, that y belongs to the demand set of n firms’ market valuation21

at price p. Concavity is then obtained as in the proof of Theorem 9.

Theorem 20 (Aggregation) If individual firms have strong-substitutes valuations, thenthe market valuation v is a strong-substitute valuation.
Proof. Let {vi }1≤i≤n denote the family of individual valuations and v denote the market
PP
valuation, defined by v(x) = max { i vi (xi ) : xi = x, xi ∈ N}. From Theorem 12, wewill prove the result if we show that v is a concave weak-substitute valuation that satisfies
the consecutive-integer property. Corollary 2 states that v is concave. From Corollary 1, v
is a weak-substitute valuation. It thus remains to show that v satisfies the consecutiveinteger property. For any price p, the demand set of v is the solution of
(
(
)
)
X
X
X
max{v(x) − px} = max max
vi (xi ) :xi = x − px =max vi (xi ) − pxi .
x

x

i

i

i

xi

P
Therefore, D(p) = i Di (p). In particular, the projection of D on the k th coordinatePsatisfies Dk =i Di,k . The sets Di,k consist of consecutive integers by Theorem 9,
implying that Dk also consists of consecutive integers.

Finally, we examine the connections between strong-substitute valuations and the structure of the core of the associated cooperative game. The setting considered in this sectionis the same as Ausubel and Milgrom (2002), but with the multi-unit formulation replacing
their binary formulation. We first recall the definitions of coalitional value functions, thecore, and Vickrey payoffs.
Suppose that, in addition to bidders, there exists a single owner (labeled “0”) of all unitsof all goods, who has zero utility for her endowment.
Definition 12 The coalitional value function of a set S of bidders is defined by
PPw(S) = max
xi ∈ X if 0 ∈ S, and w(S) = 0 otherwise.
i∈S vi (xi ) :Denote L the set consisting of all bidders and the owner of the goods.
Definition 13 The core of the economy is the set()
X
X
Core(L, w) = π ∈ RL+ : w(L) =πl , w(S) ≤πl for all S ⊂ L .
l∈L

l∈S

Definition 14 The Vickrey payoff vector is given by π̄l = w(L) − w(L \ l) for l ∈ L \ 0,P
and π̄0 = w(L) − l∈L\0 π̄l .
22

Ausubel and Milgrom (2002) show that this is the payoff at the dominant-strategy solutionof the generalized Vickrey auction.
Definition 15 The coalitional value function w is bidder-submodular if for all l ∈ L \ 0
and sets S and S 0 such that 0 ∈ S ⊂ S 0 , w(S) − w(S \ l) ≥ w(S 0 ) − w(S 0 \ l).
Theorem 21 Suppose that there are at least 2 + maxk Nk bidders. If any bidder has
a concave, weak-substitute valuation that is not a strong-substitute valuation, then there
exist linear or unit-demand valuations for remaining bidders such that the coalitional valuefunction is not bidder-submodular and the Vickrey payoff vector is not in the core.
Proof. See the Appendix.
Although related to a theorem by Ausubel and Milgrom (2002), Theorem 21 is different
because it requires a counter-example where bidders treat all units of any given good
identically (counter examples where two units of the same good have different values
for a bidder are not allowed). The converse result, which states that strong substitutes
are sufficient for the Vickrey payoffs to be in the core, is true. For that direction, thearguments provided by Ausubel and Milgrom (2002) go through because the arguments
do not hinge on intra-good symmetry, as checked by the following proof.
Theorem 22 If all bidders have strong-substitute valuations, then the coalitional valuefunction is bidder-submodular and the vector of Vickrey payoffs is in the core.
Proof.

From Ausubel and Milgrom (2002, Theorem 7), it is enough to show that thecoalitional value function is bidder-submodular. By assumption, the binary form ṽi ofeach bidder satisfies the substitutes property. Theorem 11 in Ausubel and Milgrom isvalid for the binary formulation and implies that the coalitional value function is biddersubmodular. This property is independent of the formulation (binary or multi-unit). 

6Walrasian Tâtonnement and Clock Auctions

This section analyzes auctions where goods are available in multiple units and prices
are linear. We propose a class of algorithms guaranteeing monotonic convergence of
the auction to a pseudo-equilibrium whenever bidders have weak-substitute valuations.

23

This result extends existing analyses where bidders have the more restrictive strongsubstitute valuations, as in Gul and Stacchetti (2000) and Milgrom (2000). Moreover,
we show that these algorithms generically work under the natural assumption, used inpractical designs, that bidders only submit demand singletons, as opposed to their entire
demand set.12 Combining these results with those of Section 5 shows that clock auctions
always converge to a Walrasian equilibrium whenever there exists one. For the present
analysis, we define a clock auction as a price adjustment process in which the path of prices
is monotonic—either increasing or decreasing. In practice this monotonicity and otherfeatures, especially activity rules for bidders (see Milgrom (2000)), differentiate clock
auctions from a Walrasian tâtonnement. In order to understand the relation between
substitute valuations and clock auctions, it is useful to start the analysis with Walrasiantâtonnement and only later to impose monotonicity on the process.

6.1

Continuous time and price

Our goal is to construct algorithms where i) prices increase over time, and ii) converge tothe smallest pseudo-equilibrium price p whenever bidders have weak-substitute valuations.
¯
Reverse algorithms, where price decreases and converges to the largest pseudo-equilibrium
price can similarly be constructed. By definition, pseudo-equilibrium prices minimize theconvex function f : p → π(p) + x̄p where π is the market dual profit function andx̄ ∈ NK is the supply vector. Among the general algorithms to find such minimizers aresteepest-descent algorithms. At any time, price changes are determined by the gradientof f whenever f is differentiable, and by the vector of smallest norm of its subdifferential
otherwise.13 Such algorithms amount to a particular Walrasian tâtonnement, as they
adjust prices to eliminate excess demand. For any price vector p, we denote by z(p) the
point of smallest norm in the opposite of the differential of f at p. When f is differentiable,z corresponds to the excess (aggregate) demand D(p) − x̄. In general, z is the vector ofsmallest norm in the convex hull of the set of excess demand.
Definition 16 A correspondence-based Walrasian tâtonnement (or simply “correspon12

In contrast, the Gul-Stacchetti algorithm requires that bidders report their entire demand set at

each time. When interpreted as an auction, the requirement that demand sets be reported makes theirprocedure different from any auction process in current use.
13
By definition, the subdifferential ∂f (p) at p of a convex function f is the set of vectors x such thatf (q) − f (p) ≥ x(q − p) for all q. The subdifferential is always a nonempty convex set, and coincides withf ’s gradient whenever it is differentiable.

24dence tâtonnement”) is a price-setting algorithm defined by some equation14 of motionṗr (t) = α(t, p(t))z(p(t)),(3)

where α is a continuous function taking values in [α, ᾱ] for some constants15 0 < α < ᾱ.
¯¯Let L = {p : p ≤ p and z(p) ≥ 0} denote the set of price vectors where all goods are in¯excess demand. The following theorem states that, starting any price in L, correspondencetâtonnements are well defined (i.e. from any initial price, it generates a unique trajectoryin the price space), monotonic, and converge to the lowest pseudo-equilibrium price, p.
¯In practice, the assumption that p(0) is in L is satisfied when the clock auction starts atzero price, but also any “reasonably low” prices.
Theorem 23 Correspondence tâtonnements are well defined. Suppose that bidders haveweak-substitutes valuations and that p(0) ∈ L. Then, for any correspondence tâtonnement,
the following holds: i) p(t) ∈ L for all t, ii) p(t) is increasing, and iii) p(t) converges top in finite time.
¯
The proof is in the Appendix. Theorem 23 implies that, when bidders have weaksubstitute valuations, any correspondence tâtonnement is an ascending clock auction
and converges to the smallest pseudo-equilibrium price. This result is of major importance for clock auctions, because it ensures that they always converge even with theweaker notion of substitutes. Formally, we define a correspondence (ascending) clock auction as a correspondence tâtonnement where prices can only increase: (3) is replaced byṗr (t) = α(t, p(t))z+ (p(t)), where z+ = max{z, 0} is the componentwise maximum between
the gradient z(p(t)) and 0.
Corollary 3 If bidders have weak-substitute valuations, any correspondence clock auction starting from a price in L converges to the smallest pseudo-equilibrium price.
In particular, if goods are weak substitutes, ascending clock auctions will find an equilibrium whenever there exists one. By contrast, it is easy to build examples of valuations
violating weak-substitutes such that a Walrasian equilibrium exists but ascending clock
auctions fail to find it.
14

The subscript “r” denotes right derivatives. Right derivatives are necessary to allow for discontinuities

in the smallest-norm gradient z(p).
15The lower bound α ensures that the algorithm does not stall at a suboptimal price, and the upper¯bound ensures that that the equation is integrable.

25

Our result extends Ausubel (2006) in three ways. First, it searches on the space of
linear prices, while Ausubel’s algorithm specifies separate prices for each unit of the good.
Second and more importantly, it relies only on the assumption of weak substitutes, where
Ausubel’s analysis requires on the stronger assumption of strong substitutes. Third, itshows that the process converges monotonically to a pseudo-equilibrium price, which
always exist in this setting and which are equilibrium prices whenever an equilibrium
exists.

6.2

Discrete time and priceIn actual auctions, prices are often restricted to lie on some grid. In such setting, time canbe decomposed in rounds between which prices are adjusted from one element of the gridto another. We now show that previous results are approximately true for fine enoughprice grids and that clock auctions still work if bidders only announce one desired bundleat each round, rather than their entire demand set. We emphasize again the importanceof this last result, since bidders do not submit their entire demand set in current practice.
A price grid is a lattice Pη = (ηN)K , where η is a small positive constant. A discretealgorithm generates a sequence of prices {pt : t = 0, 1, . . .} in Pη , whose evolution isdetermined by excess demand at any period. Even though prices are restricted to a grid,
they can follow the exact direction of the gradient z(p), which has rational coordinates,
provided the price step is large enough. Moreover, the thinner the price grid, and thesmaller the price step required to move along that direction (Lemma 6 in the Appendix
analyzes this point in detail). More importantly, the price sequence generated by a discrete algorithm may in principle diverge from the price path generated by its continuous
equivalent, because demand gradients are discontinuous functions of price. For example,
excess demand for one good can turn into excess supply if the price for that good is slightly
increased. Fortunately, Lemma 7 in the Appendix shows that such gradient discontinuities bear no significant consequences. Formally, it shows that trajectories of any discrete
steepest-descent algorithm that start close to each other stay close to each other. Thisimplies that any discrete algorithm closely follows its continuous equivalent (i.e. following
the same gradient rule, but where prices evolve in continuous time). For any price p0 ,denote by T (p0 ) = {p(t) : t ∈ R+ , p(0) = p0 } the trajectory generated by the continuous
correspondence tâtonnement of the previous section, and let T (p0 , ε) = ∪p∈T (p0 ) B(p, ε)26denote the tube16 of radius ε around T (p0 ).
Theorem 24 (Discrete Steepest-Descent Algorithm) For any ε > 0, there exist η > 0 and ᾱ > 0 such that for any grid finer than η, step size less than ᾱ, and initial
price p0 , the trajectory generated by the discrete steepest descent algorithm is contained in
T (p0 , ε).
The proof of Theorem 24 is in the Appendix. Finally, the above analysis allows us get
rid of the assumption that bidders submit their entire demand set. Bidder valuations
can be seen as vectors of the finite-dimensional space V = Rx̄ . Say that a property ofan algorithm holds for almost all economies if it holds for all bidder valuations except
for a subset of Lebesgue measure zero in V n , where n is the number of bidders. Let
us also define singleton-based algorithms in the same way as the correspondence-basedalgorithms, except that bidders ask only one bundle at each period. Concretely, this meansthat instead of using the vector of smallest norm in the excess demand set, the algorithm
may follow any vector of that set. The following result shows that this information loss
does not affect Theorem 24 except possibly on a set of economies with Lebesgue measure
zero.
Theorem 25 (Singleton-Based Algorithm) Under the assumptions of Theorem 24,
let p0 be any initial price of the algorithm. The trajectory of a singleton-based steepestdescent algorithm is contained in T (p0 , ε) for almost all economies.
The proof is based on the following proposition.
Proposition 4 For all (v1 , . . . , vn ) ∈ V n , the demand correspondence p → D(p) is
single-valued almost everywhere in P with respect to the Lebesgue measure on this set.
Proof.

Consider first one bidder with valuation v. For any two bundles x and x0 , thesubset P (x, x0 ) of P defined by P (x, x0 ) = {p : p(x−x0 ) = v(x)−v(x0 )}, is the intersectionof a hyperplane with the positive orthant P, and has therefore zero Lebesgue measure.
Since the number of possible bundles is finite, the set[
Q=
P (x, x0 ),
x6=x0

which contains all prices at which the bidder’s demand is multi-valued, also has zeroLebesgue measure. For a countable (in particular, finite) number of bidders, the set of
16

B(p, ε) is the open ball centered at p and radius ε.

27prices where aggregate demand is multi-valued is contained in Qa = ∪Qi , which has zeroLebesgue measure.

Proposition 4 implies that the set of economies such that Qa ∩ Pη 6= ∅ has Lebesgue measure zero. Therefore, singleton-based and correspondence-based algorithms are identicalfor almost all bidder valuations and price grids.
In practice, the auctioneer does not know bidder valuations. Theorem 25 implies thatfor any belief that is absolutely continuous with respect to the Lebesgue measure, thealgorithm is arbitrarily close to the continuous, correspondence-based steepest descentalgorithm of the ideal economy. In particular, the algorithm completely ignores bidders’indifference sets. This feature contrasts with Gul and Stacchetti (2000), whose algorithm
gives much importance to indifference sets.

7

Divisible Goods

For discrete goods, we showed that strong substitutes were sufficient and in some sensenecessary for several major results, such as i) the existence of a Walrasian equilibrium,ii) the fact that the Vickrey outcome is in the core, iii) submodularity of the dual profit
function over nonlinear prices, and iv) the law of demand. For divisible goods we define
a notion of substitutes based on nonlinear pricing17 guaranteeing that the first threeproperties above hold, but failing the law of demand and a natural generalization thereof.
We also show that this notion is equivalent to weak substitutes (i.e. based on linear
pricing), provided that valuations are concave. En route, we also show that concave
substitute valuations are characterized by submodularity of the dual profit function overnonlinear prices and are robust with respect to additive concave perturbations, which
extends a related notion of robustness established for complements, as in Milgrom (1994).

7.1

DefinitionsLet
X = Πk∈K [0, Xk ]17

Using nonlinear prices is not identical to treating goods individually, because treating goods as

distinct expands both the domain and the range of the demand correspondence, while only the domain
is changed by the switch to nonlinear pricing.

28

represent the space of possible bundles of the exchange economy. Throughout the paper,
we assume that agents have quasi-linear utilities: the utility of an agent with valuation v
acquiring a bundle x at price p(x) is u(x, p) = v(x) − p(x). The demand function of any
agent is defined by D(p) = arg maxx∈X {v(x)−p(x)}. To emphasize the difference between
the two notions of substitutes considered for divisible goods, we call them “nonlinear
substitutes” and “linear substitutes”, according to whether nonlinear pricing is allowed
or not. Linear substitutes is identical to the weak notion of substitutes used for discrete
goods, while nonlinear substitutes is closer to the stronger notion of substitutes (but see
footnote 17).
Definition 17 v is a linear-substitute valuation if whenever pj ≤ p0j , pk = p0k for all
k 6= j, and x ∈ D(p), there exists x0 ∈ D(p0 ) such that x0k ≥ xk for all k 6= j.
In the discrete case with individual item pricing, a rational consumer who buys k unitsof some type of good always buys the cheapest k units. Therefore, one way to describe
individual item pricing is to specify that the cost of acquiring goods is a convex functionof the number of goods acquired from each class and is additive across classes of goods.
Higher prices mean that the marginal cost of acquiring additional units is higher. This
characterization of the cost of acquiring goods and the corresponding representation ofhigher prices can be applied directly to the continuous case. That is the approach weadopt in this section.
Let C1 denote the space of convex functions from R+ to R which vanish at 0, and C = C1K .
An element of C contains K convex cost functions, one for each good. We endow C withthe following partial order: C  Ĉ if for all k, ck ≤ ĉk , where ck and ĉk are the derivatives
of Ck and Ĉk , respectively.18 With this order, C is a lattice, where for any C and Ĉ, themeet and the join satisfy, for all k and xk ≥ 0, (C ∨ Ĉ)0k (xk ) = max{ck (xk ), ĉk (xk } and(C ∧ Ĉ)0k (xk ) = min{ck (xk ), ĉk (xk )}, respectively.19 We extend the domain of any dual
profit function π from linear prices to C and denote π̄ its extension:π̄(C) = max{v(x) − C(x)},xwhere C(x) =18

P

k Ck (xk ).

These derivatives exist almost everywhere and are increasing by convexity of the cost functions (bythe Rademacher theorem, see Magaril-Ilyaev and Tikhomirov, 2003, p. 160). Marginal cost can beextended over the entire domain, for example by imposing right-continuity.
19
As can be easily checked, the marginal costs of (C ∧ Ĉ)0k and (C ∨ Ĉ)0k are nondecreasing for all k,
and constructed cost functions both vanish at 0, so that C ∧ Ĉ and C ∨ Ĉ belong to C.

29

Definition 18 v is a nonlinear-substitute valuation if whenever Cj ≤ Ĉj , Ck = Ĉk for
all k 6= j, and x ∈ D(C), there exists x0 ∈ D(Ĉ) such that x0k ≥ xk for all k 6= j.
For the discrete case, we have shown that there are several properties distinguishingweak substitutes and strong substitutes, so there is scope for judgment in creating theanalogue of strong substitutes in the continuous case. In place of strong substitutes, westudy the concept of concave, nonlinear-substitute valuations. This definition preservesproperties distinguishing strong substitutes from weak substitutes in the discrete setting,including robustness of the substitutes property with respect to nonlinear price changes
and existence of Walrasian equilibria.20 Moreover, we find below that these valuations
are characterized by dual submodularity on the domain of nonlinear prices, which was
also the characterization of strong substitutes in the discrete case. We find further that,given concavity, the linear-substitute and nonlinear-substitute properties are equivalent.
Therefore, our divisible-good extensions of the two concepts coincide in the case of concave
valuations. The next two theorems develop all of these relationships.
Theorem 26 (Dual Submodularity) If v is a concave linear-substitute valuation,then π̄ is submodular on C.
Proof.

Convexity of π and C implies that the function (p, x) 7→ π(p) + px − C(x) is

concave in x and convex in p. The minmax theorem (see e.g. Stoer and Witzgall (1970))
implies thatmax min{π(p) + px − C(x)} = min max{π(p) + px − C(x)}.
x

p

p

x

Concavity of v implies that v(x) = minp (π(p) + px) for all x. This, along with π̄(C)’sdefinition, implies thatπ̄(C) = max{min(π(p) + px) − C(x)}.
xpThis and the minmax theorem then imply thatnoπ̄(C) = min π(p) + max{px − C(x)} .
p

20

x

Another possible extension of strong substitutes would impose the law of aggregate demand. Thatis equivalent to requiring that a dominant diagonal property hold for the matrix [∂xi /∂pj ] of partial
derivatives of demand. Since all important properties (except of course for the law of demand itself) holdwithout this quantitative restriction, we do not follow this approach.

30

The inner maximum equals
XZ ∞(pk − ck (zk ))+ dzk .

0kTherefore,(π̄(C) = min π(p) +

XZ ∞

p

k

)
(pk − c(zk ))+ dzk.

0

We now show that the function h : (p, C) → h(p, C) =R∞0(p − c(z))+ dz is submodular on

R+ ×C1 . For q < r, h(r, C)−h(q, C) is the area of the region {(z, p) : p ∈ [q, r] and C(z) ≤Rrp}, which is also equal to q z(p, C)dp, where z(p, C) = sup{z : c(z) ≤ p}. Since z(p, C)
is nonincreasing in C for all p, so is h(r, C) − h(q, C), which proves submodularity of h in(p, C). Moreover, for any numbers p, c and d, (p − c)+ + (p − d)+ = (p − max(c, d))+ + (p −min(c, d))+ , which implies that h is modular in C. Linear substitutes implies that π is
submodular in p. Therefore, π̄ is the minimum over p ∈ P = RK
+ of an objective functionthat is submodular on P × C. This implies (Topkis (1998)) that π is submodular on C.
Theorem 26 allows us to prove the equivalence of three candidate definitions for thedivisible-good extension of strong substitutes.
Theorem 27 Suppose that v is concave. Then the three following statements are equivalent.
(i) v is a linear-substitute valuation.
(ii) v is a nonlinear-substitute valuation.
(iii) π is submodular on C.
Proof.

Clearly, (ii) implies (i). From Theorem 26, (i) implies (iii). To conclude theproof, we show that (iii) implies (ii). We fix a direction of price increase for some good,and show that along this direction, the demand for any other good is nondecreasing. Fix
goods j 6= k and a direction of increase δ (i.e. δ is nondecreasing, vanishes at 0, and issuch that C + δ is convex) for good j. Consider the restrictionπ̃(λ, µ) = max{v(x) − C(x) − λxk − µδ(xj )}xof π, defined21 on R+ × [0, 1]. Since π is submodular, so is π̃. π̃ is convex as the pointwise
maximum of a family of functions that are affine in (λ, µ). In particular, ∂ π̃/∂λ exists
21

The function C(x) + λxk + µδ(xj ) is convex for µ ∈ [0, 1], as can be easily checked.

31

almost everywhere. By an envelope theorem22 ∂ π̃/∂λ exists everywhere that demand forgood k xk (λ, µ) is a singleton and at those prices, ∂ π̃/∂λ = −xk (λ, µ). Submodularity ofπ̃ implies that ∂ π̃/∂λ(λ, µ) is nonincreasing in µ or, equivalently, that xk is nondecreasing
in µ.



Theorems 26 and 27 have an important consequence: concave nonlinear-substitute valuations are stable under perturbation by any concave modular function. Thus comparative
statics results are robust with respect to such perturbations, as stated in the following
theorem.
Theorem 28 If v is a concave nonlinear-substitute valuation, then v + f is a concave
nonlinear-substitute valuation for all f modular and concave.
Proof. Suppose that v is a concave nonlinear-substitute valuation. Then, v +f is concave
whenever f is concave. By Theorem 27, it remains to show that v +f is a linear-substitutevaluation. Let
xf (p) = arg max{v(x) + f (x) − px}.
x

Without loss of generality, we can assume that fi (0) = 0 for all terms of f . Let C(x, p) =px − f (x). Since f is modular and concave, C is modular and for each i, Ci is convex andvanishes at 0. Therefore, C belongs to C. Moreover, increasing pk implies increasing Ck .
Since v is a nonlinear-substitute valuation andxf (p) = arg max{v(x) − C(x, p)},xxfj (p) is nondecreasing in Ck , thus in pk .

We now turn to the consequences of the substitutes properties in settings with multiple
firms.

7.2

Multiple firms: Aggregation and CoreWe first show that both linear and concave nonlinear substitute valuations are closed
under aggregation.
Theorem 29 The class of linear-substitute valuations is closed under aggregation
22

Milgrom and Segal (2002), Corollary 4.

32

Proof. Suppose that individual firms have linear substitute valuations. Theorem 2, which
also holds for divisible goods, then implies that individual profit functions are submodular. By Theorem 17, the market dual profit function is therefore a sum of submodular
functions, and so itself submodular. Applying Theorem 2 once again, we conclude that v
is a linear substitute valuation.

With divisible goods, concavity is also closed under aggregation: the maximizationXv(x) = maxvi (xi )x

subject toPixi ≤ x has a concave objective function and a convex constraint function,

so v is concave23 in the constraint bound x. This shows the following result.
Theorem 30 Concave nonlinear-substitute valuations are closed under aggregation.
Proof. The above results show that concave linear-substitute valuations are closed underaggregation. This, along with Theorem 27, implies that the same is true of concave
nonlinear-substitute valuations.

With divisible goods, concavity suffices for the existence of a Walrasian equilibrium, sinceeach bundle is supported by a price vector. We show that if, in addition, firms havenonlinear-substitute valuations, then the Vickrey outcome is in the core. The setting anddefinitions of coalitional value function, core, Vickrey payoff, and bidder submodularity
are identical to those of Section 5.
Theorem 31 If all bidders have concave nonlinear-substitute valuations, the Vickrey outcome is in the core.
Proof. From Theorem 7 of Ausubel and Milgrom (2002), the Vickrey outcome is in thecore if the coalitional value function is bidder submodular. Therefore, we need to showthat w(S ∪{l})−w(S) is nonincreasing in S. Let x ∈ RK denote the supply vector. Then,w(S ∪ {l}) − w(S) = max{vl (x − y) + vS (y) − vS (x)},y≤xwhere vT (z) denote the optimal value of bundle z for coalition T (so that vT (x) = w(T )for all T ). Therefore, it is enough to show that vS (y) − vS (x) is non increasing in S or
simply that vS (z) is submodular in (−z, S). Concavity24 of vS implies thatvS (z) = min{πS (p) + pz},
p

23
24

See for example Luenberger (1969, p.216).
See discussion preceding Theorem 30.

33

(4)

where πS is the dual profit function of vS and is equal toPi∈S πi (p). Since π is submodular

in p, the objective in (4) is submodular in (−z, S, p). Hence, vS (z) is submodular in(−z, S), as required.

7.3



Law of Aggregate Demand

We have focused so far on monotone comparative statics of the demand function. In thediscrete case, strong substitutes not only implies that xj is nondecreasing in the price ofPother goods, but also that j xj (p̃) is nonincreasing in p̃, which is the discrete law of
aggregate demand. In this section, we show that this property no longer holds, and thus
is not necessary for Theorems 26 and 31 to hold.
What is the analogue of the law of aggregate demand for divisible substitute goods? One
problem is to determine the units in which such a law might be expressed. For example,
suppose that one unit of good i represents a 10-ride train pass between two cities, while
one unit of good j is a one-way bus ticket between the same cities. One expects that,starting from prices where a consumer chooses the train pass, a large price increase in
the train pass results in the consumer buying several bus tickets to replace the train
pass, implying that the sum xi + xj increases as pi increases, which violates the law of
aggregate demand. One way to pose the problem without units is to ask whether thereP
exist constants ai such that i ai xi be nonincreasing in prices? In the previous example,
a natural choice would be ai = 10 and aj = 1, given the relative similarity of a train trip
and a bus trip. More generally, we say that a valuation v satisfies the generalized law of
aggregate demand (GLoAD) if there exist increasing functions fi such thatXfi (xi (C))

i

is nonincreasing in C. It satisfies the law of aggregate demand if one can take fi (xi ) = xi
for all i. The GLoAD seems so much more flexible than the law of aggregate demandthat one is led to wonder whether it is satisfied by linear-substitute valuations, or at least
concave nonlinear-substitute valuations. However, the following theorem and its corollary
show that the GLoAD is equivalent to the law of aggregate demand up to a mere convex
re-scaling of goods. For the remaining of this section we assume that the cost functions arenondecreasing.25 To simplify the exposition, let (f ◦g)(x) = f (g1 (x1 ), . . . , gK (xK )), for any
25

This assumption if used in the proof of Theorem 32. We did not make this assumption earlier inorder to prove Theorem 28, where we consider C(x) = px − f (x) and f may be increasing.

34

function f and modular function g. Clearly, f ◦g is modular if f is also modular. Restricted
to the class of increasing modular functions, let f −1 denote the sum of component-wisePinverse functions: f −1 (x) = k fk−1 (xk ). For functions of one variable, these definitions
coincide with the usual ones. For the next two theorems, we assume that valuations arenondecreasing.
Theorem 32 Let v be a nondecreasing concave nonlinear-substitute valuation satisfying
the generalized law of aggregate demand for some function f , and g be an increasing,concave, modular function. Then ṽ = v◦g is a nondecreasing, concave nonlinear-substitutevaluation satisfying the generalized law of aggregate demand for the modular functionf˜ = f ◦ g.
Proof.

Since v and g are nondecreasing concave, so is ṽ. Let C̃ be a convex priceschedule, and y(C̃) = arg max ṽ(y) − C̃(y). We wish to show that yj is nondecreasing inC̃k for j 6= k, and that there exists an increasing modular function f˜ such that f˜(y(C̃))
is nonincreasing in C̃. The function γ = g −1 is increasing, convex, and modular. By
assumption, there exists a modular function f such that f (x(C)) is nondecreasing in
C, where x(C) is the demand of v at the convex price schedule C. Let C = C̃ ◦ γ.
Since all components of γ and C̃ are nondecreasing convex, so are the components of C.
Increasing C̃k to C̃k0 is equivalent to increasing Ck to Ck0 = C̃k0 ◦ γk . Therefore, if j 6= k,yj (C̃) = γj (xj (C)) is nondecreasing when C̃k increases. Moreover, letting f˜ = f ◦ g, wehave f˜(y(C̃)) = f (x(C̃ ◦ γ)), which is nonincreasing in C̃.

Corollary 4 Suppose that v is a nondecreasing, concave nonlinear-substitute valuation
satisfying the generalized law of aggregate demand for some convex function f . Then,ṽ = v ◦ f −1 satisfies the law of aggregate demand.
Thus, the generalized law of aggregate demand corresponds to a quantitative rather thana qualitative relaxation of the law of aggregate demand. In fact, it is possible to constructa concave nonlinear-substitute valuation that does not satisfy any generalized law of
aggregate demand. We construct a counter-example in the Appendix, which establishes
a fundamental difference between the cases of discrete and divisible goods.

35

8Conclusion

The substitutes concepts play a critical role in equilibrium theory. For discrete economies,
strong substitutes is necessary for the robust existence of equilibrium and weak substitutes
drive the monotonicity that is exploited by current auction algorithms. Strong substitutes
is also the condition that determines whether the Vickrey outcome is in the core. A
related concept–the law of aggregate demand–has been the informal justification for thewide adoption of activity rules in practical auctions. Among our findings is that the lawof aggregate demand is precisely the additional property that converts a concave weak
substitute valuation to a strong-substitute valuation when goods are discrete. Adapting
results from Hatfield and Milgrom (2005), it is also possible to show that strong substitutes
is necessary for the existence of stable matchings in their contracting model. The analysis
also showed that the two concepts of substitutes are closed under aggregation.
Section 7 extend the analysis to divisible goods. In particular, for divisible goods andconcave valuations, a natural extension of strong substitutes, which allows for nonlinear
pricing, coincides with weak substitutes. In that case, the law of aggregate demand andits unit-free extensions generally fail, but there always exists a Walrasian equilibrium, theVickrey outcome is in the core, and the dual profit function is submodular over the spaceof convex price schedules. Thus, for concave valuations, the law of aggregate demand
characterizes the difference between the cases of discrete goods and divisible goods.

9

Appendix: Proofs

9.1

Section 4

Proof of Lemma 1. Consider a bundle x such that xk ≤ Nk − 1 and xj ≤ Nj − 2. Takeany binary representant x̃ of x, and call l and m two units of good j not in x̃, and s aunit of good k not in x̃. Since ṽ satisfies the gross-substitute property, the triple{ṽ(x̃ + el + em ) − ṽ(x + el ) − ṽ(x̃ + em ), ṽ(x̃ + el + es ) − ṽ(x̃ + el ) − ṽ(x̃ + es ),ṽ(x̃ + em + es ) − ṽ(x̃ + em ) − ṽ(x̃ + es )} (5)has at least two maximizers. Symmetry of ṽ implies that the last two arguments of thatquantity are equal, and therefore greater than or equal to the first one. That is, written36

in multi-unit form v(x + ek + ej ) − v(x + ek ) − v(x + ej ) ≥ v(x + 2ej ) − 2v(x + ej) whichconcludes the proof after simplification.

Proof of Theorem 10. Suppose by contradiction that the law of aggregate demand isviolated: there exist k, p and x such that for all ε small enough, we have (i) x ∈ D(p−εek ),and (ii) for all y ∈ D(p + εek ), kyk1 > kxk1 . Clearly, for any such y, we have yk < xk .
Let Dk = Dk (p), d = min Dk and d¯ = xk = max Dk . By continuity, we have (i) x ∈ D(p),¯(ii) there exists some y ∈ D(p) such that yk < xk , and (iii) for all y ∈ D such that yk = d,¯kyk1 > kxk1 .
¯ →RFor each d ∈ Dk , define g(d) = min{ky−k k1 : yk = d and y ∈ D(p)}. Let γ : [d, d]¯denote the largest convex function such that γ(d) ≤ g(d) for all d ∈ Dk . The function γ¯ such thatis well defined and piecewise affine: there exists a partition ∆ = {δl }l∈Λ of [d, d]¯γ is affine on [δl , δl+1 ]. Moreover, d¯ and d are elements of ∆: there exist l and ¯l such that¯¯d = δl and d¯ = δl̄ . For l ∈ {l + 1, ¯l}, denote H(l) the hyperplane containing the two¯¯¯(K − 2)-dimensional affine varieties{z ∈ RK : kz−k k1 = γ(δl ) and zk = δl }and{z ∈ RK : kz−k k1 = γ(δl−1 ) and zk = δl−1 }.
There exists a unique hyperplane containing these two affine varieties, so H(l) is welldefined. Moreover, H(l) lies below D(p) and contains at least two elements z and y ofD(p) such that zk = δl and yk = δl−1 .
We claim that there exists l ∈ {l + 1, ¯l} such that γ(δl−1 ) − γ(δl ) > δl − δl−1 . Suppose that¯¯ ≤ d¯ − d = xk − d. But then, there exists y in D(p)the contrary holds. Then, γ(d) − γ(d)¯¯¯¯ ≥ d + γ(d) = kyk1 ,such that yk = d and ky−k k1 = γ(d), implying that kxk1 = xk + γ(d)¯¯¯¯which contradicts the hypothesized violation of the law of aggregate demand.
Consider an index l as in the previous paragraph, and modify p slightly so that the demand set becomes D(p) ∩ H(l). The price vector can be further modified so that theremaining bundles in the demand set are aligned on a unique straight line and, for the
new price p̄, there still exist z and y in D(p̄) such that zk > yk and kzk1 < kyk1 . There
are two cases: either there are two indices i and j such that yi > zi and yj > zj , or there
exists an index i such that yi − xi > xk − yk . Since optimal bundles are aligned, thesame properties hold for the extremities bundles of the segment containing D(p̄), so we
assume without loss of generality that z and y are these extreme bundles. In the first37

case, increasing pi slightly violates the weak-substitute property, as the optimal quantityof good j also decreases. In the second case, the convex-demand property is violated: theset Di (p̄) contains a hole between zi and yi .

Proof of Proposition 1 Trivially,

max min{π(p) + px − (p̃, x)} ≤ min max{π(p) + px − (p̃, x)}.
x

p

p

x

(6)

We need to prove that the reverse inequality also holds. We fix p̃ throughout the proof.
Consider a price p solving minp maxx {π(p)+px−(p̃, x)}. Let N (p) = arg maxx {px−(p̃, x)}.
N (p) is a hyper-rectangle: there exist two bundles r and R with r ≤ R such that N (p) ={z ∈ ZK : r ≤ z ≤ R}.
Suppose that there exists a bundle x in N (p) ∩ D(p). Then, the right-hand side of (6)equals π(p) + px − (p̃, x) = v(x) − (p̃, x), where the last equality comes from the fact thatx belongs to D(p). Now consider any linear price vector q. We have π(q) + qx − (p̃, x) ≥v(x) − (p̃, x), by definition of π(q). This last inequality implies that the left-hand sideof (6) is actually greater than or equal to its right-hand side. Therefore, we will haveconcluded the proof if we show that N (p) ∩ D(p) is nonempty, which we now turn to.
Let Co(D(p)) and Co(N (p)) denote the convex hulls of D(p) and N (p). We first showthat Co(D(p)) ∩ Co(N (p)) has a nonempty intersection. Suppose by contradiction that
Co(D(p)) ∩ Co(N (p)) = ∅.

Then, since these two sets are closed and convex, theseparating-hyperplane theorem implies that there exists a direction δ and a number asuch that yδ < a for y ∈ N (p) and xδ > a for x ∈ D(p). Now modify p by an
infinitesimal amount along the direction δ, yielding a new level q = p + εδ. The objective function π(p) + maxz {pz − (p̃, z)} is affected by this change in two ways. First,
through the sensitivity of π with respect to p. Taking any x ∈ D(q) ⊂ D(p), we haveπ(p) = v(x) − px and π(q) = v(x) − qx. Therefore, the change of π is −εxδ. Second,through the sensitivity of maxz {pz − (p̃, z)} with respect to p. There exists y ∈ N (p) suchthat maxz {pz − (p̃, z)} = py − (p̃, y) throughout the price change. Therefore, the effect on
this term equals εyδ. The overall change of the objective function is then ε(y − x)δ < 0,
implying that q leads to a strictly lower objective function than p, which contradicts
optimality of p.
We have proved that the sets Co(D(p)) and Co(N (p)) have a non empty intersection. We
38now prove that this intersection contains a point with integer coordinates. Consider any
polytope of RK . We say that an edge (i.e. a segment joining two vertices of the polytope)
is simply oriented if either (i) it is parallel to one coordinate axis {λei : λ ∈ R} of thespace or (ii) there exist two coordinates i and j such that the edge is parallel to ei −ej . We
say that a polytope is simply oriented if all its edges are simply oriented. Last, we recall
that a polytope all of whose vertices have integer coordinates is called a lattice polytope.
Lemma 2 If a lattice polytope P is simply oriented, and H is the half space {x : xk ≥ q},
where k ∈ {1, . . . , K} and q is an integer, then P ∩ H is either the empty set, or a simply
oriented, lattice polytope.
Proof.

Suppose that Q = P ∩ H is nonempty. Its vertices are either vertices of P , inwhich case they are integral, or new vertices belonging to H. We prove that any suchvertex also has integer coordinates. Any new vertex x is the intersection of H with anedge E of P that is not parallel to H. In particular, there exists an integral vertex y of
P such that x − y is parallel to E. Moreover, yk 6= q, since the edge is not parallel to H.
The edge is either parallel to ek or to ek − ei for some i 6= k. In the first case, we have
xj = yj ∈ Z for all j 6= k and xk = q ∈ Z, so x has integer coordinates. In the second
case, xj = yj ∈ Z for all j ∈/ {i, k}, xk = q ∈ Z, and xi = yi + (yk − xk ) ∈ Z, so x also
has integer coordinates. We now prove that the edges of Q are simply oriented. Thus
consider an edge E of Q, joining vertices x and y. If either x or y are vertices of P , thenE is either an edge of P , or the result of such an edge being cut by H. In either case, it issimply oriented because P is simply oriented. If both x and y are new vertices, E is theintersection of a two-dimensional face F of P with H, where F is not parallel to H. F isdefined by two linearly independent edges E 0 and E 00 of P which are simply oriented, andat least one of which contains ek . Suppose first that either E 0 or E 00 , say E 0 , is orthogonal
to ek . Then it is easy to show that E is parallel to E 00 and therefore simply oriented. Now
suppose that both E 0 and E 00 have a nonzero k th component. Because they are linearly
independent, there exist i and j such that F is generated by ek − ei and ek − ej (where
the signs come from the fact that P is simply oriented). In that case, as can be easily
verified, E is parallel to ei − ej , and therefore simply oriented.



We observe that Lemma 2 still holds if the inequality sign is reversed in the definition ofH.
Co(D(p)) is a lattice polytope since D(p) consists of integral vectors. We now prove that
Co(D(p)) is simply oriented. Thus consider any edge E of Co(D(p)). There exists a
39

vector δ of RK such that E is included in some straight line ∆ = {x0 + λδ}λ∈R . We firstshow that δ has at most two nonzero components. Suppose on the contrary that δ has atleast three components, say i, j, and k. Without loss of generality assume that δi and δjare positive. Since E is a face of Co(D(p)), there exists an infinitesimal modification of
the price vector p, such that D(p) = E. Moreover, E contains two vectors x and y suchthat x − y = λδ for some λ > 0. If we slightly increase pi , x becomes suboptimal, so the
optimal quantity of good j decreases, which violates the weak-substitute property. Thus,δ has at most two nonzero components. We now prove that E is simply oriented. If δ
has only one nonzero component, the claim is trivial. Suppose that δ has two positive
components, say i and j. We show that δi = −δj . Since E has integer vertices, we canassume that δi and δj are integers.26 If δi δj > 0, slightly increasing pi reduces the optimalquantity of good j which violates the weak-substitute property. Thus, δi and δj have
opposite signs. Now suppose that |δi | < |δj |. This implies that for all integral vectors x
and y in E, we have |xj − yj | ≥ 2, which violates the consecutive-integer property. Thus,
δi = −δj , which concludes the proof.
We have shown that Co(D(p)) is a simply oriented lattice polytope. Since Co(N (p)) is a
hyperrectangle of the form {x ∈ RK : a ≤ x ≤ b} for some integral vectors a and b, wehave, denoting H(k, q)+ = {x : xk ≥ q} and H(k, q)− = {x : xk ≤ q},\(H+ (k, ak ) ∩ H− (k, bk )) .
Co(D(p)) ∩ Co(N (p)) = Co(D(p))
1≤k≤K

Iterating Lemma 2 2K times implies that Co(D(p)) ∩ Co(N (p)) is either the empty set
or a lattice polytope. Since we have already shown that this intersection is nonempty, it
must contain an integral point, which concludes the proof of Proposition 1.

9.2



Section 5

Proof of Theorem 16. We extend part of the proof of Theorem 2 in Gul and Stacchetti(1999) to a multi-unit context. By assumption, there exist a price vector p̄, a good k,
and bundles x and x0 such that (i) {x, x0 } ∈ D(p̄), (ii) x0k − xk ≥ 2, and (iii) for all z
in D(p̄), zk ∈/ (xk , x0k ). This implies that at the price p = p̄ − ηek , x is only dominatedby bundles z such that zk ≥ xk + 2. In particular, the single-improvement property isPviolated by x at price p. Therefore, any bundle y that solves minz k |xk − zk | subject to
u1 (z, p) > u1 (x, p) satisfies yk ≥ xk + 2.
26

See for example Korte and Vygen (2000).

40

Let ρ =Pj (yj −xj )+ . By hypothesis, ρ ≥ 2. Let ε =u1 (y,p)−u1 (x,p). Let I+ = {j : xj < yj },2ρ

I− = {j : xj > yj }, and I0 = {j : xj = yj }. If j ∈ I+ , introduce Nj − yj firms, call them
“Cj ”, with unit-demand valuation v1 (X ) + 2 for a single unit of good j. If j ∈ I+ \ {k},introduce yj − xj firms, call them “cj ”, with unit-demand valuation pj + ε for a single unitof good j. If j = k, introduce yk − xk − 1 firms (“ck ”) with unit-demand valuation pk + ε
for a single unit of good k. If j ∈ I− , introduce Nj − xj firms (Cj ) with unit-demandvaluation v1 (X ) + 1 for a single unit of good j, and xj − yj firms (cj ) with unit-demandvaluation pj for a single unit of good j. If j ∈ I0 , introduce Nj −xj firms with unit-demandv1 (X ) + 1. Last, introduce a special firm, “firm 2”, with unit-demand pk + v1 (X ) + 1 fora single unit of good k.
Now suppose that there exists a Walrasian equilibrium with price vector t, and let Xidenote the bundle of the equilibrium received by firm i. Necessarily, (X1 )j ≥ min{xj , yj }for all j, since even if all unit-demand firms get one unit, there remain min{xj , yj } unitsof good j. Define a new price vector as follows: qj = tj for j ∈/ I− and qj = pj for j ∈ I− .
For j ∈ I− , Nj − xj units go to firms Cj . The remaining xj units are shared between
firm 1 and firms cj , with at least yj units for firm 1. Now, if firm 1 has none of theremaining xj − yj units, it means that tj ≤ pj , and this share remains optimal when tj isincreased to pj . If firm 1 has all of the remaining units, it means that tj ≥ pj , and thisshare remains optimal when tj is decreased pj . If firm 1 has only a part of these remaining
units, it means that tj is already equal to pj . Thus (X, q) is also a Walrasian equilibrium,
such that X1 ≥ x ∧ y. Moreover, all Cj get their units, so that X1 ≤ x ∨ y. Thereforex ∧ y ≤ X1 ≤ x ∨ y.

(7)

Firm 2 necessarily gets a unit of good k ∈ I+ . Therefore, X1k < yk . This, togetherPPwith (7), implies that k |xk − X1k | < k |xk − yk |, and thusu(X1 , p) ≤ u(x, p).

(8)Suppose that there exist some goods j in I+ such that X1j > xj . This implies thatqj ≥ pj + ε, since firms cj would otherwise want to get all the units. Combining theseprice inequalities with (8) yields u1 (X1 , q) < u1 (x, q), which contradicts optimality of X1
for firm 1.
Suppose instead that X1j ≤ xj for all j. Then, all units between xj and yj for j ∈ I+ are
consumed by firms cj and by firm 2. For j 6= k, this implies that cj have a positive value
for the good: qj ≤ pj + ε. For j = k, even though firm 2 takes one units of the yk − xk41

available units of k, the fact that yk ≥ xk + 2 implies that there is also a firm ck taking
one unit of good k, which implies that qk ≤ pk + ε. Since X1 = x on I+ and pj = qj
for j ∈
/ I+ , (8) implies u1 (X1 , q) ≤ u1 (x, q). Since qj ≤ pj + ε for all j ∈ I+ , the value
initially chosen for ε implies that u1 (x, q) < u1 (y, q), and thus u1 (X1 , q) < u1 (y, q), which
contradicts optimality of the bundle X1 for firm 1.

Proof of Theorem 21 From A&M Theorem 7 (which allows for multiple units ofgoods), the vector of Vickrey payoff vector is in the core if and only if the coalitional
value function is bidder-submodular. We show that under the assumptions of Theorem 21,
there always exist bidder valuations such that the coalitional value function is not biddersubmodular. Suppose that bidder 1’s valuation violates the consecutive-integer property.
There exist p̂ and k such that Dk (p̂) does not consist of consecutive integers. Let p =p̂ + εek for ε small enough. Then there exists x and z such that xk ≥ zk + 2, andv(z) − pz > v(x) − px > v(y) − py(9)for all y such that yk ∈ (zk , xk ). Introduce a second bidder with linear valuation v2 (x) =p−k x−k , and xk − zk unit-demand bidders who only value good k. The total number ofbidders is xk − zk + 2 ≤ Nk + 2 ≤ maxk Nk + 2. From (9), we havev(x) + p−k (x̄ − x)−k ≥ v(y) + p−k (x̄ − y)−k + pk (xk − yk )whenever xk − yk ≤ xk − zk − 1, andv(z) + p−k (x̄ − z)−k pk (xk − zk ) > v(x) + p−k (x̄ − x)−k .
Therefore, denoting S the set consisting of bidders 1, 2 and the xk − zk − 2 unit-demandfirms, and s and t the last two unit-demand bidders, we have w(S ∪ {s}) = w(S) andw(S ∪ {s, t}) > w(S ∪ {t}), showing that w is not bidder-submodular.

9.3



Section 6.1

Proof of Theorem 23. The proof is based on three lemmas, proving respectively
well-definedness, monotonicity, and confinement in L.
Lemma 3 (Well-definedness) The continuous SDA algorithm is well defined.
Proof. On any region of the price space where excess demand is constant, the algorithm
defines a straight trajectory of direction z, and is thus well-defined.27 The only possible
27

The scalar function α is immaterial, as long as it is bounded away from 0 and +∞.

42

problem, thus, is to rule out the possibility that there are infinitely many region changes
in an arbitrarily small amount of time. With the steepest-descent algorithm, the norm ofz is nondecreasing in time. Since z is constant over any region where aggregate demandis constant, and the norm of z strictly decreases each time it changes, any region that isleft is never visited again.

Lemma 4 (Monotonicity) When bidders have weak-substitute valuations and z(0) ≥0, p(·) is nondecreasing.
Proof.

Suppose by contradiction that z(t) fails to be nonnegative at some time t,

and take the smallest such time. Since z(0) ≥ 0, t > 0. By construction, z(s) ≥ 0
on a left neighborhood of t. Let m = z(t), x = z(t− ), and P be the opposite of thesubdifferential of f at p(t). P is a convex polytope, whose vertices are elements of theexcess demand at p(t), and m is the element of P with smallest norm. By assumption, x
is nonnegative. By continuity of demand, x must also belong to P . Let J = {k : mk < 0}.
By assumption, J 6= ∅. Let H be the affine hyperplane going through (the point) m
and orthogonal to (the vector) m. By assumption, P is on one side of H and touches
H at m. Let F be the largest face of P contained in H, y be any vertex of F , andPP
Cy = {z : J mk zk ≥ kmk2 − J c ms ys }. Since y − m is orthogonal to m, Cy is a conewith vertex y. We will show that Cy contains P but not x, a contradiction.
Since y − m is orthogonal to m, we have kmk2 −PJc

ms ys =P

J mk yk = mJ yJ , where theccomponents of mJ are equal to those of m on J and vanish on J , and a similar definitionP
for yJ . By convexity of F , m = y + l αl El , where {El } is the family of direction vectorsof the edges of F emanating from y. Taking the scalar product of the previous equalityPwith mJ yields mmJ = yJ mJ + l αl El mJ . We now prove that El mJ = 0 for all l. By
construction of F ,m.El = 0.

(10)

Moreover the weak substitute property implies that El has at most two nonzero components, and any two nonzero components are of opposite sign (see the proof of Proposition 1). If El has one nonzero component, it must be in J c , otherwise it would violate (10). If it has two nonzero components, then either they are both in J or both in
J c , for otherwise (10) would be violated. In any case, this implies that El .mJ = 0. Thus,P
mJ vJ = m2J > 0. In particular Cy = {z : J mk zk ≥ m2J }. Since the components of x
are nonnegative by construction, x cannot belong to Cy .
To conclude the proof, we show that Cy contains P . By convexity of P , it is enough to43

show that all edges of P emanating from y are going in the cone Cy . This will be the case
if we show that for any such edge with direction δ (away from y), we haveδmJ ≥ 0.

(11)

By definition of F , we have δm ≥ 0 (i.e. any edge from y must point outwards from H).
Since bidders have weak-substitute valuations, δ has at most two nonzero components.
Suppose first that it has exactly two components, δi and δj . If i, j are in J, then (11)trivially holds. If i, j are in J c , then (11) is an equality. If i ∈ J and j ∈ J c , then δm ≥ 0
and the fact that δi δj < 0 (by weak-substitutes) implies that δi < 0, and thus that (11)holds. If there is only one nonzero component, (11) holds trivially.



Lemma 5 (Confinement) If bidders have weak-substitute valuations, p(0) ≤ p and¯z(0) ≥ 0, then p(t) ≤ p for all t ≥ 0.
¯
Proof.

Suppose not: there exists a time t such that p(t) crosses the hyperrectangle

R = {z : z ≤ p} from inside out. In particular, the index subset I = {j : pj (t) = pj }¯¯
/ I. Moreover, p(s)  p for s in a rightis nonempty, and we have pj (t) < pj for j ∈¯¯neighborhood of t: there exists a nonempty subset J ⊂ I such that ps,j > pj for j ∈ J¯and s ∈ (t, t + ε). By construction of the algorithm, this means that the vector n ofsmallest norm in the opposite of the subdifferential of p(t) satisfies nj > 0 for j ∈ J.
We will contradict this statement by showing that the vector m defined by mj = nj forj∈/ J and mj = 0 for j ∈ J is in the opposite of the subdifferential. m’s norm is strictly
smaller than n’s, contradicting the assumption that n is of smallest norm in the oppositeof the subdifferential. By definition of the subdifferential, we need to show that, letting
p = p(t),m(q − p) ≥ f (p) − f (q)(12)

for all q. We first show this inequality in a neighborhood of p. By construction of n,n(q − p) ≥ f (p) − f (q) for all q. Therefore, (12) is automatically satisfied for q such thatqj ≤ pj for j ∈ J. Now consider the case where qj > pj for a subset J(q) of J. Consider
the vector q 0 such that qj0 = qj for j ∈/ J(q) and qj0 = pj for j ∈ J(q). Since we are ina neighborhood of p, qj ≤ pj for all j ∈/ J(q). This implies that q 0 ≤ p and, therefore,¯¯that q 0 = q ∧ p. Submodularity of f implies f (p ∧ q) + f (p ∨ q) ≤ f (p) + f (q). The¯¯¯¯inequality, combined with the fact that p is a minimum of f , implies that f (q 0 ) ≤ f (q).
¯
By construction of q 0 ,m(q − p) = m(q 0 − p) ≥ n(q 0 − p) ≥ f (p) − f (q 0 ) ≥ f (p) − f (q),44which concludes the proof on a neighborhood of p. To prove the result globally, consider
any vector q and let qλ = λq + (1 − λ)p where λ ∈ (0, 1). From the previous analysis,
we have for λ small enough m(qλ − p) ≥ f (p) − f (qλ ). By convexity of f , f (qλ ) ≤λf (q) + (1 − λ)f (p). Combining the previous two inequalities and dividing by λ yields
the result.



We now conclude the proof of the theorem. Since p(t) is nondecreasing and bounded, it
must converge to some limit in L. Since α is bounded away from zero, the rate of changeof p is bounded away from zero on any closed subset of the price space that does notcontain any pseudo-equilibrium price. Since the only pseudo-equilibrium price containedin L is p, this has to be the limit.
¯

9.4

Section 6.2

Let z(p) denote the vector of smallest norm in the convex hull of the excess (aggregate)
demand set D(p) − x̄.
Lemma 6 (Feasible directions of descent) Suppose that the number of bidders is
less than some constant N > 0, and that no bidder can demand more than overall supply
x̄. Then, for any grid Pη , there exists α(η) > 0 such that α(η)z(p) ∈ Pη for all p and all
bidder valuations. Moreover, α can be chosen such that α(η) → 0 as η → 0.
Proof. By assumption, the excess demand set is an integer polytope of RK , boundedby the rectangle [−x̄, N x̄]. Therefore, z can only take finitely many values. Since any
such z is the vector of minimum norm of an integral polytope, it has rational coordinates.
Therefore, its direction can always be achieved on any regular lattice. That is, there exists
a positive number α(z) such that α(z)z is the difference vector of two points of the lattice.
Moreover, the smallest such α(z) gets arbitrarily small as the grid gets arbitrarily thin.
Since there are finitely many values of z, maxz {α(z)} goes to zero as the grid thinness ηgoes to zero.

Let {p(t)}t∈N and {q(t)}t∈N denote the trajectories generated by a given steepest-descentalgorithm, starting from respective initial prices p(0) and q(0).
Lemma 7 (Nearness Lemma) Suppose that the number of bidders is less than someconstant N > 0, that no bidder can demand more than aggregate supply x̄, and that there
exists a vector M ∈ RK
+ such that bidders demand none of good i whenever pi > Mi .
45

Then, for any ε > 0, there exists η̄ > 0 and ᾱ > 0 such that for all η < η̄ and step sizes
less than ᾱ, kp(0) − q(0)k < ε implies kp(t) − q(t)k < ε for all periods and all bidder
valuations.
Proof. Without loss of generality, we can restrict attention to price vectors less thanM . Since the number of bidders is finite, the function f : p → π(p) + x̄p is piecewiseaffine, with finitely many regions. Moreover, directions of the hyperplanes supporting f
are determined by excess demand vectors, which take finitely many values (cf. proof of
Lemma 6). Since z is in the opposite of the differential of f , f (q) − f (p) ≥ z(p)(p − q) for
all q, with strict inequality if p and q are in distinct regions. The fact that p is boundedby M and that there are finitely many possible slopes for f implies the existence of aconstant ρ > 0 such thatf (q) − f (p) ≥ ρ + z(p)(p − q)(13)whenever p and q are not in the same region. We now consider paths of the discrete
steepest-descent algorithm starting from respective initial price vectors p0 and q0 , with
kp0 − q0 k < ε. Trajectories are parallel until the two prices reach different regions, andthus leave the vector pt − qt unchange until that time. Let s ≥ 0 denote the first timethat the two paths hit distinct regions. (13) implies f (qs ) − f (ps ) ≥ ρ + z(ps )(ps − qs ) andf (ps )−f (qs ) ≥ ρ+z(qs )(qs )−ps ). Summing these inequalities yields28 (z(ps )−z(qs ))(ps −qs ) ≤ −2ρ. Let α be the step size29 of the steepest-descent algorithm: ps+1 = ps + αz(ps ),and qs+1 = qs + αz(qs )kps+1 − qs+1 k2 = kps − qs k2 + kα(z(ps ) − z(qs ))k2 + 2α(z(ps ) − z(qs )) · (ps − qs ).
Therefore,
kps+1 − qs+1 k2 − kps − qs k2 ≤ −4ρα + O(α2 ),which is negative for α small enough, which we impose by appropriately setting ᾱ. Thus,
we have proved that kpt − qt k remains constant when prices are in the same region, anddecreases otherwise.

Proof of Theorem 24. Starting in the same region, trajectories of both algorithms
are initially undistinguishable, since gradients are identical. Let t0 denote the first timethat the trajectory T of the discrete algorithm overshoots, causing the two paths to have28

This proof strategy introduces a strict version of the theory of maximally monotone mapping. See

Rockafellar (1970).
29
The result holds if α depends on t and p, as long as it is continuous in p.

46

distinct vectors. Let  > 0 be a positive constant (to be chosen later), and denote by pt0
the price of the discrete algorithm, and by qt0 a price on T (p0 ) such that kpt0 − qt0 k < .
Such a price exists if the step size ᾱ(), which gives an upper bound on the overshoot, issmall enough. Let T1 denote the trajectory that the discretized algorithm would generate
if it were starting from qt0 . By construction T1 coincides with T (p0 ) until there is a second
overshoot. By the nearness lemma, T and T1 are within  from each other. Therefore,
when T1 overshoots, at time t1 , there is a price qt1 of T (p0 ) such that kp(t1 ) − qt1 k < 2.
Iterating the process, we thus prove that, up to the k th overshoot, we have T ⊂ T (p0 , k)
when T is truncated at t = tk . The number of overshoots is bounded above by the number
R of regions (since any region is visited at most once by the continuous algorithm, see
proof of Theorem 23). Therefore, the result obtains by setting  = ε/R.

9.5

Section 7

Counter-Example 1 There exist concave nonlinear-substitute valuations that do notsatisfy the generalized law of aggregate demand.
Proof. [Sketch] The example only requires two goods. Let x < x0 and y < y 0 be
positive numbers, and consider the bundles A = (x, y), B = (x0 , y), C = (x, y 0 ), andD = (x0 , y 0 ) and let (pi , qi ) be the supporting prices for i = A, B, C, D (such prices will
exist by concavity). If GLoAD held, there would exist some increasing functions f and gwith f (x(p, q)) + g(y(p, q)) nonincreasing in (p, q), where (p, q) is the price vector of thetwo goods and (x(p, q), y(p, q)) is the demand at that price. Suppose that at (pB , qB ) and(pC , qC ), a small increase in price p reduces x(p, q) by a very small amount and increases
y(p, q) by a very large amount (as in the ticket/pass example above). GLoAD can30 only
hold if f 0 (x0 ) is much larger than g 0 (y) (looking at B), and if f 0 (x) is much larger thang 0 (y 0 ) (looking at C). Now suppose that at (pA , qA ) and (pD , qD ), a small increase in
price q reduces y(q) by a very small amount and increases x(q) by a very large amount.
GLoAD can only hold if g 0 (y) is much larger than f 0 (x) (looking at A) and if g 0 (y 0 )much larger than f 0 (x0 ) (looking at D). These two sets of conditions are incompatible
proving that GLoAD cannot hold. To conclude the counter-example, it remains to showthat there exist concave nonlinear-substitute valuations satisfying the demand behavior
described at points A, B, C, and D. Demand variations are determined by the Hessianof the valuation at these points. As is easily checked, one can choose for each bundle
30

The proof is easily adapted if f and g are not differentiable at these points.

47

in {A, B, C, D} a Hessian matrix that is negative definite with negative cross derivatives
and that satisfies the demand behavior specified at that point. It is also possible toextend these Hessian matrices over the entire consumption space, while keeping negative
definiteness and negative cross derivatives. This construction is achieved by superpositionof four concave submodular functions, one for each bundle, whose Hessian coincides withthe specified Hessian at that bundle and vanishes around the three remaining bundles.31
Such Such superposition defines a valuation (up to an affine term) that is submodular
and concave. In two dimensions, submodularity implies the linear-substitute property.
By Theorem 27, the constructed valuation is therefore a concave nonlinear-substitutevaluation.



References
Ausubel, L. (2006) “An Efficient Dynamic Auction for Heterogeneous Commodities,”
American Economic Review, Vol 96, No. 3, pp. 602–629.
Ausubel, L., Milgrom, P.R. (2002) “Ascending Auctions with Package Bidding,”
Frontiers of Theoretical Economics, Vol. 1, No. 1.
Gul, F., Stacchetti, E. (1999) “Walrasian Equilibrium with Gross Substitutes,” Journal of Economic Theory, Vol. 87, No. 1, pp. 95–124.
Gul, F., Stacchetti, E. (2000) “The English Auction with Differentiated Commodities,” Journal of Economic Theory, Vol. 92, No. 1, pp. 66–95.
Hatfield, J., Milgrom, P. (2005) “Matching with Contracts,” American Economic
Review, Vol. 95, No. 4, pp. 913–935.
Kelso, A., Crawford, V. (1982) “Job Matching, Coalition Formation, and Gross
Substitutes,” Econometrica, Vol. 50, pp. 1483–1504.
Korte, B., Vygen, J. (2000) Combinatorial Optimization, Theory and Algorithms,
Springer-Verlag, Heidelberg.
Milgrom, P. (2000) “Putting Auction Theory to Work: The Simultaneous Ascending
Auction,” Journal of Political Economy, Vol. 108, No. 2, pp. 245–272.
31

For each of the four bundle, it is possible by Urysohn’s lemma to construct a continuous, matrix-

valued function that equals the desired Hessian at the bundle and vanishes outside an arbitrarily smallneighborhood of that bundle. See for instance Willard (1970).

48

Milgrom, P. (2004) Putting Auction Theory to Work, Cambridge University Press,
Cambridge, UK.
Milgrom, P., Strulovici B. (2006) “Concepts and Properties of Substitute Valuations
with Divisible Goods,” Working Paper.
Rockafellar, R.T. (1970) Convex Analysis, Princeton University Press, Princeton,
New Jersey.
Topkis, D.M. (1968) Ordered Optimal Solutions, Doctoral Dissertation, Stanford University, Stanford, CA.
Topkis, D.M. (1998) Supermodularity and Complementarity, Princeton University Press,
Princeton, New Jersey.

49