ISSN (Print) 0473-453X

Discussion Paper No. 1116

ISSN (Online) 2435-0982

MULTI-OBJECT AUCTION DESIGNBEYOND QUASI-LINEARITY:
LEADING EXAMPLES

Yu Zhou
Shigehiro Serizawa

January 2021

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Multi-object Auction Design Beyond
Quasi-linearity: Leading Examples
Yu Zhouy

Shigehiro Serizawaz

January 25, 2021

Abstract
In multi-object auction models with unitary demand agents, if agents’utility functions satisfy quasi-linearity, three auction formats, sealed-bid
auction, exact ascending auction, and approximate ascending auction, are
known to identify the minimum price equilibrium (MPE), and exhibit elegant e¢ ciency and incentive-compatibility. These auctions are conjured topreserve their properties beyond quasi-linearity. Nevertheless, we exemplifythat with general utility functions, these auctions fail to identify the MPEs
and are substantially ine¢ cient and manipulatable. The implications of ournegative results for multi-object auction models with agents with multi-unit
demand, and matching with contracts models are also discussed.
Keywords: Multi-object auction, minimum price equilibrium, examples, quasi-linear utility functions, general utility functions
JEL Classi…cation: C78, D44, D74

We thank Debasis Mishra, Qianfeng Tang, and Ning Sun for their helpful comments. The
preliminary version of this paper was presented at ISI-ISER Young Economists Workshop 2020
and Nanjing-Osaka Economic Theory Workshop 2021. We thank participants at those workshops
for their comments. We gratefully acknowledge …nancial support from the Joint Usage/ResearchCenter at ISER, Osaka University and Grant-in-aid for Research Activity, Japan Society for the
Promotion of Science (15H05728, 19K13653, 20H05631, 20KK0027).
yMain address: Graduate School of Economics, Kyoto University, Yoshida-Honmachi, Sakyoku, Kyoto, 606-8501, Japan. E-mail: zhouyu_0105@hotmail.com; A¢ liated address: Instituteof Social and Economic Research, Osaka University, 6-1 Mihogaoka, Ibaraki, Osaka 567-0047,
Japan.
z
Institute of Social and Economic Research, Osaka University, 6-1 Mihogaoka, Ibaraki, Osaka
567-0047, Japan. E-mail: serizawa@iser.osaka-u.ac.jp

1

Introduction

Governments in many countries conduct auctions to allocate social resources. The
most important and innovative examples are spectrum license auctions in many
countries including most of the OECD. They auction o¤ several licenses simultaneously and often generate enormous revenue. For instance, in the 2000 British
3G spectrum license auctions, the revenue from selling …ve licenses amounted to2.5% of the UK’s GNP (Binmore and Klemperer, 2002). Those auctions also haveconsiderable impacts on industry development, and so it is vitally important todesign governments’auctions to achieve their goals. However, such large-scale auctions cause violations of quasi-linearity and small (or continuous) price increment.
These are the basic assumptions of auction theory on which auction designs are
based. We analyze the e¤ects of these violations on the performance of well-known
auctions and the implications for auction design.
E¢ ciency is a central goal of government auctions. It requires that objects
be given to those who value them most. However, in many cases, informationsuch as preferences over objects is only privately known by agents. Thus, toattain e¢ ciency, it is indispensable for auction mechanisms to directly or indirectly
extract true information from agents. Strategy-proofness is such a requirement for
direct mechanisms, and it gives agents no incentive to manipulate information in
the sense that revealing true information is a dominant strategy for each agent.
We focus on the setting in which each agent has unitary demand. In thissetting, there is a minimum price equilibrium (MPE) whose price (vector) is aunique and coordinate-wise minimum among all equilibrium prices. The MPE
mechanism, the direct mechanism choosing an MPE allocation for each pro…leof agents’ preferences, is the only mechanism that satis…es e¢ ciency, strategyproofness and other essential requirements such as individual rationality and no
subsidy (Holmstrom, 1979; Morimoto and Serizawa, 2015). Moreover, the MPE
mechanism maximizes revenue among mechanisms satisfying strategy-proofness,
individual rationality, no subsidy and equal treatment of equals for each preference
pro…le (Kazumura et al., 2020). Thus, if an auction mechanism duplicates theoutcome of the MPE mechanism, it achieves important goals for governments.
In quasi-linear environments where agents’preferences are quasi-linear, there
are three representative formats of auctions that …nd the MPEs. These auctions
are fundamental to the auction theory literature and provide the basic ideas ofmany auction designs in an even more general environment, e.g., agents havemulti-unit demand (Gul and Stacchetti, 2000; Ausubel, 2006; Sun and Yang,2009). The …rst one is a sealed-bid auction, called the “Vickrey mechanism.”·The
MPE coincides with the Vickrey allocation under quasi-linearity (Leonard, 1983).
Demange et al. (1986) provide another two auction formats, exact ascending

1

(EA) auction and approximate ascending (AA) auction. For the EA auction, they
assume that the price increment coincides with the unit of agents’valuations, forexample, agents’valuations and price increments are both integers and show that
under such an assumption, the EA auction generates an MPE. For the AA auction,
originating from the salary adjustment process in Crawford and Knoer (1981), they
assume that the increment is small and …nd that the AA auction generates a pricethat deviates the MPE price coordinate-wise within some bounds. In other words,
the AA auction approximately duplicates the MPE mechanism.
However, the assumption of quasi-linearity is dubious for the government auctions cited above. A preference satis…es quasi-linearity with respect to a good if
the expenditure on the good is so much smaller than an agent’s income or wealththat its income e¤ect is negligible. However, in many government auctions, bidders pay enormous amounts and face …nancial constraints. These factors maketheir preferences far from quasi-linear.
The assumption that the increment is small and coincides with the valuation
unit is also unreasonable. Agent valuations are primitive data independent ofauctions and can be any real numbers or any amounts measured by monetary
units. In contrast, price increments are set in advance, as a part of auction design.
The speed of auctions crucially depends on the price increments, and in practice,they are set large enough that the auction concludes within a reasonable time.
Typically, the price increments are much larger than the unit of agents’valuations.
Many auction mechanisms in the literature and practice are based on theimplicit conjecture that even without quasi-linearity and the coincidence ofincrement and valuation units, the above three auction formats duplicate or approximate the MPE mechanism, and preserve e¢ ciency and strategy-proofness.
However, we demonstrate that such a conjecture is far from validated.
First, to analyze the Vickrey mechanism, we generalize agents’valuations over
objects for non-quasi-linear environments. We de…ne the generalized valuation ofan object as an agent’s willingness to pay for the object from the point where
she obtains no object and pays nothing. Then, we de…ne the generalized Vickrey
mechanism by replacing the valuations in the formula of the Vickrey allocation
with the generalized valuations. We show that in non-quasi-linear environments,
the generalized Vickrey mechanism fails to …nd the MPE, is far from e¢ cient, andprovides agents with strong incentives to manipulate.
Second, we analyze whether an EA auction will work without the coincidence
of increment and valuations’unit. We exemplify that even in quasi-linear environments, for any price increment larger than the units of agents’valuations, theEA auction overshoots the MPE prices by an arbitrarily large distance, generates
allocations that are far from e¢ cient, and provides agents with strong incentives
to manipulate. The auction mechanisms targeting MPEs in quasi-linear environ2

ments, as proposed by, e.g., Mishra and Parkes (2009), Andersson and Erlanson(2013), and Liu and Bagh (2019), are all based on the coincidence of increment
and valuation units. Our negative results extend to their auction mechanisms byconstructing similar examples.
Third, we analyze whether an AA auction will work without quasi-linearity andthe coincidence of increment and valuation units. We exemplify that in non-quasilinear environments, the AA auction overshoots and undershoots the MPE prices
by an arbitrarily large distance. Thus, in contrast to the quasi-linear environments,
the AA auction fails to approximate the MPE mechanism. We also exemplify that
the AA auction generates allocations that are far from e¢ cient and provides agentswith strong incentives to manipulate.
In addition, we also discuss the implications of our negative results for multiobject auction models with agents with multi-unit demand and matching with
contracts models at the end of this paper.
The remainder is organized as follows: Section 2 de…nes the model and MPEs.
Section 3 de…nes conditions for ine¢ ciency, manipulability, e¢ ciency and strategyproofness. Section 4 reviews the auctions for MPEs in the quasi-linear environment. Section 5 exempli…es that without quasi-linearity and the coincidence ofincrement and valuation units, the auctions shown in Section 4 fail to identify the
MPEs and are substantially ine¢ cient and manipulatable. Section 6 concludes
the paper and discusses the implications of the results obtained in Section 5.

2

The model and minimum price equilibrium

There is a …nite set of agents N and a …nite set of heterogeneous objects M . Not
receiving an object is called receiving the dummy, denoted by 0. Let L M [ f0g.
Each agent either receives an object or the dummy.
Agents have preferences on the consumption space L R. We abuse language
and identify a preference of agent i with her utility representation ui .
De…nition 1: A utility function ui : L R ! R is general if:(i) For each l 2 L, ui (l; ) is continuous and strictly decreasing in R.
(ii) For each pair l; l0 2 L, each t 2 R, there is t0 2 R such that ui (l; t) = ui (l0 ; t0 ).
Let U be the set of general utility functions and u
pro…le.

(ui )i2N 2 U n be a utility

De…nition 2: A utility function ui 2 U is quasi-linear if there is a valuation
function vi : L ! R such that for each (l; pl ) 2 L R, ui (l; pl ) = vi (l) pl .

Each quasi-linear utility function ui can be represented by a valuation function
vi . We assume, w.o.l.g., that for each i 2 N , vi (0) = 0. Let U QL be the set ofquasi-linear utility functions. Notice that U QL U.
3

For each agent i 2 N , let xi 2 L be her assigned object. An assignment
x (xi )i2N 2 LN is a list of individually assigned objects such that except for thedummy, no two agents obtain the same object, i.e., if xi 6= 0 and i 6= j, xi 6= xj .
Let X be the set of assignments.
Agent i0 s demand set at price p 2 RL+ is de…ned as Di (p) fl 2 L : ui (l; pl )ui (l0 ; pl0 ); 8l0 2 Lg. We assume, w.o.l.g., that the price of the dummy is zero andthe reserve prices of all the objects are zero.
De…nition 3: A pair (x; p) 2 X RL+ is an equilibrium if:(i) For each i 2 N , xi 2 Di (p).
(ii) For each l 2 M , if pl > 0, there is i 2 N such that xi = l.

When agents have general utility functions, there is an equilibrium, and the setof equilibrium prices is a complete lattice (Demange and Gale, 1985). Thus, there
is a minimum price equilibrium (MPE) whose price is unique and coordinatewise minimum among all equilibrium prices. For each utility pro…le u 2 U n , letpmin (u) be the MPE price. Although the MPE price is unique, the corresponding
assignment may not be unique since indi¤erence is allowed. However, for eachagent, her assignment at any MPE is welfare-equivalent: given a utility pro…le u,min0
if (x; pmin (u)) and (x0 ; pmin (u)) are two MPEs, then ui (xi ; pminxi ) = ui (xi ; px0 ).
i

3E¢ ciency and incentive-compatibility

This section studies the properties of (direct) mechanisms, which are shown to becornerstones of practical auction design.
An allocation z (xi ; ti )i2N 2 X RN is a list of individually assigned objects,
paired with the corresponding payments. Let Z be the set of allocations. A
mechanism f is de…ned as a function from U n to Z that maps to each utility pro…leu an allocation z. For each agent i 2 N , let xi (u) be the object assigned and ti (u)be the associated payment speci…ed by mechanism f , and let fi (u) = (xi (u); ti (u)).
First, we introduce e¢ ciency.
E¢ ciency: An allocation z 2 Z is e¢ cient for u 2 U n if there is no z 0 2 Z such
that.
(i) X
for each X
i 2 N , ui (zi0 ) ui (zi ) with at least one strict inequality,
(ii)
ti
t0i .
i2N

i2N

A mechanism f is e¢ cient if for each u 2 U n , f (u) is e¢ cient for u.

A mechanism f on (U QL )n is e¢ cient if and only if for each u 2 (U QL )n ,Px(u) 2 arg max i2N vi (xi ).1 However, this result typically does not hold for
x2X

general utility functions (Zhou and Serizawa, 2018).
1

See footnote 29 in Zhou and Serizawa (2018) for a complete proof of this statement.

4

We introduce variants of e¢ ciency. It allows the allocation to be ine¢ cient
but per capita ine¢ ciency to be bounded.
r-e¢ ciency:2 Given r 2 R+ , an allocation z 2 Z is r ine¢ cient for u 2 U n if
there is z 0 2 Z such that0(i) fori ) > ui (zi ), andXeach i 2 N , ui (zX(ii)
ti + r jN j
t0i ,
i2N

i2N

and z are r e¢ cient if no such z 0 exists. A mechanism f is r ine¢ cient if there
is u 2 U n such that f (u) is r ine¢ cient for u, and f is r e¢ cient if for eachu 2 U n , f (u) is r e¢ cient for u.

In the case of r = 0, r e¢ ciency coincides with e¢ ciency. For a small r > 0,r e¢ ciency is “approximate e¢ ciency.”However, given a large r > 0, r e¢ ciency
is a rather weak requirement.
Next, we de…ne the incentive properties of mechanisms. “Manipulability”
states that an agent bene…ts from misrepresenting her utility function, i.e., amechanism f on U n is manipulable if there are a utility function pro…le u 2 U n ,an agent i 2 N and u0i 2 U such that ui (fi (u0i ; u i )) > ui (fi (u)). Strategy-proofness
states that a mechanism is not manipulable.
Strategy-proofness: For each ui 2 U, each i 2 N , and each u0i 2 U, ui (fi (u))
ui (fi (u0i ; u i )).
We also introduce variants of manipulability and strategy-proofness. Givenr 2 R+ , “r-manipulability” states that an agent bene…ts more than r from misrepresenting her utility function, in terms of the payment, paired with the object
under truth telling.
r-manipulability: Given r 2 R+ , a mechanism f on U n is r-manipulable if
there are a utility function pro…le u 2 U n , an agent i 2 N and u0i 2 U such thatui (fi (u0i ; u i )) > ui (xi (u); pi (u) r).
r strategy-proofness: Given r 2 R+ , a mechanism f on U n is r strategy-proof
if f on U n is not r-manipulable.

If r = 0, r strategy-proofness is exactly strategy-proofness. For a smallr > 0, r strategy-proofness is “approximate strategy-proofness,” that is, eachagent has only a small incentive to manipulate. However, given a large r > 0,r manipulability states that an agent may have a strong incentive to manipulate
and thus implies that the mechanism cannot be implemented.
An MPE mechanism is a function that maps to each utility pro…le an MPE.
When agents have quasi-linear utility functions, the MPE mechanism is equivalent
to the Vickrey mechanism, which associates with each quasi-linear utility pro…le2

Our de…nition is in the spirit of that of the approximate core in classical general equilibrium
theory, when the size of the coalition is the set of all agents; see, e.g., Hildenbrand et al. (1973).

5

a Vickrey assignment and payment (Leonard, 1983). The MPE (Vickrey) mechanism is the unique mechanism satisfying e¢ ciency, strategy-proofness, individual
rationality, and no subsidy (Holmstrom, 1979). Such a characterization of MPE
mechanism holds for the general utility functions (Morimoto and Serizawa, 2015).

4

Auctions for MPEs with quasi-linear utility functions

In this section, we introduce three well-known auction formats designed to implement MPEs under various assumptions in the quasi-linear environment.

4.1

The sealed-bid auction

In the quasi-linear environment, the MPE allocation coincides with the Vickrey
allocation (Leonard 1983). Thus, the MPE can be characterized by a closed-form
expression. Formally, we have the following results.
Fact 1: Let u 2 (U QL )n and (x ; pmin (u)) be an MPE. Then,P(i) x 2 arg max i2N vi (xi ).
x2X(ii) If l 2 M is unassigned, pmin(u) = 0, and if l 2 M is assigned to agent i,
l P
P
pmin
(u)
=
max
v
(x
)
j
l
j2N nfig vj (xj ).
j2N nfig j
x2X

Fact 1 indicates that a sealed-bid auction can be used to implement an MPE(Leonard, 1983). In the auction, each bidder reports all her valuations of theobjects to the auctioneer. Then, the auctioneer speci…es the assignment and priceto bidders in the formula presented in Fact 1.
The mechanism induced by this sealed-bid auction is exactly the MPE mechanism, and so it is e¢ cient and strategy-proof.
In Section 5.1, we show that the sealed-bid auction or its generalized variant
fails to …nd the MPE and to be e¢ cient and strategy-proof.

4.2

The exact ascending auction

Demange et al. (1986) provide an exact ascending auction that …nds an MPE
price. The idea of this auction is to iteratively eliminate the set of objects thatare “overdemanded”by raising their prices.
De…nition 4: A nonempty set of objects M 0 M is overdemanded at p if
M 0 gj > jM 0 j .

jfi 2 N : Di (p)A set of objects M 0 is minimally overdemanded at p if M 0 is overdemanded at p
and no proper subset of M 0 is overdemanded at p.
Now, we de…ne the exact ascending auction.
6

The exact ascending (EA) auction: Let d > 0 be the increment.
Starting with reserve prices, each agent reports her demand set at the current
price. If there is a set of objects that are minimally overdemanded, then theauctioneer raises the prices of those objects by d. Otherwise, the auctioneer stops
the auction at the current price.
Demange et al. (1986) assume that agents’ valuations are discrete and multiples of the increment, i.e., the increment coincides with unit of valuation unit.
(Hereafter, coincidence assumption) In other words, they focus on the class ofutility functions, U QLd
fui 2 U QL : vi (L) d Ng. They obtain the following
result for utility pro…les in this class.
Fact 2: Let d > 0 and u 2 (U QLd )n . Then, the EA auction with increment d …nds
an MPE price for u in a …nite number of steps.
The EA mechanism with increment d is a function that maps to eachutility pro…le the outcome of the EA auction with increment d for that pro…le.
Fact 3: Let d > 0. The EA mechanism with increment d on (U QLd )n coincides
with the MPE mechanisms on (U QLd )n , and so it satis…es e¢ ciency and strategyproofness.
Compared with sealed-bid auctions, one merit of EA auctions is that theprice formation process is transparent to all bidders, i.e., all bidders can see how
prices change in the auction and where the prices stop changing. Researchers
design di¤erent formats of auctions to improve the speed of …nding an MPE in
the quasi-linear environment, see, e.g., Mishra and Parkes (2009) and Andersson and Erlanson (2013). They explicitly assume that agents’ valuations andincrementndecrement are both integers.
Note that the coincidence assumption is crucial to …nd the MPE price in abovementioned works. We discuss these points in Section 5.2.

4.3

The approximate ascending auction

Demange et al. (1986) propose another type of auction, the approximate ascending
auction, that …nds an “approximate”equilibrium price coordinate-wise close to the
MPE price. This auction is introduced by Crawford and Knoer (1981).
The approximate ascending (AA) auction: Let d > 0 be the increment.
Initially, all the agents are uncommitted and stand in a queue. Agents are called
one by one to bid. When agent i is called, she has the following three options.
Option 1 is to bid on an unassigned object l. This option commits agent i toobject l at its reserve price.
Option 2 is to bid on an object l that is tentatively assigned to some other agent
j at price pl . This option increases the price of object l by d, commits agent i to7

object l at price pl + d and drives agent j back into the queue of uncommitted
agents.
Option 3 is to drop out by bidding on the dummy.
The auction terminates when all uncommitted agents drop out.
Note that the bidding queue can be formed in many ways. In essence, it contains
two parts. The …rst part is the initial order when agents stand in a queue. The
permutations of agents make n! variants. The second part concerns treating agents
when driven back into the queue of uncommitted agents. A natural rule is to place
an agent at the end of the queue when driven back. Other rules include placing thedriven back agent …rst in the queue, second in the queue, and so forth. Moreover,di¤erent agents may be treated di¤erently. Thus, the number of variants of queues
is much more than n!. The outcomes of the AA auction also depend on how weform the bidding queue.
Additionally, note that when a bidder is called, she is supposed to bid on an
object from her demand set at the price she faces. Her demand set may containseveral objects. In that case, she needs to choose one object among them on which
to bid. The outcomes of the AA auction depend on such choices of bidders even
if the utility function pro…le is …xed.
It is known that when prices vary discretely and agents’valuations of objects
are arbitrary real numbers, an equilibrium may not exist. Moreover, the outcomeof the AA auction may not be an equilibrium even if it exists. Thus, we introduce
a concept of approximate equilibrium, the “" equilibrium.”
Given " 0, agent i’s " demand set at p is given by:Di" (p)fl 2 L : ui (l; pl )ui (0; 0), and 8l0 2 M; ui (l; pl )ui (l0 ; pl0 + ")g.

An object in Di" (p) approximately maximizes agent i’s welfare at price p for small", and when " = 0, Di" (p) = Di (p).
De…nition 5: A pair (x; p) 2 X " NL+ is an " equilibrium if:(i) For each i 2 N , xi 2 Di" (p).
(ii) For each l 2 M , if pl > 0, there is i 2 N such that xi = l.
De…nition 5(i) states that each agent receives an object in her " demand set.
De…nition 5(ii) coincides with De…nition 3(ii). When " = 0, an " equilibrium isan equilibrium. In De…nition 5, p 2 " NL+ and so prices vary discretely for " > 0.
In general, any " equilibrium is " e¢ cient.3
In the following, we set " = d, where d represents the increment, and replacethe " equilibrium with the d equilibrium.
30
Suppose that there is an " equilibrium thatXis not " e¢ cient.
XThus there is z 2 Z such00that (i) for each i 2 N , ui (zi ) > ui (zi ), and (ii)ti + " jN jti . By (ii), there is i 2 Nsuch that t0x0i

i2N

px0i + ". Thus by (i), ui (x0i ; px0i + ")8i2Nui (zi0 ) > ui ( zi ), contradicting xi 2 Di" (p).

Fact 4: Let u 2 (U QL )n , d > 0, and the bidding queue q be given. Suppose thateach uncommitted agent arbitrarily bids on an object from her demand set at theprice proposed to her.
(i) The AA auction with increment d and bidding queue q …nds an d equilibriumin …nitely many steps.
(ii) (Deviation bound) Let p(u) be the price generated by the AA auction in(u)d minfjM j ; jN jg.
(i). For each l 2 M , pl (u) pminl
In contrast to Fact 2, Fact 3 allows agents’ valuations to be arbitrary real
numbers and hence can have di¤erent measurement units from the increment.
As noted above, the outcomes of the AA auction depend on the queueing rules
and bidders’choices from their demand sets even if the utility function pro…le is…xed. Fact 4 (ii) states that for any quasi-linear utility pro…le, the deviationpl (u) pmin(u) is bounded by d minfjM j ; jN jg regardless of queueing rules andlbidders’choices from their demand sets. Thus, as d goes to zero, the outcome of
the AA auction with increment d converges to an MPE price.
The AA mechanism with increment d and bidding queue q is a functionthat maps to each utility pro…le the outcome of the AA auction with increment d
and bidding queue q for that pro…le. The AA mechanism is neither e¢ cient nor
strategy-proof. However, Fact 5 holds.
Fact 5 (Roughgarden, 2014): Let d > 0, k = 2 minfjM j ; jN jg, and a bidding
queue q be arbitrarily given. The AA mechanism with increment d and bidding
queue q on (U QL )n is d e¢ cient and k d strategy-proof.
Fact 5 implies that the AA auction works well for quasi-linear utility functions
even without the assumption of the same measurement unit. Nevertheless, it fails
to work without assuming quasi-linearity. We discuss this point in Section 5.3.

5Implementability of MPE for general utility functions

5.1

The sealed-bid auction

First, we investigate the possibility of generalizing the sealed-bid auction of Fact
1 to implement MPEs for general utility functions. The formula in Fact 1 is basedon valuations. Thus, to conduct the sealed-bid auction using this formula forgeneral utility function pro…les, the valuations need to be generalized. A naturalgeneralization of the valuation of an object is the agent’s willingness to pay forthat object from the dummy with no payment. Formally, for each i 2 N , eachui 2 U, and each l 2 L, let Vi (l) 2 R be the generalized valuation of an object lsuch that ui (l; Vi (l)) = ui (0; 0). For a quasi-linear utility function, for each l 2 L,

9

Vi (l) = vi (l), an Vi (0) = vi (0) = 0. “Generalized Vickrey allocations” employ
generalized valuations to reformulate Fact 1.
De…nition 6: A pair (xV ; pV ) 2 XP(i) xV 2 arg max i2N Vi (xi ),RL+ is a generalized Vickrey allocation if

x2X(ii) if l 2 M is unassigned, pVl = 0 and if l 2 M is assigned to agent i, pVl =PPVmax j2N nfig Vj (xj )j2N nfig Vj (xj ).
x2X

Let pV (u) be the generalized Vickrey payment for utility pro…le u.

Proposition 1: There is u 2 U n such that (i) the MPE price pmin (u) is di¤erent from the generalized Vickrey payment pV (u), and (ii) no MPE assignment
coincides with the generalized Vickrey assignment xV (u).
We demonstrate Proposition 1 by Example 1 below. This 2-object and 3-agent
example can be easily generalized to the cases of more agents and objects.
Example 1: Let M = fa; bg and N = f1; 2; 3g. Let r > 0 and u 2 U 3 be suchthat:(1) V1 (a) = r and V1 (b) = 2r.
(2) V2 (a) = 20r, V2 (b) = 10r, u2 (a; r) = u2 (b; 0) = u2 (0; 3r), and u2 (0; 1) =u2 (a; 3r) = u2 (b; 2r) = u2 (0; r).
(3) V3 (a) = 10r, V3 (b) = 30r, u3 (a; 3r) = u3 (b; 2r), and u3 (a; 8r) = u3 (b; 2r).
By the generalized valuations in (1), (2), and (3), pV (u) = (pV0 ; pVa ; pVb ) =(0; r; 2r), and there is a unique generalized Vickrey assignment xV = (xV1 ; xV2 ; xV3 ) =(0; a; b).
By the generalized valuations in (1) and utility functions in (2) and (3),min minpmin (u) = (pmin0 ; pa ; pb ) = (0; 3r; 2r) and x = (x1 ; x2 ; x3 ) = (0; b; a) is theunique MPE assignment. Thus, pmin (u) 6= pV (u) and x 6= xV .
4
Proposition 1 states that the sealed-bid auction for the generalized Vickrey
allocation may not be an MPE, and in some cases, it is even not an equilibrium;see, e.g., (xV ; pV ) in Example 1.
In the following, we discuss r e¢ ciency and r strategy-proofness of the generalized Vickrey mechanism.
Given r > 0, consider the economy in Example 1. Let z1 = (0; 0:5r), z2 =(b; 0:5r), and z3 = (a; 7:5r). For each i 2 f1; 2; 3g, ui (zi ) > ui (xVi ; pVxV ), andi
7:5r 0:5r 0:5r = 6:5r > 2r + r + 3r. Thus (xV ; pV ) is not r e¢ cient for u, andso the generalized Vickrey mechanism is not r e¢ cient.
Suppose that agent 3 has a utility function u03 such that V30 (a) = 35r, V30 (b) =8r, and u03 (a; 10r) = u03 (b; 4r). For the utility pro…le (u1 ; u2 ; u03 ), agent 3 obtains(a; 12r) under the generalized Vickrey allocation. Since u03 (b; 2r) > u03 (b; 4r) =10

u03 (a; 10r) > u03 (a; 12r), agent 3 bene…ts from reporting u3 when her true utility function is u03 . Thus, the generalized Vickrey mechanism is r manipulable.
Therefore, the following holds.
Proposition 2: For an arbitrarily large r > 0, the generalized Vickrey mechanism
is r ine¢ cient and r manipulable on U n .

5.2

The exact ascending auction

In this subsection, we study whether the EA auction works without the coincidence
assumption but in the quasi-linear environment.
Example 2 below illustrates the large overshooting of the EA auction without
the coincidence assumption even if utility functions are quasi-linear.
Example 2: Let d > 0 be an increment and r > d be a large number. Let t 2 N++
be such that t d > r > (t 1) d. Let M = fa; bg and N = f1; 2g. Let u 2 (U QL )2
be represented by a valuation pro…le (v1 ( ); v2 ( )) such that:(1) v1 (a) = (t + 0:1) d and v1 (b) = (t + 0:5) d.
(2) v2 (a) = (t + 0:2) d and v2 (b) = (t + 0:8) d.
Note thatv1 (b) v1 (a) = 0:4d and v2 (b) v2 (a) = 0:6d,( )min min
Note further that pmin (u) = (pmin0 ; pa ; pb ) = (0; 0; 0:4d) and the MPE assignment is xmin = (a; b).
We illustrate how the EA auction proceeds. The auction starts from round
0 with the initial price p0 = (0; 0; 0). By ( ), D1 (p0 ) = D2 (p0 ) = fbg. Since
only b is overdemanded at p0 , its price p0b is raised by d. Let p1 = (0; 0; d). By( ), D1 (p1 ) = D2 (p1 ) = fag. Since only a is overdemanded at p1 , its price p1a israised by d. Let p2 = (0; d; d). The EA auction repeats this process until prices
exceed agents’ valuations, i.e., until p2t+2 = (0; (t + 1) d; (t + 1) d). However,D1 (p2t+2 ) = D2 (p2t+2 ) = f0g. Thus, both bidders simultaneously drop out, andthe auction terminates at p2t+2 . That is, the outcome of the EA auction is thatthe price is p2t+2 and each agent receives the dummy and pays nothing.
4

Example 2 demonstrates that the EA auction may fail to …nd an MPE price.
Since r is arbitrarily large, the auction may substantially overshoot an MPE price.
This 2-object and 2-agent example can be easily generalized to the cases of moreagents and objects. Thus, Proposition 3 holds.
Proposition 3: (Large overshooting) For each d > 0 and arbitrarily larger > 0, there is u 2 (U QL )n such that the EA auction with increment d generates
a price p with pl > pmin(u) + r for each l 2 M .
lSince prices vary only discretely with increment d > 0, no equilibrium exists
for the utility pro…le u in Example 2. The nonexistence of equilibrium may be
11

a fundamental factor of the above problems. Thus, we consider approximate
equilibria and focus on d equilibria. The d equilibria for the utility pro…le u areprices p such that p = (0; k d; k d) for k = 0; 1; : : : ; t. However, the outcome priceof the EA auction for u in Example 2 is not among them. Thus, the EA auction
may fail to …nd even an d equilibrium price. Moreover, the assignment in the EA
auction outcome for u is not a d equilibrium assignment. Thus, the EA auction
may also fail to …nd a d equilibrium assignment.
Note that in Example 2, p0 = (0; 0; 0) is the closest d equilibrium price topmin (u) among all d equilibrium prices, and so p0 is an approximate MPE price.
Formally, an d equilibrium price pA is called the closest d equilibrium priceto pmin (u) if there is no other d equilibrium price p0 such that for each l 2 M ,pA
pljp0l pl j with at least one strict inequality. The price pA approximateslthe MPE price among d equilibrium prices.
Based on the insight from Example 2, we generalize it to the case with moreagents and objects and obtain the following result.
Proposition 4: For each d > 0 and arbitrarily large r > 0, there is u 2 (U QL )nsuch that the EA auction with increment d generates a price p with pl pA
l +r
for each l 2 M .
Finally, we study r e¢ ciency and r strategy-proofness of the EA mechanism.
Given r > 0, consider the economy in Example 2. Let z1 = (a; td) and z2 =(b; td). For each i 2 f1; 2g, ui (zi ) > ui (0; 0) = 0, and by t d > r, it holds thatt d + t d > 0 + 2r. Thus, the EA mechanism with increment d fails to …nd anr e¢ cient allocation for u.
Let u02 2 U QL be represented by a valuation function v20 ( ) such that v20 (a) =(t + 0:3) d and v10 (b) = (t + 0:1) d. Then, agent 2 with u02 demands only object aat the initial price p0 = (0; 0; 0). In this case, the EA auction concludes instantly,
and agents 1 and 2 receive objects b and a with no payment. Since td > r, itholds that u2 (a; 0) = (t + 0:2) d > u2 (0; r) = r. Thus, agent 2 bene…t morethan r from misreporting u02 when her true utility function is u2 . Thus the EA
mechanism with increment d is r manipulable.
The above discussion can be easily generalized to the cases of more agents andobjects, which indicates the following result.
Proposition 5: For each d > 0 and an arbitrarily large r > 0, the EA mechanismwith increment d is r ine¢ cient and r manipulable on (U QL )n .
Propositions 3, 4 and 5 imply that the EA auction fails to work without thecoincidence assumption even in the quasi-linear environment. Note that in Example 2, if one of two agents is given a priority to obtain object b at p0 at the
beginning of the auction, each agent obtains some object at a low price. This outcome is close to the MPE allocation and makes both agents much better o¤ than
12the outcome of the EA auction. This raises the question of whether the above
negative results on the EA auction might be due to the lack of a priority rule thatshould be applied when several agents demand the same object. We discuss thispoint in Subsection 5.3 since the AA auction has such a priority rule.
Mishra and Parkes (2009), Andersson and Erlanson (2013), and Liu and Bagh(2019), among others, propose auctions targeting MPEs in a quasi-linear environment with the coincidence assumption. By constructing similar examples, theabove negative results extend to their auctions.

5.3

The approximate ascending auction

In this subsection, we study whether the AA auction works as predicted by Facts
4 and 5 when agents have general utility functions. In the following, we set " = d,where d represents the increment in the auction.
First, we show that for a given general utility pro…le, if the increment issu¢ ciently small, the outcome price of an AA auction will be su¢ ciently close to
the MPE price.
Proposition 6: Let u 2 U n be given. Suppose that each uncommitted agent
arbitrarily bids on an object from her demand set at the price proposed to her
and the bidding queue is arbitrarily given. Let fdn g be a decreasing sequence suchthat for each n 2 N, dn > 0 and limn!1 dn = 0. Let pdn be the price generated
by the AA auction with increment dn . Then, limn!1 pdn = pmin (u).
The proof of Proposition 6 is relegated to the Appendix. Proposition 6 implies
that at the limit, i.e., as d goes to zero, the induced mechanism is indeed theMPE mechanism. This proposition assumes that when the utility pro…le u 2 U n
is …xed, the AA auction works well for a su¢ ciently small increment d. Note thathow fast auctions conclude depends on d.
However, it is common in practice for d to be set large enough in advance sothat the auction can terminate reasonably fast, without knowing the utility pro…leu. Thus, it is necessary to analyze whether the AA auction works for any utility
pro…le when d is …xed.
In an economy with two objects and three agents, Example 3 below illustrates
that the AA auction substantially undershoots the MPE price for any bidding
queue if only one agent has the non-quasi-linear utility function. The insight canbe easily generalized to the cases of more agents and objects.
Example 3: Let M = fa; bg and N = f1; 2; 3g. The bidding queue is in the orderof agent 1; 2 and 3, without any speci…cation about how uncommitted agents are
driven back into the queue in the auction. Let d > 0 be an increment and r > 0
be a large number. Let t 2 N++ be such that t d > r.
13

(1) Let u1 2 U QL be such that u1 (a; pa ) = td

pa and u1 (b; pb ) = 3td

pb :

4

(2) Let u2 2 U be such thatu2 (a; 0) > u2 (b; d) > u2 (a; 0:5d) = u2 (b; 2td) > 0.
(3) Let u3 2 U QL be such that u3 (a; pa ) = 0:5d

pa and u3 (b; pb ) = 0:6dpb .

For this pro…le u, pmin = (0; 0:5d; 2td), and x = (x1 ; x2 ; x3 ) = (b; a; 0) is aunique MPE assignment.
We illustrate how the AA auction proceeds. The auction starts in round 0
with the initial price p0 = (0; 0; 0). By D1 (p0 ) = fbg, agent 1 bids on b and is
tentatively assigned (b; 0). Then, agent 2 is called. If she bids on b, the price of bthat agent 2 faces is d. Thus, let p1 = (0; 0; d). By D2 (p1 ) = fag, agent 2 bids ona and is tentatively assigned (a; 0).
Then, agent 3 is called. If agent 3 bids on a, the price of a that she faces is d.
If agent 3 bids on b, the price of b that she faces is also d. Thus, let p2 = (0; d; d).
By D3 (p2 ) = f0g, agent 3 drops out by biding 0 and is assigned (0; 0).
There is no uncommitted agent in the queue, and so the auction terminates ata price p = (0; 0; 0) and an allocation where agents 1, 2 and 3 get (b; 0), (a; 0) and(0; 0), respectively. Note that pmin
pb = 2td > r. Thus, the outcome price of thebmin
AA auction can be smaller than pb by an arbitrarily large amount r.
4
Next, we provide Example 4 to show that in an economy with two objects andthree agents, the AA auction may substantially overshoot the MPE price.
Example 4:5 Let M = fa; bg and N = f1; 2; 3g. The bidding queue is such thatthe initial order of agents is 1; 2 and 3, and when driven back, the uncommitted
agent is placed last in the queue. Let d > 0 be an increment and r > 0 be a large
number. Let t 2 N++ be such that t = 3k for some odd number k 2 N++ and(t 2) d > r. Let u = (u1 ; u2 ; u3 ) 2 U QL U U satisfy the following6 :
u1 (a; pa ) =u2 (b; (tpa , and u1 (b; pb ) = (t + 0:1)dpb ;0:3)d) > u2 (a; 0) andu2 (a; 0:5d) = u2 (b; (t + 0:1)d) > u2 (0; 0) = u2 (a; (tu3 (b; (t0:5)d) = u2 (b; (t + 0:5)d),0:4)d) > u3 (a; 0) andu3 (a; 0:6d) = u3 (b; td) > u3 (0; 0) = u3 (a; (t40:4)d) = u3 (b; (t + 0:4)d).

For example, we can have that u2 (a; pa ) = 20td (20t 1:8)pa and u2 (b; pb ) = (12t+0:9)d pb .
Liu and Bagh (2019) provide a hybrid format of the EA and AA auctions that …nds an MPE
for quasi-linear utility functions. When applying their auction to the economy in Example 4,
overshooting also occurs.
6
The conditions for u2 and u3 are satis…ed by the following utility functions: u2 (0; p0 ) = p0 ,u2 (a; pa ) = (t 0:5) d pa , and u2 (b; pb ) = (2:5t 2:5) [(t + 0:5) d pb ]; u3 (0; p0 ) = p0 ,u3 (a; pa ) = (t 0:4) d pa , and u3 (b; pb ) = (2:5t 2:5) [(t + 0:4) d pb ].
5

14

For this pro…le u, the MPE price is pmin = (0; 0:5d; (t + 0:1) d) and the uniqueminmin
MPE assignment is xmin = (xmin
1 ; x2 ; x3 ) = (0; b; a).
We illustrate how the AA auction proceeds. The auction starts from round 0
with the initial price p0 = (0; 0; 0). By D1 (p0 ) = fbg, agent 1 bids on b and is
tentatively assigned (b; 0). Then agent 2 is called. If she bids on b, the price of bthat agent 2 faces is d. Thus, let p1 = (0; 0; d). By D2 (p1 ) = fbg, agent 2 bids onb and is tentatively assigned (b; d). Then, agent 1 is placed last in the queue, andagent 3 is called. If agent 3 bids on b, the price of b that agent 3 faces is 2d. Thus,
let p2 = (0; 0; 2d). By D3 (p2 ) = fbg, agent 3 bids on b and is tentatively assigned(b; 2d). Then, agent 2 is placed last in the queue, and agent 1 is called. Note thatsimilarly the three agents bid only on b until round t and pt = (0; 0; td). Then, by
t = 3k, agent 1 is tentatively assigned (b; td).
At round t + 1, since agent 2 is …rst in the queue, she is called. If she bids on b,
the price of b that agent 2 faces is (t + 1) d. Thus, let pt+1 = (0; 0; (t + 1) d). By
D2 (pt+1 ) = fag, agent 2 bids on a and is tentatively assigned (a; 0). Then agent
3 is called. Let pt+2 = (0; d; (t + 1) d). By D3 (pt+2 ) = fag, agent 3 bids on aand is tentatively assigned (a; d). Note that agents 2 and 3 bid only on a untilround 2t. In round 2t with price p2t = (0; (t 1) d; (t + 1) d), since t is an odd
number, agent 2 is called, bids on a and is tentatively assigned (a; (t 1) d). Let
p2t+1 = (0; td; (t + 1) d). Then agent 1 is called. By D3 (p2t+1 ) = f0g, agent 3
drops out by biding 0 and is assigned (0; 0).
Since there is no uncommitted agent in the queue, the auction terminates atprice p = (0; (t 1) d; t d) and assignment x = (x1 ; x2 ; x3 ) = (b; a; 0). Note that
= (t 1:5) d > r can be arbitrarily large.
4
pa pmina
The insight of Example 4 can be easily generalized to the cases with moreagents and objects with an arbitrary bidding queue. We summarize the insights
of Examples 3 and 4 by Proposition 7.
Proposition 7: Let an increment d > 0 and a bidding queue be given in the
AA auction. Suppose that each uncommitted agent bids on an object from her
demand set at the price proposed to her. Then, the following results hold forarbitrarily large r > 0.
(i) (Substantial undershooting) There is u 2 U n such that the AA auction
generates the price p with pa < pmin
r for each a 2 M .
a(ii) (Substantial overshooting) For each a 2 M , there is u 2 U n such that the
AA auction generates the price p with pa > pmin
+ r.
a
In contrast to Fact 4(ii), Proposition 7 implies that there is no increment
across all the general utility pro…les such that the AA auction neither substantially overshoots nor undershoots the MPE price.
Corollary 1: Let pd (u; q) be the price generated by the AA auction with increment15

d and a bidding queueing q for u 2 U n . Then, there are no d > 0 and a bidding(u)d.
queue q such that for each u 2 U n and each l 2 M , pdl (u) pminlFinally, we discuss the incentive issue of AA auctions. Let u03 2 U QL besuch that v30 (a) = 1:5d and v30 (b) = 2d in Example 4. Then when agent 3 iscalled in round 2 with price p2 = (0; 0; 2d), v30 (b) v30 (a) < p2b p2a = 2d; and so
D3 (p2 ) = fag. Then, agent 3 bids on a and is tentatively assigned (a; 0). Next,
agent 1 is called and faces price p3 = (0; d; 2d). By D1 (p3 ) = fbg, agent 1 bids
on b and is tentatively assigned (b; 2d). Then, agent 2 is called and faces pricep4 = (0; d; 3d). Agents 1 and 2 bid only on b until round t + 1. In round t + 1
with the price pt+1 = (0; d; td), since t is an odd number, agent 2 is called. Since
D2 (pt+1 ) = fbg, agent 2 bids on b and is tentatively assigned (b; td). In roundt + 2, agent 1 faces a price pt+2 = (0; d; (t + 1)d), since D1 (pt+2 ) = f0g, agent 1
drops out by biding 0 and is assigned (0; 0). Since there is no uncommitted agent
in the queue, the auction terminates, and generates a price p0 = (0; 0; td) and an
assignment x0 = (x01 ; x02 ; x03 ) = (0; b; a) where agent 3 obtains (a; 0).
Recall that in Example 4, under the utility pro…le (u1 ; u2 ; u3 ), agent 3 obtains(0; 0). Since t = 3k 3 and u3 (a; 0) > u3 (a; (t 0:4)t) = u3 (0; 0), when agent 3’strue utility function is u3 , she has the incentive to misreport u03 .
The insight of Example 4 and above discussion can be extended to show thefollowing result.
Proposition 8: For each d > 0 and arbitrarily large r > 0, the AA mechanismwith increment d and an arbitrary bidding queue q is r manipulable U n .

6Concluding remarks

We conclude by discussing the implications of our negative insights. First, in the
one-object auction model, existing work also studies a di¤erent auction format,
called a “clock auction.”It is the continuous variant of the ascending price auction.
The price rises continuously at a rate kept by a clock, and bidders drop out atsome point in time. The auction stops when there is only one bidder remaining
and generates a price at which the winning bidder obtains the object and pays thatprice. Since it is a dominant strategy for each bidder to drop out at her valuation,
this auction is simple and expeditious but also duplicates the MPE mechanism forone object. In Appendix B, we demonstrate the impossibility of extending such aclock auction to multi-object cases with general utility functions.
Second, consider multi-object auction models with agents who have multi-unit
demand quasi-linear utility functions. In such models, the Vickrey payment is not
an MPE price, but the Vickrey mechanism is strategy-proof and e¢ cient. However,
our result in Subsection 5.1 indicates that when agents have multi-unit demand16general utility functions, the generalized Vickrey mechanism that is de…ned inparallel to ours is far from e¢ cient and incentive-compatible.
If agents’multi-unit demand quasi-linear utility functions further satisfy certain substitutable and complementary properties, the MPE is well de…ned, andthe MPE mechanism is e¢ cient, although not strategy-proof. Assuming the coincidence of the increment and the unit of agents’valuations, Gul and Stacchetti(2000), Ausubel (2006), and Sun and Yang (2009) propose auctions that identify
the MPEs. Note that unit-demand quasi-linear utility functions are special casesof their utility functions. When applied to the unit-demand settings, the auctionsin those three papers are essentially the same as the EA auction. Thus, our results in Subsection 5.2 also imply that for any price increment larger than the unitof agents’ valuations, the auctions proposed by those papers also overshoot theMPE prices by an arbitrarily large distance, generate allocations far from e¢ cient
outcomes and provide agents with strong incentives to manipulate.
Third, we examine the matching with contracts models with transfers. In the
one-to-one setting, if agents are buyers and each object is owned by one seller whose
utility only depends on the transfer, then those models coincide with ours, andtheir buyer-optimal outcomes coincide with the MPE. If transfers are discretizedand sellers and buyers have strict preferences over contracts, the cumulative o¤er
process of buyers coincides with the AA auction and …nds the buyer-sided optimal
outcome. Thus, our results in Subsection 5.3 also imply that in non-quasi-linear
environments, the cumulative o¤er process overshoots or undershoots the MPE
prices by an arbitrarily large distance, which generates an outcome far from ef…ciency and provides agents with strong incentives to manipulate. This insightextends to the many-to-one matching with contracts models and trading networkmodels for general utility functions; see, e.g., Fleiner et al. (2019) and Schlegel(2020): the one-sided optimal outcome with continuous transfers cannot be approximated by the one-sided optimal outcome obtained with discretized transfers
and induced strict preferences through variants of the cumulative o¤er process.
Overall, our results inspire new techniques to study e¢ cient and incentivecompatible auction design when agents have general utility functions.
Appendix A: Proof of Proposition 6
First, we introduce the following characterization.
A set M 0 M of objects is weakly underdemanded at p if [8x 2 M 0 , px > 0] )jfi 2 N : Di (p) \ M 0 6= ;gj jM 0 j.

Lemma (Morimoto and Serizawa, 2015): p is an MPE price if and only if no setof objects is overdemanded and no set of objects is weakly underdemanded at p.
Let (xdn ; pdn ) be the assignment and price generated by the AA auction withincrement dn . The proof consists of …ve steps.
17Step 1: For each dn > 0, (xdn ; pdn ) is an dn equilibrium.
Consider an agent i who drops out. She bids 0 either at the price lower thandn
(pd1n + dn ; : : : ; pd1n + dn ). Thus, 0 2 Didn (pdn ). Consider
p or at the price pdn
an agent i who obtains xdi n 2 M . She bids object xdi n just at the price pdxndn , whereithe price of other object l is equal or less than pdl n + dn . Thus, xdi n 2 Didn (pdn ).
Thus, De…nition 5(i) holds.
In the AA auction, whenever an object is bided on by some agent, it will keep
assigned till the end. Thus, De…nition 5(ii) holds.
0
Step 2: There is a convergent subsequence fpdn g in fpdn g whose assignments
remain the same.
For each l 2 M and each n, 0 pdl n maxi2N Vi (l)+2dn . Thus, fpdn g contains
00
00
a convergent subsequence fpdn g. Since agents and objects are both …nite, fpdn g0contains a subsequence fpdn g whose assignments remain the same.
0
0
Step 3: (x; p) limn!1 (xdn ; pdn ) is an equilibrium.
By De…nition 5(ii), De…nition 3(ii) holds. Thus, we show De…nition 3(i). For
each n and each i 2 N , xi 2 Ddn (pdn ) implies that for each y 2 M , ui (xi ; pdxni )0ui (y; pdyn + dn ) and ui (xi ; pdxni ) ui (0; 0). Thus, for each y 2 M , limn!1 pdn = p
implies ui (xi ; pxi ) ui (0; 0) and ui (xi ; pxi ) ui (y; py ). Thus xi 2 Di (p).
Step 4: Let (x; p) be the equilibrium at Step 3. Then p = pmin .
Suppose p 6= pmin . Since (x; p) is an equilibrium, by Lemma, there is aweakly underdemanded set M 0
M at p, that is, for each l 2 M 0 , pl > 00
and jfi 2 N : Di (p) \ M 6= ;gj = jM 0 j. Let N 0
fi 2 N 0 : xi 2 M 0 g. Then,N 0 = fi 2 N : Di (p) \ M 0 6= ;g and for each i 2 N nN 0 and each l 2 M 0 ,ui (xi ; pxi ) > ui (l; pl ). Thus, since for each l 2 M 0 , pl > 0, De…nition 1(i) implies
that there is > 0 such that for each l 2 M 0 , pl
> 0, and for each i 2 N nN 0 ,ui (xi ; pxi + ) > ui (l; pl

(a)

2 ):

0

Since limn!1 d0n = 0 and limn!1 pdn = p, for some d00n 2 fd0n g,
and(b) d00nd00n(c) plpl> 0 for each l 2 M 0 .
Thus for each i 2 N nN 0 and each l 2 M 0 ,00

ui (xi ; pdxni )Step 1(b)ui (xi ; pxi + d00n )ui (xi ; pxi + ) > ui (l; pl
(a)

d00

2 )
(c)

ui (l; pl n

d00

)
(b)

ui (l; pl n

d00n ).

Thus, no agent in N nN 0 bids an objects in M 0 when the price of l 2 M 0 reaches
d00
d00
pl n d00n . In contrast, by (c), l is assigned to some i 2 N 0 at price pl n d00n .
d00Thus, by jN 0 j = jM 0 j, the price of any object l 2 M 0 cannot be increased to pl n ,00contradicting that pdn is the outcome of auction with increment d00n .
18

Step 5: limn!1 pdn = pmin (u).
Recall that a bounded sequence converges if and only if any of its convergent
subsequence has the same limit. Thus, we prove that any convergent subsequence
000
in fpdn g has the same limit. Let fpdn g and fpdn g be two convergent subsequences
000
in fpdn g such that limn!1 pdn = p0 and limn!1 pdn = p00 .
0
Analogous to Step 2, there is a subsequence of fpdn g converging to p0 whose00
assignments remain the same, say x0 . Similarly, there is a subsequence of fpdn gconverging to p00 whose assignments remains the same, say x00 . Analogous to Steps
3 and 4, we can show p0 = pmin and p00 = pmin . Thus, since the MPE price isunique, p0 = p00 .
Appendix B: Clock auction for multiple objects with non-quasi-linearity
Let M = fa; bg and N = f1; 2; 3g. Let u 2 (U QL )3 be such that v1 (a) = 3;
v1 (b) = 1; v2 (a) = 1; v2 (b) = 3; v3 (a) = v2 (b) = 2. Then pmin (u) = (0; 2; 2) andxmin (u) = (a; b; 0).
One possible extension of the clock auction is that each agent chooses an object
from her demand set given a price, and bids on it. The prices of overdemanded
objects are increased. At p0 = (0; 0; 0), D1 (p(0)) = fag; D2 (p(0)) = fbg; andD3 (p(0)) = fa; bg. Thus agent 1 bids on a, agent 2 bids on b, and agent 3 bids ona or b. When the price of a or b, say a, increases higher than b, agents 3 bids on
b. Thus, starting from (0; 0; 0), if the price is raised continuously, agents 3 needs
to move between a and b continuously until the price reaches pmin (u) = (0; 2; 2).
Such a bidding behavior is physically impossible, and moreover, the price path in
the auction is not well-de…ned.
Another possible extension is that each agent reports her demand set at a given
price, and the prices of minimally overdemanded objects are increased. Indeed,this is the continuous variant of the EA auction. In this extended clock auction, if
the prices increase continuously along the path p(t) = (t; t) where t 2 [0; 2], agents
1, 2 and 3 keep reporting D1 (p(t)) = fag; D2 (p(t)) = fbg; and D3 (p(t)) = fa; bg,
respectively. Finally, the price reaches pmin (u) = (0; 2; 2).
However, consider a general utility function of agent 3, u03 2 U such that (i)u03 (0; 0) = u03 (a; 1) = u03 (b; 2), and (ii) u03 (a; t) = u03 (b; 2t) for each t 2 [0; 1]. Let
u0 = (u1 ; u2 ; u03 ). Then, pmin (u0 ) = (0; 1; 2) and xmin (u0 ) = (a; b; 0). Note that for
pa 2 [0; 1], D3 (p) = fag if pb > 2pa , D3 (p) = fbg if pb < 2pa , D3 (p(0)) = fa; bg
if pb = 2pa . Thus, starting from (0; 0; 0), if the prices of minimally overdemanded
objects increase continuously with the same rate, agents 3 needs to move between
fa; bg and fbg continuously, which is physically impossible. Note that in such acase, the price path to pmin (u) = (1; 2) is not well-de…ned either.
Overall, it is both theoretically and practically impossible to extend the clock
auction for multiple objects with general utility pro…les to duplicate or approxi19

mate the MPE mechanism.

References[1] Andersson, T., Erlanson, A., 2013. Multi-item Vickrey–English–Dutch Auctions. Games and Economic Behavior 81, 116-129.
[2] Ausubel, L.M., 2006. An e¢ cient dynamic auction for heterogeneous commodities. American Economic Review 96(3), 602-629.
[3] Binmore, K., Klemperer, P., 2002. The biggest auction ever: the sale of the
British 3G telecom licences. The Economic Journal, 112(478) C74-C96.
[4] Crawford, V.P., Knoer, E.M., 1981. Job matching with heterogeneous …rms
and workers. Econometrica 49(2), 437-450.
[5] Demange, G., Gale, D., 1985. The strategy structure of two-sided matchingmarkets. Econometrica 53(4), 873-888.
[6] Demange, G., Gale, D., Sotomayor, M., 1986. Multi-item auctions. Journalof Political Economy 94(4), 863-872.
[7] Echenique, F., 2012. Contracts versus salaries in matching. American Economic Review 102(1), 594-601.
[8] Fleiner, T., Jagadeesan, R., Jankó, Z., Teytelboym, A., 2019. Trading networks with frictions. Econometrica 87(5), 1633-1661.
[9] Gul, F., Stacchetti, E., 2000. The English auction with di¤erentiated commodities. Journal of Economic Theory 92(1), 66-95.
[10] Hat…eld, J.W., Milgrom, P.R., 2005. Matching with contracts. American Economic Review 95(4), 913-935.
[11] Hildenbrand, W., Schmeidler, D., Zamir, S., 1973. Existence of approximate
equilibria and cores. Econometrica 41(6), 1159-1166.
[12] Kazumura, T., Mishra, D., Serizawa, S., 2020. Strategy-proof multi-object
mechanism design: Ex-post revenue maximization with non-quasilinear preferences. Journal of Economic Theory 188, 105036.
[13] Kelso Jr, A. S., Crawford, V. P., 1982. Job matching, coalition formation,and gross substitutes. Econometrica 50(6), 1483-1504.
20

[14] Leonard, H.B., 1983. Elicitation of honest preferences for the assignment of
individuals to positions. Journal of Political Economy 91(3), 461-479.
[15] Liu, D., Bagh, A, 2019. Preserving bidder privacy in assignment auctions:design and measurement. Management Science, forthcoming.
[16] Mishra, D., Parkes, D.C., 2009. Multi-item Vickrey–Dutch Auctions. Gamesand Economic Behavior 66, 326-347.
[17] Morimoto, S., Serizawa, S., 2015. Strategy-proofness and e¢ ciency with nonquasi-linear preferences: A characterization of minimum price Walrasian rule.
Theoretical Economics 10(2), 445-487.
[18] Roughgarden, T., 2014. CS364B: Frontiers in Mechanism Design Lecture #3:
The Crawford-Knoer Auction (http://timroughgarden.org/w14/l/l23.pdf).
[19] Schlegel, J.C., 2020. The structure of equilibria in trading networks withfrictions. Working paper.
[20] Shapley, L.S., Shubik, M., 1971. The assignment game I: The core. International Journal of Game Theory 1(1), 111-130.
[21] Sun, N., Yang, Z., 2009. A double-track adjustment process for discrete markets with substitutes and complements. Econometrica 77(3), 933-952.
[22] Zhou, Y, Serizawa, S., 2018. Strategy-proofness and e¢ ciency for non-quasilinear common-tiered-object preferences: Characterization of minimum pricerule. Games and Economic Behavior 109, 327-363.

21