ISSN (Print) 0473-453X

Discussion Paper No. 1116

ISSN (Online) 2435-0982

MULTI-OBJECT AUCTION DESIGNBEYOND QUASI-LINEARITY:
LEADING EXAMPLES

Yu Zhou
Shigehiro Serizawa

Revised November 2022
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

November 29, 2022

Abstract
In multi-object auction models with unitary demand agents, if agents’utility functions satisfy quasi-linearity, the exact ascending auction of Demange et al. (1986), the sealed-bid Vickrey auction, as well as the approximate ascending auction of Demange et al. (1986) are fundamental tothe auction theory and known to identify the minimum price equilibrium(MPE). In particular, these auctions exhibit elegant e¢ ciency and incentivecompatibility. We exemplify that these auctions fail to identify the MPEs
and are substantially ine¢ cient and manipulatable without assuming thecoincidence between price increment and valuation unit or without assuming the quasi-linearity of utility functions. The implications of our negative
results for multi-object auction models with agents with multi-unit demand,and matching with contracts models are discussed as well.
Keywords: Multi-object auction, minimum price equilibrium, examples, the coincidence assumption, quasi-linearity
JEL Classi…cation: C78, D44, D74
We thank Vincent Crawford, Andrew Mackenzie, Debasis Mishra, Bernardo Moreno, Ning
Sun, Qianfeng Tang, and Alex Teytelboym for their helpful comments. The preliminary versionof this paper was presented at ISI-ISER Young Economists Workshop 2020, Nanjing-Osaka
Economic Theory Workshop 2021, the 12th Conference on Economic Design, 2022 Conference on
Mechanism and Institution Design, and the 6th Spain-Japan Meeting on Economic Theory. Partof the results was also presented in the 21st annual SAET conference. We thank participantsat those workshops and conferences for their comments. We gratefully acknowledge …nancial
support from the Joint Usage/Research Center at ISER, Osaka University, Research Projects in
the Humanities, Social Sciences and Interdisciplinary Fields 2022 at IFOHS, Kyoto University,and Grant-in-aid for Research Activity, Japan Society for the Promotion of Science (15H05728,
19K13653, 20H05631, 20KK0027, 22K13364, 22H00062).
yGraduate School of Economics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 6068501, Japan. E-mail: zhouyu_0105@hotmail.com
zInstitute 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

The most successful examples of auction theory are spectrum license auctionsorganized by governments in OECD countries that auction o¤ several licenses
simultaneously, often generating enormous revenues. As a case in point, in the2000 British 3G spectrum license auctions, the revenue generated from selling …velicenses amounted to 2.5% of the UK’s GNP. These auctions play important rolesin the overall development of the mobile phone industry. In these auctions, it is
widely observed that winning bids involve copious sum of money and the priceincrement is set su¢ ciently large in advance (to have a reasonable stopping time)(Klemperer, 2004). The huge winning bids end up violating the quasi-linearity
assumption on preferences, i.e., an agent’s bene…t from the auctioned object can bepresented by her valuation of that object, independent of the associated payment.
The sizable increment leads to the violation of the coincidence assumption thatthe price increment coincides with the valuation unit, which further restricts thequasi-linearity of preferences. These two assumptions are common in auction
theory but remain undesirable in many real-life applications. This paper analyzes
the rami…cations of the violations of both assumptions on the performance ofauctions that are of utmost signi…cance in theory, but generally studied in thequasi-linear settings.
In particular, we focus on auctions with government-concerned and sociallydesirable properties, e¢ ciency and strategy-proofness. E¢ ciency requires that
objects should be given to those who value them the most. However, agents’preference information of objects is only privately known in many cases. Thus, it
is indispensable for the auction to directly or indirectly extract true informationfrom agents to attain e¢ ciency. Strategy-proofness requires agents to have no
incentive to manipulate information in the auction in the sense that revealing true
information is a dominant strategy for each agent.
We study the multi-object auction model where agents have unit demand, i.e.,each agent gets at most one object, and also have the classical utility functions thatsatisfy the standard monotonicity and continuity, taking the quasi-linear utility
functions as special cases. In such settings, there is a minimum price equilibrium(MPE). The MPE mechanism, a direct mechanism to select an MPE allocationfor each utility pro…le, is the only mechanism that satis…es e¢ ciency, strategyproofness, individual rationality, and no subsidy when agents have either quasilinear utility functions (Holmstrom, 1979) or classical utility functions (Saitoh andSerizawa, 2008; Morimoto and Serizawa, 2015). For this reason, any auction that
duplicates the outcome of the MPE mechanism is e¢ cient and is imbued with anice incentive property, thus eliciting particular attention by auction theorists.
1

There are three well-known auctions that …nd the MPEs in the quasi-linear
settings. The …rst one is proposed by Demange et al. (1986), the exact ascending(EA) auction. The EA auction generates the MPE price by further imposing thecoincidence assumption. The second one is the sealed-bid Vickrey auction, whose
outcome coincides with the MPE (Leonard, 1983). Meanwhile, the third one isprovided by Demange et al. (1986), the approximate ascending (AA) auction. The
AA auction originates from the salary adjustment process in Crawford and Knoer(1981) and Kelso and Crawford (1982). The AA auction generates a price thatthen coordinate-wise approximates the MPE price. In these auctions, objects canbe heterogenous.1 As explicated later, these auctions are fundamental to auction
theory and provide the essential ideas of several auction designs in more generalenvironments.
In practice, variants of the aforementioned auctions are also utilized. For
example, the multi-unit demand variant of the EA auction runs in power purchasein New Jersey, U.S.A. (Chapter 7, Milgrom, 2004). Facebook uses the sealed-bid
Vickrey auction to sell its online ads slots (Varian and Harris, 2014). It is also
noteworthy that the simultaneous ascending auction adopted by the U.S. Federal
Communications Commission (FCC) for selling spectrum licences is similar to themulti-unit demand variant of the AA auction (Chapter 7, Milgrom, 2004).
We study the performance of three aforementioned auctions by dropping thecoincidence assumption and quasi-linearity assumption. In practice, the coincidence assumption may be unsuitable for auctions with sizeable increments. The
willingness of an agent to pay is the primitive data independent of auctions, which
can take arbitrary values, whereas the price increment is set in advance. The
coincidence assumption is not realistic except for technical reasons. The quasilinear assumption is dubious for the aforementioned large-scale auction. Notably
the coincidence assumption is a further restriction in the quasi-linear setting, anda violation of quasi-linearity assumption leads to a violation of the coincidence
assumption.
To evaluate the performance of three aforementioned auctions, in terms of theirassociated (direct) mechanisms, apart from the standard notions of e¢ ciency, approximate e¢ ciency, strategy-proofness, and approximate strategy-proofness, weformulate two additional concepts of absolute ine¢ ciency and absolute manipulability. These are the properties of the mechanism. The former states that it
1

When applied to the case of homogenous objects, the sealed-bid Vickrey auction is sometimes
referred to as the Vickrey auction for k objects where k objects are assigned to the agents whose
values are among the kth highest and they just pay the (k + 1)th highest valuation. On the other
hand, the EA auction is sometimes called the ascending auction for k objects where informationrevelation of all bidders follows the same fashion as the ascending auction for one object.

2

is impossible for the mechanism to achieve approximate e¢ ciency to any degree.
The latter states that it is impossible for the mechanism to achieve any degree ofapproximate incentive compatibility.
When objects are homogenous, the three aforementioned auctions perform wellon the classical domain. The intuition is as follows. The key to determine theMPE is an agent’s generalized valuation, a natural generalization of valuations forquasi-linear preferences, de…ned as the maximum willingness to pay for the object
relative to the status of getting nothing and paying nothing. The MPE price isthe same across all the objects, which is equal to the (k + 1)th-highest generalized
valuation if there are k objects to be auctioned and those objects are assigned toagents whose generalized valuation is among the (k + 1)th-highest generalized valuation. However, the generalized valuation does not include su¢ cient information
to determine the MPE when objects are heterogenous and agents have classicalutility functions. Our main results stated below exhibit such abnormalities.
In the quasi-linear settings, we consider a “perturbation”of the quasi-linear
domain with valuations that are mutiples of natural numbers, by allowing
rational numbers in the neighborhood of the natural numbers. This, inturn, breaches the coincidence assumption. We demonstrate that the EA
auction always overshoots the MPE prices by an arbitrarily large distancein the perturbed quasi-linear domain, leading to absolute ine¢ ciency andabsolute manipulability of the mechanism associated with EA auction. Ifsuch a perturbation allows the agents to have valuations that are multples
of irrational numbers, we further contend that it could be the case that the
EA auction always largely overshoots the MPE for any positive increment.
Furthermore, the continuous-time clock auction for selling one object can
not be extended to multi-object cases with classical utility functions.
When agents have classical utility functions, the generalized sealed-bid Vickrey auction is de…ned by replacing the valuations in the formula of the Vickrey allocation with the generalized valuations. Both the price and the assignment generated by this auction are di¤erent from MPE price and assignment.
Its associated mechanism, the generalized Vickrey mechanism is absolutelyine¢ cient and absolutely manipulable.
When agents have classical utility functions, the AA auction overshoots andundershoots the MPE prices by an arbitrarily large distance if the increment
is …xed in advance. It never approximates the MPE and leads to absolute
manipulability of the mechanism associated with the AA auction. By con3

trast, for a …xed classical utility pro…le, a decrease in increment makes theoutcome of AA auction approximate the MPE.
In the following, we contrast our negative results with the auction designs invarious settings. First, auctions that target MPEs in quasi-linear settings withunitary demand agents, as proposed by Mishra and Parkes (2009) and Andersson
and Erlanson (2013), are premised on the coincidence assumption. Therefore, ournegative results of EA auctions can be carried over to their models without thecoincidence assumption by constructing similar examples.
Second, consider multi-object auction models with agents with multi-unit demand quasi-linear utility functions. In such models, a Vickrey allocation is not
an MPE allocation; however the Vickrey mechanism remains strategy-proof ande¢ cient. When agents have classical utility functions, our negative result of thegeneralized sealed-bid Vickrey auction de…ned via generalized valuations can be
carried over.2
If the utility functions of agents further satisfy certain substitutable properties,
the MPE is well-de…ned, and the MPE mechanism is e¢ cient, albeit not strategyproof. Under the coincidence assumption, Gul and Stacchetti (2000), Ausubel(2006), and Sun and Yang (2009) propose auctions that identify the MPEs. When
applying their auctions to our model, those auctions are essentially the same as the
EA auction; thus our negative results of the EA auction hold for their auctions.
Finally, we consider the matching with contracts models with transfers (Hat…eld and Milgrom, 2005). With regard to the one-to-one setting, if agents arebuyers and each object is owned by one seller whose utility hinges on only thetransfer, then those models coincide with ours, and their buyer-optimal outcomes
coincide with the MPEs. If transfers are discretized and both 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 (Echenique,2012). Consequently, our negative results of the AA auction imply: The onesided optimal outcome with continuous transfers cannot be approximated by the
one-sided optimal outcome derived from discretized transfers and induced strict
preferences via variants of the cumulative o¤er process.3
Our paper is also related to the literature of e¢ cient and incentive compatible
auction designs when agents have classical utility functions. When objects are homogenous, Saitoh and Serizawa (2008) characterize the e¢ cient and strategy-proof
direct mechanisms. On the other hand, when objects are heterogenous, Morimoto2

A similar conclusion is reached by Malik and Mishra (2020).
Such an insight holds even for the trading network model with continuous transfers, see,
Fleiner et al. (2019) and Schlegel (2022).
3

4and Serizawa (2015), Zhou and Serizawa (2018), Baisa (2020), Kazumura et al.
(2020), and Malik and Mishra (2021) characterize the e¢ cient, strategy-proof,
and fair direct mechanisms. Prices are continuous variables in all these auction
models. Hat…eld et al. (2021) characterize the cumulative o¤ers process that canbe regarded as the auctions with discretiezed payments. Apart from the analysis
of properties of direct mechanisms studied by those papers, their indirect implementations through various auction formats also bear signi…cance for practical
purpose.
The novelty of this paper is to exemplify that the myriad well-known auctions
listed above are neither e¢ cient nor incentive-compatible even when applied tosimple non-quasi-linear settings where agents have unit demand. Our key message
is to note the challenges and inspire the development of novel analytical techniques
for the auction design by dropping the coincidence assumption along with thequasi-linearity assumption.
The remainder of this paper is organized in the following manner: We de…nethe model and MPEs in Section 2. In Section 3, we expound on the notions fore¢ ciency, ine¢ ciency, strategy-proofness, and manipulability. In Section 4 wede…ne auctions for MPEs. We review the existing results of auctions for MPEs on
the quasi-linear domain in Section 5. In Section 6, we present our main …ndings
and study the performance of auctions in Section 5 by dropping the coincidence
assumption and quasi-linearity assumption. Finally, we conclude the study in
Section 7.

2

The model and minimum price equilibrium

There is a …nite set of agents N and a …nite set of objects M . For the purposeof this paper, we ignore the trivial analysis of jN j = 1 or jM j = 1 and assumejN j, jM j 2.4 Not receiving an object is called receiving the null object, which isdenoted by 0. Let L M [ f0g. Each agent has unit demand: She either receives
an object or the null object.
Agents have preferences on the consumption set L R.5 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 classical if:

4Here j j is the cardinality of set .
Following the convention, R is the set of reals, Q is the set of rational numbers, Z is the setof integers, and N = f0; 1; g is the set of natural numbers. Let R+ , Q+ , and N+ be the setsof non-negative reals, non-negative rational numbers, and positive integers, respectively. For apositive real d > 0, d Z = fd; 0; d; g and d T where T 2fQ; Q+ ; N; N+ g can be similarly
de…ned.
55(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 classical utility functions and U N be the classical domain.
Let u (ui )i2N 2 U N be a pro…le of utility functions, i.e., the utility pro…le.
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, without loss of generality (w.l.o.g.), that for each i 2 N , vi (0) = 0.
Let U QL be the set of quasi-linear utility functions and (U QL )N be the quasi-linear
domain. Notice that U QL U.
For each agent i 2 N , let xi 2 L be her assigned object. An assignmentx(xi )i2N 2 LN is a list of individually assigned objects such that except for
the null object, 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.
For each l 2 L, let pl 2 R+ denote the price of object l and p = (pl )l2L 2 RL+ bea price. Agent i0 s demand set at price p is de…ned as Di (p) fl 2 L : ui (l; pl )ui (l0 ; pl0 ); 8l0 2 Lg. An object in agent i0 s demand set maximizes her welfare at thegiven price. We assume, w.l.o.g., that the price of the null object always remains
zero and the reserve prices of all the objects are zero.
De…nition 3: A pair (x; p) 2 X RL+ is a (Walrasian) 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 3(i) states that each agent receives an object in her demand set.
De…nition 3(ii) speci…es that an object with a positive price must be assigned.
Equivalently, the price of an unassigned object is its reserve price …xed at zero.
For each utility pro…le from the classical domain, there is an equilibrium. In
particular, the set of equilibrium prices is a complete lattice (Demange and Gale,
1985). Therefore, there is a minimum price equilibrium (MPE) whose price isunique and coordinate-wise minimum among all equilibrium prices. For eachutility pro…le u 2 U N , let pmin (u) be the associated MPE price. Notably, theassociated MPE price is unique for each given utility pro…le, but the corresponding assignment may not be unique since indi¤erence in preferences is allowed.
Moreover, each agent is welfare-equivalent across all the MPEs.
The equilibrium prices and the MPE price indeed can be characterized via theinteractions between demand and supply.
De…nition 4: (i) A non-empty set of objects M 0
p if jfi 2 N : Di (p) M 0 gj > jM 0 j.
6

M is overdemanded at price(ii) A non-empty set of objects M 0 M is (weakly) underdemanded at price p if
[8x 2 M 0 , px > 0] ) jfi 2 N : Di (p) \ M 0 6= ;gj ( ) < jM 0 j.
The following characterizations of the equilibrium prices and MPE price hold.
Fact 1 (Mishra and Talman, 2010; Morimoto and Serizawa, 2015): Let u 2 U N .
(i) A price p is an equilibrium price for u if and only if no set of objects isoverdemanded and no set of objects is underdemanded at p for u.
(ii) A price p is an MPE price for u if and only if no set of objects is overdemanded
and no set of objects is weakly underdemanded at p for u.
Fact 1(ii) introduces the following property of MPEs.
Fact 2 (Demand connectedness) (Morimoto and Serizawa, 2015): Let u 2 U N
and (x; pmin ) be an MPE for u. For each l 2 M such that pmin
> 0, there is alsequence fik gk=1 of distinct agents such that(i) xi1 = 0 or pmin
xi1 = 0,(ii) xi = l,(iii) for each k 2 f2;; K 1g, xik 2 M and pminxik > 0, and(iv) for each k 2 f1;; K 1g, fxik ; xik+1 g Dik (pmin ).
Fact 2 states that for each object with a positive price, it will be connected tothe object with zero price alternatively via agents’demands.
Facts 1 and 2 are vital in designing auctions that implement the MPEs on
the quasi-linear domain and understanding the strategy-proofness of the MPE
mechanisms (Mishra and Talman, 2010; Morimoto and Serizawa, 2015).
A weaker notion of equilibrium, the approximate equilibrium, called the “" equilibrium,”is studied as well. The " equilibrium tackles the case where equilibrium prices
are restricted to be discrete, i.e., multiples of some grid say ".
For some " > 0, agent i’s " demand set at p 2 RL+ 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. When
" = 0, an " demand set is reduced to a demand set.
De…nition 5: Let some " > 0 be given. A pair (x; p) 2 X" 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.

(" N)L is an

De…nition 5(i) is parallel to De…nition 3(i) in the approximate sense and De…nition 5(ii) is the same as De…nition 3(ii).
7

When prices are discrete, an equilibrium compatible with discrete prices may
not exist; refer to Example 1 below for more details. The " equilibrium is usefulin the auction model where " is set to be the bid increment, as discussed later.

3

Notions of (in)e¢ ciency, and (non-)manipulability

An allocation z (xi ; ti )i2N 2 (L R)N such that (xi )i2N 2 X denotes a list of
individually assigned objects, paired with the associated transfers. Let Z be theset of allocations. A (direct) mechanism f is de…ned as a function from U N to
Z that maps to each utility pro…le u an allocation z. For each agent i 2 N , letxi (u) be the object assigned and ti (u) represent the associated transfer speci…edby mechanism f , and let fi (u) = (xi (u); ti (u)). Given a utility pro…le u 2 U N ,(f ( ); u) forms a revelation game: agents report their utility functions and theoutcome of their reports is selected by f ( ).
We now let D
U and de…ne the (in)e¢ ciency and (non-)manipulability ofmechanisms on domain DN .
We …rst introduce e¢ ciency. Given an allocation z 2 (L R)N , let Rev(z)PN
i2N ti be the revenue generated by z. An allocation z 2 Z is e¢ cient for u 2 D
if there is no z 0 2 Z such that (i) for each i 2 N , ui (zi0 ) ui (zi ) with at least one
strict inequality, and (ii) Rev(z) Rev(z 0 ).
E¢ ciency: A mechanism f is e¢ cient on domain DN if for each u 2 DN , f (u)is e¢ cient for u.6
Due to practical considerations, achieving e¢ ciency is sometimes demanding.
Instead, approximate e¢ ciency is often taken into consideration. Given r 2 R+ ,an allocation z 2 Z is r e¢ cient for u 2 DN if there is no z 0 2 Z such that (i)for each i 2 N , ui (zi0 ) > ui (zi ), and (ii) Rev(z) + r jN j Rev(z 0 ).7

r-e¢ ciency: Given r 2 R+ , a mechanism f is r e¢ cient on domain DN if foreach u 2 DN , 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 “approximately e¢ cient.”
Absolute ine¢ ciency: A mechanism f is absolutely ine¢ cient on domain DN
if there is no r 2 R+ such that f is r e¢ cient on domain DN .
6

A mechanism f on (U QL )N is e¢ cient if and only if for each u 2 (U QL )N , x(u) 2Parg max i2N vi (xi ) (See Zhou and Serizawa (footnote 29, 2018) for a complete proof of thisx2X

statement).
7
Our notion is in the spirit of the de…nition of the approximate core allocation in classicalgeneral equilibrium theory, see, e.g., Hildenbrand et al. (1973).

8

Absolute ine¢ ciency speci…es that it is impossible for a mechanism to achieve
approximate e¢ ciency to any degree.
Thereafter, we introduce the incentive notions. A mechanism f is manipulable
on domain DN if there are u 2 DN , i 2 N , and u0i 2 D such that ui (fi (u0i ; u i )) >ui (fi (u)). If a mechanism is immune to manipulability, it is strategy-proof.
Strategy-proofness: A mechanism f is strategy-proof on domain DN if it is notmanipulable on domain DN .
Strategy-proofness implies that in the revelation game (f ( ); u), truthfully reporting her utility function is a dominant strategy for each agent.
Next, we de…ne a weaker notion of strategy-proofness. Given r 2 R+ , “rmanipulability”states that an agent bene…ts more than r from misrepresenting her
utility function, with respect to the payment, paired with the assigned object undertruth telling. Given r 2 R+ , a mechanism f on domain DN is r-manipulable if
there are u 2 DN , i 2 N , and u0i 2 D such that ui (fi (u0i ; u i )) > ui (xi (u); pi (u) r).
If a mechanism is immune to r-manipulability, it is r-strategy-proof.
r strategy-proofness:8 Given r 2 R+ , a mechanism f is r strategy-proof on
domain DN if it is not r-manipulable on domain DN .
If r = 0, r strategy-proofness coincides with strategy-proofness. For a smallr > 0, r strategy-proofness is approximately strategy-proof: Each agent has onlya small incentive to manipulate.
Absolute manipulability: A mechanism f is absolutely manipulable on domain
DN if there is no r 2 R+ such that f is r strategy-proof on domain DN .
Absolute manipulability points out that it is impossible for a mechanism toachieve approximate strategy-proofness to any degree.
An MPE mechanism is a function that maps to each utility pro…le an MPE
allocation9 for that pro…le. On the quasi-linear domain, the MPE mechanism isequivalent to the Vickrey mechanism de…ned in Section 4 (Leonard, 1983). Morespeci…cally, the MPE/Vickery mechanism is the unique mechanism satisfying e¢ ciency, strategy-proofness, individual rationality, as well as no subsidy (Holmstrom,1979). This characterization of the MPE mechanism holds on the non-quasi-linear
domains (Morimoto and Serizawa, 2015; Zhou and Serizawa, 2018).
8

Our notion is in the spirit of limiting incentive compatibility of Robert and Postlewaite(1976).
9An MPE allocation is an allocation compatible with the MPE where each agent gets anobject assigned by the MPE and pays its MPE price.

9

4

Auctions for MPEs

We introduce three well-known auctions in this section. The …rst auction is theexact ascending auction introduced by Demange et al. (1986). This dynamic
procedure …nds an MPE price by recursively increasing the prices of objects in aminimally overdemanded set identi…ed at the current price. The minimal overdemanded set is a particular type of overdemanded set such that none of its nonempty proper subsets is overdemanded.10
De…nition 6: The exact ascending (EA) auction is de…ned as follows:
Let d > 0 be the increment. Starting from reserve prices, each agent reports
her demand set at the current price. If there is a set of objects that are minimally
overdemanded, then the prices of those objects are increased by d; otherwise, stopat the current price.
The assignment of the EA auction is not explicitly speci…ed, but implicitly
given in Theorem 2 in Demange et al. (1986). Put succinctly, each agent is
assigned an object from her demand set at the termination price. Among allthese assignments, …nd the assignment such that objects with positive prices are
assigned.
The second auction is known as the sealed-bid Vickrey auction (Leonard,1983).11 In this auction, the auctioneer asks each agent to report her maximum
willingness to pay for each object relative to the status of getting the null object
and paying nothing, which is formulated as follows, to facilitate our discussion
on both the quasi-linear domain and the classical domain. For each i 2 N , eachui 2 U, and each l 2 L, let Vi (l) 2 R be the maximum willingness to pay for objectl, called the generalized valuation of object l, such that ui (l; Vi (l)) = ui (0; 0). In
the quasi-linear settings, the generalized valuation Vi ( ) is simply the valuationvi ( ).
De…nition 7: The generalized sealed-bid Vickrey auction is de…ned in the following manner: Each agent reports Vi ( ). Then calculate (xV ; pV ) 2 X RL as
follows:
P(i) xV 2 arg max i2N Vi (xi ), andx2X(ii) pV0 = 0, if l 2 M is unassigned, pVl = 0, and if l 2 M is assigned to agent i,PPV
pVl = max j2N nfig Vj (xj )j2N nfig Vj (xj ).
x2X

10A non-empty set of objects M 0
M is minimally overdemanded at p if (i)jfi 2 N : Di (p) M 0 gj > jM 0 j and (ii) there is no non-empty set M 00
M 0 such thatjfi 2 N : Di (p) M 0 , Di (p) \ M 00 6= ;gj > jM 00 j.
11
The closed-form expression of the sealed-bid Vickrey auction is essentially introduced byVickrey (1961), Clarke (1971), and Groves (1977).

10

If u 2 (U QL )N , i.e., for each i 2 N , Vi ( ) = vi ( ), we simply call the generalized
sealed-bid Vickrey auction the sealed-bid Vickrey auction. For each utility pro…leu 2 U N , let pV (u) be the associated generalized sealed-bid Vickrey price. Byfurther assigning zero prices to unassigned objects, it extends the well-known
Vickrey payment. We do so just for the sake of convenience when comparing it to
the MPE price, see, e.g., Fact 5 and Proposition 5.
The third auction is also proposed by Demange (1986), known as the approximate ascending auction. The following de…nition comes from Demange (1986).12
De…nition 8: The approximate ascending (AA) auction is de…ned as follows: Letd > 0 be the increment. Initially, all the agents are uncommitted and stand in aqueue. These uncommitted agents are called one by one to bid. When agent i iscalled, she is presented with 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 toobject 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 null object.
The auction terminates when all uncommitted agents drop out and each committed agent buys her assigned object at its current price.
We …nally de…ne the mechanisms associated with the aforementioned threeauctions on the domain DN
U N . An allocation is speci…ed by some auction
in such a manner that each agent pays the price of her assigned object upon thetermination of the auction. The EA mechanism is a function that maps to eachutility pro…le from DN an allocation speci…ed by the EA auction for that utility
pro…le. The generalized Vickrey mechanism is a function maps to each utility
pro…le from DN an allocation speci…ed by the generalized sealed-bid auction forthat utility pro…le. If it is de…ned on the quasi-linear domain, it is called theVickrey mechanism. The AA mechanism is a function that maps to each utility
pro…le from DN an allocation speci…ed by the AA auction for that utility pro…le.
12

In Page 867 of Demange et al. (1986), they wrote“[...]If one wishes to structure this procedure
the auctioneer could call on the uncommitted bidders, say in alphabetical order, requiring themto choose one of the three alternatives listed above[...]” Our formulation of the AA auction iscongruent with its original de…nition in Demange et al. (1986), but utilizes a more general wayof dealing with the uncommitted agents, taking the alphabetical order as a special case.

11

5

Implementability of MPEs on the quasi-linear domain

In this section, we review the current results of the EA auction, the sealed-bid
auction, as well as the AA auction on the quasi-linear domain.13
To begin with, we review the results of the EA auction. Demange et al. (1986)
assume that agents’valuations are multiples of the increment d > 0, i.e., they focus
on the class of quasi-linear utility functions UNQLdfui 2 U QL : 8l 2 M; vi (l) 2d Ng and the EA auction operates on domain (UNQLd )N . They obtain the following
results.
Fact 3 (Demange et al. 1986): Let d > 0 and u 2 (UNQLd )N . Then, the EA auction
with increment d …nds an MPE price for u in a …nite number of rounds.
The EA mechanism has nice e¢ ciency and incentive properties.
Fact 4 (Leonard, 1983): Let d > 0. The EA mechanism with increment d on
(UNQLd )N coincides with the MPE mechanism on (UNQLd )N . It is e¢ cient andstrategy-proof.
The coincidence assumption is essential to establish Facts 3 and 4. We will
elaborate further on this point in Section 6.1.
Remark 1: Facts 3 and 4 can be established on the classical domain that satis…es
the “generalized coincidence assumption.” Given an increment d > 0, let U d
fui 2 U : 8l; l0 2 L; 8k 2 d Z, 9k 0 2 d Z s.t. ui (l; k) = ui (l0 ; k 0 )g be the setof classical utility functions that exhibits quasi-linearity over L (d Z). ThenU d nU QL 6= ; and UNQLd U d .14 The generalized coincidence assumption says thatthe domain is (U d )N . Facts 3 and 4 hold on (U d )N since their original proofs also
work on (U d )N . A violation of the generalized coincidence assumption must leadto a violation of the coincidence assumption.
Second, we overview the results of the sealed-bid Vickrey auction. The MPE
allocation coincides with the sealed-bid Vickrey allocation for each quasi-linear
utility pro…le (Leonard 1983). Thus, we have the following result.
Fact 5 (Leonard, 1983): Let u 2 (U QL )N , (x ; pmin (u)) be an MPE, and pV (u) be
the sealed-bid Vickrey price. Then,P(i) x 2 arg max i2N vi (xi ).
x2X

13Facts 3 to 7 are established on the quasi-linear domain where each agent has non-negative
valuations of objects. It is not di¢ cult to ascertain that Facts 3 to 7 hold even when agents havenegative valuations of some objects.
14
It is not di¢ cult to construct a utility function satisfying quasi-linearity only on L (d Z),
but violating it on L (Rn(d Z)).

12

(u) = pVl (u).
(ii) For each l 2 M , pminlTherefore, on the quasi-linear domain, an MPE can be implemented via thesealed-bid Vickrey auction and an equivalence exists between the MPE mechanism
and the Vickrey mechanism. The e¢ ciency and strategy-proofness of the Vickrey
mechanism on the quasi-linear domain comes from Holmstrom (1979). In Section
6.2, we demonstrate that none of these results hold on the classical domain.
Finally, we overview the results of AA auction. Some factors might a¤ect
the AA auction’s outcome. First, it is possible to form the bidding queue in
myriad ways. The initial order when agents stand in a queue has jN j! variants.
Several possibilities open up when an agent is replaced and is driven back into
the queue of uncommitted agents, there are also several possibilities. That agent
could be placed …rst in the queue, second in the queue, or so forth. Moreover,di¤erent agents may be treated di¤erently as well. This implies that the number ofvariants of queues of uncommitted agents is much greater than jN j!. De…nitely, theoutcomes of the AA auction are predicated on how the bidding queue is formed.
Second, when an agent is called to bid, her demand set at the price that agent
faces may contain several objects, and the agent is supposed to bid on one ofthem. Each uncommitted agent could bid arbitrarily on any object in her demand
set. Therefore, the outcome of the AA auction relies on agents’bidding choiceseven if the utility pro…le is …xed. As shown below, the results of the AA auction
and the AA mechanism are robust to these factors.
Fact 6: Let u 2 (U QL )N , d > 0, and the bidding queue q be arbitrarily given.
(i)15 (Roughtgarden, 2014) The AA auction with increment d and bidding queue
q …nds a d equilibrium in a …nite number of rounds.
(ii) (Deviation bound) (Demange et al. 2016) Let p(u) be the price generated(u)d minfjM j ; jN jg.
by the AA auction in (i). For each l 2 M , pl (u) pminlFact 6(i) states that the outcome of AA auction is an approximate equilibriumby setting " = d, i.e., d equilibrium. Fact 6(ii) is the most interesting property of
the AA auction. It mentions that for any quasi-linear utility pro…le, the deviationpl (u) pmin(u) is bounded by d minfjM j ; jN jg, which is independent of thelbidding queues and agents’ choices from their demand sets. Thus, as d goesto zero, the outcome of the AA auction converges to an MPE. Unlike Fact 3,
Fact 6 enables agents’valuations to be arbitrary non-negative reals and does notnecessitate the coincidence assumption.
The AA mechanism is neither e¢ cient nor strategy-proof, but it does manage to achieve some degrees of approximate e¢ ciency and approximate strategy15

Step 1 in the proof of Proposition 9 gives an independent proof of Fact 6(i).

13proofnes.
Fact 7: Let d > 0, k = 2 minfjM j ; jN jg, and a bidding queue q be arbitrarily
given. The AA mechanism with the increment d and the bidding queue q on
(U QL )N is d e¢ cient and k d strategy-proof.
Indeed, d equilibrium is d e¢ cient,16 which ensures the d e¢ ciency of the
AA mechanism. The k d strategy-proofness of AA auction is shown by Roughgarden (2014). Fact 7 implies that the AA auction works well on the quasi-linear
domain even in the absence of the coincidence assumption. Nevertheless, it fails
to work on the classical domain. We discuss this point in Section 6.2.

6Implementability of MPE on the classical domain

To emphasize the feature of our model with heterogenous objects, we discuss thecase of homogenous objects where agents have classical utility functions. Homogeneity implies that for each payment, an agent’s utility hinges only on whether
she is assigned an object or the null; for this reason, each object gives her thesame utility level. In such cases, the MPE price is the same across all the objects, represented by a single number, and the MPE assignment is determined by
the ranking of generalized valuations. Put di¤erently, the MPE assigns objects
to agents whose generalized valuations are among jM j th-highest, and have them
pay a price equal to the (jM j + 1)th-highest generalized valuation, whereas theremaining agents get the null and pay nothing.17 When it comes to homogeneous
objects, the MPE allocation is exactly the generalized sealed-bid Vickrey allocation and the generalized Vickrey mechanism is the MPE mechanism, which, inturn, satis…es e¢ ciency and strategy-proofness (Saitoh and Serizawa, 2008).
However, when objects are heterogenous and agents have classical utility functions, the information of the generalized valuation is insu¢ cient to determine theMPE. In such an environment, for each payment, an agent’s utility depends on
16

We demonstrate that d equilibrium is d e¢ cient. By contradiction, suppose that there is ad equilibrium (x; p), which is not d e¢ cient. Let z 2 Z be the allocation compatible with (x; p),i.e., Xfor each i 2 N , tiX= pxi . Thus there is z 0 2 Z such that (i) for each i 2 N , ui (zi0 ) > ui (zi ), and(ii)
ti + d jN j
t0i . By (ii), there is i 2 N such that zi0 = (x0i ; t0i ) and t0i px0i + d. If not,
i2N

i2N

i.e., for each i 2 N , t0i < px0i + d, then

X

i2N

t0i <

X

i2N

px0i + d jN j

X

x2M

px + d jN j =X

i2N

ti + d jN j,contradicting (ii). Thus by (i), ui (x0i ; px0i + d) ui (zi0 ) > ui ( zi ), contradicting xi 2 Did (p).
17
To be precise, if jM j jN j or the (jM j + 1)th highest generalized valuation is non-positive,
the MPE price is zero. Otherwise, the MPE price is the (jM j + 1)th highest generalized valuation.

14

which object is assigned to her, and not merely on whether she is assigned an
object or the null. Moreover, an agent’s preference over object also depends on
payments. For example, at the payment t, an agent may prefer object a to b,
but at t0 , e.g., t0 > t, the opposite may occur, i.e., the agent prefers b to a. Notably, such a complexity never occurs in the case of homogenous objects or in thequasi-linear settings.
In the following, we demonstrate that the above complexity results in the poor
performance of the auctions studied in Section 5.

6.1

The exact ascending auction

Since the coincidence assumption requires the quasi-linearity, a violation of quasilinearity assumption leads to a violation of the coincidence assumption. We further
argue that if we arbitrarily select a utility pro…le from (U)N , in most cases, it does
not come from (U d )N de…ned in Remark 1 and so the generalized coincidence
fui 2
assumption, as well as the coincidence assumption, is violated. Let U d0000
U : 8l; l 2 L; 8k; k 2 d Z, ui (l; k) 6= ui (l ; k )g be the set of utility functions that
represents the strict preferences over L (d Z). It is noteworthy that U d is indeed
open and dense in U, and so U d U U d is non-generic in U. This implies that
if we arbitrarily select a utility pro…le from (U)N , in most cases it will come from
(U d )N , instead of (U d )N , and so the argument holds.
In the following, we examine the performance of EA auction by dropping thecoincidence assumption, but still keep quasi-linearity. We show that the EA auction and EA mechanism perform poorly without the coincidence assumption.
First, we demonstrate that even a small “perturbation” of UNQLd may lead tothe break-down of the EA auction. We …x an increment d > 0. For agent i, let
UQQLd
fui 2 U QL : 8l 2 M; vi (l) 2 d Q+ g. Given > 0, let UNQLd (Q+ ; ) fui 2+
UQQLd: 9ui 2 UNQLd such that 8a 2 M; jvi (a) v i (a)j d g. It is easily seen that+
UNQLd UNQLd (Q+ ; ) UQQLd, that all the three sets are countable, and that when
+
QLd
QLd
! 0, UN (Q+ ; ) ! UN .
Example 1 shows that for an arbitrarily small > 0, the EA auction does notwork.
Example 1: Let d > 0, r > 0, 0 < < 1, and t 2 N+ be such that (t 1) d > r.
Let M = fa; bg and N = f1; 2g. Let u 2 UNQLd (Q+ ; ) be represented by avaluation pro…le (v1 ( ); v2 ( )) such that:(1) v1 (a) = (t + 1 ) d and v1 (b) = (t + 1 ) d.
(2) v2 (a) = (t + 2 ) d and v2 (b) = (t + 2 ) d.
(3) 1 ; 2 ; 1 ; 2 2 Q+ ; 0 < 1 < 1 < 1, 0 < 2 < 2 < 1, and 1
1 < 2
2.
15

(4) 1 < and 2 < .18
We remark that the following analysis depends only on (1), (2), and (3), and that(4) is just used to specify where (v1 ( ); v2 ( )) comes from. There are several ways
to perturb valuation pro…les in UNQLd to get (v1 ( ); v2 ( )), by varying (4).
Note thatv1 (0) = v2 (0) = 0 < ( 1

1)

(3)

d = v1 (b)(1)< v2 (b)(3)

v1 (a)

v2 (a) = ( 2
(2)

( )
2)

d < d:(3)

min min
The MPE (x; pmin (u)) is: x = (x1 ; x2 ) = (a; b) and pmin (u) = (pmin0 ; pa ; pb ) =(0; 0; ( 11 ) d).
We con…rm that (x; pmin (u)) is an MPE. For agent 1,

v1 (a)

pmin= v1 (b)apmin= (t +b1)

d > 0 = v1 (0)pmin0and so x1 = a 2 D1 (pmin (u)) = fa; bg. For agent 2,
v2 (b)pmin= (t +
b

2

1+

1)

d > (t +(3)2)

d = v2 (a)pmin> 0 = v2 (0)
a

pmin
0

and so x2 = b 2 D2 (pmin (u)) = fbg. Thus De…nition 3(i) holds and De…nition 3(ii)holds vacuously. Thus (x; pmin (u)) is an equilibrium.
We use Fact 1(ii) to show that (x; pmin (u)) is an MPE. Note that fi 2 N :Di (pmin (u))
fagg = ;, fi 2 N : Di (pmin (u)) fbg = jf2gj = 1 = jfbgj, andfi 2 N : Di (pmin (u)) fa; bg = 2 = jfa; bgj. Thus no set of objects is overdemanded at pmin (u). Since pmin
> 0, fi 2 N : Di (pmin (u)) \ fbg =6 ;g = jf1; 2gj =b
2 > 1 = jfbgj. Thus no set of object is weakly underdemanded, as desired. Since= 0, b is connected via agent
x2 = b 2 D1 (pmin (u)) = fa; bg and x1 = a with pmina1’s demand set. Therefore, Fact 2 is also illustrated.
We now illustrate how the EA auction proceeds. The auction starts from round
0 with the initial price p0 = (0; 0; 0). At p0 , by ( ), both agents prefer b to a and0, i.e., D1 (p0 ) = D2 (p0 ) = fbg. Therefore, only b is minimally overdemanded
at p0 and so, its price p0b is raised by d while the price of a remains unchanged.
Therefore, we proceed to round 1 with p1 = (0; 0; d). At p1 , by ( ), both agents
prefer a to b and 0, i.e., D1 (p1 ) = D2 (p1 ) = fag. Therefore, only a is minimally
overdemanded at p1 and so, its price p1a is raised by d while the price of b does notchange. Therefore, we proceed to round 2 with p2 = (0; d; d) and so on.
18

When is given, there is k 2 N+ such that 10 k
. For example, we can setkkk
1 = 0:5=10 , 2 = 0:2=10 , and 2 = 0:8=10 . Then (1) to (4) hold.

16

1 = 0:1=10k,

At round 2t + 1 with price p2t+1 = (0; t d; (t + 1) d), by ( ), both agents prefera to b and 0, i.e., D1 (p2t+1 ) = D2 (p2t+1 ) = fag. Therefore, only a is minimallyis raised by d while the price of b does
overdemanded at p2t+1 and so, its price p2t+1
a
not change. The auction proceeds to round 2t+2 with p2t+2 = (0; (t+1) d; (t+1) d).
At price p2t+2 , no agent is willing to obtain either a or b, and they prefer to drop
the auction, i.e., D1 (p2t+2 ) = D2 (p2t+2 ) = f0g. At price p2t+2 , there are no sets ofobjects that are minimally overdemanded. Therefore, the auction terminates at
p2t+2 , with an allocation that each agent receives the null object and pays nothing.
= (t + 1) d > r and p2t+2
=
pmin
pmin
In the above case, note that p2t+2aabb(t + 1 ( 141 )) d > t d > r.
In Example 1, since r can be arbitrarily large, the EA auction may overshootthe MPE price by a substantial margin. Example 1 can be easily generalized tocases of more agents and objects. Proposition 1 summarizes this overshooting
result.
Proposition 1 (Substantial overshooting): For each d > 0, each arbitrarily
large r > 0, and each arbitrarily small > 0, there is u 2 (UNQLd (Q+ ; ))N suchthat the EA auction with increment d generates a price p with pl > pmin(u) + rl
for each l 2 M .
It is easy to con…rm that no equilibrium is compatible with discrete prices in(d N)L in Example 1. One may wonder whether this nonexistence result is a key
factor that results in the large overshooting of the EA auction. Thus, we consider
approximate equilibria where the deviation is set to be the increment, i.e., " = d.
The prices compatible with d equilibria for the utility pro…le u in Example 1 aresuch that p = (0; k d; k d) for k = 0; 1; : : : ; t, or p0 = (0; k 0 d; (k 0 + 1) d) fork 0 = 0; 1; : : : ; t 1. However, in Example 1, the outcome price is not among them,and moreover, the outcome assignment is not a d equilibrium assignment either.
Thus, the EA auction does not …nd a d equilibrium.
In the following, we argue that the EA auction largely overshoot even thed equilibrium price that is “closest” to the MPE price. Formally, given a utility
pro…le u 2 U N , a d equilibrium price pA (u) is called a closest d equilibrium priceto pmin (u) if there is no other d equilibrium price p0 for that utility pro…le suchthat for each l 2 M , pA
pmin(u)
p0l pmin(u) with at least one strict
l (u)
l
l
A
min
inequality. The price p (u) approximates p (u) among all 1 equilibrium prices.
0
In Example 1, if 1
1 < 0:5, p = (0; 0; 0) is a closest d equilibrium price topmin (u) among all d equilibrium prices.19 The insight of large overshooting from
19

1
min
If 1
(u) among all
1 > 0:5, p = (0; 0; d) is a closest d equilibrium price to p
01
d equilibrium prices. If 1
1 = 0:5, both p and p are closest d equilibrium prices to17

Example 1 extends to a closest d equilibrium price.
Proposition 2: For each d > 0, each arbitrarily large r > 0, and each arbitrarily
small > 0, there is u 2 (UNQLd (Q+ ; ))N such that the EA auction with incrementd generates a price p with pl pAl (u) + r for each l 2 M .
Propositions 1 and 2 demonstrate that the EA auction completely breaks downon (UNQLd (Q+ ; ))N even when is su¢ ciently small. Notably, the smaller is, thesmaller UNQLd (Q+ ; )nUNQLd will be. Thus, the operation of EA auction to get the
MPE is rather demanding.
Corollary 1: Let d > 0, an arbitrarily small > 0 be given, an arbitrarilyNlarge r > 0 be given, and UNQLd (Q+ ; )U
U. There is u 2 U such that
the EA auction with increment d generates a price p with plpmin(u) + r andlApl pl (u) + r for each l 2 M .

Proposition 1 perturbs UNQLd only by allowing agents’valuations to take positive
rational numbers in the neighborhood of natural numbers. It concludes that there
is no common increment such that for each u 2 UNQLd (Q+ ; ), the EA auction …nds
the associated MPE price pmin (u). However, for each u 2 UNQLd (Q+ ; ), there is anincrement such that the EA auction …nds the associated MPE price pmin (u).20
On the other hand, if we perturb UNQLd by allowing agents’valuations to takepositive irrational numbers in the neighborhood of natural numbers as well, we
can conclude a stronger result as in illustrated by Example 2 below: For somevaluation pro…le, regardless of increments the EA auction will always overshootthe MPE price and a closest d equilibrium price.
Given > 0, let UNQLd (R+ ; )fui 2 U QL : 9ui 2 UNQLd such that 8a 2
M; jvi (a) v i (a)j d g. It is easily seen that UNQLd UNQLd (R+ ; ) U QLd , andthat when ! 0, UNQLd (R+ ; ) ! UNQLd .
Example 2: Let d > 0, r > 0, 0 < < 1, and 1 ; 2 ; 3 2 d N+ be suchthat r + 1 < 1 < 2 < 3 be given. Let M = fa; b; cg and N = f1; 2; 3g. Let
u 2 (UNQLd (R+ ; ))3 be represented by a valuation pro…le (v1 ( ); v2 ( ); v3 ( )) suchthat:pmin (u) among all d equilibrium prices. It can be easily veri…ed that Proposition 2 holds evenwhen there are multiple closest d equilibrium prices.
20
To see this point, assume, w.l.o.g, that for each i 2 N , there is an object l 2 M such thatvi (l) > 0, and let Mi0 be the collection of such objects. For each i 2 N and each l 2 Mi0 , letvi (l) 2 d Q+ be such that vi (l) = d (pli =qil ) where pli ; qil 2 N+ and pli =qil is irreducible, and let
di = d ( l2M 0 q1i ). Then, if d0 = i2N di is the increment in the auction, agents’valuations arelinteger multiples of d0 . For each u 2 UQQLd, an increment d0 de…ned as above guarantees that+
the EA auction …nds an MPE for u.

18

(1) v1 (a) = 1 , v1 (b) = 1 + , and v1 (c) = 1 +(2) v2 (a) = 2 , v2 (b) = 2 + , and v2 (c) = 2 +(3) v3 (a) = 3 1, v3 (b) = 3 + , and v3 (c) = 3 + .
(4) ; ; 2 R+ nQ+ , 2 R+ nQ+ and < < < 1.
(5) < d .21
Similarly to Example 1, we remark that the following analysis relies only on (1),(2), (3), and (4), and that (5) is just used to specify where (v1 ( ); v2 ( ); v3 ( )) comes
from, and one may verify that by varying (5), there are several ways to perturb
valuation pro…les in UNQLd to get (v1 ( ); v2 ( ); v3 ( )).
min min min
The MPE price for u speci…ed above is pmin (u) = (pmin0 ; pa ; pb ; pc ) =(0; 0; ; ).
Let ml = 0 if l = a, ml = if l = b, and ml = if l = c. We show that foreach increment d > 0, the EA auction …nds a price p(0; pa ; pb ; pc ) such thatpl
1 + ml for each l 2 M .
We proceed by contradiction. Suppose that for some increment d > 0, the EA
auction …nds a price p such that there is a non-empty set M 0 M such that eachl 2 M 0 , pl < 1 + ml and for each l 2 M nM 0 , pl
1 + ml .
We begin by proving Claims 1 and 2 below.
Claim 1: (a) There is no set of objects that is overdemanded at (0; pa ; pb ; pc ).
(b) For each i 2 N , each l 2 M , vi (l) ( 1 + ml ) 0.
(c) For each i 2 N , Di (p) M .

Part (a): If there is a set of objects that is overdemanded at (0; pa ; pb ; pc ), then it
is easy to verify that set contains a minimally overdemanded set at (0; pa ; pb ; pc ),contradicting the termination of the EA auction.
Part (b): For agent 1, for each l 2 M , v1 (l) = 1 + ml . For agent 2, if l 2 fa; bg,
v2 (l) ( 1 + ml ) = 2( 1 + ml ) = 2.
1 > 0. If l = c, v2 (c)1 +Since 1 ; 2 2 N+ , 2 > 1 , and (4), it holds 2
0 and so1 +v2 (c) ( 1 + ml ) 0. For agent 3, if l 2 fb; cg, v3 (l) ( 1 + ml ) = 3
0.
1
If l = a, v3 (a) ( 1 + ml ) = 3 1
1 . Since 1 ; 3 2 N+ and 3 > 1 , it holds
that 3 1
0 and so v3 (a) ( 1 + ml ) 0. Thus, (b) holds.
1
Part (c): For each i 2 N , each l 2 Di (p), and each l0 2 M 0 ,vi (l)

plso 0 2= Di (p) and Di (p)vi (l0 )pl0 0 > 0 vi (l0 )l 2M( 1 + ml0 )0,Claim 1(b)M.

Claim 2: (a) pb = pa + , and (b) pc = pb +.

21
is given, thereis p
k 2 N+ such that 10pk
p Whenpp3)=10k+1 , = ( 113)=10k+1 , and = ( 7( 5

example, we can set=
pd . Fork+13)=10. Then (1) to (4) hold.

19

Part (a): Suppose that pb 6= pa + . We consider two cases, i.e., pb > pa +(Case 1), or pb < pa + (Case 2), and derive a contradiction in each case.
Case 1: pb > pa +For each i 2 f1; 2g,vi (a)pa=vi (b)(1)&(2)pa > vi (b)Case 1pb ;so b 2= Di (p). Thus, by Claim 1(c), for each i 2 f1; 2g, Di (p) M nfbg = fa; cg.
If b 2= D3 (p), then by Claim 1(c) D3 (p)M nfbg = fa; cg, and so fa; cg isoverdemanded, contradicting Claim 1(a). Thus b 2 D3 (p). Since b 2 D3 (p) implies
v3 (b) pb v3 (c) pc , by (3), we have pc pb +. Thus by pb > pa + , wehave pc > pa + . Therefore, for each i 2 f1; 2g,vi (a)pavi (c)

pa(1);(2)&(4)>pc >pa +vi (c)pc ;so c 2= Di (p). Thus for each i 2 f1; 2g, by Claim 1(c) and Di (p)D1 (p) = D2 (p) = fag, contradicting Claim 1(a).
Case 2: pb < pa +For each i 2 f1; 2g,vi (b)

pb=(1)&(2)vi (a) +pb > vi (a)Case 2fa; cg, we havepa ;so a 2= Di (p). Thus for each i 2 f1; 2g, by Claim 1(c), Di (p) M nfag = fb; cg.
If a 2= D3 (p), then by Claim 1(c), D3 (p)M nfag = fb; cg, and so fb; cg isoverdemanded, contradicting Claim 1(a). Thus a 2 D3 (p). Since a 2 D3 (p)implies v3 (a) pa
v3 (c) pc , by (3), we have pc
pa + + 1. Thus bypb < pa + , we have pc > pb
+ + 1 > pb +. Note that by (1),v1 (b) = v1 (c) +, and by (2) and < , v2 (b) = v2 (c) +> v2 (c) +.
Thus, for each i 2 f1; 2g;vi (b)pbvi (c)

(

)

pb

>

pc >pb +vi (c)pc ;so c 2= Di (p). Thus, for each i 2 f1; 2g, by Claim 1(c) and Di (p) fa; cg, we haveD1 (p) = D2 (p) = fag, contradicting Claim 1(a).
Thus, pb = pa + .
Part (b): Suppose that pc 6= pb +. We consider two cases, i.e., pc > pb +(Case 1), or pc < pb +(Case 2), and derive a contradiction in each case.
Case 1: pc > pb +For each i 2 f1; 3g,vi (b)

pb=(1)&(3)vi (c) +pb > vi (c)Case 120pc ,so c 2
= Di (p). Thus, by Claim 1(c), for each i 2 f1; 3g, Di (p)Note thatv2 (b)

pb = v2 (c) +pb > v2 (c) +pb > v2 (c)Case 1>(2)

M nfcg = fa; bg.
pc

so c 2= D2 (p). Thus by Claim 1(c), D2 (p)M nfcg = fa; bg. Thus for eachi 2 f1; 2; 3g, Di (p) fa; bg and fa; bg is overdemanded, contradicting Claim 1(a).
Case 2: pc < pb +Note that by Claim 2(a), i.e., pb = pa + , (1) implies v1 (b) pb = v1 (a) pa ,while (3) implies v3 (b) pb = v3 (a) + 1 pa > v3 (a) pa . Thus for each i 2 f1; 3g,vi (c)

pc=(1)&(3)vi (b)+

pc > vi (b)Case 2pb

vi (a)pa

so a; b 2
= Di (p). Thus for each i 2 f1; 3g, by Claim 1(c), Di (p) = fcg. Thus
D1 (p) = D3 (p) = fcg and fcg is overdemanded, contradicting Claim 1(a).
Thus pc = pb +. Thus Claim 2 holds.
Since the EA auction stops at (0; pa ; pb ; pc ), there are ka ; kb ; kc 2 N such that
pa = ka d, pb = kb d, and pc = kc d. By Claim 2 and (4), we have pb pa =(kb ka )d = > 0 and pc pb = (kc kb )d => 0. Therefore,
kc
kb

kb
pc
=
ka
pb

pb
=
pa

:

Note that by (4),is an irrational number. However, by ka ; kb ; kc 2 N, (kckb )=(kb ka ) is a rational number. This is a contradiction.
Thus we conclude that for each increment d > 0, the EA auction …nds a price(0; pa ; pb ; pc ) such that pa
1 , pb
1 + , and pc
1+ .
min
4
By (4) and 1 > r + 1, for each l 2 M , pl > pl (u) + r.
Example 2 can be easily generalized to cases of more agents and objects. Example 2 also works to demonstrate that for any positive increment d, the EA
auction is always largely overshooting a closest d equilibrium price, which canbe skipped to avoid the redundancy. Proposition 3 summarizes the insights of
Example 2.
Proposition 3: Let d > 0. For an arbitrarily large r > 0 and an arbitrarily small> 0, there is u 2 (UNQLd (R+ ; ))N such that for any positive increment, the EA
auction generates a price p with plpmin(u) + r and plpAll (u) + r for eachl 2 M.
Proposition 3 strengthens the results in Propositions 1 and 2, by further enlarging the range of agents’valuations slightly.
21

In the following, Example 1 is used to study the r e¢ ciency and r strategyproofness of the EA mechanism.
Example 3: Consider the economy in Example 1. We …rst consider the e¢ ciency
issue. Let z1 = (a; (t 1) d) and z2 = (b; (t 1) d). For each i 2 f1; 2g,ui (zi ) > ui (0; 0) = 0, and Rev(z) = (t + t 2) d > 2r > 0. Thus, the EA
mechanism fails to …nd an r e¢ cient allocation for u.
Next, we consider the incentive issue. Let u02 2 U QL be denoted by v20 ( ) suchthat v20 (a) = (t + 2 ) d and v20 (b) = (t + 2 ) d. Then, agent 2 with u02 demands
only object a at the initial price p0 = (0; 0; 0), i.e., D20 (p0 ) = fag while as analyzed
in Example 1, D1 (p0 ) = fbg. Since no set of objects is minimally overdemanded,
the EA auction concludes at p0 , and agents 1 and 2 receive objects b and a withno payment. Since t 1 > r > 0, it holds that u2 (a; 0) = (t + 2 ) d > u2 (0; r) =v2 (0) + r = r. As a result, agent 2 bene…ts more than r from misreporting v20 ( )when her true valuation function is v2 ( ). Therefore, the EA mechanism withincrement d is r manipulable.
4
Example 3 can easily be generalized to cases of more agents and objects, whichindicates the following result.
Proposition 4: Let d > 0, an arbitrarily small > 0 be given, and UNQLd (Q+ ; )U
U QL . The EA mechanism with increment d is absolutely ine¢ cient andNabsolutely manipulable on U .
By Proposition 4, we have the following result.
Corollary 2: Let d > 0, an arbitrarily small > 0 be given, and UNQLd (Q+ ; )U
U. The EA mechanism with increment d is absolutely ine¢ cient and abN
solutely manipulable on U .
We end this section by discussing the predicament of extending the continuoustime clock auction for one object with quasi-linear utility functions to our modelfor heterogeneous objects with classical utility functions.
Continuous-time clock auction: The continuous-time clock auction, originatedfrom the Japanese simultaneous-bidding auction (Cassady, 1967), is a particular
type of the English auction for selling only one object. The price increases continuously at some rate kept by a clock, and agents drop out at some point. The
auction stops a price when all agents drop out except for one and the remaining
agent wins the object and pays that stopping price. This auction duplicates the
MPE mechanism for one object.
We begin by discussing its extension to multiple heterogenous objects. Let
M = fa; bg and N = f1; 2; 3g. Let u 2 (U QL )3 be such that v1 (a) = 3, v1 (b) = 1,22

v2 (a) = 1, v2 (b) = 3, and v3 (a) = v3 (b) = 2. In such a case, the MPE (x; pmin (u))
min minis x = (x1 ; x2 ; x3 ) = (a; b; 0) and pmin (u) = (pmin0 ; pa ; pb ) = (0; 2; 2).
One possible extension of the continuous-time clock auction is that each agent
chooses an object from her demand at the current price, and bids on it. The pricesof minimally overdemanded objects are increased continuously at the same rate.
At p0 = (0; 0; 0), D1 (p0 ) = fag; D2 (p0 ) = fbg; and D3 (p0 ) = fa; bg. Thus at p0 ,agent 1 bids on a, agent 2 bids on b, and agent 3 bids on a or b. Whenever the priceof a (or b) is higher than b (or a), agents 3 demands and bids on b (or a). Therefore,
beginning from (0; 0; 0), if the price increases continuously, agents 3’s bid needs
to move between a and b continuously until the price reaches pmin (u) = (0; 2; 2).
Such a bidding behavior is physically impossible. Furthermore, the associatedprice path to pmin (u) is not well-de…ned.
Another possible extension is that each agent reports her demand set at thecurrent price, and the prices of minimally overdemanded objects are increased
continuously at the same rate. Indeed, this is the continuous variant of the EA
auction. It works well on the quasi-linear domain.22 However, such an auction
is fraught with problems on the classical domain. Consider a classical utility
function u03 2 U of agent 3 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 the MPE
price is pmin (u0 ) = (0; 1; 2). Note that for pa 2 [0; 1], D3 (p) = fag if pb > 2pa ,D3 (p) = fbg if pb < 2pa , D3 (p) = fa; bg if pb = 2pa . Thus, starting from (0; 0; 0),
if the prices of minimally overdemanded objects increase continuously with thesame rate, agents 3 needs to move between fa; bg and fbg continuously, which is
physically impossible. Note that in such a case, the price path to pmin (u0 ) = (0; 1; 2)
is not well-de…ned either.
Morimoto and Serizawa (Proposition 1, 2015) show that if the price path generated by the aforementioned continuous variant of the EA auction is well-de…ned,then such an auction converges to the MPE price with multiple objects in a …nitetime on the classical domain. However, their result does not guarantee the existence of such a price path. Our discussion demonstrates that the price path of the
EA auction’s continuous variant may not be well-de…ned for some classical utility
pro…les. In particular, it is both theoretically and practically impossible to use
such an auction on the classical domain as an alternative option to approximate
or duplicate the MPE mechanism.
22

If the prices increase continuously along the path p(t) = (0; 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).

23

6.2

The generalized sealed-bid Vickrey auction and approximate ascending auction

In contrast to the EA auction, the operations of the sealed-bid Vickrey auction
and the AA auction are not predicated on the coincidence assumption and work
well on the quasi-linear domain. However, in this section, we show that the niceproperties of those two auctions elucidated in Section 5 do not hold on the classicaldomain.
6.2.1

The generalized sealed-bid Vickrey auction

Example 4 below highlights that both the assignments and prices are di¤erent
between the MPE and generalized sealed-bid Vickrey on the classical domain.
Example 4: 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), and u2 (a; 3r) = u2 (b; 2r).
(3) V3 (a) = 10r, V3 (b) = 30r, u3 (a; 3r) = u3 (b; 2r), and u3 (a; 8r) = u3 (b; 2r).
The generalized sealed-bid Vickrey outcome (xV ; pV (u)) is xV = (xV1 ; xV2 ; xV3 ) =(0; a; b) and pV (u) = (pV0 ; pVa ; pVb ) = (0; r; 2r). In this a case, the generalized sealedbid Vickrey assignment is unique.
We show how to calculate (xV ; pV (u)). It is not hard to see that assigninga to agent 2 and b to agent 3 while agent 1 gets the null object maximizes thesum of generalized valuations V1 ( ) + V2 ( ) + V3 ( ), which is equal to 50r. Thus
xV satis…es De…nition 7(i). In the absence of agent 2, assigning b to agent 3 andassigning a to agent 1 maximizes the sum of generalized valuations V1 ( ) + V3 ( ),which is equal to 31r. Therefore, by De…nition 7(ii), agent 2 gets a and pays
V1 (a)+V3 (b) (V1 (xV1 )+V3 (xV3 )) = r. Without agent 3, assigning a to agent 2 andassigning b to agent 1 maximizes the sum of generalized valuations V1 ( ) + V2 ( ),which is equal to 22r. Therefore, by De…nition 7(ii), agent 2 gets a and pays
V1 (b) + V2 (a) (V1 (xV1 ) + V2 (xV2 )) = 2r.
min min
The MPE (x; pmin (u)) is x = (x1 ; x2 ; x3 ) = (0; b; a) and pmin (u) = (pmin0 ; pa ; pb ) =(0; 3r; 2r). In this case, the MPE assignment is unique as well.
Thus, pmin (u) 6= pV (u) and x 6= xV .
4
Since Example 4 can be easily generalized to cases of more agents and objects,
we have Proposition 5.
Proposition 5: There is u 2 U N such that (i) for each l 2 M , pmin(u) 6= pVl (u),land (ii) there is no intersection between the set of the MPE assignments and the24set of the generalized sealed-bid Vickrey assignments for u.
We discuss the intuition behind Proposition 5 via Example 4. By its de…nition, the generalized sealed-bid Vickrey price is determined only by fVi ( )gi2N .
However, the information in fVi ( )gi2N is not su¢ cient to determine equilibrium
prices. Indeed, at the generalized sealed-bid Vickrey price pV (u) = (0; r; 2r), sinceui (a; r) > ui (b; 2r) > ui (0; 0) for i = 2; 3, agents 2 and 3 both demand only a,and so pV (u) is not an equilibrium price. Put di¤erently, the determination of thegeneralized sealed-bid Vickrey price and equilibrium price may require di¤erent
parts of preference information in fui ( )gi2N , which may not convey in fVi ( )gi2N .
Therefore, the di¤erent usage of preference information results in various outcomes. Moreover the larger deviation of utility pro…les from quasi-linearity may
lead to larger di¤erences in such outcomes. Indeed, that the generalized sealedbid Vickrey price is not an equilibrium price; it is rather a robust property on
the classical domain although the generalized sealed-bid Vickrey prices could be
equilibrium prices for some utility pro…les.23
In contrast to the classical domain, on the quasi-linear domain, since for eachagent i, vi ( ) contains all the information of her preference ui ( ), the generalized
sealed-bid Vickrey price is an equilibrium price as well. For instance, consider autility pro…le u0 2 (U QL )3 in Example 4 that for each i 2 f1; 2; 3g, vi0 ( ) = Vi ( ).
Then, pV (u0 ) = pV (u) = (0; r; 2r), and x0V = xV = (0; a; b). Since u01 (0; 0) =u01 (a; r) = u01 (b; 2r); u02 (a; r) > u02 (b; 2r) > u02 (0; 0); and u03 (b; 2r) > u02 (a; r) >u02 (0; 0), each agent demands her assignment at x0V . Thus, (x0V ; pV (u0 )) is anequilibrium for u0 .
Next, we show the ine¢ ciency and manipulability of the generalized Vickrey
mechanism.
Example 5: Consider the economy in Example 4. 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
Rev(z) = 6:5r > pV0 + pVa + pVb + 3r = 6r. Thus (xV ; pV ) is not r e¢ cient for u.
Let u03 2 U be such that V30 (a) = 35r, V30 (b) = 8r, and u03 (a; 10r) = u03 (b; 4r).
23

Fix r > 0 and u1 as shown in Example 4. Let U2 (20r; 10r)
fu2 ( ; ) 2 U : V2 (a) = 20r,
V2 (b) = 10rg, and U3 (10r; 30r) fu3 ( ; ) 2 U : V3 (a) = 10r, V3 (b) = 30rg. Any pair (u2 ; u3 ) 2
U2 (20r; 10r) U3 (10r; 30r) of utility functions of agents 2 and 3, together with u1 , have thegeneralized sealed-bid Vickrey price pV = (0; r; 2r) and the associated assignment xV = (0; a; b).
However, for any utility pro…le u0 2 fu1 g U2 (20r; 10r) U3 (10r; 30r) such that u02 (a; r) <0
u2 (b; 2r) or u03 (b; 2r) < u03 (a; r), (xV ; pV ) is not an equilibrium. Thus, for these utility pro…les,the generalized sealed-bid Vickrey outcome is not an equilibrium.
For any utility pro…le u0 2 fu1 g U2 (20r; 10r) U3 (10r; 30r) such that u02 (a; r) u02 (b; 2r) and0
u3 (b; 2r) u03 (a; r), (xV ; pV ) is an equilibrium. Thus, for these utility pro…les, the generalized
sealed-bid Vickrey outcome is an equilibrium.

25

Agent 3 obtains (a; 12r) under the generalized sealed-bid Vickrey auction for theutility pro…le (u1 ; u2 ; u03 ). Since u03 (b; 2r) > u03 (b; 4r) = u03 (a; 10r) > u03 (a; 12r),
agent 3 bene…ts from reporting u3 when her true utility function is u03 . Thus, it
can be inferred that the generalized Vickrey mechanism is r manipulable.
4
Since Example 5 can be easily generalized to cases of more agents and objects,
we have Proposition 6.
Proposition 6: The generalized Vickrey mechanism is absolutely ine¢ cient andabsolutely manipulable on U N .
Morimoto and Serizawa (2015) characterize the MPE mechanism via e¢ ciency,
strategy-proofness, and some mild axioms on the classical domain with some mild
restriction. In their Section 6.2, an example is cited to show that the MPE mechanism is di¤erent from the generalized Vickrey mechanism, which, coupled with
their characterization of the MPE mechanism, indicates that the generalized Vickrey mechanism is neither e¢ cient nor strategy-proof. Proposition 5 is congruent
with their result, but Proposition 6 complements their result by arguing thatwhen the deviation of utility pro…les from quasi-linearity is large, the generalized
Vickrey mechanism cannot achieve even approximate e¢ ciency and approximate
strategy-proofness to any degree.
6.2.2

The approximate ascending auction

Next, we study whether the AA auction works as predicted by Facts 6 and 7 when
agents have the classical utility functions.
In an economy with two objects and three agents, Example 6 below demonstrates that the AA auction substantially undershoots the MPE price even if only
one agent has the classical utility function.
Example 6: Let M = fa; bg and N = f1; 2; 3g. The bidding queue is in theorder of agent 1; 2 and 3, without any speci…cation about the manner in which
uncommitted agents are driven back into the queue in the auction. Let d > 0 be
the increment and r > 0 be a large number. Let t 2 N+ be such that t d > r andu 2 U 3 be such that:(1) Let u1 2 U QL be such that u1 (a; pa ) = td pa and u1 (b; pb ) = 3td pb :(2) Let u2 2 U be such thatu2 (a; 0) > u2 (b; d) > u2 (a; 0:5d) = u2 (b; 2td) > 0 = u2 (0; 0).24
24

For example, u2 can take the form of u2 (a; pa ) = 20td0:9)d pb .

26

(4t

1:8)pa and u2 (b; pb ) = (20t +(3) Let u3 2 U QL be such that u3 (a; pa ) = 0:5d

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

min

min

pb .

min min(u) = (pmin0 ; pa ; pb ) =The MPE (x; p (u)) is x = (x1 ; x2 ; x3 ) = (b; a; 0) and p(0; 0:5d; 2td).
We illustrate how the AA auction proceeds. AA auction begins from theinitial price pb0 = (0; 0; 0). At pb0 , agent 1 bids …rst. Agent 1 only demands
b at p0 since u1 (b; 0) = 3td > u1 (a; 0) = td > u1 (0; 0) = v1 (0) = 0. Thus
D1 (p0 ) = fbg, she bids on b and is tentatively assigned (b; 0). The market pricegenerated in round 0 is p0 = (0; 0; 0) and auction proceeds to round 1. Then agent
2 is called. By the de…nition of the AA auction, if agent 2 bids b, the price of bthat she faces is updated, i.e., pb1b = p0b + d = d while the price of a that she faces
remains the same, i.e., pb1a = p0a = 0. Agent 2 only demands a at pb1 = (0; 0; d)since u2 (a; 0) > u2 (b; d) > u2 (0; 0). Thus D2 (bp1 ) = fag, agent 2 bids on a andis tentatively assigned (a; 0). Then, the market price generated in round 1 is
p1 = (0; 0; 0) and the auction proceeds to round 2. Then agent 3 is called. If agent
3 bids a or b, the prices of a and b that she faces are updated, i.e., pb2a = p1a + d = dand pb2b = p1b + d = d. Since agent 3 only demands the null object at pb2 = (0; d; d),i.e., D3 (bp2 ) = f0g, agent 3 drops out. Since there is no uncommitted agent in
the queue, the auction terminates at round 2 with an unchanged market pricep2 = p1 = (0; 0; 0) and agents 1, 2, and 3 get (b; 0), (a; 0) and (0; 0), respectively.
Notice that p2b = 0 and pmin
p2b = 2td > r. Thus, the AA auction generates zerobby an arbitrarily large amount r.
4
revenue and pb is smaller than pminbNext, we use Example 7 to demonstrate that the AA auction may substantiallyovershoot the MPE price.
Example 7: Let M = fa; bg and N = f1; 2; 3g. The biding 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 the increment and r > 0 be alarge 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 following:
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) > u3 (0; r) andu3 (a; 0:6d) = u3 (b; td) > u3 (0; 0) = u3 (a; (t0:4)d) = u3 (b; (t + 0:4)d).

min min
The MPE (x; pmin (u)) is x = (x1 ; x2 ; x3 ) = (0; b; a) and pmin (u) = (pmin0 ; pa ; pb ) =(0; 0:5d; (t + 0:1)d).

27

We illustrate how the AA auction proceeds. AA auction begins from the initial
price pb0 = (0; 0; 0). At pb0 , agent 1 bids …rst. Since agent 1 only demands b at pb0 ,i.e., D1 (bp0 ) = fbg, she bids on b and is tentatively assigned (b; 0). The market
price generated in round 0 is p0 = (0; 0; 0) and auction proceeds to round 1. Then
agent 2 is called. By the de…nition of the AA auction, if agent 2 bids b, the priceof b that she faces is updated, i.e., pb1b = p0b + d = d while the price of a thatshe faces remains unchanged, i.e., pb1a = p0a = 0. Since agent 2 only demands b
at pb1 = (0; 0; d), i.e., D2 (bp1 ) = fbg, agent 2 bids on b and is tentatively assigned(b; d). Then, agent 1 is placed last in the queue behind agent 3. Then, the market
price generated in round 1 is p1 = (0; 0; d) and the auction proceeds to round 2.
Then agent 3 is called. By the de…nition of the AA auction, if agent 3 bids b, theprice of b that she faces is updated, i.e., pb2b = p1b + d = 2d while the price of athat she faces remains the same, i.e., pb2a = p1a = 0. Since agent 3 only demands b
at pb2 = (0; 0; 2d), i.e., D3 (bp2 ) = fbg, agent 3 bids on b and is tentatively assigned(b; 2d). Then, agent 2 is placed last in the queue behind agent 1. Then, the market
price generated in round 2 is p2 = (0; 0; 2d) and the auction proceeds to round 3.
Then agent 1 is called and so on.
Since u1 (b; (t 1)d) > u1 (a; 0), u2 (b; (t 0:3)d) > u2 (a; 0), and u3 (b; (t 0:4)d) >u3 (a; 0), three agents will just compete for b, which makes the auction proceed toround t 1. The market price generated in round t 1 is pt 1 = (0; 0; (t 1)d)and since t = 3k for some odd number k 2 N+ , agent 3 gets (b; (t 1)d); in thequeue, agent 2 is behind agent 1. In round t, agent 1 is called. If agent 1 bids b,
the price of b that she faces is updated, i.e., pbtb = ptb 1 + d = td while the priceof a that she faces remains unchanged, i.e., pbta = pta 1 = 0. Since agent 1 only
demands b at pbt = (0; 0; td), i.e., D1 (bpt ) = fbg, agent 1 bids on b and is tentatively
assigned (b; td). Then, agent 3 is placed last in the queue behind agent 2. Then,the market price generated in round t is pt = (0; 0; td) and the auction proceeds
to round t + 1.
In round t + 1, agent 2 is called. If agent 2 bids b, the price of b that she
faces is updated, i.e., pbt+1= ptb + d = (t + 1)d while the price of a that shebfaces remains unchanged, i.e., pbt+1= pta = 0. Since agent 2 only demands a atapbt+1 = (0; 0; (t + 1)d), i.e., D2 (bpt+1 ) = fag, agent 2 bids on a and is tentatively
assigned (a; 0). The market price generated in round t + 1 is pt+1 = (0; 0; td) andthe auction then proceeds to round t + 2. Agent 3 is called. If agent 3 bids b, the= pt+1+ d = (t + 1)d and if she bids
price of b that she faces is updated, i.e., pbt+2bba, the price of a that she faces is updated either, i.e., pbt+2= pt+1+ d = d. Since
a
a
t+2
t+2
agent 3 only demands a at pb = (0; d; (t + 1)d), i.e., D3 (bp ) = fag, agent 3
bids on a and is tentatively assigned (a; d). Then, agent 2 is placed in the queue.
28

Agents 2 and 3 will recursively bid on a.
The market price generated by round 2t is (0; (t 1)d; td). Since t is an odd
number, agent 2 is tentatively assigned (a; (t 1)d) while agent 1 is tentatively
assigned (b; td). Agent 3 is in the queue. The auction proceeds to round 2t + 1
and agent 3 is called. If agent 3 bids b, the price of b that she faces is updated,i.e., pb2t+1= p2t
b + d = (t + 1)d and if she bids a, the price of a that she faces isb= p2t
updated either, i.e., pb2t+1
a + d = td. Since agent 3 only demands the nulla2t+1
object at pb= (0; td; (t + 1)d), i.e., D3 (bp2t+1 ) = f0g, agent 3 drops out. The
auction terminates at round 2t + 1 and the market price generated in round 2t + 1
is p2t+1 = (0; (t 1)d; td) where agent 1 is assigned (b; td), agent 2 is assigned(a; (t 1)d), and agent 3 drops out.
Note that pa pmin
= (t 1:5)d > r can be arbitrarily large.
4a
Examples 6 and 7 can be easily generalized to cases with more agents andobjects and with an arbitrary bidding queue. Thus, we have Proposition 7.
Proposition 7: Let d > 0 be the increment and a bidding queue be arbitrarily
given in the AA auction. Then, for an arbitrarily large r > 0, the following resultshold.
(i) (Substantial undershooting) For each a 2 M , there is u 2 U N such that
AA auction generates price p = (0; : : : ; 0) with pa < pminr.
a(ii) (Substantial overshooting) For each a 2 M , there is u0 2 U N such that the
AA auction generates price p with pa > pmin
+ r.
aAs seen in the case of the sealed-bid Vickrey auction, when the deviation ofutility pro…les from quasi-linearity is large, the outcome of the AA auction may
not even approximate the MPE. Notably, by Proposition 7(i), it is possible for the
AA auction to generate zero revenue even if some agent has a very high willingness
to pay for some object.
In the following, let pd (u; q) be the price generated by the AA auction withincrement d and a bidding queue q for u 2 U N . By Proposition 7, we have thefollowing result.
Corollary 3: There are no increment d > 0 and no bidding queue q such that foreach u 2 U N and each l 2 M , pdl (u; q) pmin(u)d minfjM j ; jN jg.
lCorollary 3 implies there is no increment across all the classical utility pro…lessuch that the AA auction neither substantially overshoots nor undershoots the
MPE price. In other words, Fact 6(ii) does not hold on the classical domain.
Finally, we study the incentive of AA auction.
Example 8: Consider the economy in Example 7 with an replacement of agent 3’s
utility function. Let u03 2 U QL be such that v30 (a) = 1:5d and v30 (b) = 2d. Rounds29

0 and 1 are the same in Example 7. Recall that the market price generated inround 1 is p1 = (0; 0; d) where agent 2 is tentatively assigned b and 1 stands behind
3 in the queue of uncommitted agents. The auction then proceeds to round 2 andagent 3 is called. If agent 3 bids b, the price of b that she faces is updated, i.e.,
pb2b = p1b + d = 2d whereas the price of a that she faces remains unchanged, i.e.,
pb2a = p1a = 0. Since v30 (a) pb2a = 1:5d > v30 (b) pb2b = v30 (0) = 0, agent 3 only
demands a at pb2 = (0; 0; 2d), i.e., D3 (bp2 ) = fag so she bids a and is tentatively
assigned (a; 0). The market price generated in round 2 is p2 = (0; 0; d). The
auction proceeds to round 3 and agent 1 is called. If agent 1 bids b, the price ofb that she faces is also updated, i.e., pb3b = p2b + d = 2d and if she bids a, the priceof a that she faces is updated either, i.e., pb3a = p2a + d = d. Since agent 1 only
demands b at pb3 = (0; d; 2d), i.e., D1 (bp3 ) = fbg, agent 1 bids b and is tentatively
assigned (b; 2d). Then, agent 2 is driven to the queue.
In the later round of the auction, agents 1 and 2 will compete for b. The market
price generated by round t + 1 is (0; 0; td) where agent 2 is tentatively assigned(b; td), agent 3 is tentatively assigned (a; 0), and agent 1 is in the queue. The
auction proceeds to round t + 2 and agent 1 is called. If agent 1 bids b, the priceof b that she faces is updated as well, i.e., pbt+2= pt+1+ d = (t + 1)d and if she bidsbba, the price of a that she faces is updated as well, i.e., pbt+2= pt+1+ d = d. Sinceaat+2
agent 1 only demands the null object at pb = (0; d; (t+1)d), i.e., D1 (bpt+2 ) = f0g,
she drops out. The auction terminates at price (0; 0; td) where agent 1 drops out,
agent 2 gets (b; t), and agent 3 gets (a; 0).
Recall that in Example 7, agent 3 obtains (0; 0) for (u1 ; u2 ; u3 ). Since r > 0,
and u3 (a; 0) > u3 (0; r) > u3 (0; 0), when agent 3’s true utility function is u3 , she
has the incentive to misreport u03 .
4
The insight of Example 8 can be extended to show the following result.
Proposition 8: For each d > 0, the AA mechanism with increment d and withan arbitrary bidding queue q is absolutely manipulable on U N .
Proposition 8 demonstrates that k d strategy-proofness of Fact 7 does nothold on the classical domain. However, even if the AA auction may substantially
undershoot or overshoot on the classical domain, it can still …nd an approximate
equilibrium, i.e., d equilibrium.25 In other words, the AA mechanism still could
achieve some degree of approximate e¢ ciency. One may consider this point to bea merit of the AA auction in comparison to the EA auction.
In both Propositions 7 and 8, the increment is given regardless of utility pro…lesand the properties of AA auction and mechanisms are derived when agents have25

The statement is implied by Step 1 in the proof of Proposition 9.

30

the ‡exibility to alter heir utility functions. In the following, we show that in caseof a …xed classical utility pro…le, if the increment is su¢ ciently small, the outcome
price of an AA auction will be su¢ ciently close to the MPE price.
Proposition 9: Let u 2 U N be 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 and with an arbitrary bidding queue. Then,
limn!1 pdn = pmin (u).
The proof of Proposition 9 is relegated to Appendix A. Proposition 9 implies
that when a utility pro…le is …xed, the AA auction works well in approximating
the MPE mechanism for a su¢ ciently small increment. Even when agents haveclassical utility functions, the AA auction is still a good candidate to obtain the
MPE if we carefully choose the increment, so practitioners should limit themselvesto auctions of this form and its variant such as the cumulative o¤er procedure
mentioned in the introduction.

7

Conclusion

In this paper, we study multi-object auction models with unitary demand agents
whose utility functions may not be quasi-linear. We contend that the exact ascending auction of Demange et al. (1986), the sealed-bid Vickrey auction, and theapproximate ascending auction of Demange et al. (1986) …nding the minimum
price equilibrium in the quasi-linear settings, cannot identify or even approximate
the MPEs and fail to be e¢ cient and incentive-compatible. Our results allude
to the challenges of e¢ cient and incentive-compatible auction design when agents
have utility functions without assuming quasi-linearity, and inspire developmentof novel analytical techniques in the future research.
Appendix A: Proof of Proposition 9
Let (xdn ; pdn ) be the outcome generated by the AA auction with increment dn
and with an arbitrarily given bidding queue. The proof comprises …ve steps.
Step 1: For each dn > 0, (xdn ; pdn ) is a dn equilibrium.
Consider an agent i who drops out. Agent i bids 0 when she faces a price lower
than or equal to (0; (pdl n + dn )l2M ). Thus, 0 2 Didn (pdn ). Consider an agent i who
obtains xdi n 2 M . She bids on xdi n when the price of xdi n that she faces is pdxndn andithe price of any other object l 2 M that she faces is less than or equal to 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
getting assigned till the end. Thus, De…nition 5(ii) holds.
31

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 2 N+ , 0 pdl n maxi2N Vi (l) + 2dn . Thus, fpdn g
00contains a convergent subsequence fpdn g. Since agents and objects are both …nite,
000
fpdn g contains a subsequence fpdn g whose assignments remain the same.
0
0
Step 3: (x; p) limn!1 (xdn ; pdn ) is an equilibrium.
0
By Step 2, for each n 2 N+ , x = xdn . By De…nition 5(ii), De…nition 3(ii)holds. Thus, we show De…nition 3(i). For each n 2 N+ and each i 2 N , by
Step 2, xi 2 Didn (pdn ) and moreover xi 2 Didn (pdn ) implies that for each y 2 M ,ui (xi ; pxdni )ui (y; pdyn + dn ) and ui (xi ; pdxni )ui (0; 0). Thus, for each y 2 M ,d0n
ui (0; 0) and ui (xi ; pxi )ui (y; py ). Thus
limn!1 p = p implies ui (xi ; pxi )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 Fact 1, there is aweakly underdemanded set M 0
M at p, that is, for each l 2 M 0 , pl > 0
and jfi 2 N : Di (p) \ M 0 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

and since limn!1 d0n = 0 and limn!1 pdn = p, for some d00n 2 fd0n g,
00
00
d00
(b) pxni
pxi + dn and dn
, and
d00
n
(c) plpl> 0 for each l 2 M 0 .
Thus for each i 2 N nN 0 and each l 2 M 0 ,0000

ui (xi ; pdxni )(b)ui (xi ; pxi + dn )(b)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
00
d00
d00
pl n dn . 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 price of auction with increment d00n .
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. Hence, we prove that any convergent subsequence
000
in fpdn g has the same limit. Let fpdn g and fpdn g be two convergent subsequences
32

00

0

in fpdn g such that limn!1 pdn = p0 and limn!1 pdn = p00 . In the following, weshow p0 = p00 . Then Step 5 holds, as desired.
0
Analogous to Step 2, there is a subsequence of fpdn g converging to p0 whose
assignments remain unchanged, say x0 . By Step 3, (x0 ; p0 ) is an equilibrium and00
moreover, by Step 4, p0 = pmin . Similarly, there is a subsequence of fpdn g converging to p00 whose assignments remains unchanged, say x00 . By Step 3, (x00 ; p00 ) is anequilibrium and moreover, by Step 4, p00 = pmin . Since the MPE price is unique,p0 = p00 .

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] Baisa, B.H, 2020. E¢ cient multiunit auctions for normal goods. Theoretical
Economics 15(1), 361-413.
[4] Crawford, V.P., Knoer, E.M., 1981. Job matching with heterogeneous …rms
and workers. Econometrica 49(2), 437-450.
[5] Cassady, R., 1967. Auctions and auctioneering. University of California Press.
[6] Clarke, E.H., 1971. Multipart pricing of public goods. Public Choice 11, 17-33.
[7] Demange, G., Gale, D., 1985. The strategy structure of two-sided matchingmarkets. Econometrica 53(4), 873-888.
[8] Demange, G., Gale, D., Sotomayor, M., 1986. Multi-item auctions. Journalof Political Economy 94(4), 863-872.
[9] Echenique, F., 2012. Contracts versus salaries in matching. American Economic Review 102(1), 594-601.
[10] Fleiner, T., Jagadeesan, R., Janko, Z., Teytelboym, A., 2019. Trading networks with frictions. Econometrica 87(5), 1633-1661.
[11] Groves, T., 1973. Incentives in teams. Econometrica 41(4), 617-631.
[12] Gul, F., Stacchetti, E., 2000. The English auction with di¤erentiated commodities. Journal of Economic Theory 92(1), 66-95.
33

[13] Hat…eld, J.W., Milgrom, P.R., 2005. Matching with contracts. American Economic Review 95(4), 913-935.
[14] Hat…eld, J.W., Kominers, S.D., Westkamp, A., 2021. Stability, strategyproofness, and cumulative o¤er mechanisms. The Review of Economic Studies
88(3), 1457-1502.
[15] Hildenbrand, W., Schmeidler, D., Zamir, S., 1973. Existence of approximate
equilibria and cores. Econometrica 41(6), 1159-1166.
[16] Holmstrom, B., 1979. Groves’ scheme on restricted domains. Econometrica
47(5), 1137-1144.
[17] 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.
[18] Kelso Jr, A. S., Crawford, V. P., 1982. Job matching, coalition formation,and gross substitutes. Econometrica 50(6), 1483-1504.
[19] Klemperer, P., 2004. Auctions: theory and practice. Princeton University
Press.
[20] Leonard, H.B., 1983. Elicitation of honest preferences for the assignment of
individuals to positions. Journal of Political Economy 91(3), 461-479.
[21] Malik, K., Mishra, D., 2021. Pareto e¢ cient combinatorial auctions: Dichotomous preferences without quasilinearity. Journal of Economic Theory
191, 105-128.
[22] Milgrom, P., 2004. Putting auction theory to work. Cambridge University
Press.
[23] Mishra, D., Parkes, D.C., 2009. Multi-item Vickrey–Dutch auctions. Gamesand Economic Behavior 66, 326-347.
[24] Mishra, D., Talman, D., 2010. Characterization of the Walrasian equilibria of
the assignment model. Journal of Mathematical Economics 46(1), 6-20.
[25] 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.

34

[26] Roberts, D.J., Postlewaite, A., 1976. The Incentives for Price-Taking Behavior in Large Exchange Economies. Econometrica 44 (1), 115-127.
[27] Saitoh, H., Serizawa, S., 2008. Vickrey allocation rule with income e¤ect.
Economic Theory 35(2), 391–401.
[28] Schlegel, J.C., 2022. The structure of equilibria in trading networks withfrictions. Theoretical Economics 17(2), 801-839.
[29] Roughgarden, T., 2014. Lecture 3 in Frontiers in Mechanism Design.
[30] Sun, N., Yang, Z., 2009. A double-track adjustment process for discrete markets with substitutes and complements. Econometrica 77(3), 933-952.
[31] Varian, H.R., Harris, C., 2014. The VCG auction in theory and practice.
American Economic Review 104(5), 442-45.
[32] Vickrey, W., 1961. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance 16(1), 8–37.
[33] 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.

35