『経済研究』（明治学院大学）第 161 号

2021 年

The Ausubel Auction with the Receive Option ofOver-Assignments＊
Noriaki Okamoto†
Abstract
The Ausubel auction, which is introduced by Ausubel（2004）, is a dy-namic version of theVickrey auction. Okamoto（2018）shows that in the original Ausubel auction, sincere-bidding by all
bidders may not be an ex-post perfect equilibrium, and modifies the Ausubel auction, the Ausubel
auction with sequential rationing, so that sincere-bidding by all bidders is always an ex-post perfectequilirium. In this paper, we propose another modification of the Ausubel auction, namely the Ausubel auction with the receive option of over-assignments. We also show that in this auction, sincere-bidding by all bidders is always an ex-post perfect equilibrium, which obtains the Vickrey outcome.

1．Introduction
Ausubel（2004）designs a dynamic auction for multiple homogeneous objects, called the Ausubel auction, which obtains the Vickrey outcome at a sincere-bidding equilibrium.1 Okamoto（2018）showsthat in the Ausubel auction, sincere-bidding by all bidders is always an ex-post equilibrium, but may
not be an ex-post perfect equilibrium. The notion of ex-post perfect equilibrium requires that the strategy profile is an ex-post equilibrium at all subgames. In other words, if a strategy profile is not an expost perfect equilibrium, then some bidder has an in-centive to deviate at some subgame. Therefore,
in the Ausubel auction, a bidder may not bid sincerely after making a bidding mistake. Okamoto（2018）modifies the Ausubel auction by introducing a new rationing rule, sequential rationing, so that＊The author thanks Toyotaka Sakai, Yoko Kawada, Yuta Nakamura, and Hiroyuki Komatsu for help comments.
Okamoto’s Research is financially supported by KAKENHI（20K13456）and the Grant-in-Aid for JSPS Fellows（15J06887）.

†

Faculty of Economics, Meiji Gakuin University, Tokyo 108-8636; nokamoto@eco.meijigakuin.ac.jp1

The Vickrey outcome is an outcome of the Vickrey auction, which is introduced by Vickrey（1961）. In themechanism design literature, the Vickrey outcome is often called the VCG outcome.（Vickrey（1961）, Clarke（1971）,Groves（1973））See, for example, Krishna（2009）for details.
29『経済研究』（明治学院大学）第 161 号

sincere bidding by all bidders is always an ex-post perfect equilibrium.
Ausubel（2018）states that the optimality of sincere-bidding in dynamic auc-tions may be sensitive to the fine details of the rationing rule for tie-breaking. In the dynamic Ausubel auction with sequential rationing, all bidders have in-centives to bid sincerely even after making a mistake. However, in the dynamic Ausubel auction, under some rationing rules for tie-breaking, some bidder may
have an incentive to underbidding after overbidding.2 On the other hand, in the static Vickrey auction, under any rationing rule for tie-breaking, all bidders have strong incentives to bid sincerely,that is, sincere-bidding is a weakly dominant strategy for each bidder. There is only one round in
static auctions, bidders have no chance to bid after making mistakes, and we do not have to consider
bidders’ incentives after that.
Seminal works investigate auction rules which always assign all the auctioned objects entirely
according to a rationing rule for tie-breaking. In those auctions, bidders may be assigned in excess of
their（last）bids without they are not asked whether they want those or not. In fact, in the Ausubel
auction with sequential rationing, if a bidder overbids at some round, then the bidder may be overassigned in the next round, that is, bidders could be punished for bidding mistakes even in the next
round.
In this paper, we introduce a new auction rule, the Ausubel auction with the receive option of overassignments, in which at each round, each bidder bids a quantity of objects and a signal as to whether
or not the bidder receives the excess supply. In this auction, even if a bidder overbids at some round,the bidder is not be over-assigned in the next round by bidding the signal not to receive the excess
supply. We then show that in this auction, sincere-bidding by all bidders is always an ex-post perfectequilibrium. Furthermore, in a sincere-bidding equilibrium path, this auction assigns all the auctioned
objects entirely and obtains the Vickrey outcome.
This paper is organized as follows. In Section 2 , we introduce definitions. In Section 3 , weshow our main result. In Section 4, we conclude our discussions.

2．Definitions
We almost follow notation of Ausubel（2004）and Okamoto（2018）.
2-1．Bidders
A seller puts M homogeneous divisible objects for an auction. There is a finite set of bidders N＝2For example, consider proportional rationing, which is introduced by Ausubel（1997）. Okamoto（2018）gives anexample such that under any rationing rule which satisfies mono-tonicity property, sincere bidding by all bidders is not an ex-post perfect equilibrium.
30

The Ausubel Auction with the Receive Option of Over-Assignments

1, 2, …, n with n≥2. Each bidder i∈N has a consumption set Xi＝［0, λi］with 0＜λi≤M and a valuation
function Ui : Xi → ℝ＋. When a bidder i∈N is assigned xi∈Xi and pays yi∈ℝ, bidder i’s utility is U（i xi）－yi. For each xi∈Xi, the value U（i xi）can be calculated by the integral of corresponding marginalvalue ui : Xi → 0, 1, ..., ū , so thatxU（dq＝∫ i u（
i xi）
i q）
0

where ū is a positive integer. We introduce the three assumptions on ui such that（i）each ui is aweakly decreasing function in Xi,（ii）ui（xi）is an integer in 0, 1, ..., ū for all xi∈Xi, and（iii）ū＜∞.
2-2．Auction rule
We shall offer the Ausubel auction with the receive option over-assignments. This auction is almost
the same as the Ausubel auction, except for signals（ai）i∈N as to whether or not the bidders receive
the excess supply.
An auction proceeds by discrete time 0, 1, ..., T with T＜ū. For each time t∈ 0, 1, ..., T , let
the price pt＝t. An auction starts at t＝0, and it proceeds as follows.

t＝0: Each bidder i∈N simultaneously bids a quantity xi0∈Xi and a signal ai∈ 0, 1 for tie-breaking. The signal a0i＝0 means that i does not want to receive the excess supply, and a0i＝1 means that i
can receive the excess supply. Ifsuch that∑i∈M xi ≤ M , the auction ends at t＝0 with assignment（xi）i N＊0∈x＊i＝xi0 ∀i∈N.
Otherwise, for each bidder i∈N, let
⎧

⎫

xj⎬
∑
j≠i ⎭

Ci0＝max⎨0, M－⎩

0be bidder i’s cumulative clinches at t＝0, and the auction continues to t＝1.

t＝s＜T: The auctioneer announces full information of prior bids to each bidder. Each bidderi∈N simultaneously bids a quantity x si satisfying the bidding constraint
Cis－1≤x is≤x is－1.
and a singal asi∈ 0, 1 . If

∑ i N xis≤M, the auction ends at t＝s with an assignment x i which is de＊∈cided by the following way: Let N0＝ i∈N : ai＝0 and N1＝ i∈N : ai＝1 . Then,x＊i＝x is ∀i∈N031

『経済研究』（明治学院大学）第 161 号⎧

xj ＝xjs＋min⎨xjs－1－xjs，*

xjs－1－xjs

xis）⎬ ∀j∈N .
∑
i∈N ⎭

・
（M－

∑k∈N xks－ －xks

⎩

1

1

⎫

1

∑ j i xis   be bidder i’s cumulative clinches, and the auction contin-

Otherwise, let C is＝max 0, M－
ues to t＝s＋1.

≠

t＝T : The auctioneer announces full information of prior bids to each bidder. Each bidder i∈Nsimultaneously bids a quantity xTi satisfying the bidding constraint
CTi－1≤ xTi≤ xTi －1.
and a signal aTi∈ 0 , 1 . In any case, the auction ends, even when there is the excess demand. If∑i∈N xTi ＞ M , an assignment（x i）i N such that∑i∈N xi ＝M and＊*∈x＊i ≤ x Ti ∀i∈N.
Otherwise, similarly to the case ends at t＝s＜T , an assignment（x＊i）i∈N is decided.
This auction process finishes in at most T＋1 rounds. Let L be the last round of the auction
game, i.e.,∑i∈N xLi ≤ M or L = T. For each bidder i∈N , define cumulative clinches of the last timetLby i’s assignment, CLi＝x＊
i . Then, by this process, we obtain a vector of cumulative clinches（C i）
i∈N t＝0.
L
We then define the vector of current clinches（cti）
i∈N  t＝0. as follows: For each i∈N and t ≥1,

cti＝C ti－C ti －1,
and c0i＝C 0i.
For each bidder i∈N, the payment yi is calculated as the bidder buys each current clinch cit ateach price pt. Therefore, the payment is given byL

p tcit.
∑
i＝

yi＝

0

2-3．Histories and Strategies
At each time t∈ 0, 1, ..., T , a history is a vector of all prior bids to ts , as ）ht＝（（x 1s, a 1s）（, x 2s, a 2s）,...,（x N∈N ）（×i∈N（Xi× 0, 1 ））0, 1...,t－1

such that for each i∈N and each s≤t－1,

C is－1 ≤ x is≤ x is－1,
xjt－ ＞ M.
∑
j∈N
2

32

The Ausubel Auction with the Receive Option of Over-Assignments

Define the history of starting point t＝0 by the empty sequence, h0＝Ø.

∪Tt

t
＋1
＝ 0 H be the set of all histories. A history

Let H t be the set of histories at t, and H≡z t＋1＝（（x 1s, a 1s）,...,（x sN, a sN））s≤t∈H t＋1∪t＝ Zt be the set of all ter-is terminal if t＝L. Let Z t be the set of terminal histories at t, and Z≡

T＋1
1

minal histories.
A strategy of bidder i is a function σ i : H  \Z → Xi× 0,1 satisfying the bidding constraint: fortt （x t at）and x t－1 is i’s bid at t 1 in ht. For each i∈N, the set
any h ∈H t, x ti ≤ x ti－1 where σ（
＝ i i
－
i h）
i
of strategies is defined by ∑ i .
Definition 1. Bidder i’s sincere-demand at price p∈ℤ＋ is defined byQ（＝min arg max（U（－pxi）.
i p）
i xi）
xi∈Xi

Definition 2. Bidder i’s sincere-bidding is the strategy such that for any t ≥1 and ht∈H t \Z t,t （min xt－1, max Q（pt）
t－1）
σ＊（,C ti－1 ,1（x t－1）≤Q（
）,
＝
i h）
i
i p
i
i

＊ 0
0
, 1）. Note that 1（xt－1）≤Q（i pt－1） is the indicator function, that is,and σ（
＝（Q（
i h）
i p）

i

⎧
t－1
t－1）
｜ 1 if xi ≤ Q（i p
1（x t－1 ）≤ Q（p t－1 ）＝⎨ii｜ 0 otherwise.
⎩
For any history, sincere-bidding bids the sincere-demand as long as it satisfies the bidding
constraint, and reports 0 as a signal if and only if the bidder overbids just before the history.
A strategy profile（σi）i∈N is an n-tuple of strategies. Sincere-bidding by all bidders（σ＊i ）i∈N is the ntuple of sincere bidding.
2-4．Subgames
In this paper, we assume that at each round, each bidder can observe all the previous bids ofthe others.3 Therefore, for each non-terminal history h∈H \ Z, we can define the subgame that follows the history h.4
For each h, let

H |h＝ h′∈H：h′＝（h, h″）for some sequence h″.
be the set of all histories in the subgame that follows h, and
3This assumption is often called the full bid information.

4

See, for example, Osborne and Rubinstein（1994）for details of subgames and induced strategies.
33

『経済研究』（明治学院大学）第 161 号

Z|h＝Z

∩H |h

be the set of all terminal histories in the subgame that follows h. For each h and each σi∈∑ i , the induced strategy is denoted by σi|h, and let ∑ i |h be the set of induced strategies in the subgame that follows h.
2-5．Equilibrium concept
In extensive form games, a famous equilibrium notion is subgame perfect equilibrium, which is
introduced by Selten（1975）. On the other hand, we sometimes investigate ex-post equilibrium in auction games.5 Ausubel（2004）combines these two concepts and introduces the notion of ex post perfectequilibrium.
Definition 3. A strategy profile（σi）i∈N is an ex-post perfect equilibrium if for any history h∈H \Z, the induced
strategy profile（σi|h）i∈N is an ex post equilibrium in the subgame that follows h.

3．Result
Theorem 1. In the Ausubel auction with the receive option of over-assignments, sincere-bidding by all bidders isalways an ex-post perfect equilibrium which obtains the Vickrey outcome.
Proof of Theorem 1. Consider any time t∈ 0, 1, ..., T , any non-terminal historyh t＝（（x s1, a s1）,（x s2 , a s2）...,（x sN, a sN））s≤t－1∈H t \Z t＊
and any marginal utilities（uj）
j∈N. For each j∈N, let σ j be sincere-bidding which is corresponding touj, and σ＊j |ht be induced sincere-bidding in the subgame that follows ht.
t－1）, then we can show that the bidder i has no incentive to deviate by the simiIf x it－1≤Q（i p

lar way to Lemma 2 of Okamoto（2018）.Then, we suppose thatt－1）
x it－1>Q（i pthat is, bidder i overbids at t in ht.
Take any i∈N and any strategy σi∈∑ i |ht of subgame that follows ht. Letz L＋1＝（（x s1, a s1）,（x s2, a s2）, ...,（x sn, a sn））s ≤ L
be the terminal history which is reached by（σ＊j |ht）j∈N, and
5For example, See Crémer and Richard（1985）.
34⑴

The Ausubel Auction with the Receive Option of Over-Assignments

w L′＋1＝（（x̂ s1, â s1）,（x̂ s2, â s2）,...,（x̂ sn, â sn））s ≤ L′
be the terminal history which is reached by（σi,（σ＊j |ht）j≠i）. Denote （C tj）j∈N Lt＝0 the cumulative′
L′＋1.
clinches of z L＋1, and （Ĉ tj）j∈N Lt＝
0 the cumulative clinches of w

We shall consider the three cases:（Case 1）L＞t,（Case 2）L′＞L＝t, and（Case 3）L′＝L＝t.
Note that the proof technique of Cases 1 and 2 is the same as the proof of Proposition 1 of Okamoto（2018）.
Case 1. L＞t.
Claim 1-1. x Li－1≠C Li－2 or C Li－1＝0.
Suppose that x Li－1＝C Li－1and C Li－1＞0. By C Li－1≠0 and the definition of cumulative clinches,∑j≠i xiL－ . Therefore, xiL－ ＝M－∑j≠i xiL－ . By bidding constraint for each j∈N,
x Lj ≤ x Lj . Hence, ∑i∈N x ti ≤ M .This means that the auction ends at L－1. This is a contradiction.

CiL－2＝M－
－1

1

2

2

－2

L－1）
.
Claim 1-2. x Li－1≤Q（
i p

By the definition of sincere-bidding,L－1） .
x Li－1＝min x Li－2, max C Li－2, Q（
i p

Then, by Claim 1-1,
L－1）.
x Li－1＝min x Li－2, Q（
i p
L－1）
.
Hence, x Li－1 ≤ Q（
i p

Claim 1-2 is the same argument as step 1 of Lemma 2 of Okamoto（2018）.Therefore, by using
Claim 1-2, we can show that bidder i has no incentive to deviate similarly to Lemma 2 of Okamoto（2018）.
Case 2. L′＞L＝t.
For each j∈N and each s ≤ t－1, x js＝x̂ sj , because there are parts of h t.
Hence, for each s ≤ t－1＝L－1, C si＝Ĉ si . Then, we shall calculate Ci and Ĉ si Ls′＝L .
L
Claim 2-1. Q（≤C Li.
i p ）By the definition of sincere-bidding,Lx Li＝min x Li－1, max C Li－1, Q（
i p ） .

By the bidding constraint and the definition of the sincere-demand,x Li－1 ≥ C Li－1
35

『経済研究』（明治学院大学）第 161 号
L－1） Q（p L）
x Li－1＞Q（
.
≥ i
i p

Then,
L
x Li＝max C Li－1, Q（
i p ）.
L
Therefore, Q（≤x Li. By the definition of assignments, x Li  ≤C Li  ≤ x Li－1.
i p ）L
Hence, Q（≤C Li.
i p ）Claim 2-2. C Li≤Ĉ Li.
＊tL
t . Then, for each j i, x L
Since t＝L, for each j≠i, x Lj＝σ＊j |h（t h ）and x̂  j＝σ j |h（t h）≠ j＝ x̂ Lj . Since

L′＞L, the auction does not end at L in the history w L′＋1.
Then,x̂ jL＝M－∑xjL.
∑
j≠i
j≠i

ĈiL＝M－

Since the auction ends at L in the history z L＋1,

xiL.
∑
j≠i

CiL ≤ xiL ≤ M－
Therefore, C Li  ≤Ĉ Li.

Ls
By Claim 2-1 and Claim 2-2, Q（≤C Li≤Ĉ Li . Furthermore, for all s≥L＋1, Q（≤Ĉ si , bei p ）
i p ）
s
L
L
s
L＋1 is not less than that in w L′
＋1.
cause Q（≤Q（i p ）i p ）and Ĉ i  ≤Ĉi . Therefore, i’s utility in z

Case 3. L′＝L＝t.
Similarly to Case 2, we show that for each s≤t－1＝L－1, C si＝Ĉ si . Then, we shall calculate C Li
and Ĉ Li.
Claim 3-1. C Li＝x Li.
By the definition of sincere-bidding and x Li－1＞Q Li－1,

a Li＝0.
Therefore, by the auction rule, i’s assignment in z L＋1 is the same as i’s last bid x Li, and so C Li＝x Li.
L , then obviously i’s utility in z L＋1 is not less than that in w L′＋1. Then, we supIf x Li＝Q（
i p ）L . Thus, C L Q
pose x Li＝C Li－1. Hence, C Li＝C Li－1. By the definition of sincere-bidding, C Li－1≥Q（
i p ）
i≥ i

（p L）. By the definition cumulative clinches, Ĉ Li≥Ĉ Li－1 . Therefore, Ĉ Li  ≤C Li  ≤Q Li, and so i’s utility inz L＋1 is not less than that in w L′＋1.
On the equilibrium path, all bidders never overbid at each round by the definition of sincerebidding, and so all signals are 1. If all signals are 1, the outcome of the Ausubel auction with the receive option of over-assignments is the same as the outcome of original Ausubel auction with proportional rationing. Therefore, sincere-bidding equilibrium obtains the Vickrey outcome.
36

The Ausubel Auction with the Receive Option of Over-Assignments

4．Conclusion
We have proposed a new auction, the Ausubel auction with the receive option of over-assignments. We have shown that in this auction, sincere-bidding equilibrium is an ex-post perfect equilibrium and yields the Vickrey outcome. Here, we compare our new rule with the Ausubel auction withsequential rationing. In the Ausubel auction with sequential rationing, the bidders have to be prioritized by some way. Therefore, as a priority changes, does an allocation in that auction.6
On the other hand, our new auction does not need a priority on bidders. In fact, if the bids oftwo bidders are the same, then the assignments of two bidders are the same. In this sense, our auction treats all bidders equally. It is sure that there may be some unsold objects in our auction. However, on a sincere-bidding equilibrium path, our auction are able to sell all objects, and it obtains aneﬃcient outcome because it is the Vickrey outcome.

References
Ausubel, Lawrence M.（1997）“An Eﬃcient Ascending-Bid Auction for Multiple Objects,” University of Maryland, Working Paper 1997.
Ausubel, Lawrence M.（2004）“An Eﬃcient Ascending-Bid Auction for Multiple Objects,” American Economic Review, Vol. 94 ⑸ , pp. 1452-1475.
Ausubel, Lawrence M.（2018）“An Eﬃcient Ascending-Bid Auction for Multiple Objects: Reply” American Economic Review, Vol. 108-2, pp. 561-563.
Clarke, Edward H.（1971）“Multipart Pricing of Public Goods,” Public Choice, Vol. 11, pp. 17-33.
Crémer, Jacques and Richard P. McLean（1985）“Optimal Selling Strategies under Uncertainty for a Discriminating Monopolist when Demands Are Interde- pendent,” Econometrica, Vol. 53 ⑵ , pp. 345-341.
Groves, Theodore（1973）“Incentives in Teams,” Econometrica, Vol. 41-4, pp. 617-31.
Krishna, Vijay（2009）Auction Theory, Second Edition, Academic Press. Okamoto, Noriaki（2018）“An Eﬃcient Ascending-Bid Auction for Multiple Objects: Comment,” American Economic Review, Vol. 108-2, pp. 555-560.
Osborne, Martin J. and Ariel Rubinsterin（1994）A Course in Game Theory, MIT Press.
Selten, Reinhard（1975）“Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games,”
International Journal of Game Theory, Vol. 4-1, pp. 25-55.
Vickrey, William（1961）“Counterspeculation, Auctions, and Competitive Sealed Tenders,” Journal of Finance, Vol.
16-1, pp. 8-37


6

Note that on an sincere-bidding equilibrium path, the utilities of all bidders never change even if a prioritychanges.
37