The Bidding Strategy in Proxied Package Auctions with
Complementarities∗
Ryuji Sano†
University of Tokyo
January 25, 2009

Abstract
This paper investigates the bidding strategy in a package auction underincomplete information. I consider a simpliﬁed and limited case, where eachbidder wants a unique bundle of the goods and evaluates them as perfect complements. The rule of the auction is a standard ascending auction with package
bidding but I adopt the “proxy bidding rule.” The auction is interpretted asa limited version of Ausubel and Milgrom (2002)’s ascending proxy auction.
Moreover, in some cases the rule of the auction also covers the combinatorialclock auction by Porter et al (2003). I derive the condition under which bidders
report their values truthfully in a Bayesian Nash equilibrium even when there’recomplementarities. Truthful reporting is optimal when bidders’ geographic relationships about thier wants are transitive. This result implies that package
auctions cannot implement eﬃcient outcome in almost every case of package
auction problems.
JEL classiﬁcation: D44, D82
Keywords: Package Auction, Complementarity, Incomplete Information, Ascending Proxy Auction, Bidding Strategy, Threshold Problem.

1

Introduction

Since the design of the auction of spectrum licenses by Federal Communication Commission, it is an important problem how to sell the multiple items those values areinterrelated. Some auction designs allow bidders to submit bids for packages of∗I am grateful above all to my adviser Professor Hitoshi Matsushima for many beneﬁcial comments and help. I would like to thank Professor Masaki Aoyagi and Professor Michihiro Kandori
for many comments and advice.
†
E-mail: ryujisano@gmail.com

1goods.1 Particularly, when there may be high complementarities among the goods,
it is said that auctions with package bidding will improve the eﬃciency.
Recent studies show that goods complementarities causes diﬃculty in both theory
and applications.2 From theoretical point of view, when goods may be complements,
often there is no mechanism that satisﬁes desired properties. Many familiar package
auctions are known not to satisfy incentive compatibility. However, because of its
complexity of rules and the vast strategy space, few studies have so far been madeat incentive structure of package auctions.
This paper formulates a model of a package auction, which is very simpliﬁed
and limited but incomplete information model with complementarities. And I limit
bidders’ strategy space by adopting a “proxy auction” rule and investigate bidders’
incentive properties in an ascending auction with package bidding.
I consider the case where each bidder evaluates goods as perfect complements.
That is, each bidder is interested in a unique bundle of goods and makes proﬁts only
when he obtains all of the goods in that bundle. For example, in a spectrum auction,
each mobile phone company has his business areas, and wants all of licenses covering
those areas. There will be no use for licenses out of his areas and for only a part oflicenses in the area.
The allocation of the goods is determined by an ascending package auction. And
I adopt the “proxy bidding rule.” In a proxy auction, bidders report their valuations
on goods to their agents. Agents participate in an ascending auction and raise bids
automatically up to maximum bids reported by bidders.3 Proxy auctions are said
to be more eﬀective against dishonest behavior such as collusions and shill biddings
than non-proxy auctions.4 Moreover, the proxy rule accelerates the implementationof the auction (Parkes (2006)). Proxy rule restricts strategy space and makes it easy
to analyze strategic behavior.
1
Milgrom (2004) explains the FCC auctions and the basic theory of single- and multi-object
auctions in detail. Parkes (2006) surveys theoretical and computational problems of iterative combinatorial auctions.
2
In real world problems, goods complementarities matter well. See Milgrom (2007) for the
diﬃculties in designing package auctions. Ausubel et al (1997) show the evidence of synergies in a
FCC spectrum auction.
3
A general model of a proxy auction with package bidding is introduced by Ausubel and Milgrom(2002). The model of this paper is a special case of their “ascending proxy auction.” See Ausubel
and Milgrom (2002, 2006).
4
The rich information structure and the vast strategy space of dynamic (ascending) auction canmake it possible for bidders to collude with each other and to lower prices. Brusco and Lopomo(2002) show there’s a collusive Bayesian Nash equilibrium in an ascending multi-object auction
without package bidding.

2

I show that bidders’ relationships about their wants, in other words, bidders’geographical relationships, take an important role in bidding strategy in an equilibrium. When some two bidders are interested in a same good, then they are rivalsof each other. The necessary and suﬃcient condition for each bidder reporting his
willingness to pay truthfully is the transitivity about these rival relations, i.e. anyrival of rival must be a rival. When this is not satisﬁed, a bidder has a friend whocompetes against a common rival. In package auctions, friends should cooperate inorder to outbid the common rival in general. However, a kind of a freerider problem
about their shares of payment arises in such a case. Bidders will underbid theirvalues to avoid large shares of the payment.
This freerider problem has been pointed as the “threshold problem” in the literature of package auction theory.5 The threshold problem is a coordination problem
between local bidders (friends). Local bidders can outbid global bidders (common
rivals) by coordinating their bids, but incentive to avoid large payment results ina coordination failure and they may not win the auction. This paper analyzes thisproblem under incomplete information and show that it’s a main problem of package
auctions.
One of the main contributions is that I formulate a limited model of package
auctions and analyze bidders’ incentive properties. In addition, I clarify the main
weak point of package auctions partially by the simpliﬁed model. I show that thefreerider problem in package auctions arises almost necessarily.
I start with viewing the limited model and the procedure of the auction using
an example in section 2. Section 3 provides the model and introduces the protocolformally. Section 4 analyzes incentive structure in the simplest case described in
section 2. In section 5 I formally deﬁne the “transitivity condition” and provide
main results.

2

The Procedure of the Auction

I start by viewing how the ascending auction procedes before deﬁning the model
formally. Consider that there’re two objects, {A, B}, and three bidders, {1, 2, 3}.
Bidder 1 wants only good A, while bidder 2 wants only good B. Bidder 3, on theother hand, wants both A and B and values zero for either of them alone. These
circumstances are illustrated in ﬁgure 1.
5

See Ledyard et al (1997) and Milgrom (2000) for example.

3

In the auction, ﬁrstly bidders report their maximal bids to their agents, or “proxies.” Then the proxies participate in an ascending auction submit bids up to thereported maximum values.
Suppose that bidder 1 and 2 report values of 4 and 2, respectively, to their proxies.
And suppose that bidder 3 reports 4 for the package of the goods, {A, B}.
Figure 2 illustrates the process of the ascending auction. In period 1, each (proxied) bidder submit 1 for the (set of) items. In each period, the auctioneer selects a
feasible revenue-maximizing bids and chooses provisional winners. In period 1, when
the seller allocates the goods for bidder 1 and 2, its revenue is 2. On the other hand,
if she allocates them to bidder 3, the revenue is only 1. So the auctioneer chooses
the allocation ({A}, {B}, ∅) and bidder 1 and 2 are provisional winners.
In period 2, only bidder 3 raises the bid to 2. Then (∅, ∅, {A, B}) is also a revenuemaximizing allocation, whose revenue is 2. Suppose the seller chooses the allocationin which bidder 3 wins.
In period 3, bidder 1 and 2 raise their bids and submit 2. The auctioneer allocatesthe goods to bidder 1 and 2. Now the revenue is 4. In period 4 and 5, bidder 3 raise
the bid up to 4. Suppose that the auctioneer selects the bid of bidder 3 in period 5.
In period 6, bidder 1 and 2 are going to raise bids. However, bidder 2’s bid has
already reached to 2, the maximal bid. So bidder 2 cannot raise his bids any more
and only bidder 1 raises the bid to 3. Then, bidder 3’s bid is already binding at the
maximal bid, 4, so the auction stops. In the ﬁnal allcation, bidder 1 gets A at 3,
bidder 2 gets B at 2, and bidder 3 gets nothing.

3

The Model and the Auction

A seller wants to allocate some heterogeneous and indivisible commodities among
a set of bidders. Let K = {1, . . . , k} be the ﬁnite set of goods for sale, which are
diﬀerent from each other. Let I = {1, . . . , n} be the set of all bidders. The seller, or
the auctioneer, is denoted by 0. All bidders and the seller are risk-neutral and havequasi-linear utilities. let K be the power set of K and let Xi be the set of bidder
i ’s possible packages, i.e. Xi ⊆ K. We assume ∅ ∈ Xi for all i ∈ I. vi : Xi → R+
denotes bidder i ’s value function. We normalize vi (∅) = 0 for all i ∈ I. Bidder i gets
his payoﬀ of vi (xi ) − pi (xi ∈ Xi ,) where pi is the monetary transfer to the seller.
x ≡ (x1 , . . . , xn ) denotes an allocation, and x is feasible if for ∀i, j ∈ I, xi ∩ xj = ∅∪and i∈I xi ⊆ K. Let X be the set of feasible allocations. Seller’s utility is the4revenue from the trades,

3.1

∑

pi .

Bidders’ Valuations

I impose some assumptions on bidders’ value functions. This paper assumes thatevery bidder values the items as perfect complements. And I consider the case where
each buyer’s private information is described as one-dimensional value. Following
assumptions can simplify the situation of complicated package auctions.
A1 (Perfect Complements) There exists a nonempty bundle of the goods Ki ∈ Xi
for each i ∈ I, which is the bidder i ’s region. And{vi if Ki ⊆ xi
vi (xi ) =, where vi ≥ 0.
0 otherwise
A2 (Known Regions) Each bidder’s region, Ki is publicly known to each other andthe seller, while vi is private information for bidder i.
A3 (Independent Values) Each bidder’s value, vi is drawn from some continuous
distribution on the interval [0, v¯i ] ≡ Vi independently.
The key assumption is Perfect Complements. It means that each bidder is interested in a unique package of the goods. When Ki contains more than one item, it
indicates that there’re perfect complementarities across these goods. Given PerfectComplements, Known Regions is not too restrictive. Even if each Ki is also private
information, if Perfect Complements is common knowledge and if the seller requests
potential bidders to report their regions before the auction, bidders will report theirregions truthfully. Given Perfect Complements and Known Regions, Independent
Values is standard in the literature of the auction theory.

3.2

The Auction, Strategy, and the Equilibrium Concept

Next I introduce the rule of the package auction. In the auction, each bidder instructs
a “proxy agent” that participates in a simultaneous ascending auction with package
bidding on his behalf. Firstly each bidder inputs a value function. Then the agent forbidder i bids straightforwardly according to the reported valuation. In other words,
proxy bidders behave as price-taker.
The proxy rule is adopted in many internet auctions, in which potential participants aren’t always involved. A package auction with proxy bidding is introduced by5

Ausubel and Milgrom (2002). The auction noted here is a simpliﬁed and limited version of the ascending proxy auction by Ausubel and Milgrom.6 Ausubel-Milgrom’s
proxy auction is deﬁned to have a discrete price increase rule and authers consider
the case where the price increment is negligibly small. I also deﬁne the auction withdiscrete price increases ﬁrst and then consider the case where the price increment
converges to zero.
I impose another assumption on bidders’ behavior in the auction in order tosimplify the analysis. I consider the case where bidders report not their value function(vi (·)) but only their values for their regions, vi . It forbid bidders to bid for any
packages that they don’t want.
A4 (No Cross-Bids) Xi = {∅, Ki } for all i ∈ I.7
Given these assumptions, the package auction is deﬁned as follows.
1. Each bidder inputs the valuation for his region, bi ∈ Vi .
2. At period 0, initialize x0i = ∅ and p0i = 0 for all i ∈ I.
3. At period t (≥ 1), the agent for bidder i bids pti on the package Ki and{
pt−1+ ² if xt−1
= ∅ and pt−1
+ ² ≤ bi
i
i
i
pti =
t−1
pi
otherwise
where ² > 0 is an exogenous bid increment.
4. The seller chooses a feasible allocation xt ∈ X that maximizes her revenue
under the price vector pt = (pti )i∈I . If there’re more than one allocation thatmaximize the revenue, she selects one of them randomly.
5. Repeat 3-4, and if pT = pT −1 , then the auction ends and xT is the ﬁnal
allocation. Bidders such that xTi = Ki win the package Ki with the price pTi .
I limit attention to the case in which the bid increment ² is negligibly small,and I consider the case of ² → 0 (and t increases continuously). In the appendix I
provide a class of ascending auctions with continuous price increase, which includes
6

The protocol of the ascending auction in the Ausubel-Milgorm auction is identical to iBundle
by Parkes and Ungar (2000). So our rule of the ascending auction is also same as iBundle.
7
It may veil some important part of strategic behavior in the package auction with high complementarities, cross-bidding. For example, when there’re complementarities, increasing the price forthe good B can reduce the demand for the good A. So the bidder who wants only the good A might
be able to kick out the global bidders earlier by bidding for the good B.

6the auction here. I describe the mechanism of the auction as (g, p). When the proﬁle()
of bidders’ reports is b = (b1 , . . . , bn ), the outcome is represented by g(b), p(b) ∈(X, Rn ), which speciﬁes the choice of the allocation x = g(b) ∈ X and the payment
pi = pi (b) ∈ R. The associated payoﬀs are given by ui (b; vi ) ≡ vi (gi (b)) − pi (b) for∑i ∈ I and u0 (b) ≡ pi (b) for the seller.
Bidder i ’s strategy is a mapping from bidder’s value to his bid: βi : Vi → Vi . I
call βi bidding function.8
I use the Bayesian Nash equilibrium as the equilibrium concept. It is convenient to deﬁne bidder’s interim expected payoﬀ given some other bidders’ strategies:
πi (bi , vi ) ≡ E[vi (gi (bi , β−i )) − pi (bi , β−i )|β−i ].
Deﬁnition. A proﬁle of bidding functions {βi }i∈I is a Bayesian Nash equilibrium if∀i ∈ I, ∀vi ∈ Vi , ∀bi ∈ Vi , πi (βi (vi ), vi ) ≥ πi (bi , vi ).
To rule out some unreasonable equilibria that consist of (weakly) dominatedstrategies, I only consider the equilibrium in which no strategy is dominated.
Deﬁnition. A strategy βi is (weakly) dominated if ∃β̂i : Vi → Vi , ∀vi ∈ Vi , ∀v−i ∈ V−i,u((βi (vi ), v−i ); vi ) ≤ u((β̂i (vi ), v−i ); vi ),and for some (vi , v−i ) strict inequality holds.
3.2.1

Basic Properties of the Auction

The model and the rule of the auction is a simpliﬁed version of Ausubel and Milgrom(2002)’s “ascending proxy auction.” Ausubel and Milgrom (2002, 2006) formulate
a general model of the package auction problem and investigate incentive undercomplete information and derive Nash equilibrium.9 Their results holds for the
package auction here too.
The crucial fact used here is that the auction computes an eﬃcient allocation withrespect to the reported preferences. When I consider the eﬃciency of the auction, it
is convenient to deﬁne the total value of the auction. Ausubel and Milgrom deﬁne
and use coalitional value function for treating the auction as a cooperative game. In

8

I consider only pure strategies and don’t think of mixed strategies.
Ausubel and Milgrom show that if goods are substitutes for all bidders, truthful reporting,βi (vi ) = vi , is a weakly dominant strategy of the ascending proxy auction.
97

my setting of incomplete information the total value depends on private information
explicitly.
Deﬁnition. Coalitional value function w : 2I ×
w(J, v) = max
x∈X

∑

∏

Vi → R + ,vj 1{xj ⊇Kj } .

j∈Jw(J, v) denotes the total value which every subset of bidders J ⊆ I can achieve by
allocating goods eﬃciently among them. Let w(∅, v) ≡ 0. By deﬁnition, w(J, v) does( ())
not depend on (vi )i6∈J , so that I often use the same notation w(J, v) as w J, (vj )j∈J , (ṽi )i6∈J
for arbitrary (ṽi )i6∈J , or sometimes I drop some of (ṽi )i6∈J for simple description.
Let v = (v1 , . . . , vn ) be a proﬁle of bidders’ values. And let ui (v; vi ) be bidder
i ’s payoﬀ when bidder i ’s bid is equal to his valuation for his region. Ausubel and
Milgrom show that the payoﬀ proﬁle u(v) ≡ (u0 (v), u1 (v; v1 ), . . . , un (v; vn )) is in thecore of the economy.
Theorem. (Ausubel and Milgrom (2002, 2006)) The payoﬀ proﬁle determined by
the auction is a core with respect to the reported preferences:u(v) ∈ Core(I ∪ {0}, v)
¯
{
}
∑
∑
n+1 ¯
≡ u ∈ R+ ¯ w(I, v) = u0 +
ui , w(J, v) ≤ u0 +uj for ∀J ⊂ I .
i∈I

4

j∈J

An Illustration

In this section I consider the 2-good and 3-bidder case again. Let K = {A, B},
I = {1, 2, 3}, K1 = {A}, K2 = {B}, and K3 = {A, B}. This simple model gives
intuition of main theorems in the next section.
In this case, we can specify the auction mechanism and describe the auction asa normal form game. Let bi be the bidder i ’s reported value. Then the mechanismof the auction is speciﬁed as{({A}, {B}, ∅) if b1 + b2 ≥ b3 10
g(b) =,(∅, ∅, {A, B}) otherwise

Precisely if b1 + b2 = b3 , winner(s) are determined randomly from {1, 2} and {3}. Winners will
have to pay pi = bi . It isn’t important how to deal with the tie-breaking here.
10

8



( 12 b3 , 12 b3 , 0)(b , b − b , 0)
1 3
1p(b) =

(b
−
b
,
b
3
2 2 , 0)(0, 0, b + b )
1
2

and

if min{b1 , b2 } ≥ 21 b3
if 2b1 < b3 ≤ b1 + b2.
if 2b2 < b3 ≤ b1 + b2
otherwiseFirst I note that bidder 3 has a dominant strategy of truthtelling. We can checkthis easily by following argument. Bidder 3 wins if and only if his report is bigger
than b1 + b2 and the amount of payment is determined by the highest rejected bid,
b1 + b2 . This rule is the same as the second-price auction. Hence truthful reportingis a weakly dominant strategy for bidder 3.
Next consider the strategy of bidder 1. Fix the (equilibrium) strategies of bidder
2 and 3; β2 and β3 . Bidder 1’s interim expected payoﬀ given his true value v1 andthe reported value b1 is
π1 (b1 , v1 ) = v1 Pr{b1 > β3 (v3 ) − β2 (v2 )} − b1 Pr{2b1 < β3 < b1 + β2 }1− E[ β3 1{2b1 ≥β3 , 2β2 ≥β3 } ] − E[(β3 − β2 )1{2β2 <β3 <b1 +β2 } ].
2
By diﬀerentiating by b1 and using β3 (v3 ) = v3 , we have the ﬁrst-order condition for
maximization,(v1 − b1 )φ(b1 ) − Pr{2b1 < v3 < b1 + β2 (v2 )} ≤ 0,

(1)

where equality holds when b1 > 0. And∫φ(b1 ) =f2 (v)f3 (b1 + β2 (v))dv
v2

and

∫

∫ b1 +β2Pr{2b1 < v3 < b1 + β2 (v2 )} =f2 (v)f3 (u)dudv,
b1 <β22b1

where fi is the density function of vi . We summerize and have the following proposition.
Proposition 1. Bidder i(= 1, 2) submits the value under his true value, i.e. βi (vi ) <vi if bidder j = 3 − i submits non-zero bid with positive probability and if Pr{2vi <v3 < vi + βj (vj )} > 0. On the other hand, Bidder 3 has a weakly dominant strategyof truth telling.
Now I assume that bidder 1 and 2 are symmetric and that all values are drawn
from uniform distributions. Let V1 = V2 = [0, 1], and V3 = [0, a] where a ≥ 2. And
F1 (v) = F2 (v) = v and F3 (v) = v/a.
9

Then FOC of bidder 1’s maximization problem is∫1(v1 − b1 )
dv −
v2 a
∫
∴ (v1 − b1 ) −∫∫ b1 +β2

β2 >b12b1

1
dudv ≤ 0,a{β2 (v) − b1 }dv ≤ 0.

(2)

β2 (v)>b1

Consider the equilibrium such that β1 (·) = β2 (·) = β(·) and β is continuous. The
equation (2) yields∫
v1 − β(v1 ) ≤{β(v) − β(v1 )}dv,

(3)

v>v1

where equality holds if β(v1 ) > 0. Evaluating (3) at v1 = 1 yields β(1) = 1. And
after some calculations, we have{0β(v) =
1 + log v

if v < e−1.
if v ≥ e−1(4)

We can check β(v) < v when v ∈ (0, 1).

4.1

The Threshold Problem

This 2-good and 3-bidder model is a basic example when we explain the thresholdproblem in package auctions. Table 1 explains the threshold problem in this case.
Local bidder 1 and 2 can outbid global bidders and obtain goods if at least oneof them bid actively (“bid more”) in the auction. On the other hand, when bothabstain active bidding and stop raising bids, goods are sold to a global bidder. Whenboth 1 and 2 bid actively, both bidders pay a moderate price and will get the (net)
payoﬀs of 2. When only either of them, say bidder 1, bids actively, he must pay ahigher price, and then his payoﬀ is 1. Bidder 2, on the other hand, will get goods at
a lower price, so that his payoﬀ is large.
There are multiple Nash equilibria in which either of local bidders bids actively
and the other stops bidding (and a mixed strategy equilibrium). Hence local bidders
may not win the goods unless they successfully coordinate their bids to outbid global
bidders. This is known as the threshold problem.
Under incomplete information, this multiple equilibria of the coordination problem is solved by bidders’ private information. Figure 3 illustrates the equilibrium
bidding function. If a bidder is weak, or a low type, he doesn’t submit bids actively
and drops out early. On the other hand, a strong, high type bidder bids actively andsubmits almost true valuation.
10

In this numerical example, incentive of lower types to freeride is quite strong.
Bidding up to the willingness to pay raises the probability of win and never generates
negative proﬁts unless bids exceed the true valuation. However, for a low type, theproﬁt in cases where he wins by “working hard” is actually very small because hereally has to work hard (pay the maximum bid he set.) Rather, raising the limit of
the bid increases the payment in cases where he wins even if he doesn’t work hard,
and this cost is relatively high.
On the other hand, a high type bidder expects that the opposing friend is relatively weak. Then the friend’s bid is lower than mine whenever he bids actively
or not. In addition, the cost of losing by shading bids is higher for the higher tpye
bidder. So the high type bidder has no incentive to rely on the friend’s contribution.
The equilibrium strategy also generates a serious low revenue problem. The
numerical example implies that there may be cases where package auctions fail.
Particularly, local bidders bid zero if their values are less than 1/e ; 0.37. The seller
gets zero revenue at the probability of (1/e)2 ; 0.14.11

5

Main Results

This section provides main results. Results in the previous section imply that bidders’ relationships about their targets strongly aﬀect their bidding strategies. I
clarify that the key concept is the transitivity condition about bidders’ geographical relationships. Bidders must satisfy the transitivity condition in order to have adominant strategy of truthful reporting.

5.1

The Transitivity Condition

First I introduce the transitivity condition. It is deﬁned on each bidder. Considering
bidders’ strategic biddings, one important point is bidders’ geographical location, or
what each bidder wants. The transitivity condition requires that any rival of thebidder’s rival should also be a rival.
Deﬁnition. Bidder i satisﬁes the transitivity condition if the following condition

11

Ausubel and Milgrom (2002) argue that one of disadvantages of the Vickrey auction is its nonmonotonic revenue and that the Vickrey auction sometimes generates low revenue. The example
in this section implies that the package auction may also result in low revenue because of strategic
underbidding.

11

holds:∀j, j 0 ∈ I (j 6= j 0 ) Ki ∩ Kj 6= ∅ and Kj ∩ Kj 0 6= ∅ ⇒ Ki ∩ Kj 0 6= ∅.
To describe bidders’ geographical relation, we deﬁne the concepts of rivals andfriends.
Deﬁnition. Bidder j is a rival of bidder i if Ki ∩ Kj 6= ∅. Ri denotes the set of rivalsof i. Bidder j is a friend of bidder i if Ki ∩ Kj = ∅. Ci = I−i \ Ri denotes the set offriends of i.
By using the notation of Ri and Ci , we can restate the transitivity condition as
the following form.
Lemma 1. Bidder i satisﬁes the transitivity condition if and only if for ∀j ∈ Ri and∀j 0 ∈ Ci , Kj ∩ Kj 0 = ∅.
Proof. All proofs appear in Appendix.
Figure 4 illustrates the transitivity condition. In top three cases, bidder i satisﬁes
the transitivity condition, and in the bottom case not. The top right case shows thatbidder i satisﬁes the transitivity condition, while bidder j and j’ don’t. The top leftcase is the fundamental case where the transitivity condition holds.
The transitivity is almost necessary and suﬃcient condition for truthful reporting.
The top left case of ﬁgure 4 implies that bidder i (and also j and j’ ) should outbid
others by himself. This is the source of truthful reporting.
The transitivity condition is rarely satisﬁed in the real auctions. We’ll checkthis by considering simple spectrum license auctions. Consider the situation wherea government plans to allocate licenses of radio spectrum of a single band to mobile
phone companies. The license is divided in two by regions, west and east. Someﬁrms (local ﬁrms) want a part of the licenses, while others (global ﬁrms) need bothof them. This is described by ﬁgure 5(i). In this case, global ﬁrm g satisfes thetransitivity, but local ﬁrms, l1 and l2 don’t.
Figure 5(ii) illustrates another case. Now the government sells two bands andeach of them separated with east and west. Four licenses are to be sold. Global ﬁrms
need the licenses of both regions, while local ﬁrms will want both bands of a single
region in order to operate rich variety of services. In such a case no one satisﬁes thetransitivity condition, so that everyone will have incentive to underbid.

12

5.2

The Dominant Strategy

First I consider the dominant strategy. The transitivity condition is the very condition for the existence of a dominant strategy. The key observations are that whenbidder i wins, all rivals of i, Ri , lose the auction, and that all other winners arein Ci . In addition, the auction leads to an eﬃcient allocation. These imply thatbidder i wins the auction if and only if w(I, b) = bi + w(Ci , b) ≥ w(I−i , b).12 Whenthe transitivity condition is satisﬁed, friends of bidder i are also friends of i ’s rivals.
This means that friends of bidder i have no inﬂuence in determination of allocationof bidder i. Then bidder i must outbid his rivals by his bid only. Furthermore,when bidder i wins, his payment is determined by the highest value of his rivals, by
the ascending auction algorithm. That is, nothing diﬀers from a simple single-unit
ascending auction.
Theorem 1. Suppose A1-A4. The truthfully reporting strategy, βi (vi ) = vi , is aweakly dominant strategy for bidder i if and only if bidder i satisﬁes the transitivity
condition.

5.3

The Bayesian Nash Equilibrium Strategy

When bidders have no dominant strategy, how about the optimal strategy in theBayesian Nash equilbrium? Roughly speaking, when a bidder has no dominant
strategy, a kind of freerider problem necessarily arises and there exists incentive tounderbid.
Unfortunately, it is hard to specify a closed form of (g, p) in general. However,
we can obtain some properties which are necessary for specifying bidders’ decision
problems. So ﬁrst I provide some observations about the auction mechanism.
Fix others’ bid. If a bidder wins the goods with the price of p̂i < bi , bidder i’s
payment must never increase by increasing his bid. As long as he submits the value
over p̂i , he wins the goods with p̂i because the algorithm always stops at p̂i . Hence
we have following observation.
Observation 1. For each b ∈ V , if gi (b) = Ki and pi (b) = p̂i < bi , then gi (b̃i , b−i ) =Ki and pi (b̃i , b−i ) = p̂i for all b̃i > p̂i .
12Precisely, we should consider the case of tie. Particularly, under the equilibrium strategies
which we consider in this section, tie-breaking rule does aﬀect the result when winning bids are
zero. However, tie-breaking rule doesn’t aﬀect our main theorems.

13

Next I deﬁne the minimal required bid. Let β be a proﬁle of bidding functions
and let W ≡ w(I−i , β−i (v−i )) − w(Ci , β−i (v−i )).13 W is a random variable generated
from v−i . Remenber bidder i wins the auction if and only if bi + w(Ci , b) ≥ w(I−i , b).
Hence when other bidders’ strategies are β, W represents the minimal bid for bidder
i to win the auction. Moreover, if bidder i wins, his payment pi must be above W .
This fact is obtained from Ausubel and Milgrom (2002).14 These observations play
important roles to derive bidder’s ﬁrst order condition of the payoﬀ maximization
problem.
Observation 2. gi (b) = Ki if bi > W . And bi ≥ W if gi (b) = Ki . Further pi (b) ≥ W
if gi (b) = Ki .
One problem is whether the distribution of W has a density function. Following
lemma assures that the distribution of W has no atom except the corner when I limit
the class of strategies.
Lemma 2. The distribution of W has no atom except W = 0 if for each j ∈ I−i , βj
is continuous and strictly increasing as long as βj (vj ) > 0.
Suppose that each βj is a candidate of the equilibrium bidding strategy thatsatisﬁes the conditions of lemma 2. Φ denotes the distribution function of W andlet φ be the density function of W such that φ(0) ≡ limδ→+0 Φ(δ)−Φ(0).
δ
Now we have the interim expected payoﬀ of bidder i given his private informaiton
vi and the report bi :πi (bi , vi ) = vi Φ(bi ) − E[pi (bi , β−i )].

(5)

Following lemmas help to investigate how the Bayesian Nash equilibrium strategy
is. The equilibrium strategy must be nondecreasing and bidders never make any
choice of overvidding.
Lemma 3. Bidder i ’s equilibrium strategy βi is weakly increasing.
Lemma 4. For every bidder i, any bidding strategy β̃i such that for ∃vi , β̃i (vi ) > vi
is weakly dominated by the following strategy β̂i , where β̂i (v) = min{β̃i (v), v}.
13

For precise notation, w(I−i , β−i ) should be described as w(I−i , (bi , β−i )). We use simplyw(I−i , β−i ) and w(Ci , β−i ) as long as no confusion rises.
14
Actually, w(I−i , b) − w(Ci , b) is equal to the payment of the Vickrey auction (Vickrey-ClarkeGroves mechanism; Vickrey (1961), Clarke (1971), Groves (1973)). The Vickrey payoﬀ is known as
the maximum possible payoﬀ in the core of the economy. Our auction also leads to a core payoﬀ,
so that the price should be over the Vickrey price.

14

Combining these lemmas and observations about the mechanism of the auction,
I have the ﬁrst-order condition for bidder’s maximization problem.
Lemma 5. Suppose A1-A4. And suppose that for each j ∈ I−i , βj is continuous andstrictly increasing as long as βj (vj ) > 0. Then the ﬁrst-order condition for bidder
i ’s maximization is given by(vi − bi )φ(bi ) − Pr{gi (bi ) = Ki ∧ pi (bi ) = bi } ≤ 0, 15(6)where equality holds when bi > 0.
Lemma 5 is explained intuitively as follows. When bidder i raises the bid by one
unit marginally, then the probability of winning rises marginally by φ(bi ). In thecase of such a new winning he will get the payoﬀ of (vi − bi ) because the minimal
required bid is exactly bi . On the other hand, raising the bid increases the amountof the payment by one unit in the cases in which he wins the package Ki and thepayment is binding at bi . So the marginal payoﬀ of bidder i is represented as theleft hand side of (6).
Truthful reporting, bi = vi is never optimal whenPr{gi (vi ) = Ki ∧ pi (vi ) = vi } > 0.
And generally this is satisﬁed when the transitivity condition is not satisﬁed andwhen vi is suﬃciently low. Lemma 6 shows that if bidder i doesn’t satisfy the transitivity and if all other bidders behave “actively” to some extent, truthful strategy
is suboptimal for some types.
Lemma 6. Suppose A1-A4. And suppose that bidder i does not satisfy the transitivity condition. If β is a Bayesian Nash equilibrium strategy proﬁle, each of whichis continuous and βj (v̄j ) > 0 for ∀j ∈ I, then βi is not truthful strategy and there
exists some α > 0 and βi (vi ) < vi for all vi ∈ (0, α).
Lemma 6 claims that the transitivity condition is almost necessary condition fortruthtelling in the Bayesian Nash equilibrium. However, it is not exactly necessary
condition and a slight diﬀerence arises because of the following consideration. Theremay be an equilibrium in which some bidders always submit zero, because there’rethe cases in which even if some bidders submit zero, they can win the goods bygrace of others’ high contribution. Therefore even if the transitivity condition is not
15

Pr{A ∧ B} denotes the probability of the events in which both A and B occur.

15

satisﬁed, there’re the case in which truthful reporting is still optimal. Considering
the possibility of such a “zero-bidder,” we imagine that zero-bidders are replaced
from the market. The following theorem is second main theorem. Proof is given asa corrollary of theorem 1 and lemma 6.
Theorem 2. Suppose A1-A4. Let β be a strategy proﬁle, each of which is continuous. And let Iˆ ≡ {j ∈ I|βj (v̄j ) > 0}. If β is a Bayesian Nash equilibrium and if iˆ then βi (vi ) = vi for all vi ∈ Vi . On the other hand, if
satisﬁes the transitivity on I,
ˆ then there exists
β is an equilibrium and if i does not satisfy the transitivity on I,
some α > 0 and βi (vi ) < vi for all vi ∈ (0, α).
As we’ve already seen, the transitivity condition is restrictive in practical applications. Theorem 2 implies that if the auction is ex ante eﬃcient all bidders mustsatisfy the transitivity condition.16 However, this will not be the case in practicegenerally. If there are some local buyers in the market, they will frequently violate
the transitivity condition. In addition, theorem 2 shows a negative result in anothermeaning. One of the aims of package auction is to ﬁnd an optimal bundle of thegoods. When all bidders satisfy the transitivity condition, the market is separated
and closed with rivals. This means that what the optimal packaging is obvious andthat there’s no need to determine the bundling during the process of the auction.
In other words, our package auction is ex ante eﬃcient only when we don’t have todesign a package auction.

6

Concluding Remarks

I have analyzed the bidders’ strategy in a package auction. One of the contributionsof this paper is that we formulate a Bayesian model of a package auction with complementarities. Preceding studies construct models of complete information and derivesome Nash equilibria of package auctions (Ausubel and Milgrom (2002), Milgrom(2007)). I derived a necessary and suﬃcient condition for the truthful dominant
strategy property. Moreover, it is also almost necessary and suﬃcient condition for
the incentive compatibility in the Bayesian Nash equilibrium.
I showed that almost all local bidders have incentive of underbidding when
there’re high complementarities. This ﬁnding corresponds to the “threshold prob16

Even in the cases where all bidders underbid in the equilibrium, the degree of underbidding
diﬀers among bidders and private information. So ex ante eﬃciency will not be achieved when somebidders underbid in equilibrium.

16

lem” in package auctions, a coordination problem among local bidders. I adopted
an incomplete information model and partially clariﬁed the environment where thethreshold problem, which is rather a freerider problem under incomplete information,
takes place in package auctions.
A simpliﬁed and limited case gives us bidders’ incentive properties in package
auctions more. However, our results will be adaptable even when more generalvalues are permitted. In the general values case, bidders will underbid more for small
packages of the goods, while they will bid more sincerely on the larger packages. Thisbidding strategy, truthtelling on the large packages and underbidding on the small
packages, is not a complex, rather simple strategy. The results are also testable inlaboratory experiments.
Some combinatorial auctions achieve high eﬃciency in experimental studies.17
However, little attention has been given to the point why high eﬃciency is achievedin experiments, for there’re few studies on theoretical and experimental analysis
about bidders’ bidding strategies in combinatorial auctions. Many experimental
studies have paid attention only to the eﬃciency and seller’s revenue of auctions
with and without package bidding. The results will be useful for analyzing andunderstanding strategic bidding behavior in experiments and real auction data. The
theoretical analysis on bidders’ behaviors in combinatorial auctions accompaniedwith experimentation will be in need much more.18

A

Appendix

In the appendix, ﬁrst I note the rule of ascending auction with continuous priceincrease. Then I provide proofs of lemmas and theorems.

A.1

A Continuous Price Package Auction

In the rule of the ascending auction described in section 3 the price increment is² > 0. We considered the case where the increment is negligibly small. As I’ve
already noted, we cannot specify the monetary transter function of the package
17

There’re few experimental studies on proxied package auctions such as the ascending proxyauction. Kazumori (2006) test the “Clock-Proxy Auction” by Ausubel, Cramton, and Milgrom(2006). See Porter et al (2003) and Cybernomics (2000) for the experimental studies on several
other multi-object auctions.
18
Of course experimental economics take very important roles in design of auctions or markets.
I’m also going to carry out the experiments in order to examine the bidders’ bidding strategies incombinatorial auctions. Roth (2002) notes the importance of each of theory, experimentation, andcomputation.

17

auction, p. So I deﬁne the auction with continuous prices by imposing some axioms
that it should satisﬁes.
First I deﬁne the provisionally winning( coalitions. A )subset of bidders
J ⊂ I∑
is a provisionally winning coalition at t if (Kj )j∈J , (∅)j6∈J ∈ X and j∈J pj (t) =w(I, p(t)). P W (t) denotes the set of provisionally winning coalitions at t.
Auctions which satisfy following properties include the one we consider in thispaper. An package auction determines a price path p(t) = (pi (t))i∈I as follows.
1. Each bidder inputs the valuation for his region, bi ∈ Vi .
2. At time t = 0, initialize pi (0) = 0 for all i ∈ I.
3. A price path p(t) (t ≥ 0) is determined as follows. If ṗ(T ) = 0 at T , go to thenext step.
∩(a) For all j ∈ J∈P W (t) J, ṗj (t) = 0.
∩(b) For all j 6∈ J∈P W (t) J, ṗj (t) = qjt > 0 if pj (t) < bj . And ṗj (t) = 0 if
pj (t) ≥ bj .
∑∑(c) For all J, J 0 ∈ P W (t), J ṗj (t) = J 0 ṗj 0 (t).
(d) (Competitiveness) Suppose for J ∈ P W (t), i, j ∈ J, pi (t) < bi and pj (t) <bj . [∀J 0 ∈ P W (t), [j ∈ J 0 ⇒ i ∈ J 0 ]] ⇒ ṗi (t) ≤ ṗj (t).
4. t = T . If for some J, J 0 ∈ P W (T ), J ⊂ J 0 , then P ˆW (T ) ≡ P W (T ) \ {J} andreplace P W (T ) ≡ P ˆW (T ).
5. The seller choose randomly J ∈ P W (T ) and they are winners. Each winnerpays pj (T ).
One of important characteristics is that we don’t completely specify the speedof each bidders’ price increase (step 3(b)). But the speeds is restricted by step 3(c)and (d). Step 3(c) requires that any candidate of winning allocation should oﬀer the
maximum revenue at any time. Step 3(d) requires that when a bidder competes withmore people, then the price increases fast. Step 3(d) also implies following symmetry
property.
symmetry: Suppose for J ∈ P W (t), i, j ∈ J, pi (t) < bi and pj (t) < bj . If for∀J 0 ∈ P W (t), [i, j ∈ J 0 ] or [i, j 6∈ J 0 ], then ṗi (t) = ṗj (t).

A.2

Proofs

Proof of Lemma 1. Suppose that for ∃j ∈ Ri and ∃j 0 ∈ Ci , Kj ∩Kj 0 6= ∅. However,
the transitivity for bidder i requires j 0 ∈ Ri , which is contradiction. Conversely, theviolation of the transitivity implies for ∃j ∈ Ri and ∃j 0 ∈ Rj , j 0 ∈ Ci . ¥Proof of Theorem 1. (Suﬃciency.) Suppose that bidder i satisﬁes the transitivity
condition. Then for each j ∈ Ri and each j 0 ∈ Ci , Kj ∩ Kj 0 = ∅. So by constructionof coalitional value function, we havew(I−i , b) = w(Ri , b) + w(Ci , b).
18

Note that if bidder i wins the items, w(I, b) = bi + w(Ci , b). So bidder i wins if andonly ifbi + w(Ci , b) ≥ w(Ri , b) + w(Ci , b).
Hence bidder i wins if and only if bi ≥ w(Ri , b). (If bi = w(Ri , b), winners are
determined randomly.)
All bidders in Ri lose the auction when bidder i wins, so that at ﬁnal period
T in the ascending auciton they bid their reported values: pTj = bj for all j ∈ Ri .
Whenever pti < w(Ri , b), there necessarily exists some blocking allocation against
one which bidder i wins, and then the auction never stops. Once bidder i bids
pti = w(Ri , b), then no allocation can block bidder i after that period. Therefore
bidder i ’s winning bid is pTi = w(Ri , b).
So bidder i ’s payoﬀ is{vi − w(Ri , b) if bi ≥ w(Ri , b)ui (b; vi ) =.
0otherwise
It is easy to check that bi = vi is a weakly dominant strategy.
(Necessity.) Suppose that for j ∈ Ri and j 0 ∈ Ci , Kj ∩ Kj 0 6= ∅. Bidder i wins the
goods if and only if bi + w(Ci , b) ≥ w(I−i , b). Let b−i be such that bj 0 > bj > 0 andbm = 0 for all m ∈ I \{i, j, j 0 }. Then w(Ci , b) = w(I−i , b) = bj 0 and w(Ri , b) = bj > 0.
Then even if bidder i bids zero, i wins and its price is zero. On the other hand, if ibids any bi > 0, then he must win with price of pi > 0 because w(Ri , b) > 0. ¥Proof of Lemma 2. Suppose that each βj is continuous and strictly increasing as
long as βj > 0. And suppose that w(I−i , β−i ) − w(Ci , β−i ) = w > 0.
∗ and C ∗ be sets of bidders, who win the goods when goods are allocated
Let I−iieﬃciently among I−i and Ci , respectively. That is,∑∗
βjw(I−i , β−i ) = w(I−i, β−i ) =
∗
j∈I−i

and

w(Ci , β−i ) = w(Ci∗ , β−i ) =

∑

βj .

j∈Ci∗

Then

∑
∗
j∈I−i

βj −

∑

βj = w.

(7)

j∈Ci∗

∗ and ĵ 6∈ C ∗ . Hence equation
Because w > 0, there exists some ĵ such that ĵ ∈ I−ii(7) always binds as a linear equality constraint of (βj )j∈I−i . The continuity and thestrict monotonicity of β assure that the set of v−i which satisﬁes (7) must have zero
∗ , C ∗ ) is ﬁnite, so Φ(w) has no atom
measure. Further the way of selection of (I−iiwhen w > 0. ¥19

Proof of Lemma 3. Let Πi (vi ) ≡ πi (βi (vi ), vi ). ThenΠi (vi ) ≥ πi (βi (ṽi ), vi ) = Πi (ṽi ) + vi Φ(βi (ṽi )) − ṽi Φ(βi (ṽi )),hence
Πi (vi ) − Πi (ṽi ) ≥ (vi − ṽi )Φ(βi (ṽi )).
Similarly
Πi (vi ) − Πi (ṽi ) ≤ (vi − ṽi )Φ(βi (vi )).
Therefore(vi − ṽi )Φ(βi (vi )) ≥ (vi − ṽi )Φ(βi (ṽi )).
If vi > ṽi , thenTherefore βi (vi ) ≥ βi (ṽi ).

Φ(βi (vi )) ≥ Φ(βi (ṽi )).
¥Proof of Lemma 4. Consider any vi such that β̃i (vi ) > vi . If bidder i wins withthe price pi < vi , he would also win the goods by submitting vi with the same
price (observation 1). When we ﬁx the other bidders’ bids, the auction stops at pi
whenever bidder i submits any bi > pi . If bidder i wins with the price over vi , thenhe gets negative payoﬀ. If he reports vi , he will get zero payoﬀ in that case. ¥Proof of Lemma 5. First we rewrite the interim expected payment E[pi (bi , β−i )]as follows,E[pi (bi , β−i )] = E[pi (bi , β−i ) · 1{pi (bi ,β−i )<bi } ] + bi Pr{gi (bi ) = Ki ∧ pi (bi , β−i ) = bi }.
(8)
Expectations and probabilities are taken conditionally on bidder i ’s some report bi
and others’ strategies β−i .
Now we consider the marginal expected payment when bidder i increases thevalue by δ > 0. We describe pi (bi , β−i ) simply as pi (bi ).
E[pi (bi + δ)] − E[pi (bi )][]= E[pi (bi + δ) · 1{pi (bi +δ)<bi +δ} ] − E[pi (bi ) · 1{pi (bi )<bi } ][]+ bi Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) = bi + δ} − Pr{gi (bi ) = Ki ∧ pi (bi ) = bi }+ δ Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) = bi + δ}.
(9)
By observation 1, if gi (bi + δ, b−i ) = Ki and pi (bi + δ, b−i ) < bi , then gi (b) = Ki
and pi (bi + δ, b−i ) = pi (bi , b−i ). So
E[pi (bi +δ)·1{pi (bi +δ)<bi +δ} ]−E[pi (bi )·1{pi (bi )<bi } ] = E[pi (bi +δ)·1{bi ≤pi (bi +δ)<bi +δ} ].

20

And
E[bi · 1{bi ≤pi (bi +δ)<bi +δ} ] ≤ E[pi (bi + δ) · 1{bi ≤pi (bi +δ)<bi +δ} ]< E[(bi + δ) · 1{bi ≤pi (bi +δ)<bi +δ} ],hencebi Pr{bi ≤ pi (bi + δ) < bi + δ} ≤ E[pi (bi + δ) · 1{bi ≤pi (bi +δ)<bi +δ} ]< (bi + δ) Pr{bi ≤ pi (bi + δ) < bi + δ}.

(10)

Next, observation 1 also implies
Pr{gi (bi ) = Ki ∧ pi (bi ) < bi } = Pr{gi (bi ) = Ki ∧ pi (bi + δ) < bi }.
In addition, observation 2 implies
Pr{gi (bi ) = Ki ∧ pi (bi + δ) < bi } = Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) < bi }.
Therefore
Pr{gi (bi ) = Ki ∧ pi (bi ) < bi } = Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) < bi }.

(11)Then, we havePr{gi (bi + δ) = Ki ∧ pi (bi + δ) = bi + δ} − Pr{gi (bi ) = Ki ∧ pi (bi ) = bi }= Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) ≤ bi + δ} − Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) < bi + δ}
− Pr{gi (bi ) = Ki ∧ pi (bi ) ≤ bi } + Pr{gi (bi ) = Ki ∧ pi (bi ) < bi }= Φ(bi + δ) − Φ(bi ) − Pr{bi ≤ pi (bi + δ) < bi + δ}
− Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) < bi } + Pr{gi (bi ) = Ki ∧ pi (bi ) < bi }= Φ(bi + δ) − Φ(bi ) − Pr{bi ≤ pi (bi + δ) < bi + δ}.
(12)Using these equations (9), (10) and (12), we have following inequality after some
calculation,bi (Φ(bi + δ) − Φ(bi )) + δ Pr{gi (bi + δ) = Ki ∧ pi (bi + δ) = bi + δ}
≤ E[pi (bi + δ, β−i )] − E[pi (bi , β−i )](13)< bi (Φ(bi + δ) − Φ(bi )) + δ Pr{gi (bi + δ) = Ki ∧ bi ≤ pi (bi + δ) ≤ bi + δ}.
Therefore we haveΦ(bi + δ) − Φ(bi )− Pr{bi ≤ pi (bi + δ) ≤ bi + δ}δ
πi (bi + δ, vi ) − πi (bi , vi )<δΦ(bi + δ) − Φ(bi )≤ (vi − bi )− Pr{pi (bi + δ) = bi + δ}.
δ(vi − bi )

21

(14)

Similarly we haveΦ(bi + δ) − Φ(bi )− Pr{bi − δ ≤ pi (bi ) ≤ bi }δπi (bi , vi ) − πi (bi − δ, vi )<δΦ(bi + δ) − Φ(bi )≤ (vi − bi + δ)
− Pr{pi (bi ) = bi }.
δ(vi − bi + δ)(15)

By taking limit δ → 0, we have∂
πi (bi , vi ) = (vi − bi )Φ(bi ) − Pr{gi (bi ) = Ki ∧ pi (bi ) = bi }.
∂bi

(16)

So the FOC for maximization is represented as(vi − bi )Φ(bi ) − Pr{gi (bi ) = Ki ∧ pi (bi ) = bi } ≤ 0,
where equality holds if bi > 0.

(17)

¥

Proof of Lemma 6. Suppose that β is an equilibrium strategy proﬁle, each ofwhich is continuous and βi (v̄i ) > 0. By lemma 3, each βi is weakly increasing.
Further suppose that each βi is strictly increasing as long as βi > 0. Then bylemma 5, if βi > 0, the FOC of maximization problem is satisﬁed by equality. The
left hand side of the FOC is linear in vi , so that if vi > v̂i , βi (vi ) > βi (v̂i ). Therefore
if all other bidders satisfy the partial strict monotonicity property in the equilibrium,then the optimal reaction also satisﬁes the partial strict monotonicity property. So weapply lemma 5 and what to show is for some α > 0, Pr{gi (vi ) = Ki ∧ pi (vi ) = vi } > 0
for vi ∈ (0, α).
Now suppose that for j ∈ Ri and j 0 ∈ Ci , Kj ∩ Kj 0 6= ∅.
Suppose that all bidders except bidder i play equilibrium strategies, which arecontinuous and strictly increasing when β > 0. We∏ exhibit an measurable space of
message proﬁles except bidder i, B−i (vi ) ⊂ V−i = m∈I−i Vm such that bidder i winswith value binding. Each bidder’s strategy is non-decreasing and no one overbids
in the equilibrium by lemma 3 and 4. Therefore for any b̂m > 0, the probability ofthe event that bidder m’s equilibrium bid βm is in the interval [0, b̂m ) is positive.
Therefore if we propose a message proﬁle space of positive measure, then the areaof true value proﬁle, which maps into that message proﬁle space, is also positive
measure.
Let β̄m ≡ βm (v̄m ) for m ∈ I, and let α be some positive value and 0 < α <min{β̄j 0 , 21 β̄j }.
Let B−i (vi ) be the set of proﬁle of bids, b−i , which satisﬁes following conditions
C1-C5:
C1 bj 0 ≥ α,i
C2 bm < |Ri v\{j}|for all m ∈ Ri \ {j} (if Ri \ {j} 6= ∅,)22

i
C3 bm < |Rα−v
for all m ∈ Rj 0 \ {j} (if Rj 0 \ {j} 6= ∅,)0 \{j}|jβ̄ −2αC4 bm < |Cji ∩C 0 | for all m ∈ Ci ∩ Cj 0 (if Ci ∩ Cj 0 6= ∅,)j

C5 2vi + w(Rj 0 \ {j}, b) + w(Ci ∩ Cj 0 , b) < bj < vi + bj 0 + w(Ci ∩ Cj 0 , b).
Let vi < α. C2, C3, and C4 imply w(Ri \ {j}, b) < vi , w(Rj 0 \ {j}, b) + vi < α, andvi + α + w(Ci ∩ Cj 0 , b) < 2α + w(Ci ∩ Cj 0 , b) < β̄j , respectively. C4 guarantees that bj
which satisﬁes C5 exists and that Pr{v−i |β−i (v−i ) ∈ B−i (vi )} > 0. C5 implies thatbidder j loses, and that bidder i and j 0 win the auction.
Now let bi = vi and let period t in the ascending auction be the very period atwhich all bidders in Rj 0 \ {j} drop out and lose the auction, i.e.
t ≡ min s [psj0 ≥ w(I \ {j 0 , j}, b) − w(Cj 0 , ps )].
If Rj 0 \ {j} = ∅, let t = 0. This means that bidder j is the only rival of bidder j 0
after period t.
At period t, bidder j is still standing. Bidder j 0 19 outbids the rivals except
bidder j by bidding at most w(Rj 0 \ {j}, b). At that period, on the other hand,
other winning bidders {i} ∪ (Ci ∩ Cj 0 ) bid at most vi + w(Ci ∩ Cj 0 , b). Because
vi + w(Ci ∩ Cj 0 , b) + w(Ri \ {j}, b) < bj by C5, bidder j never drops out before t andstill stands.
Let b̃m ≡ bm − ptm for each m ∈ I−i , ṽi ≡ vi − pti , and w̃(Ci ∩ Cj 0 ) ≡ w(Ci ∩Cj 0 , b) − w(Ci ∩ Cj 0 , pt ). Thenb̃j = bj − ptj ≥ 2vi + w(Rj 0 \ {j}, b) + w(Ci ∩ Cj 0 , b)
− pti − ptj 0 − w(Ci ∩ Cj 0 , pt )≥ ṽi + vi + w̃(Ci ∩ Cj 0 )(18)≥ 2ṽi + w̃(Ci ∩ Cj 0 ).
The ﬁrst inequality in the equation (18) follows from C5 and the fact ptj ≤ pti +ptj 0 + w(Ci ∩ Cj 0 , pt ) when ² → 0. This inequality is obtained from the rule of theauction (step 3(c) of the auction with continuous price increases.) When the priceincrements are negligible, any candidate of ﬁnal allocation must always oﬀer therevenue maximizing prices. So at period t, bidder i, j 0 , and j stand, so the allocationin which i and j 0 obtain the goods and one in which j obtains the items oﬀer thesame price: ptj + w(Cj , pt ) = pti + ptj 0 + w(Ci ∩ Cj 0 , pt ). The second inequality follows
from the deﬁnition of ṽi and w̃(Ci ∩ Cj 0 ), and from ptj 0 ≤ w(Rj 0 \ {j}, b).
Consider the auction after period t as a new auction with reported proﬁle (ṽi , b̃−i ).
Bidder j is the only rival of bidder j 0 , so bidder j 0 raises the bid if and only if bidder
j is the provisional winner. And at those periods bidder i is not a provisional winner
too, so that bidder i also raises the bid as long as bidder i ’s bid does not bind. Hence
19

Hereafter we don’t distinguish players in the game “bidders” from “agents” for bidders. We callboth bidder.

23

ṗi ≥ ṗj 0 if ṗi > 0 (step 3(d) of the auction with continuous price increases.) So if
bidder i wins with the price of v̂i + pti < ṽi + pti = vi , then bidder j 0 should win atb̂j 0 +ptj 0 ≤ v̂i +ptj 0 . However, this means v̂i + b̂j 0 + w̃(Ci ∩Cj 0 ) ≥ b̃j > 2ṽi + w̃(Ci ∩Cj 0 ),which is contradiction. Therefore bidder i wins with the price of ṽi + pti = vi .
We have Pr{gi (vi ) = Ki ∧ pi (vi ) = vi } ≥ Pr{vi |β−i (v−i ) ∈ B−i (vi )} > 0. ¥References[1] Ausubel, L. M., P. Cramton, R. P. McAfee, and J. McMillan (1997) “Synergies
in Wireless Telephony: Evidence from the Broadband PCS Auctions,” Journalof Economics and Management Strategy, 6, 497-527.
[2] Ausubel, L. M., P. Cramton, and P. Milgrom (2006) “The Clock-Proxy Auction:
A Practical Combinatorial Auction Design,” in Combinatorial Auctions, eds. P.
Cramton, Y. Shoam, and R. Steinberg, MIT Press, 115-138.
[3] Ausubel, L. M., and P. Milgrom (2002) “Ascending Auctions with Package
Bidding,” Frontier of Theoretical Economics, 1, 1-42.
[4] Ausubel, L. M., and P. Milgrom (2006) “Ascending Proxy Auctions,” in Combinatorial Auctions, eds. P. Cramton, Y. Shoam, and R. Steinberg, MIT Press,
79-114.
[5] Brusco, S, and G. Lopomo (2002) “Collusion via Signalling in Simultaneous
Ascending Bid Auctions with Heterogeneous Objects, with and without complementarities,” Review of Economic Studies, 69, 407-436.
[6] Clarke, E. H. (1971) “Multipart Pricing of Public Goods,” Public Choice, 11,17-33.
[7] Cybernomics (2000) “An Experimental Comparison of the Simultaneous Multiple Round Auction and the CRA Combinatorial auction,” available atwww.fcc.gov/wtb/auctions/comin/98540191.pdf.
[8] Groves, T. (1973) “Incentives in Teams,” Econometrica, 41, 617-631.
[9] Kazumori, E. (2006) “Auctions with Package Bidding: An Experimental Study.”[10] Ledyard, J. O., D. Porter, and A. Rangel (1997) “Experiments Testing Multi
Object Allocation Mechanisms,” Journal of Economics and Management Strategy, 6, 639-675.
24

[11] Milgrom, P. (2000) “Putting Auction Theory to Work: The Simultaneous Ascending Auction,” Journal of Political Economy, 108, 245-272.
[12] Milgrom, P. (2004) Putting Auction Theory to Work, Cambridge University
Press.
[13] Milgrom, P. (2007) “Package Auctions and Exchanges,” Econometrica, 75, 935965.
[14] Parkes, D. C. (2006) “Iterative Combinatorial Auctions,” in Combinatorial Auctions, eds. P. Cramton, Y. Shoam, and R. Steinberg, MIT Press, 41-77.
[15] Parkes, D. C., and L. H. Ungar (2000) “Iterative Combinatorial Auctions: Theory and Practice,” in Proceedings of the 17th National Conference on Artiﬁcial
Intelligence (AAAI-00), 74-81.
[16] Porter, D., S. Rassenti, A. Roopnarine, and V. Smith (2003) “Combinatorial
Auction Design,” Proceedings of the National Academy of Sciences, 100, September, 11153-11157.
[17] Roth, A. (2002) “The Economist as Engineer: Game Theory, Experimentation,
and Computation as Tools for Design Economics,” Econometrica, 70, 1341-1378.
[18] Vickrey, W. (1961) “Counterspeculation, Auctions, and Competitive Sealed
Tenders,” Journal of Finance, 16, 8-37.

25

Table 1: Threshold problem.
1\2

bid morestop

bid morestop(2, 2)(3, 1)(1, 3)(0, 0)

Figure 1: The 2-good and 3-bidder case.

Figure 2: An example of the procedure of the auction.

26

Figure 3: The equilibrium bidding function of bidder 1 and 2 in the 2-good and3-bidder case.

Figure 4: Bidder i satisﬁes the transitivity in top three cases, while not in the bottom
case.

27

Figure 5: Two examples of spectrum auction.

28