ISSN (Print) 0473-453X

Discussion Paper No. 1001

ISSN (Online) 2435-0982

STRATEGY-PROOF
MULTI-OBJECT MECHANISM DESIGN:
EX-POST REVENUE MAXIMIZATIONWITH NON-QUASILINEAR PREFERENCES

Tomoya Kazumura
Debasis Mishra
Shigehiro Serizawa

Revised January 2020
May 2017

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

Strategy-proof multi-object mechanism design: Ex-post
revenue maximization with non-quasilinear preferences∗

Tomoya Kazumura, Debasis Mishra, and Shigehiro Serizawa †January 7, 2020
Abstract
A seller is selling multiple objects to a set of agents, who can buy at most one object. Each agent’s preference over (object, payment) pairs need not be quasilinear. The
seller considers the following desiderata for her mechanism, which she terms desirable:(1) strategy-proofness, (2) ex-post individual rationality, (3) equal treatment of equals,(4) no wastage (every object is allocated to some agent). The minimum Walrasianequilibrium price (MWEP) mechanism is desirable. We show that at each preference
profile, the MWEP mechanism generates more revenue for the seller than any desirable mechanism satisfying no subsidy. Our result works for the quasilinear domain,
where the MWEP mechanism is the VCG mechanism, and for various non-quasilinear
domains, some of which incorporate positive income effect of agents. We can relax no
subsidy to no bankruptcy in our result for certain domains with positive income effect.
Keywords. multi-object allocation; strategy-proofness; ex-post revenue maximization; minimum Walrasian equilibrium price mechanism; non-quasilinear preferences;
no wastage; equal treatment of equals.
JEL Code. D82, D47, D71, D63.
∗

We have benefited from insightful comments of three referees and an associate editor. We are also

grateful to Brian Baisa, Elizabeth Baldwin, Inés Moreno de Barreda, Dirk Bergemann, Yeon-koo Che,
Vincent Crawford, Bhaskar Dutta, Albin Erlanson, Johannes Horner, Paul Klemperer, Hideo Konishi, Nicolas
S. Lambert, Andrew Mackenzie, Komal Malik, Paul Milgrom, Noam Nisan, Andrew Postlewaite, Larry
Samuelson, James Schummer, Ilya Segal, Alex Teytelboym, Ryan Tierney, Rakesh Vohra, Jörgen Weibull,and various seminar participants for their comments. We gratefully acknowledge financial support from the
Joint Usage/Research Center at ISER, Osaka University and the Japan Society for the Promotion of Science(Kazumura, 14J05972; Serizawa, 15J01287, 15H03328, 15H05728).
†
Kazumura: Tokyo Institute of Technology, pge003kt@gmail.com; Mishra: Indian Statistical Institute, Delhi, dmishra@isid.ac.in; Serizawa: Institute of Social and Economic Research, Osaka University,
serizawa@iser.osaka-u.ac.jp1

1

Introduction

One of the most challenging problems in microeconomic theory is the design of a revenue
maximizing mechanism in the multi-object allocation problems. Ever since the seminal workof Myerson (1981) for solving the revenue maximizing mechanism in the single object environment, advances in the mechanism design literature have convinced researchers that it isdifficult to precisely describe a revenue maximizing mechanism in multi-object environments.
In the literature on revenue maximizing mechanism design, authors conventionally impose only incentive compatibility and individual rationality conditions, and try to find amechanism that maximizes the (expected) revenue among mechanisms satisfying those conventional conditions. When allocating public assets, governments are supposed to pursue
several goals, such as fairness and efficiency, besides revenue maximization.1 Since our main
focus is on revenue maximization, we impose only moderate desiderata for other goals on
mechanisms. In other words, we define several conditions embodying other goals, and maximize revenue in the class of mechanisms satisfying those new conditions along with theconventional incentive and participation constraints.
We study the problem of allocating m indivisible heterogenous objects to n > m agents,
each of whom can be assigned at most one object (unit demand agents) – such unit demandsettings are common in allocating houses in public housing schemes (Andersson and Svensson,2014), selling team franchises in professional sports leagues, and even in selling a small
number of spectrum licenses (Binmore and Klemperer, 2002).23 Agents in our model canhave non-quasilinear preferences over consumption bundles - (object, payment) pairs.
We briefly describe the additional axioms that we impose for our revenue maximization
exercise. Equal treatment of equals is a desideratum for fairness, and requires that two agents
1
2

For example, Klemperer (2002) discusses the list of goals pursued in UK 3G auction conducted in 2000.
When a professional cricket league, called the Indian Premier League (IPL) was started in India in 2007,

professional teams were sold to interested owners (bidders) by an auction. Since it does not make sense foran owner to have two teams, the unit demand assumption is satisfied in this problem. See the Wiki entry of
IPL for details:
https://en.wikipedia.org/wiki/Indian_Premier_League and a news article here: http://contentusa.cricinfo.com/ipl/content/current/story/333193.html
3
Although modern spectrum auctions involve sale of of bundles of spectrum licenses, Binmore and Klemperer (2002) report that one of the biggest spectrum auctions in the UK involved selling a fixed number oflicenses to bidders, each of whom can be assigned at most one license. The unit demand setting is also one of
the few computationally tractable model of combinatorial auction studied in the literature (Blumrosen and
Nisan, 2007).

2

having identical preferences be assigned consumption bundles (i.e., (object, payment) pairs)
to which they are indifferent. No wastage is a desideratum for a mild form of efficiency, andrequires that every object be allocated to some agent. We term a mechanism desirable if itsatisfies strategy-proofness, ex-post individual rationality, equal treatment of equals, and no
wastage.
The mechanism we identify in this paper is based on a market clearing idea. A pricevector on objects is called a Walrasian equilibrium price (WEP) vector if there is an allocation of objects such that each agent gets an object from his demand set. Demange andGale (1985) showed that the set of WEP vectors is always a non-empty compact latticein our model. This means that there is a unique minimum WEP vector.4 The minimum
Walrasian equilibrium price (MWEP) mechanism selects the minimum WEP vector at every
profile of preferences and uses a corresponding equilibrium allocation. The MWEP mechanism is desirable (Demange and Gale, 1985) and satisfies no subsidy. No subsidy requiresthat payment of each agent be non-negative. In the quasilinear domain of preferences, the
MWEP mechanism coincides with the Vickrey-Clarke-Groves (VCG) mechanism (Leonard,1983). However, we emphasize that outside the quasilinear domain, a naive generalizationof the VCG mechanism to non-quasilinear preferences is not strategy-proof (Morimoto andSerizawa, 2015).5 This also means that for an arbitrary domain of classical preferences, the
MWEP mechanism is very different from a generalization of the VCG mechanism.
We show that on a variety of domains (the set of admissible preferences), the MWEP
mechanism is ex-post revenue optimal among all desirable mechanisms satisfying no subsidy,i.e., for each preference profile, the MWEP mechanism generates more revenue for the seller
than any desirable mechanism satisfying no subsidy (Theorem 1). Further, we show that if
the domain includes all positive income effect preferences, then the MWEP mechanism is
ex-post revenue optimal in the class of all desirable and no bankruptcy mechanisms (Theorem2). No bankruptcy is a weaker condition than no subsidy and requires the sum of paymentsof all agents across all profiles be bounded below.
Our results are robust in the following sense. First, the MWEP mechanism maximizes
ex-post revenue. Hence, we can recommend the MWEP mechanism without resorting toany prior-based maximization. Notice that ex-post revenue optimality is much stronger than
expected (ex-ante) revenue optimality, and mechanisms satisfying ex-post revenue optimality
4

Results of this kind were earlier known for quasilinear preferences (Shapley and Shubik, 1971; Leonard,1983).
5
See Section 6.2 in Morimoto and Serizawa (2015).

3

rarely exist. Second, our results hold on a variety of domains. This is in contrast to many
papers in the literature on mechanism design in which results are established only on quasilinear domain. Our main result (Theorem 1) holds on every domain satisfying a richness
condition. The richness condition requires the domain to include enough variety preferences.
However it is weak enough to be satisfied by various well known domains, such as the quasilinear domain, the classical domain, the domain of positive income effect preferences, andany domain including one of those domains.
Ours is the first paper to study revenue maximization in a multi-object allocation problem
when preferences of agents are not quasilinear. While quasilinearity is standard and popularin the literature, its practical relevance is debatable in many settings. There are at least two
obvious reasons why quasilinearity may fail in practice. First, bidders in auctions usuallyinvest in various supporting products and processes to realize the full value of the object. For
instance, cellular companies invest in communication infrastructure development, a sports
team owner invests in marketing, and so on. Such ex-post investments cannot be assumed
to be independent of the payments in auctions. This hints at an explicit effect of paymentsin the auction mechanism on the values of objects in these problems. Another source of nonquasilinearity is borrowing costs. Usually, bidders in large auctions (like spectrum auctions,
housing auctions, etc.) borrow to pay for objects. The higher interest rates imposed on thelarger amount of borrowings make preferences non-quasilinear.6
Finding optimal mechanism (expected revenue maximizing mechanism subject to Bayesian
incentive compatibility and individual rationality) in multi-object auction environment is adifficult problem – see Section 8 for an extensive literature review. The main difficulty is thatthe traditional Myersonian approach works by figuring out the binding incentive constraints,
which is difficult to characterize in multi-object auction models. This is a long recognizedproblem (Armstrong, 2000). The literature is developing new toolkits to solve these problems – see Carroll (2016), who imposes an additional informational robustness condition to
figure out the binding incentive constraints; and Daskalakis et al. (2017), who use optimaltransportation theory to find the optimal mechanism in a single agent problem. While wecertainly do not introduce any new method to solve the multidimensional mechanism design
problems, our results show that one can circumvent some of the difficulties in these problems
by imposing additional axioms.
We briefly discuss the practical relevance of two of our axioms: equal treatment of equals
and no wastage. Later, we elaborate the kind of mechanisms we rule out by imposing these6

We will discuss the effect of borrowing cost on preferences in Subsection 4.1.

4axioms. Equal treatment of equals is arguably the weakest fairness axiom in the literature –as Aristotle (1995) writes, justice is considered to mean “equality for those who are equal, andnot for all”.7 Sometimes, there are practical implications of violating fairness – for instance,
Deb and Pai (2016) cite many legal implications of violating symmetry in mechanisms, which
is a stronger property than equal treatment of equals.
Efficiency is an important goal for governments. Although Pareto efficiency is a standard
efficiency desideratum in the literature, since we focus on revenue maximization, we impose
no wastage, a much weaker desideratum. Unlike Pareto efficiency, no wastage is an easily
detectable axiom (detecting violation of Pareto efficiency requires the knowledge of preferences). Violation of no wastage in government auctions creates a lot of controversies in the
public, and often, the unsold objects are resold.8 In such environments, governments cannot
commit to reserve prices even though expected revenue maximization may require them.
Indeed, McAfee and McMillan (1987); Ashenfelter and Graddy (2003); Jehiel and Lamy(2015); Hu et al. (2017) report that many real-life auctions have zero reserve price – McAfee
and McMillan (1996), Jehiel and Lamy (2015) and Hu et al. (2017) build theoretical models
to explain it as an equilibrium phenomenon. While our results do not provide a theory for
why the seller should not keep a reserve price, we show that if the seller uses a mechanism
satisfying no wastage and other desirable properties, then the MWEP mechanism is ex-post
revenue optimal.
Finally, the MWEP mechanism is Pareto efficient and can be implemented as a simultaneous ascending auction (SAA) - for quasilinear domains, see Demange et al. (1986), and for
non-quasilinear domains, see Morimoto and Serizawa (2015).9 SAAs have distinct advantagesof practical implementation and are often used in practice to allocate multiple objects. The
efficiency foundations for SAAs have been well-established. Because of their practical importance, it is worth providing alternate foundations for SAAs. Our results provide a revenue
maximization foundation for SAAs. This differentiates our results from previous research on
7

The quote is from Aristotle’s Book III titled “The Theory of Citizenship and Constitutions”. It can befound in Part C of the book, titled “The Principle of Oligarchy and Democracy and the Nature of Distributive
Justice”, in Chapter 9 and paragraph 1280a7.
8
As an example, the Indian spectrum auctions reported a large number of unsold spectrum
blocks in 2016, and all of them are supposed to be re-auctioned.
See the following news article: http://www.livemint.com/Industry/xt5r4Zs5RmzjdwuLUdwJMI/Spectrum-auction-ends-afterlukewarm-response-from-telcos.html
9
To be precise, the MWEP mechanism can be implemented as a simple ascending price auction with asufficiently small price increment.

5the MWEP mechanism and SAA, most of which focus on efficiency properties (Ausubel and
Milgrom, 2002).

2

Preliminaries

A seller has m objects to sell, denoted by M := {1, . . . , m}. There are n > m agents(buyers), denoted by N := {1, . . . , n}. Each agent can receive at most one object (unitdemand preference). Let L := M ∪ {0}, where 0 is the null object, which is assigned toany agent who does not receive any object in M – thus, the null object can be assigned tomore than one agent. Note that the unit demand restriction can either be a restriction on
preferences or an institutional constraint. For instance, objects may be substitutable whenhouses are being allocated in a public housing scheme (Andersson and Svensson, 2014). The
unit demand restriction can also be institutional as was the case in the spectrum license
auction in UK in 2000 (Binmore and Klemperer, 2002) or in the Indian Premier League
auction. As long as the mechanism designer restricts messages in the mechanisms to only
use information on preferences over individual objects, our results apply.
The consumption set of every agent is the set L × R, where a typical (consumption)
bundle z ≡ (a, t) corresponds to object a ∈ L and payment t ∈ R. Notice that t denotes theamount paid by an agent to the designer. Now, we formally introduce preferences of agentsand the notion of a desirable mechanism.

2.1 The preferences
A preference ordering Ri (of agent i) over L × R, with strict part Pi and indifference part Ii ,is classical if it satisfies the following assumptions:
1. Money monotonicity. for every t, t0 ∈ R with t > t0 and for every a ∈ L, we have(a, t0 ) Pi (a, t).
2. Desirability of objects. for every t ∈ R and for every a ∈ M , (a, t) Pi (0, t).
3. Continuity. for every z ∈ L × R, the sets {z 0 ∈ L × R : z 0 Ri z} and {z 0 ∈ L × R :z Ri z 0 } are closed.
4. Possibility of compensation. for every z ∈ L × R and for every a ∈ L, there exists
a pair t, t0 ∈ R such that z Ri (a, t) and (a, t0 ) Ri z.
6

A classical preference Ri is quasilinear if there exists v ∈ R|L| such that for every a, b ∈ L
and t, t0 ∈ R, (a, t) Ri (b, t0 ) if and only if va − t ≥ vb − t0 . We refer to v as the valuation of
the agent, and we normalize v0 to 0. The idea of valuation may be generalized as follows for
non-quasilinear preferences.
Definition 1 The valuation at a classical preference Ri for object a ∈ L with respect tobundle z ∈ L × R is defined as V Ri (a, z), which uniquely solves (a, V Ri (a, z)) Ii z.
Hence, V Ri (a, z) is the amount t agent i is willing to pay so that he is indifferent between(a, t) and z. A straightforward consequence of our assumptions is that for every a ∈ L, forevery z ∈ L × R, and for every classical preference Ri , the valuation V Ri (a, z) exists. For
any R and for any z ∈ L × R, the valuations at R with respect to z is a vector in R|L| .
An illustration of the valuation is shown in Figure 1. In the figure, the horizontalcBetter bundlesbz ≡ (b; t)

V Ri (c; z)

Worse bundles
V Ri (a; z)a00transfer

V Ri (0; z)
Figure 1: Valuation at a preferencelines correspond to objects: L = {0, a, b, c}. The horizontal lines indicate payment levels. Hence, the consumption set consists of the four lines. For example, z denotes thebundle consisting of object b and the payment equal to the distance of z from the verticaldotted line. A preference Ri can be described by drawing (non-intersecting) indifference
vectors through these consumption bundles (lines). One such indifference vector passing
through z is shown in Figure 1. This indifference vector actually consists of four points:(0, V Ri (0, z)), (a, V Ri (a, z)), z ≡ (b, t), and (c, V Ri (c, z)) as shown. Parts of the indifference7

line in Figure 1 which lie between the consumption bundle lines is useless and has no meaning, and it is only displayed for convenience. As we go to the right along the horizontal lines
starting from any bundle, we get worse bundles (due to money monotonicity). Similarly,
bundles to the left of a particular bundle are better than that bundle. This is shown in
Figure 1 with respect to the indifference vector.
Our modeling of preferences captures income effects even though we do not model income
explicitly. We explain this point when we introduce positive income effect in Section 4.1.

2.2 Desirable mechanisms
Let RC denote the set of all classical preferences and RQ denote the set of all quasilinear
preferences. We will consider an arbitrary subset of classical preferences R ⊆ RC - wewill put specific restrictions on R later. A preference of agent i is denoted by Ri ∈ R. A
preference profile is a list of preferences R ≡ (R1 , . . . , Rn ). Given i ∈ N and N 0 ⊆ N , let
R−i ≡ (Rj )j6=i and R−N 0 ≡ (Rj )j∈N 0 , respectively.
An object allocation is an n-tuple (a1 , . . . , an ) ∈ Ln such that no real (non-null) object
is assigned to two agents, i.e., ai 6= aj for all i, j ∈ N with ai , aj 6= 0. The set of all object
allocations is denoted by A. A (feasible) allocation is an n-tuple ((a1 , t1 ), . . . , (an , tn )) ∈(L × R)n such that (a1 , . . . , an ) ∈ A, where (ai , ti ) is the bundle of agent i. Let Z denote theset of all feasible allocations. For every allocation (z1 , . . . , zn ) ∈ Z, we will denote by zi thebundle of agent i.
An mechanism is a map f : Rn → Z. By definition, we restrict ourseleves to deterministic mechanisms. Allowing for randomization will entail considering preferences overlotteries of allocations. This brings substantial difficulty in modeling and analysis. We do
not know how our results will extend if we allow for randomization.
At a preference profile R ∈ Rn , we denote the bundle of agent i in mechanism f as fi (R) ≡(ai (R), ti (R)), where ai (R) and ti (R) are respectively the object allocated to agent i and i’s
payment at preference profile R. We call a(·) ≡ (a1 (·), . . . , an (·)) and t(·) ≡ (t1 (·), . . . , tn (·))
the object allocation mechanism and the payment mechanism, respectively of f .
Definition 2 A mechanism f : Rn → Z is desirable if it satisfies the following properties:
1. Strategy-proofness. for every i ∈ N , for every R−i ∈ Rn−1 , and for every Ri , Ri0 ∈R, we havefi (Ri , R−i ) Ri fi (Ri0 , R−i ).
82. (Ex-post) individual rationality (IR). for every i ∈ N , for every R ∈ Rn , we havefi (R) Ri (0, 0).
3. Equal treatment of equals (ETE). for every i, j ∈ N , for every R ∈ Rn with
Ri = Rj , we have fi (R) Ii fj (R).
4. No wastage (NW). for every R ∈ Rn and for every a ∈ M , there exists some i ∈ Nsuch that ai (R) = a.
Besides desirability, for some of our results, we will require some form of restrictions on
payments.
Definition 3 A mechanism f : Rn → Z satisfies no subsidy if for every R ∈ Rn and forevery i ∈ N , we have ti (R) ≥ 0.
No subsidy can be considered desirable to exclude “fake” agents, who participate in mechanisms just to take away available subsidy. It is an axiom satisfied by most standard mechanisms in practice. It is also motivated by the fact that in many settings, the seller may nothave any means to finance any agent.

3

The minimum Walrasian equilibrium pricemechanism

In this section, we define the notion of a Walrasian equilibrium, and use it to define a desirable|L|mechanism. A price vector p ∈ R+ defines a price for every object with p0 = 0. At any|L|price vector p ∈ R+ , let D(Ri , p) := {a ∈ L : (a, pa ) Ri (b, pb ) ∀ b ∈ L} denote the demand
set of agent i with preference Ri at price vector p.
|L|

Definition 4 An object allocation (a1 , . . . , an ) ∈ A and a price vector p ∈ R+ is a Walrasian equilibrium at a preference profile R ∈ Rn if
1. ai ∈ D(Ri , p) for all i ∈ N and2. pa = 0 for all a ∈ M \ {a1 , . . . , an }.
We refer to p and ((a1 , pa1 ), . . . , (an , pan )) defined above as a Walrasian equilibrium
price vector and a Walrasian equilibrium allocation at R respectively.
9

Since we assume n > m and preferences satisfy desirability of objects, the conditions ofWalrasian equilibrium imply that for all a ∈ M , we have ai = a for some i ∈ N .10
A Walrasian equilibrium price vector p is a minimum Walrasian equilibrium pricevector at preference profile R if for every Walrasian equilibrium price vector p0 at R, we havepa ≤ p0a for all a ∈ L. At every R ∈ (RC )n , a Walrasian equilibrium exists (Alkan and Gale,
1990), the set of Walrasian equilibrium price vectors forms a lattice with a unique minimum
and a unique maximum Walrasian equilibrium price vector (Demange and Gale, 1985). We
denote the minimum Walrasian equilibrium price vector at R ∈ (RC )n as pmin (R). Notice11that by desirability of objects, if n > m, then for every a ∈ M , we have pmina (R) > 0.

We give an example to illustrate the notion of minimum Walrasian equilibrium pricevector. Suppose N = {1, 2, 3} and M = {a, b}. Figure 2 shows some indifference vectors of apreference profile R ≡ (R1 , R2 , R3 ) and the corresponding minimum Walrasian equilibriumminprice vector pmin (R) ≡ pmin ≡ (pmin= 0, pmin).
0a , pb

pmin
b

b
R1

R3

R2
pmin
a

a
0

transfer

0

Figure 2: The minimum Walrasian equilibrium price vector
First, note that
D(R1 , pmin ) = {a}, D(R2 , pmin ) = {a, b}, D(R3 , pmin ) = {0, b}.
10

To see this, suppose that there is a ∈ M such that ai 6= a for each i ∈ N . Then, by the second

condition of Walrasian equilibrium, pa = 0. By n > m, ai = 0 for some i ∈ N . By desirability of objects,(a, 0) Pi (ai , 0), contradicting the first condition of Walrasian equilibrium.
11
To see this, suppose pmin(R) = 0 for some a ∈ M . Then any agent i ∈ N who is not assigned in theaWalrasian equilibrium will prefer (a, 0) to (0, 0) contradicting the fact that he is assigned a bundle from his
demand set. Indeed, this argument holds for any Walrasian equilibrium price vector.

10Hence, a Walrasian equilibrium is the allocation where agent 1 gets object a, agent 2 gets
object b, and agent 3 gets the null object at the price vector pmin . Also, pmin is the minimum
Walrasian equilibrium price vector. To see this, let p be any other Walrasian equilibrium pricevector. If pa < pmin
and pb < pmin
, then no agent demands the null object, contradictingab
Walrasian equilibrium. Thus, pa ≥ pmin
or pb ≥ pmin
. If pb < pmin
, then by pa ≥ pmin
a
a ,
b
b
both agents 2 and 3 will demand only object b, contradicting Walrasian equilibrium. Thus,. But, if pa < pmin
pb ≥ pmin
a , both agents 1 and 2 will demand only object a, a contradictionb
to Walrasian equilibrium. Hence, p ≥ pmin .
We now describe a desirable mechanism satisfying no subsidy. The mechanism picks
a minimum Walrasian equilibrium allocation at every profile of preferences. Although theminimum Walrasian equilibrium price vector is unique at every preference profile, there may
be multiple supporting object allocations – all these object allocations must be indifferent to
all the agents. To handle this multiplicity problem, we introduce some notation. Let Z min (R)denote the set of all allocations at a minimum Walrasian equilibrium at preference profile R.
Note that if n > m and ((a1 , pa1 ), . . . , (an , pan )) ∈ Z min (R) then p ≡ (pa )a∈L = pmin (R).
Definition 5 A mechanism f min : Rn → Z is a minimum Walrasian equilibrium
price (MWEP) mechanism if f min (R) ∈ Z min (R) ∀ R ∈ Rn .
As discussed earlier, at any preference profile R, Z min (R) may contain multiple allocations
but each agent is indifferent between its allocations in this set. Hence, we refer to f min as the
MWEP mechanism, even though there can be more than one MWEP mechanism (dependingon which allocation in Z min (R) is picked at every R).
Demange and Gale (1985) showed that the MWEP mechanism is strategy-proof. Clearly,
it also satisfies IR, ETE, NW, and no subsidy. We document this fact below.
Fact 1 The MWEP mechanism is desirable and satisfies no subsidy.
In fact, Demange and Gale (1985) show that the MWEP mechanism satisfies a stronger
incentive property called (weak) group-strategy-proofness, which means that for each R ∈ Rn ,
0

0
|N |
there are no coalition N 0 ⊆ N , of agents and RN
such that for each i ∈ N 0 ,0 ∈ R0fi (RN
0 , R−N 0 ) Pi fi (R). Further, the MWEP mechanism satisfies stronger fairness properties- it is anonymous (permuting preferences of agents does not change the outcome) and envyfree.
It is worth comparing the MWEP mechanism with the VCG mechanism for quasilinear
preferences. Indeed, there is a naive way to generalize the VCG mechanism to any classical11preference domain. Consider a preference profile R. For every agent i ∈ N with preference
Ri , let via := V Ri (a, (0, 0)) for all a ∈ M . Let vi0 = 0 for all i ∈ N . Now, we compute theallocation and payments according to the VCG mechanism with respect to this profile ofvectors (v1 , . . . , vn ). Such a generalized VCG mechanism coincides with the MWEP mechanism if the domain is the quasilinear domain (Leonard, 1983). Else, the generalized VCG
mechanism is very different from the MWEP mechanism. Further, it is not strategy-proof if
the domain is not the quasilinear domain (Morimoto and Serizawa, 2015).

4

The results

In this section, we formally state our two results. The proofs of both the results are in
Section 7. Before we state the results, we explain the domain richness they use.

4.1 Rich domains|L|

For each pair of price vectors p, p̂ ∈ R+ , we write p > p̂ if pa > p̂a for all a ∈ M . The
domain of preferences that we consider for our first result requires the following richness.
Definition 6 A domain of preferences R is rich if for all a ∈ M and for every p̂ withp̂a > 0, p̂b = 0 for all b 6= a and for every p > p̂ there exists Ri ∈ R such that
D(Ri , p̂) = {a} and D(Ri , p) = {0}.
Figure 3 illustrates this notion of richness with two objects a and b - two possible pricevectors p and p̂ are shown and two indifference vectors of a preference Ri are shown suchthat D(Ri , p) = {0} and D(Ri , p̂) = {a}.
The requirement of the richness condition is weak enough to be satisfied by many domains
of interest. Obviously, if a domain of preferences is rich, then any superset of that domain isalso rich. We give below some interesting examples of rich domains. Any superset of these
domains are also rich.
• Any domain of preferences containing RQ satisfies richness. To see this, fix an objecta ∈ M and a price vector p̂ with p̂b = 0 for all b 6= a and p̂a > 0. Consider any otherprice vector p > p̂. Now, consider the quasilinear preference Ri given by the valuation
vector v such that(vb =p̂b + 2 if b = a,if b 6= a,


12

b

pb

p^b = 0
Ri

Ri
p^a

a
0

pa

transfer

0

Figure 3: Illustration of richness
where  > 0 is small enough such that va = p̂a + 2 < pa and  < pb for all b ∈ M \ {b}.
This means that D(Ri , p̂) = {a} but D(Ri , p) = {0}.
• The set of all positive income effects preferences and the set of all non-negative income
effect preferences satisfy richness.
Definition 7 A preference Ri satisfies positive income effect if for every a, b ∈ L
and for every t, t0 with t < t0 and (b, t0 ) Ii (a, t), we have(b, t0 − δ) Pi (a, t − δ)∀ δ > 0.

A preference Ri satisfies non-negative income effect if for every a, b ∈ L and forevery t, t0 with t < t0 and (b, t0 ) Ii (a, t), we have(b, t0 − δ) Ri (a, t − δ)∀ δ > 0.

Let R++ be the set of all positive income effect preferences and R+ be the set of all
non-negative income effect preferences.
A standard definition of positive income effect will say that a preferred object is more
preferred as income increases. We do not model income explicitly, but the zero payment
corresponds to the endowed income. Thus, in our model, when income increases by
δ > 0, the origin of consumption space moves to right by δ. This movement is equivalent
to sliding indifference vectors to left. In other words, if the origin is fixed, the increase13

of income by δ is expressed as the decrease of payments of all bundles by δ. In the above
definition, (b, t0 ) Ii (a, t) and t0 > t imply that object b is strictly preferred to object a
at any common payment levels t00 ∈ [t, t0 ]. Then, positive income effect requires thatwhen payments are decreased by δ, b will be preferred to a, i.e., (b, t0 − δ) Pi (a, t − δ).
Hence, our modeling of preferences captures income effects even though we do notmodel income explicitly.
Both R+ and R++ are rich domains. The fact that R+ is rich follows from the observation that RQ ⊆ R+ and RQ is rich. Even though R++ ∩ RQ = ∅, R++ is still a richdomain.
• The set of all quasi-linear preferences with non-linear borrowing cost satisfies richness.
Imagine a situation in which an agent has a quasilinear preference with valuation v,
but has to borrow money from banks at interest rate r > 0 if his payment for an object
exceeds his income I > 0. Then, given t ∈ R, his cost of payment, which we denote byc(t, I, r), is as follows.
c(t, I, r) =t

if t ≤ I,

I + (t − I)(1 + r) if t > I.
Thus, for each pair (a, t), (b, t0 ) ∈ L × R, the agent weakly prefers (a, t) to (b, t0 ) if andonly if v(a)−c(t, I, r) ≥ v(b)−c(t0 , I, r). Such preferences are obviously not quasilinear.
Let RB be the set of all such preferences. Then, RB is rich.
• The set of all single-peaked preferences satisfies richness. Imagine a condominium inwhich each floor has one room. Some agents prefer the highest floor because of goodviews, some prefer the lowest to avoid walking up stairs, and some prefer middle floors.
Then, it is natural that each agent has a single-peaked preference – an ideal floor, andas we go away from the ideal floor, we go down our preference.
Formally, there is a strict order  over L such that for each a ∈ M , a  0. A preference
Ri is single-peaked if there is a unique object τ (Ri ) such that for all t ∈ R– (τ (Ri ), t) Pi (a, t) for all a ∈ M \ {τ (Ri )} and– if τ (Ri )  a  b or b  a  τ (Ri ), then (a, t) Pi (b, t).
In other words, an agent with preference Ri has a “peak” floor, say τ (Ri ), such thatwhen the prices of all floors are the same, he prefers τ (Ri ) to other floors, and for any
14

Figure 4: Illustration of relationship between rich domains: RC , RQ , R+ , R++ .
two floors a and b, if b  a  τ (Ri ) or τ (Ri )  a  b, he preferes a to b. Let RS be
the set of all single-peaked preferences. Then, RS is rich.
We can summarize the above discussions in this claim.
Claim 1 The following domains are rich: RQ , R+ , R++ , RB , RS , RC .
We omit a formal proof for the above claim. However, the intuition for its proof is similar to|L|

the quasilinear domain proof outlined above. Given a ∈ M and two price vectors p, p̂ ∈ R+

with p̂ < p, in those domains, we can find a preference Ri that has two indifference vectors
satisfying the following: V Ri (a, (0, 0)) < pa and for each b ∈ M \ {a}, V Ri (b, (0, 0)) is close tozero and V Ri (b, (a, p̂a )) < 0. Then, for preferences satisfying these conditions, the demand
sets at p and p̂ contain only 0 and a, respectively. The relationship between some of the richdomains are shown in Figure 4.
Claim 1 shows that many plausible domains satisfy our definition of richness. Of course,richness is a condition which ensures a variety of preferences in the domain. For instance,
if we just take a domain containing two (or any finite) quasilinear preferences, it will notsatisfy richness.
A concrete domain which violates richness appears in Zhou and Serizawa (2018). They
consider a domain where objects are commonly ranked. For instance, suppose there are
two objects, M = {a, b}, and there is a common ranking of objects given by the ordering
: b  a. Further, assume that agents have quasilinear preferences over consumption
bundles. A quasilinear preference, represented by a valuation vector vi ∈ R2++ , must satisfy
vib > via > vi0 = 0. This means that the set of quasilinear preferences satisfying common
15object ranking is a smaller subset of RQ .12 Such a domain cannot satisfy richness. To see
this, consider a price vector where p̂a > 0 and p̂b = 0 (as in Definition 6). By common
object ranking, for any valuation vector vi of any agent i, we must have vib > via and thismeans that vib − p̂b > via − p̂a . This implies that agent i with this preference cannot demand
object a at price vector p̂. This means that the common object ranking domain of Zhou andSerizawa (2018) is not rich.
Another domain which violates richness is the identical objects domain. As the namesuggests, in this domain, all the objects are identical. This means that if the prices are thesame for all the objects, then the agent is indifferent between all the objects. Just as we
argued about the common object ranking domain, it is not difficult to see that the identicalobjects domain violates richness – with identical objects via = vib and the arguments do
not change in the previous paragraph. Adachi (2014) studies the domain of quasilinear
preferences when objects are identical and provides an example of a desirable mechanism
satisfying no subsidy, which is not the Vickrey auction (the MWEP mechanism in this case).

4.2 Ex-post revenue maximization of desirable mechanisms
We now formally state our first main result. For any mechanism f : Rn → Z, we define therevenue at preference profile R ∈ Rn as
Revf (R) :=X

ti (R).

i∈N

Definition 8 A mechanism f : Rn → Z revenue dominates another mechanism g :Rn → Z if
Revf (R) ≥ Revg (R)∀ R ∈ Rn .

A mechanism is ex-post revenue optimal among a class of mechanisms if it belongs tothis class of mechanisms and revenue dominates every mechanism in this class.
Since revenue domination is not a complete binary relation in a typical class of mechanisms, an ex-post revenue optimal mechanism rarely exists. Our main result shows that an
ex-post revenue optimal mechanism exists among the class of desirable mechanisms satisfying
no subsidy, and it is the MWEP mechanism.
12

As Zhou and Serizawa (2018) argue that the restriction of common object ranking is a natural one inmany settings. For instance, objects are houses located on a street with a public facility located at one endof the street or objects are condominiums located on different floors of an apartment building.

16

Theorem 1 Suppose R is a rich domain of preferences. The MWEP mechanism is theunique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no subsidy defined on Rn .
Theorem 1 clearly implies that even if we do expected revenue maximization with respect
to any prior on the preferences of agents, we will only get the MWEP mechanism among
the class of desirable and no subsidy mechanisms.
We use Claim 1 to spell out our result in specific domains.
Corollary 1 Suppose R ∈ {RQ , R+ , R++ , RB , RS , RC }. The MWEP mechanism is theunique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no subsidy defined on Rn .
In the quasilinear domain, the outcome of the MWEP mechanism coincides with the VickreyClarke-Groves (VCG) mechanism. Hence, the VCG mechanism is ex-post revenue optimal in
the quasilinear domain among the class of desirable mechanisms satisfying no subsidy. Notethat Holmstrom’s celebrated theorem (Holmstrom, 1979) does not imply this result since ituses Pareto efficiency but we do not. Similarly, Krishna and Perry (1998) show that among
the class of Pareto efficient, BIC and IIR mechanisms, the VCG mechanism maximizes
expected revenue among all Pareto efficient, BIC, and IIR mechanisms in the quasilinear
domain. This result works for multiple object auction problems even when agents can beallocated more than object. Again, this result uses Pareto efficiency but we do not.
A closer inspection of the richness reveals that if p is too small, then richness requires theexistence of a preference where the valuations (with respect to (0, 0)) for real objects is verysmall. We can weaken this richness to a weaker condition which requires that valuations lie
in an interval of the form (v min , v max ), where v min and v max are any lower and upper bounds
on the valuation of the objects such that v max > v min ≥ 0 and v max ∈ R+ ∪ {+∞}. Theorem
1 continues to hold in such domains.
We now show how Theorem 1 can be strengthened in some specific rich domains. In
particular, if the domain contains all the positive income effect preferences, then our result
can be strengthened – we can replace no subsidy in Theorem 1 by the following no bankruptcy
condition.
Definition 9 A mechanism f : Rn → Z satisfies no bankruptcy if there exists ` ≤ 0
Psuch that for every R ∈ Rn , we have i∈N ti (R) ≥ `.

17

Obviously, no bankruptcy is a weaker property than no subsidy.13 No bankruptcy is motivated by settings where the seller has limited means to finance the auction participants.
Theorem 1 can now be strengthened in the positive income effect domain.
Theorem 2 Suppose R ⊇ R++ . The MWEP mechanism is the unique ex-post revenue
optimal mechanism among the class of desirable mechanisms satisfying no bankruptcy definedon Rn .
Analogous to Corollary 1, the following is a corollary of Theorem 2.
Corollary 2 Suppose R ∈ {R+ , R++ , RC }. The MWEP mechanism is the unique ex-post
revenue optimal mechanism among the class of desirable mechanisms satisfying no bankruptcy
defined on Rn .

4.3 Pareto efficiency
Since no wastage is a minimal form of efficiency axiom, it is natural to explore the implicationsof stronger forms of efficiency. We now discuss the implications of Pareto efficiency in our
problem and relate it to our results. Before we formally define it, we must reiterate that nowastage is a much weaker but more testable axiom in practice than Pareto efficiency.
Definition 10 A mechanism f : Rn → Z is Pareto efficient if at every preference profileR ∈ Rn , there exists no allocation ((â1 , t̂1 ), . . . , (ân , t̂n )) ∈ Z such that(âi , t̂i ) Ri fi (R)∀i∈NXt̂i ≥ Revf (R),i∈Nwith either the second inequality holding strictly or some agent i strictly preferring (âi , t̂i ) tofi (R).
The above definition is the appropriate notion of Pareto efficiency in this setting. Noticethat by distributing some money among all the agents, we can always make each agent betteroff than the allocation in any mechanism. Hence, the above definition requires that there
13

In the literature, the no-deficit condition is sometimes imposed instead of no subsidy. A mechanism
P
f : Rn → Z satisfies no deficit if for each R ∈ Rn , i∈N ti (R) ≥ 0. It is clear that no bankruptcy is weaker
than no deficit.

18

should not exist another allocation where the auctioneer’s revenue is not less and every agent
is weakly better off.
The MWEP mechanism is Pareto efficient (Morimoto and Serizawa, 2015). Our results
establish that even if a seller maximizes her revenue with this weak form of efficiency, it will
be forced to use a Pareto efficient mechanism. We state this as corollaries below.
Corollary 3 Let R be rich and f : Rn → Z be ex-post revenue optimal among desirable
mechanisms satisfying no subsidy. Then, f is efficient.
Corollary 4 Let R ⊇ R++ and f : Rn → Z be ex-post revenue optimal among desirable
mechanisms satisfying no bankruptcy. Then, f is efficient.
In other words, even if the seller maximizes her revenue among the set of all desirable
mechanisms satisfying no subsidy (or no bankruptcy in the positive income effect domain),it will be forced to use a Pareto efficient mechanism. Hence, we get Pareto efficiency as acorollary without imposing it explicitly.

5

Desirable mechanisms satisfying no subsidy

An important question is whether the MWEP mechanism is the unique desirable mechanism
satisfying no subsidy in rich domains. The answer to this question will depend on thedomain of the mechanism. We can answer this question for two important rich domains. For
the non-negative income effect domain, we provide below a family of desirable mechanisms
satisfying no subsidy. In the Supplementary Appendix B.1, we include an example, due toTierney (2019), of a desirable mechanism satisfying no subsidy for the quasilinear domain.
These mechanisms are different from the MWEP mechanism. Hence, at least in these two richdomains, we can conclude that the MWEP mechanism is not the unique desirable mechanism
satisfying no subsidy and our ex-post revenue maximization requirement is necessary for
Theorem 1.
Now, we describe a family of desirable mechanisms satisfying no subsidy for the nonnegative income effect domain R+ . No mechanism in this family is the MWEP mechanism.
To describe the idea of the new mechanisms, recall that in a slot machine, a player wins money
if numbers or symbols in the slot constitute a “winning combination”. Our mechanism is avariant of the MWEP mechanism. The variation resembles a slot machine in the sense that if
for an agent i ∈ N , the preference profile of the other agents are aligned in a special way and19constitutes a “discounting combination”, then agent i can get discounts from her payment in
the MWEP mechanism. To retain the properties of the MWEP mechanism, we need to givesuch discounts carefully. The discounting combination and discounts are cleverly constructed
such that the new mechanism remains desriable and satisfies no subsidy.
Though the family of mechanisms can be defined very generally, we define it for the simple
case when M = {a, b} and N = {1, 2, 3, 4}. First, we formalize the idea of a discounting
combination in this case.
Definition 11 A discounting combination is a collection of three distinct preferences
T ≡ {Rα , Rβ , Rγ } ⊂ R+ such that there are two price vectors pT , pT ∈ R3+ with the following
properties: 0 < pTa = pTb < pTa = pTb and for each Ri ∈ {Rα , Rβ , Rγ },(a, pTa ) Ii (b, pTb ) Ii (0, 0) and (a, pTa ) Ii (b, pTb ).
Hence, a discounting combination requires three preferences such that two of its indifference vectors satisfy some condition: (1) the indifference vector through (a, pTa ) also passes
through (b, pTb ) and (0, 0); (2) the indifference vector through (a, pTa ) passes through (b, pTb ).
If a preference is quasilinear, this is impossible to achieve since these two indifference vectors are parallel and there can only be one preference which can have these two indifference
vectors. On the other hand, a discounting combination requires three unique preferences.
Hence, a discounting combination (as defined in Definition 11) cannot be defined in quasilinear domain.
We denote by T a set of discounting combinations. We say a set of discounting combinations T is disjoint if for each T, T 0 ∈ T with T 6= T 0 , T ∩ T 0 = ∅. Given a set of discounting
combinations T , a profile of preferences R ∈ (R+ )4 is a discounting combination foragent i if {Rj : j 6= i} ∈ T .
Our family of mechanisms will be defined using a disjoint set of discounting combinations.
In particular, for every disjoint set of discounting combinations, we will define a desirable
mechanism satisfying no subsidy which is different from the MWEP mechanism.
For the two claims below, we fix a disjoint set of discounting combinations T . Hence,for each T ∈ T , there exists two price vectors pT and pT as defined in Definition 11. The
claims below relate the minimum Walrasian equilibrium allocation to these price vectors at
a discounting combination.
Claim 2 If R ≡ (R1 , R2 , R3 , R4 ) ∈ (R+ )4 is a discounting combination for agent i and{Rj : j 6= i} = T ∈ T , then pmin (R) = pT .
20

Let R ≡ (R1 , R2 , R3 , R4 ) ∈ (R+ )4 be a discounting combination for agent i and

Proof :

{Rj : j 6= i} = T . Then by the definition of discounting combination, D(Rj , pT ) = L foreach j 6= i. Hence, pT is a Walrasian equilibrium price vector.
Let p0 ≤ pT be such that p0a < pTa or p0b < pTb . Then by the definition of discounting
combination, 0 ∈/ D(Rj , p0 ) for every j 6= i. Hence, only agent i may demand 0. Thus, by
n = 4 and m = 2, p0 cannot be a Walrasian equilibrium.



Note that since T is disjoint and each set in T contains only distinct preferences, at any
preference profile R, there can be a maximum of two agents for whom R is a discounting
combination. Further, if R is a discounting combination for i and j, then {Rk : k 6= i} ={Rk : k 6= j}. Hence, Claim 2 is consistent with such preference profiles.
The next claim establishes an important property involving discounting combinations –we will use this property crucially to define our mechanism. The proof of this claim is given
in Appendix A.
Claim 3 For each R ∈ (R+ )4 , there exists an object allocation (a1 , . . . , a4 ) such that {a1 , a2 , a3 , a4 } ={0, a, b} and for each i ∈ N ,1. if R is a discounting combination for agent i with {Rj : j 6= i} = T ∈ T , thenai ∈ D(Ri , pT ),2. if R is not a discounting combination for agent i, then there exists a minimum Walminminrasian equilibrium price allocation ((b1 , pmin(R) suchb1 (R)), . . . , (b4 , pb4 (R))) ∈ Z

that bi = ai .
Claim 3 shows that for every disjoint set of discounting combinations T , at every preference profile R, we can identify an object allocation satisfying (1) and (2) of Claim 3. Though
there may be more than one such object allocation, we identify one such object allocation
at every R and use it to formally define our mechanism.
Definition 12 Given a disjoint set of discounting combinations T , the MWEP mechanism with discounting combinations T , denoted by f T , is defined as follows: for every
R ∈ (R+ )4 , (aT1 (R), . . . , aT4 (R)) is an object allocation satisfying Claim 3, and for everyi∈NtTi (R) =pTT

ai (R)

if R is a discounting combination for i,pmin (R) otherwise,aT (R)iT

where p is the price vector defined in Definition 11 for every T ∈ T .
21

It is clear that f T satisfies individual rationality, equal treatment of equals, no wastage,and no subsidy. We show that it is also strategy-proof. As shown below in the proof, Claim
3 plays an important role in showing strategy-proofness.
Proposition 1 For every disjoint set of discounting combinations T , the mechanism f T is
strategy-proof.
Proof :

Fix R ∈ (R+ )4 , and i ∈ N . If R is not a discounting combination for i, then bychanging his preference to Ri0 , (Ri0 , R−i ) is not a discounting combination for i. By Claim 3,
in both the preference profiles, we can pick the respective minimum Walrasian equilibrium
allocation, and by Demange and Gale (1985), i cannot manipulate to Ri0 .
If R is a discounting combination for i with respect to discounting combination T , thenby changing his preference to Ri0 , (Ri0 , R−i ) is also a discounting combination for i withrespect to discounting combination T . As a result, we get that aTi (R) ∈ D(Ri , pT ) andaTi (Ri0 , R−i ) ∈ D(Ri0 , pT ). Clearly, agent i cannot manipulate to Ri0 .



Note that if R is a discounting combination for i, then she pays according to pT which islower than pT = pmin (R) (Claim 2). Hence, f T is different from the MWEP mechanism. By
varying the choice of T , we generate a family of such mechanisms. Note that even thoughthese mechanisms are defined for R+ , f T can be defined on a smaller domain D ⊆ R+
as long as we can define T . However, as discussed earlier, a discounting combination T
containing only quasilinear preferences is not possible. Hence, there is no set of discounting
combinations in RQ (the domain of quasilinear preferences). But we show in Supplementary
Appendix B.1 that the MWEP mechanism is not the unique desirable mechanism satisfying
no subsidy on RQ .
The above family of mechanisms clarify that we cannot afford to drop ex-post revenue
maximization in Theorem 1. In that sense, our result is not entirely an axiomatic exercise,and revenue maximization is an essential part of our result. At the same time, ex-post
revenue maximization is about picking a desirable mechanism satisfying no subsidy whichrevenue dominates every such mechanism. Here, if this property is treated as an axiom, thenour result can be viewed as providing an axiomatic foundation for the MWEP mechanism.

6

Discussion

In this section, we discuss various extensions and interpretations of our results.
22

6.1 Extending a quasilinear domain result
In this section, we interpret Theorem 1 as a generalization of a revenue maximization resultin the single object quasilinear domain setting. In particular, we impose no wastage inMyerson’s analysis of optimal single object auction. We observe that if agents’ values are
independently and identically distributed (IID, hereafter) random variables, then the optimalmechanism is the Vickrey auction. We then interpret our Theorem 1 as an extension of thisresult.
Consider the single object auction setting and the quasilinear domain. So, the valuation
vi of each agent is drawn from (0, ∞) using independent and identical cumulative distributioni)function Γ (with pdf γ). Define the virtual value function of each agent i as w(vi ) = vi − 1−Γ(vγ(vi )

for each vi ∈ R++ . We assume that the virtual valuation function is increasing (regularity).
Myerson (1981) optimizes expected revenue over the set of all Bayesian incentive compatible and interim individually rational mechanisms. He also allows for randomization. Our
first observation here points out that we get the Vickrey auction to be optimal if we restrict
the set of mechanisms by imposing no wastage. As will be clear, the IID assumption of
distribution plays a crucial role for this result.
To see this, consider a Bayesian incentive compatible (BIC) and interim individual rational (IIR) mechanism f ≡ (a, t), where f can be a random mechanism.14 Myerson (1981)shows that the expected revenue from such a mechanism can be written as:XEvw(vi )ai (v) ,i∈Nwhere Ev denotes the expectation across all valuation profiles using the IID distribution Γ.
Since ai (v) is the object allocation probability of agent i at valuation profile v, the termw(vi )ai (v) is the expected virtual value of agent i at valuation profile v. Hence, to maximize
expected revenue, it is sufficient to maximize expected virtual value at every valuation profile.
Now, suppose we want to maximize expected revenue over all BIC, IIR, and no wastage
mechanisms. Since at every valuation profile v, we have to allocate the object and we needP
to maximize i∈N w(vi )ai (v), we can do so by setting ak (v) = 1 if k ∈ arg maxi∈N w(vi ). In
other words, we allocate the object to the agent with the highest virtual value.15 Since the
distribution is regular, revenue equivalence pins down the payment such that the resulting
mechanism is BIC and IIR. Of course, it satisfies no wastage by construction. In fact, this14
15

We do not formally define BIC and IIR as they are standard in the literature.
If no wastage is not imposed, then as Myerson (1981) shows, the expected revenue maximizing mechanism

should not sell the object when virtual values of all the agents are negative.

23

mechanism is the Vickrey auction since the agent with the highest virtual value is also theagent with the highest value – this is not the case if the IID is assumption is dropped. We
list this as a fact below, and note that no analogue of this fact is known in the literature in
our model (multiple heterogenous objects with unit demand agents).
Fact 2 (Myerson (1981)) Suppose there is a single object (m = 1) and the domain ofpreferences is the quasilinear domain with valuations of agents identically and independently
distributed and the distribution satisfies regularity. Then, the Vickrey auction maximizes
expected revenue over the set of all BIC and IIR mechanisms satisfying no wastage.

Fact 2

Theorem 1

Number of objects

m=1

m<n

Domain of preferences

Quasilinear

Any rich domain (Corollary 1)

Distributional assumptions

IID values

Nonewith regularity
Revenue maximization

Ex-ante (expected)

Ex-post (at every profile)

Incentive compatibility

BIC

Strategy-proofness

Axioms

BIC, IIR, andStrategy-proofness, Ex-post IR,

no wastage

no wastage, ETE and no subsidy

Considered

Not considered

Random mechanisms

Table 1: Comparison of Fact 2 and Theorem 1
Clearly, there are many ways in which Theorem 1 generalizes Fact 2: (i) it considers morethan one object; (ii) it allows for domains of preferences which can contain non-quasilinear
preferences; (iii) it shows ex-post revenue maximizing mechanism; (iv) it does not assume
anything about the priors (i.e., completely prior-free prediction)16 . But these generalizations
come with some further assumptions. Theorem 1 only considers strategy-proof mechanisms(as compared to BIC mechanisms in Fact 2). Theorem 1 does not consider random mechanisms while Fact 2 optimizes over random mechanisms. Finally, Theorem 1 imposes no
subsidy and equal treatment of equals but Fact 2 does not impose these axioms. These
differences are summarized in Table 1.
16

For instance, Fact 2 is no longer true if values of agents are drawn from different distributions. In thatcase, the object goes to the agent with the highest virtual value, and such an agent need not have the highest
value (the Vickrey auction gives the object to the agent with the highest value).

24

6.2 A lower bound on expected revenue
In this section, we show the consequence of dropping the following axioms from Theorem
1: no wastage, equal treatment of equals, and no subsidy. Hence, we will consider a larger
class of mechanisms than in Theorem 1 - mechanisms which are strategy-proof and (ex-post)individually rational. We will also be interested in maximizing expected revenue.
We explicitly focus on quasilinear domain of preferences, where the MWEP mechanismis the VCG mechanism. A preference Ri of agent i can be represented by a valuation vectorvi ≡ {via }a∈L , where the valuation for the null object is normalized to zero: vi0 = 0. The
discussion in this section will require assumptions on prior distribution of values of agents.
We will assume a symmetric prior: every agent i draws valuation for object j ∈ M using
the same distribution Γ from (0, ∞), which is strictly increasing, differentiable, and admits adensity function γ. Hence, the joint distribution of valuations is independent (across agentsand objects) and identical (IID). Further, we will assume that Γ is regular, which means
is increasing in x.
x − 1−Γ(x)γ(x)
Given a mechanism f ≡ (a, t) on the quasilinear domain, we denote the expected revenue
from f asE(Revf ) = EvXti (v) ,i∈N

where ti (v) is the payment of agent i at valuation profile v. Using this, we define the notionof the standard optimal mechanism, which we call ex-ante revenue optimality.
Definition 13 A mechanism f : (RQ )n → Z is ex-ante revenue optimal among a classof mechanisms in the quasilinear domain if for every mechanism g : (RQ )n → Z in thisclass, we have
E(Revf ) ≥ E(Revg ).
If the number of agents is at least twice the number of objects, Roughgarden et al. (2012)
show that the expected revenue of the VCG mechanism in our model is at least half the
expected revenue from the ex-ante revenue optimal mechanism among the class of strategyproof and ex-post individually rational mechanisms. Since the MWEP mechanism coincides
with the VCG mechanism in the quasilinear domain, the following corollary is immediatefrom Theorem 1 and their result.
Corollary 5 Suppose n ≥ 2m. Let f : (RQ )n → Z be an ex-post revenue optimalmechanism among the class of desirable mechanisms satisfying no subsidy in (RQ )n . Let
25

g : (RQ )n → Z be an ex-ante revenue optimal mechanism among the class of mechanisms
satisfying strategy-proofness and ex-post individual rationality in (RQ )n . Then,
1
E(Revf ) ≥ E(Revg )2
The main point about Corollary 5 is that the ratio of expected revenue from f and g isbounded by a constant, i.e., it does not depend on m or n.17
Corollary 5 shows that by requiring no wastage, equal treatment of equals, and no subsidy, we do not sacrifice arbitrary proportion of expected revenue in the quasilinear domain.
Further, we gain in terms of robustness since the VCG mechanism is a prior-free mechanism
and is ex-post revenue optimal in the class of desirable mechanisms satisfying no subsidy.

6.3 Our axioms
As we have discussed at several places, the expected revenue maximization with multiple
objects is a difficult problem. The objective of our exercise was to see the implication of
additional axioms on this problem. These axioms surprisingly gave us a robust solution – expost revenue maximization. Futher, our result can incorporate non-quasilinear preferences.
Such a robust prediction is rarely seen in the mechanism design literature.
How do our axioms help in achieving such a robust result? Below, we give some examples
to illustrate the implications of our axioms on the result. In particular, we show that eachof the axioms are necessary to get our result.
Notion of incentive compatibility and IR. Consider a mechanism that chooses the
maximum Walrasian equilibrium allocation at every profile. Such a mechanism will satisfy no
subsidy and all the properties of desirability except strategy-proofness. Similarly, the MWEP
mechanism supplemented by a participation fee satisfies no subsidy and all the propertiesof desirability except ex-post IR. Both these mechanisms generate more revenue than the
MWEP mechanism. Hence, strategy-proofness and ex-post IR are necessary for our results
to hold.
17

Roughgarden et al. (2012) have similar constant approximation bounds for n < 2m also, and we canuse them to derive analogues of Corollary 5 for m < n < 2m. Further, Corollary 5 does not explicitly
consider randomized and Bayesian incentive compatibile mechanisms. But results in similar spirit can also
be obtained by allowing for such mechanisms. This is because Chawla et al. (2015) show that similar bounds
can be obtained between deterministic and randomized ex-ante revenue optimal mechanisms.

26

What is less clear is if we can relax the notion of incentive compatibility to Bayesian
incentive compatibility in our results. In Appendix B.2, we consider the single object auction
model in the quasilinear domain, and show that a modified first-price auction (modified
only at a set of zero measure valuation profiles) is Bayesian incentive compatible, ex-post
individually rational, and satisfies no wastage, equal treatment of equals, and no subsidy.
Clearly, a first-price auction generates more revenue than the Vickrey mechanism at somevaluation profiles.
At least in quasilinear domain, we know that there are many revenue equivalent Bayesian
incentive compatible mechanisms to the Vickrey auction (for single object). Hence, our notion of incentive compatibility eliminates such mechanisms.
No wastage. We have already argued about why no wastage as an axiom makes sense. In
Section 6.1, we gave an example of a result in the quasilinear domain where we explicitly
point out the implication of no wastage. In short, no wastage gets rid of all mechanisms
with reserve price. Hence, it is easy to see that no wastage is required for our result –in the quasilinear domain of preferences with one object, Myerson (1981) shows that the
Vickrey mechanism with an optimally chosen reserve price maximizes expected revenue forindependent and identically distributed values of agents. Such a mechanism wastes the object
and generates more revenue than the Vickrey mechanism at some profiles of preferences.
No wastage is also necessary in a more indirect manner. Consider the domain of quasilinear preferences with two objects M ≡ {a, b} and N = {1, 2, 3}. We show that the seller
may increase her revenue by not selling all the objects. Consider a profile of valuations asfollows:
v1 (a) = v1 (b) = 5
v2 (a) = v2 (b) = 4
v3 (a) = v3 (b) = 1.
The MWEP price at this profile is pmin
= pmin= 1, which generates a revenue of 2 to theabseller. On the other hand, suppose the seller conducts a Vickrey mechanism of object a only.
Then, he generates a revenue of 4. Hence, the seller can increase her ex-post revenue at someprofiles of valuations by withholding objects. Notice that withholding objects is a stronger
violation of efficiency, and is easier to detect than misallocating the objects among agents.
Equal treatment of equals. There are various fairness notions in the mechanism design
27

literature. A typical notion of ex-post fairness is envy freeness (Varian, 1974; Sprumont,2013). A typical notion of ex-ante fairness is anonymity (Sprumont, 1991; Moulin and
Shenker, 1992; Barbera and Jackson, 1995).18 Equal treatment of equals is the weakest
fairness notion in the sense that it is weaker than each of envy-freeness and anonymity.
There are ample examples of mechanisms violating equal treatment of equals in themechanism design literature In the single object auction model in quasilinear domain, if
values of agents are drawn from different distributions, then revenue is maximized by anasymmetric mechanism - see Section 6.1 for a precise statement. Hence, for some profiles ofpreferences, such mechanisms must generate more revenue than the Vickrey auction. Equal
treatment of equals rules out such mechanisms.
Another example that shows the necessity of equal treatment equals in our result is thefollowing. Suppose that there are one object and two agents, and preferences are quasilinear.
Hence, the preference of each agent i ∈ {1, 2} can be described by his valuation for the objectvi .
We define the following mechanism: the object is first offered to agent 1 at price p > 0; if
agent 1 accepts the offer, then he gets the object at price p and agent 2 does not get anything
and does not pay anything; else, agent 2 is given the object for free.
This mechanism generates a revenue of p whenever v1 > p (but generates zero revenue
otherwise). However, note that the Vickrey mechanism generates a revenue of v2 whenv1 > v2 . Hence, if v1 > p > v2 , then this mechanism generates more revenue than the
Vickrey mechanism. Also, this mechanism satisfies no subsidy and all the properties of desirability except equal treatment of equals.
No subsidy. It is tempting to conjecture that no subsidy can be relaxed in quasilinear
domain of preferences. The following example shows that this need not be true.
Consider an example with one object and two agents in the quasilinear domain - hence,
preferences of agents can be represented by their valuations v1 and v2 . Further, assume thatvaluations lie in R++ . Choose k ∈ (0, 1) and define the mechanism f ≡ (a, t) as follows: forevery (v1 , v2 )(a(v1 , v2 ) =18(1, 0) if kv1 > v2 ,(0, 1) otherwise,

Anonymity is sometime called symmetry in the literature (Manelli and Vincent, 2010; Deb and Pai,

2016). Though it is stronger than equal treatment of equals in our model, it is often used when randommechanisms are allowed.

28

(
t1 (v1 , v2 ) =−(v2 − kv2 )if a1 (v1 , v2 ) = 0,v2
− (v2 − kv2 )kif a1 (v1 , v2 ) = 1,(t2 (v1 , v2 ) =0

if a2 (v1 , v2 ) = 0,

kv1 if a2 (v1 , v2 ) = 1.

It is straightforward to check that the mechanism is strategy-proof. It is also not difficult
to see that utilities of the agents are always non-negative, and hence, individual rationality
holds. Finally, if v1 = v2 , we havea1 (v1 , v2 ) = 0, a2 (v1 , v2 ) = 1, t1 (v1 , v2 ) = −(v2 − kv2 ), t2 (v1 , v2 ) = kv1 .
Hence, net utility of agent 1 is v2 − kv2 and that of agent 2 is v1 − kv1 , which are equal sincev1 = v2 . This shows that the mechanism satisfies equal treatment of equals.
However, the mechanism pays agent 1 when he does not get the object. Thus, it violates
no subsidy. The revenue from this mechanism when kv1 > v2 is1
+ k − 1 ≥ v2 .
v2k
The Vickrey mechanism generates a revenue of v2 when kv1 > v2 . Hence, this mechanism
generates more revenue than the Vickrey mechanism when kv1 > v2 . This shows that wecannot drop no subsidy from Theorem 1. 19

6.4 Extension to other combinatorial auction models
It is not clear whether Theorem 1 extends to other models of combinatorial auctions. First,
if we just consider the quasilinear preference domain, the VCG mechanism generalizes toother combinatorial auction models. However, a crucial feature of the VCG mechanism
in our model (heterogenous objects and unit demand buyers) is that it coincides with the
MWEP mechanism. This plays a crucial role in all our proofs. This equivalence is lostin other models of combinatorial auctions (Gul and Stacchetti, 1999; Bikhchandani and
Ostroy, 2006), and further, the Walrasian equilibrium price vector may fail to exist in othermodels (Bikhchandani and Ostroy, 2006). Hence, it is not clear how our result extends to19

Further inspection reveals that the revenue from this mechanism when v1 = v2 = v is kv − v(1 − k) =v(2k − 1). So, if k < 12 , this revenue approaches −∞ as v → ∞. Hence, this mechanism even violates nobankruptcy.

29

other models of combinatorial auctions (even in the quasilinear domain). We keep this as anagenda for future research.
On the other hand, when the set of preferences include all or a very rich class of nonquasilinear preferences, strategy-proofness and Pareto efficiency (along with other axioms)
have been shown to be incompatible if the unit demand assumption is violated - (Kazumura
and Serizawa, 2016) show this for multi-object allocation problems where agents can beallocated more than one object; (Baisa, 2019, Forthcoming) shows this for homogeneous
object allocation problems where agents can be assigned any number of units. In otherwords, no canonical mechanism is known to exist once we relax the unit demand assumption,and it is not clear how Theorem 1 extends.

7

The proofs of Theorems 1 and 2

In this section, we present all the proofs. The proofs use the following fact very crucially:
the MWEP mechanism chooses a Walrasian equilibrium outcome. Before diving into theproofs, we want to stress here that a greedy approach of proving our results would be to firstprove that any desirable mechanism satisfying no subsidy and maximizing revenue must be
Pareto efficient. In the quasilinear domain, using revenue equivalence will then pin down the
MWEP (VCG) mechanism. This approach will fail in our setting because our results work
even without quasilinearity and revenue equivalence does not hold in such domains. Further,
it is not obvious even in quasilinear domain that the desirability, no subsidy, and the revenue
optimality implies Pareto efficiency. Our proofs work by showing various implications ofdesirability and no subsidy on consumption bundles of agents. It uses richness of the domain
to derive these implications. In that sense, it departs from traditional Myersonian techniques,
where revenue maximization is a programming problem with object allocation mechanisms
as decision variables.
It is worth discussing how our proofs are different from Morimoto and Serizawa (2015),
who characterize the MWEP mechanism. Their focus is on Pareto efficiency and their proofs
depend on this. Since we use only no wastage as a efficiency desideratum, which is much
weaker than Pareto-efficiency, we need to develop our own proof techniques to establish our
results.
We start off by showing an elementary lemma which shows that at every preference
profile, if a mechanism gives every agent weakly better consumption bundles than the MWEP
mechanism, then its revenue is no more than any MWEP mechanism. This lemma will be30

used to prove both our results.
Lemma 1 For every mechanism f : Rn → Z and for every R ∈ Rn , the following holds:





min
fi (R) Ri fimin (R) ∀ i ∈ N ⇒ Revf (R) ≥ Revf (R) ,where f min is the MWEP mechanism.
Proof :

Fix a profile of preferences R ∈ Rn and denote fimin (R) = (ai , pminai (R)) for eachi ∈ N . Now, for every i ∈ N , we have fi (R) ≡ (ai (R), ti (R)) Ri (ai , pminai (R)) and by themin
Walrasian equilibrium property, (ai , pminai (R)) Ri (ai (R), pai (R) (R)). This gives us ti (R) ≤pmin
ai (R) (R) for each i ∈ N . Hence,
Revf (R) =Xi∈Nti (R) ≤Xfpmin
ai (R) (R) ≤ Rev

min

(R),

i∈N
|L|

where the last inequality follows from pmin (R) ∈ R+ .



7.1 Proof of Theorem 1
We start with a series of Lemmas before providing the main proof. Throughout, we assume
that R is a rich domain of preferences and f is a desirable mechanism satisfying no subsidy
on Rn . For the proofs, we need the following definition.
Definition 14 A preference Ri is (a, t)-favoring for t ≥ 0 and a ∈ M if for price vector
p with pa = t, pb = 0 for all b 6= a, we have D(Ri , p) = {a}.
An equivalent way to state this is that Ri is (a, t)-favoring for t > 0 and a ∈ M if
V Ri (b, (a, t)) < 0 for all b 6= a. A slightly stronger version of (a, t)-favoring preference isthe following.
Definition 15 A preference Ri is (a, t) -favoring for t ≥ 0, a ∈ M , and  > 0 if it is(a, t)-favoring andV Ri (a, (0, 0)) < t + 
V Ri (b, (0, 0)) <  ∀ b ∈ M \ {a}.
The following lemma shows that if R is rich, then (a, t) -favoring preferences exist for every(a, t) ∈ M × R+ and  > 0.
31

Lemma 2 Suppose R is rich. Then, for every bundle (a, t) ∈ M × R+ and for every  > 0,
there exists a preference Ri ∈ R such that it is (a, t) -favoring.
Proof : Define p̂ as follows: p̂a = t, p̂b = 0 ∀ b 6= a.
Define p as follows: pa = t + , p0 = 0, pb =  ∀ b ∈ M \ {a}.
By richness, there exists Ri such that D(Ri , p̂) = {a} and D(Ri , p) = {0}. But this implies
that Ri is (a, t)-favoring. Further, V Ri (a, (0, 0)) < t +  and V Ri (b, (0, 0)) <  ∀ b ∈ M \ {a}.
Hence, Ri is (a, t) -favoring.

Using this, we prove the following lemma which will be used in the proof.
Lemma 3 For every preference profile R ∈ Rn , for every i ∈ N , for every t ∈ R+ , if there
exists j 6= i such that Rj is (ai (R), t)-favoring, then ti (R) > t.
Proof : Suppose ti (R) ≤ t. Since Rj is (ai (R), t)-favoring, ti (R) ≤ t implies that Rj is also0
= R−i ).
fi (R) ≡ (ai (R), ti (R))-favoring. Consider a preference profile R0 ≡ (Ri0 = Rj , R−i

By equal treatment of equals (since Ri0 = Rj0 = Rj ),fi (R0 ) Ij fj (R0 ).

(1)

We argue that fi (R0 ) = fi (R). If ai (R0 ) = ai (R), then strategy-proofness implies thatti (R0 ) = ti (R) and we are done. Assume for contradiction that ai (R) = a 6= b = ai (R0 ).
0

By strategy-proofness, (b, ti (R0 )) Ri0 (a, ti (R)), which implies that ti (R0 ) ≤ V Ri (b, (a, ti (R))).
0

Since Ri0 = Rj is (a, ti (R))-favoring, we have V Ri (b, (a, ti (R))) < 0. This implies that ti (R0 ) <0, which is a contradiction to no subsidy. Hence, we havefi (R0 ) = fi (R).

(2)

Combining Inequality (1) and Equation (2), we get that fi (R) Ij fj (R0 ). Hence, tj (R) =V Rj (aj (R0 ), fi (R)) < 0, where the strict inequality followed from the fact Rj is fi (R)-favoring
and ai (R) = ai (R0 ) 6= aj (R0 ). This is a contradiction to no subsidy.



We will now prove Theorem 1 using these lemmas.
Proof of Theorem 1
Proof :

Fix a desirable mechanism f : Rn → Z satisfying no subsidy, where R is a richdomain of preferences. Fix a preference profile R ∈ Rn . Let (z1 , . . . , zn ) ≡ f min (R) be the32allocation chosen by the MWEP mechanism f min at R. Let p ≡ mina∈M pmina (R). Clearly,p > 0. For simplicity of notation, we will denote zi ≡ (ai , pi ), where pi ≡ pminai (R) for alli ∈ N . We prove that fi (R) Ri zi for all i ∈ N , and by Lemma 1, we will be done.
Assume for contradiction that there is some agent i ∈ N such that zi Pi fi (R). We
first construct a finite sequence of distinct agents and preferences, without loss of generality(1, R10 ), . . . , (n, Rn0 ), satisfying certain properties. Let N0 ≡ ∅, Nk ≡ {1, . . . , k} for each k ≥ 1,0
and (RN, R−N0 ) ≡ R. This sequence satisfies the properties that for every k ∈ {1, . . . , n},00, R−Nk−1 ) for each k ≥ 1,
1. zk Pk fk (RN
k−1

2. ak 6= 0,0, R−Nk−1 ))−pk , p}.
3. Rk0 is (zk )k -favoring for some k > 0 with k < min{V Rk (ak , fk (RN
k−1

Now, we construct this sequence inductively.
Step 1 - Constructing (1, R10 ). Let i = 1. By our assumption, z1 P1 f1 (R). This implies
p1 − V R1 (a1 , f1 (R) < 0. Thus, there is 1 > 0 such that 1 < min{V R1 (a1 , f1 (R)) − p1 , p}.
By Lemma 2, there is a (z1 )1 -favoring preference R10 . Suppose a1 = 0. Then, (0, 0) =z1 P1 f1 (R), which contradicts individual rationality. Hence, a1 6= 0.
Step 2 - Constructing (k, Rk0 ) for k > 1. We proceed inductively - suppose, we have already0
constructed (1, R10 ), . . . , (k − 1, Rk−1
) satisfying Properties 1, 2, and 3. By no wastage and0, R−Nk−1 ) = ak−1 .
the fact that ak−1 6= 0, there is agent j ∈ N such that aj (RNk−10, R−Nk−1 ) = ak−1 imply thatIf j = k − 1, then individual rationality of f and aj (RN
k−1
0

0
0
tk−1 (RN, R−Nk−1 ) ≤ V Rk−1 (ak−1 , (0, 0)) < pk−1 +k−1 < V Rk−1 (ak−1 , fk−1 (RN, R−Nk−2 )),
k−1
k−2
0
where the second inequality followed from the fact that Rk−1
is (zk−1 )k−1 -favoring, and the0last inequality followed from the definition of k−1 . Thus, by aj (RN, R−Nk−1 ) = ak−1 , we
k−1

have
0
0
fk−1 (RN, R−Nk−1 ) Pk−1 fk−1 (RN, R−Nk−2 ),k−1
k−2

which contradicts strategy-proofness. Hence, j 6= k − 1.
If j ∈ Nk−2 , then by individual rationality of f , we get00tj (RN, R−Nk−1 ) ≤ V Rj (ak−1 , (0, 0)) < j < pk−1 ,
k−1

33

(3)

where the second inequality followed from the fact that Rj0 is (zj )j -favoring and j 6= (k − 1),and the last inequality followed from the definition of j . But, notice that agent (k − 1) 6= j00
, R−Nk−1 ) = ak−1 .
is zk−1 -favoring (since it is (zk−1 )k−1 -favoring). Further aj (RN
and Rk−1
k−10Then, Lemma 3 implies that tj (RN, R−Nk−1 ) > pk−1 , which contradicts Inequality (3).
k−1Thus, we have established j ∈/ Nk−1 , i.e., j is a distinct agent not in Nk−1 . Hence, wedenote j ≡ k, and note that0zk Rk zk−1 Pk fk (RN, R−Nk−1 ),k−1where the first preference relation follows from the Walrasian equilibrium property and the00, R−Nk−1 ), R−Nk−1 ) = ak−1 and pk−1 < tk (RNsecond follows from the fact that ak (RN
k−1
k−1(Lemma 3). Hence Property 1 is satisfied for agent k. Next, if ak = 0, then (0, 0) =0
, R−Nk−1 ) contradicts individual rationality. Hence, Property 2 also holds.
zk Pk fk (RNk−10
By zk Pk fk (RN, R−Nk−1 ), pk − V Rk (ak , fk (Rn0 k−1 , R−Nk−1 )) > 0. Thus, there is k > 0
k−10, R−Nk−1 )) − pk , p}. Hence, by Lemma 2, there is asuch that k < min{V Rk (ak , fk (RNk−1zkk -favoring Rk0 .
Thus, we have constructed a sequence (1, R10 ), . . . , (n, Rn0 ) such that ak 6= 0 for all k ∈ N .
This is impossible since n > m, giving us the required contradiction.
Finally, we show that the MWEP mechanism is the unique ex-post revenue optimalmechanism among the class of desirable mechanisms satisfying no subsidy defined on a richdomain. Suppose fˆ ≡ (â, t̂) is another (not the MWEP) desirable mechanism satisfying no
subsidy that is ex-post revenue optimal among the class of desirable mechanisms satisfying
no subsidy. Then, there is some preference profile R and an agent i such that the objectâi (R) assigned to agent i by the mechanism fˆ is not in her demand set at pmin (R). Let(aj , pminaj (R)) denote the consumption bundle assigned to each agent j ∈ N at preference
profile R by the MWEP mechanism f min . Hence,min(ai , pminai (R)) Pi (âi (R), pâi (R) (R)).

For all j 6= i, by the definition of Walrasian equilibrium, we havemin(aj , pminaj (R)) Rj (âj (R), pâj (R) (R)).

In the first part of the proof of this theorem, we have already shown that for all j ∈ N ,(âj (R), t̂j (R)) Rj (aj , pminaj (R)).

34

Combining the above relations, for all j ∈ N , we have (âj (R), t̂j (R)) Rj (âj (R), pminâj (R) (R))
with strict relation holding for agent i. This implies that t̂j (R) ≤ pminâj (R) (R) with strict
inequality holding for agent i. Adding it over all the agents, we getˆ

Revf (R) =Xj∈Nt̂j (R) <

X

f
pmin
âj (R) (R) ≤ Rev

min

(R),

j∈N

which is a contradiction to the ex-post revenue optimality of fˆ.



7.2 Proof of Theorem 2
We now fix a desirable mechanism f : Rn → Z, where R ⊇ R++ . Further, we assume thatf satisfies no bankruptcy, where the corresponding bound as ` ≤ 0. We start by proving ananalogue of Lemma 3.
Lemma 4 For every preference profile R ∈ Rn , for every i ∈ N , and every (a, t) ∈ M × R+
with a = ai (R), if there exists j 6= i such that for each b ∈ L \ {a},
V Rj (b, (a, t)) < −n max max V Rk (c, (0, 0)) + `,k∈N c∈M

then ti (R) > t.
Proof :

Assume for contradiction ti (R) ≤ t. Consider Ri0 = Rj . By strategy-proofness,fi (Ri0 , R−i ) Ri0 fi (R) = (a, ti (R)). By equal treatment of equals,
fj (Ri0 , R−i ) Ij fi (Ri0 , R−i ) Rj (a, ti (R)).
Note that either ai (Ri0 , R−i ) 6= a or aj (Ri0 , R−i ) 6= a. Without loss of generality, assume thataj (Ri0 , R−i ) = b 6= a. Then, using the fact that (b, tj (Ri0 , R−i )) Rj (a, ti (R)) and ti (R) ≤ t,
we gettj (Ri0 , R−i ) ≤ V Rj (b, (a, ti (R)))≤ V Rj (b, (a, t))< −n max max V Rk (c, (0, 0)) + `.
k∈N c∈M

By individual rationality
00ti (Ri0 , R−i ) ≤ V Ri (ai (Ri0 , R−i ), (0, 0)) ≤ max V Ri (c, (0, 0)).
c∈M35

Further, individual rationality also implies that for all k ∈/ {i, j},tk (Ri0 , R−i ) ≤ V Rk (ak (Ri0 , R−i ), (0, 0)) ≤ max V Rk (c, (0, 0)).
c∈MAdding these three sets of inequalities above, we getX

tk (Ri0 , R−i )

k∈N


0
< −n max max V Rk (c, (0, 0)) + ` + max V Ri (c, (0, 0)) +k∈N c∈Mc∈M

k∈N \{i,j}= −n max max V Rk (c, (0, 0)) + ` + max V Rj (c, (0, 0)) +k∈N c∈Mc∈M
≤ −n max max V Rk (c, (0, 0)) + (n − 1)k∈N c∈M

X
X
k∈N \{i,j}max V Rk (c, (0, 0))c∈Mmax V Rk (c, (0, 0))c∈Mmax max V Rk (c, (0, 0)) + `k∈N \{i} c∈M≤ `.
This contradicts no bankruptcy.

Using Lemma 4, we can mimic the proof of Theorem 1 to complete the proof of Theorem
2. We start by defining a class of positive income effect preferences by strengthening thenotion of (a, t) -favoring preference. For every (a, t) ∈ M × R+ , for each  > 0, and for eachδ > 0, let R((a, t), , δ) be the set of preferences such that for each R̂i ∈ R((a, t), , δ), thefollowing holds:
1. R̂i is (a, t) -favoring and2. V R̂i (b, (a, t)) < −δ for all b 6= a.
A graphical illustration of R̂i is provided in Figure 5. Since δ > 0, it is clear that aR̂i can be constructed in R((a, t), , δ) such that it exhibits positive income effect. Hence,R++ ∩ R((a, t), , δ) 6= ∅.
Proof of Theorem 2
Proof : Now, we can mimic the proof of Theorem 1. We only show parts of the proof that
requires some change. As in the proof of Theorem 1, by Lemma 1, we only need to show thatfor every profile of preferences R ∈ Rn and for every i ∈ N , fimin (R) Ri f (R), where f min is
the MWEP mechanism. Assume for contradiction that there is some profile of preferences
36

c
b

^i
R

^i
R

t

a
0

−δ

0

transfer
ϵt+ϵFigure 5: Illustration of R̂i
R ∈ Rn and some agent i ∈ N such that zi Pi fi (R), where (z1 , . . . , zn ) ≡ f min (R) be theallocation chosen by the MWEP mechanism at R. Let p ≡ mina∈M pmina (R). For simplicity
of notation, we will denote zj ≡ (aj , pj ), where pj ≡ pminaj (R), for all j ∈ N .
Define δ̄ > 0 as follows:δ̄ := n max max V Rk (c, (0, 0)) − `.
k∈N c∈M

We first construct a finite sequence of agents and preferences, without loss of generality(1, R10 ), . . . , (n, Rn0 ), satisfying certain properties. Let N0 ≡ ∅, Nk ≡ {1, . . . , k} for each k ≥ 1,0
and (RN, R−N0 ) ≡ R. This sequence satisfies the properties that for every k ∈ {1, . . . , n},00
1. zk Pk fk (RN, R−Nk−1 ) for each k ≥ 1,k−1

2. ak 6= 0,0
3. Rk0 ∈ R+ ∩ R(zk , , δ̄) for some k > 0 with k < min{V Rk (ak , fk (RN, R−Nk−1 )) −k−1

pk , p}.
Now, we can complete the construction of this sequence inductively as in the proof of
Theorem 1 (using Lemma 4 instead of Lemma 3), giving us the desired contradiction.
The uniqueness proof is identical to the proof of uniqueness given in Theorem 1.

37



8

Relation to the literatureEver since the work of Myerson (1981), various extensions of his work to multi-object casehave been attempted in quasilinear domain. Most of these extensions focus on the single
agent (or, screening problem of a monopolist) with additive valuations (value for a bundleof objects is the sum of values of objects). Armstrong (1996, 2000) are early papers thatshow the difficulty in extending Myerson’s optimal mechanisms to multiple objects case he identifies optimal mechanisms for the cases where agents’ preferences are binary, i.e, thevaluations of each agent on a given object are only low and high values, but demonstrates
that it is too complicated to identify optimal mechanisms for other cases.20 Rochet andChoné (1998) show how to extend the convex analysis techniques in Myerson’s work to multidimensional environment and point out various difficulties in the derivation of an optimalmechanism. These difficulties are more precisely formulated in the following line of workfor the single agent additive valuation case: (1) optimal mechanism may require randomization (Thanassoulis, 2004; Manelli and Vincent, 2007); (2) simple mechanism like selling eachgood separately (Daskalakis et al., 2017) and selling all the goods as a grand bundle (Manelli
and Vincent, 2006) are optimal for very specific distributions; (3) there is inherent revenue
non-monotonicity of the optimal mechanism - if we take two distributions with one first-orderstochastic-dominating the other, the optimal mechanism revenue may not increase (Hart andReny, 2015); (4) the optimal mechanism may require an infinite menu of prices (Hart andNisan, 2019). The complexity of revenue maximization in our model is apparent in the workof Thirumulanathan et al. (2017), who show that the analysis becomes intractable even for
one buyer (with unit demand) and two objects (with uniformly distributed values).
Since these extensions are for a single agent who has additive valuation for bundles of objects, this may give the impression that the multi-object optimal mechanism design problem
is difficult only when agents can be allocated more than one object. However, this impression
is not true - the source of the problem is the multiple dimension of private information, which
continues to exist even in the unit demand model considered in our paper. In our model,
even with quasilinearity, the multiple dimensions of private information will be valuations
for each object. As illustrated in Armstrong (1996, 2000), the multiple dimensions of private
information implies that the incentive constraints become complicated to handle. In quasilinear domain, the Myersonian approach to this problem would pin down payments of agents
20

Whenever we say optimal mechanisms, we mean, like in Myerson (1981), an expected revenue maximizing

mechanism under incentive and participation constraints with respect to some prior distribution.

38

in terms of object allocation rules using the well known revenue equivalence formula (Krishna
and Maenner, 2001; Milgrom and Segal, 2002). Then, the objective function (maximizing
sum of expected payments) is rewritten in terms of object allocation rule. On the constraintside, necessary and sufficient conditions are identified for the object allocation rule to be implementable (Rochet, 1987; Jehiel et al., 1999; Bikhchandani et al., 2006), and they are put
as constraints. Whether agents can be allocated at most one object or multiple objects, themultidimensional nature of private information makes both the revenue equivalence formulaand the constraints of the optimization problem become extremely difficult to handle. Vohra(2011) provides a linear programming approach to study such multidimensional mechanism
design problems and points out similar difficulties.
Further, it is unclear how some of the above single agent results can be extended tothe case of multiple agents. In the multiple agent problems, the set of feasible allocations starts interacting with the incentive constraints of the agents. Further, the standard
Bayesian incentive compatibility constraints become challenging to handle. Note that in the
single agent problem, these notions of incentive compatibility are equivalent, and for onedimensional mechanism design problems, they are equivalent in a useful sense (Manelli andVincent, 2010; Gershkov et al., 2013). Because we work in a model without quasilinearity,
we are essentially operating in an “infinite” dimensional mechanism design problem. Hence,
we should expect the problems discussed in quasilinear environment to appear in an evenmore complex way in our model.
To circumvent the difficulties from the multidimensional private information and multiple
agents, a literature in computer science has developed approximately optimal mechanisms forour model - multiple objects and multiple agents with unit demand agents (but with quasilinearity). Contributions in this direction include Chawla et al. (2010a,b); Briest et al. (2010);
Cai et al. (2012). Many of these approximate mechanisms allow for randomization. Further, these approximately optimal mechanisms involve reserve prices and violate no wastage
axiom. It is unlikely that these results extend to environments without quasilinearity.
Finally, the Myersonian approach may not work if preferences are not quasilinear. In a
companion paper (Kazumura et al., 2017), we investigate mechanism design without quasilinearity more abstractly and illustrate the difficulty of solving the single object optimalmechanism design problem. Hence, solving for full optimality without imposing the additional axioms that we put seems to be even more challenging in our model. In that sense,
our results provide a useful resolution to this complex problem.
Our work can be connected to a result by Bulow and Klemperer (1996) and its exten39

sion by Roughgarden et al. (2015). In Bulow and Klemperer (1996), it was shown that
(under standard independent and identical agent assumption with regular distribution) asingle object optimal mechanism (with quasilinear preferences) for n agents generates lessexpected revenue than a single object Vickrey mechanism for (n + 1) agents. Hence, if thecost of recruiting an agent is small, then the Vickrey mechanism can be recommended.21
This result has been extended to our multi-object unit-demand agent setting with quasilinear preferences: the expected revenue maximizing mechanism for n agents generates lessexpected revenue than the VCG mechanism for (m + n) agents, where m is the number ofobjects (Roughgarden et al., 2015) - note that the MWEP mechanism is the VCG mechanism in the quasilinear domain. Our results complement these results by establishing anaxiomatic revenue maximizing foundation of the MWEP mechanism (even when preferences
are not quasilinear).22
We motivated our no wastage axiom by saying that the seller may not be able to commit
to a no sale in future if the objects are not sold. If the seller can commit to a mechanism
after a no-sale, then we can invoke a revelation principle and our results will follow. However,in many realistic settings, the seller is not able to commit to a future mechanism. Skreta(2015) analyzes a single object auction model in quasilinear domain and models the noncommitment of the seller explicitly. In a finite-period model, she finds that the expected
revenue maximizing mechanism takes the same form as in the case of commitment. Her
optimal mechanism does not satisfy no wastage, i.e., it is still optimal for the seller to nottrade the object at the last period.
Ausubel and Cramton (1999) consider a model of a seller selling identical objects to aset of buyers who can consume at most one unit. They assume quasilinear preferences andexplore the conequences of ex-post resale. They show that the Vickrey auction with reserve
price stands out as the optimal (expected revenue maximizing) mechanism with resale (in asubclass of allocation rules called the monotonic aggregate allocation rules). They also offer
other results to show that an inefficient allocation is suboptimal if there is perfect resale.
21

Of course, one can argue that if we have (n + 1) agents, then the seller must use the expected revenue

maximizing mechanism for (n + 1) agents. The main point in Bulow and Klemperer (1996) is that the
Vickrey mechanism is a prior-free robust mechanism, whereas the expected revenue maximizing mechanism
requires knowledge of priors.
22
The computer science literature is interested in such prior-free bounds on optimal multidimensional
mechanisms (which is hard to compute) - a recent paper by Eden et al. (2017) provide further extensions of
Bulow-Klemperer results in multi-object environments where buyers can consume more than one object but
have additive valuations.

40

While they do not consider non-quasilinear preferences and the heterogenous objects model,
their results also hint that some form of revenue maximization and perfect resale leads toa restricted Pareto efficient mechanism (i.e., whenever there is sale, the object is allocatedefficiently).
There is a short but important literature on object allocation problem with non-quasilinear
preferences. Baisa (2016) considers the single object model and allows for randomization with
non-quasilinear preferences. He introduces a novel mechanism in his setting and studies its
optimality properties (in terms of revenue maximization). We do not consider randomizationand our solution concept is different from his. Further, ours is a model with multiple objects.
The literature with non-quasilinear preferences and multiple objects have traditionally
looked at Pareto efficient mechanisms. As discussed earlier, the closest paper is Morimoto andSerizawa (2015) who consider the same model as ours. They characterize the MWEP mechanism using Pareto efficiency, individual rationality, incentive compatibility, and no subsidy
when the domain includes all classical preferences - see an extension of this characterization
in a smaller domain in Zhou and Serizawa (2018). Similar characterizations are also available
for other settings: Sakai (2008, 2013b,a) provide such characterizations in the single object
auction model; Saitoh and Serizawa (2008); Ashlagi and Serizawa (2012); Adachi (2014) inthe homogeneous object auction model with unit demand preferences. Pareto efficiency andthe complete class of classical preferences play a critical role in pinning down the MWEP
mechanism in these papers. As we point out in Section 5, even in the quasilinear domain ofpreferences, there are desirable mechanisms satisfying no subsidy which are different from
the MWEP mechanism. By imposing revenue maximization as an objective instead of Pareto
efficiency, we get the MWEP mechanism in our model. Pareto efficiency is obtained as animplication (Corollaries 3 and 4). Finally, our results work for not only the complete classof classical preferences, but for a large variety of domains, such as the class of all quasilinear preferences, one including all non-quasilinear preferences, one including all preferences
exhibiting positive income effects, etc.
Tierney (2019) considers axioms like no discrimination, welfare continuity, and somestronger form of strategy-proofness to give various characterizations of the MWEP mechanism with reserve prices in the quasilinear domain. Using our result, he shows that in thequasilinear domain, the MWEP mechanism is the unique mechanism satisfying strategyproofness, no-discrimination, individual rationality, no wastage, and welfare continuity.

41

References
Adachi, T. (2014): “Equity and the Vickrey allocation rule on general preference domains,”
Social Choice and Welfare, 42, 813–830.
Alkan, A. and D. Gale (1990): “The core of the matching game,” Games and Economic
Behavior, 2, 203–212.
Andersson, T. and L.-G. Svensson (2014): “Non-Manipulable House Allocation With
Rent Control,” Econometrica, 82, 507–539.
Aristotle (1995): Politics, Oxford World’s Classics, translated by Barker E. and revisedby Stalley, R. F.
Armstrong, M. (1996): “Multiproduct nonlinear pricing,” Econometrica, 64, 51–75.
——— (2000): “Optimal multi-object auctions,” The Review of Economic Studies, 67, 455–
481.
Ashenfelter, O. and K. Graddy (2003): “Auctions and the price of art,” Journal of
Economic Literature, 41, 763–787.
Ashlagi, I. and S. Serizawa (2012): “Characterizing Vickrey Allocation Rule byAnonymity,” Social Choice and Welfare, 38, 531–542.
Ausubel, L. M. and P. Cramton (1999): “The optimality of being efficient: Designing
auctions,” Working Paper, University of Maryland.
Ausubel, L. M. and P. Milgrom (2002): “Ascending auctions with package bidding,”
Frontiers of Theoretical Economics, 1, 1–42.
Baisa, B. (2016): “Auction design without quasilinear preferences,” Theoretical Economics,
12, 53–78.
——— (2019, Forthcoming): “Efficient Multi-unit Auctions for Normal Goods,” Theoretical
Economics.
Barbera, S. and M. Jackson (1995): “Strategy-proof Exchange,” Econometrica, 63,
51–87.

42

Bikhchandani, S., S. Chatterji, R. Lavi, A. Mualem, N. Nisan, and A. Sen(2006): “Weak Monotonicity Characterizes Deterministic Dominant Strategy Implementation,” Econometrica, 74, 1109–1132.
Bikhchandani, S. and J. M. Ostroy (2006): “From the assignment model to combinatorial auctions,” in Combinatorial Auctions, ed. by P. Cramton, Y. Shoham, and
R. Steinberg, Cambridge, MA: MIT Press, chap. 8.
Binmore, K. and P. Klemperer (2002): “The biggest auction ever: The sale of the
British 3G telecom licences,” The Economic Journal, 112, C74–C76.
Blumrosen, L. and N. Nisan (2007): “Combinatorial auctions,” in Algorithmic Game
Theory, ed. by N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Cambridge:
Cambridge University Press, chap. 28, 699–716.
Briest, P., S. Chawla, R. Kleinberg, and S. M. Weinberg (2010): “Pricing randomized allocations,” in Proceedings of the twenty-first annual ACM-SIAM symposium on
Discrete Algorithms, Society for Industrial and Applied Mathematics, 585–597.
Bulow, J. and P. Klemperer (1996): “Auctions versus negotiations,” The American
Economic Review, 86, 180–194.
Cai, Y., C. Daskalakis, and S. M. Weinberg (2012): “Optimal multi-dimensional
mechanism design: Reducing revenue to welfare maximization,” in Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, IEEE, 130–139.
Carroll, G. (2016): “Robustness and separation in multidimensional screening,” Forthcoming, Econometrica.
Chawla, S., J. D. Hartline, D. L. Malec, and B. Sivan (2010a): “Multi-parametermechanism design and sequential posted pricing,” in Proceedings of the forty-second ACM
symposium on Theory of computing, ACM, 311–320.
Chawla, S., D. Malec, and B. Sivan (2015): “The power of randomness in bayesian
optimal mechanism design,” Games and Economic Behavior, 91, 297–317.
Chawla, S., D. L. Malec, and B. Sivan (2010b): “The power of randomness in bayesian
optimal mechanism design,” in Proceedings of the 11th ACM conference on Electroniccommerce, ACM, 149–158.
43

Daskalakis, C., A. Deckelbaum, and C. Tzamos (2017): “Strong duality for a
multiple-good monopolist,” Econometrica, 85, 735–767.
Deb, R. and M. Pai (2016): “Discrimination via symmetric auctions,” American Economic
Journal: Microeconomics, 9, 275–314.
Demange, G. and D. Gale (1985): “The strategy structure of two-sided matching markets,” Econometrica, 53, 873–888.
Demange, G., D. Gale, and M. Sotomayor (1986): “Multi-item auctions,” The Journalof Political Economy, 94, 863–872.
Eden, A., M. Feldman, O. Friedler, I. Talgam-Cohen, and S. M. Weinberg(2017): “The competition complexity of auctions: A Bulow-Klemperer result for multidimensional bidders,” in Proceedings of the 18th ACM conference on Electronic commerce,
ACM.
Gershkov, A., J. K. Goeree, A. Kushnir, B. Moldovanu, and X. Shi (2013): “Onthe equivalence of Bayesian and dominant strategy implementation,” Econometrica, 81,
197–220.
Gul, F. and E. Stacchetti (1999): “Walrasian equilibrium with gross substitutes,” Journal of Economic Theory, 87, 95–124.
Hart, S. and N. Nisan (2019): “Selling multiple correlated goods: Revenue maximizationand menu-size complexity,” Journal of Economic Theory, 183, 991–1029.
Hart, S. and P. J. Reny (2015): “Maximal revenue with multiple goods: Nonmonotonicity and other observations,” Theoretical Economics, 10, 893–922.
Holmstrom, B. (1979): “Groves’ Scheme on Restricted Domains,” Econometrica, 47, 1137–
1144.
Hu, A., S. A. Matthews, and L. Zou (2017): “Low reserve prices in auctions,” Working
paper, University of Pennsylvania.
Jehiel, P. and L. Lamy (2015): “On absolute auctions and secret reserve prices,” The
RAND Journal of Economics, 46, 241–270.

44

Jehiel, P., B. Moldovanu, and E. Stacchetti (1999): “Multidimensional mechanism
design for auctions with externalities,” Journal Economic Theory, 85, 258–293.
Kazumura, T., D. Mishra, and S. Serizawa (2017): “Mechanism design without quasilinearity,” ISER Discussion paper No. 1001.
Kazumura, T. and S. Serizawa (2016): “Efficiency and strategy-proofness in object
assignment problems with multi-demand preferences,” Social Choice and Welfare, 47, 633–
663.
Klemperer, P. (2002): “What really matters in auction design,” Journal of Economic
Perspectives, 16, 169–189.
Krishna, V. (2009): Auction theory, Academic press.
Krishna, V. and E. Maenner (2001): “Convex potentials with an application to mechanism design,” Econometrica, 69, 1113–1119.
Krishna, V. and M. Perry (1998): “Efficient mechanism design,” Available at SSRN
64934.
Leonard, H. B. (1983): “Elicitation of honest preferences for the assignment of individuals
to positions,” The Journal of Political Economy, 91, 461–479.
Manelli, A. M. and D. R. Vincent (2006): “Bundling as an optimal selling mechanism
for a multiple-good monopolist,” Journal of Economic Theory, 127, 1–35.
——— (2007): “Multidimensional mechanism design: Revenue maximization and themultiple-good monopoly,” Journal of Economic Theory, 137, 153–185.
——— (2010): “Bayesian and dominant-strategy implementation in the independent privatevalues model,” Econometrica, 78, 1905–1938.
McAfee, R. P. and J. McMillan (1987): “Auctions and bidding,” Journal of Economic
Literature, 25, 699–738.
——— (1996): “Analyzing the airwaves auction,” Journal of Economic Perspectives, 10,
159–175.
Milgrom, P. and I. Segal (2002): “Envelope theorems for arbitrary choice sets,” Econometrica, 70, 583–601.
45

Morimoto, S. and S. Serizawa (2015): “Strategy-proofness and efficiency with nonquasi-linear preferences: A characterization of minimum price Walrasian rule,” Theoretical
Economics, 10, 445–487.
Moulin, H. and S. Shenker (1992): “Serial cost sharing,” Econometrica, 60, 1009–1037.
Myerson, R. B. (1981): “Optimal auction design,” Mathematics of Operations Research,
6, 58–73.
Rochet, J. C. (1987): “A Necessary and Sufficient Condition for Rationalizability in a
Quasi-linear Context,” Journal of Mathematical Economics, 16, 191–200.
Rochet, J.-C. and P. Choné (1998): “Ironing, sweeping, and multidimensional screening,” Econometrica, 66, 783–826.
Roughgarden, T., I. Talgam-Cohen, and Q. Yan (2012): “Supply-limiting mechanisms,” in Proceedings of the 13th ACM Conference on Electronic Commerce, ACM,
844–861.
——— (2015): “Robust auctions for revenue via enhanced competition,” Tech. rep., Working
paper.
Saitoh, H. and S. Serizawa (2008): “Vickrey allocation rule with income effect,” Economic Theory, 35, 391–401.
Sakai, T. (2008): “Second price auctions on general preference domains: Two characterizations,” Economic Theory, 37, 347–356.
——— (2013a): “Axiomatizations of second price auctions with a reserve price,” International
Journal of Economic Theory, 9, 255–265.
——— (2013b): “An equity characterization of second price auctions when preferences may
not be quasilinear,” Review of Economic Design, 17, 17–26.
Shapley, L. S. and M. Shubik (1971): “The assignment game I: The core,” International
Journal of Game Theory, 1, 111–130.
Skreta, V. (2015): “Optimal auction design under non-commitment,” Journal of Economic
Theory, 159, 854–890.

46

Sprumont, Y. (1991): “The division problem with single-peaked preferences: A characterization of the uniform allocation rule,” Econometrica, 59, 509–519.
——— (2013): “Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms,” Journal of Economic Theory, 148, 1102–1121.
Thanassoulis, J. (2004): “Haggling over substitutes,” Journal of Economic Theory, 117,
217–245.
Thirumulanathan, D., R. Sundaresan, and Y. Narahari (2017): “On optimal mechanisms in the two-item single-buyer unit-demand setting,” arXiv preprint
arXiv:1705.01821.
Tierney, R. (2019): “Pairwise incentives and lattice optimality in matching with transfers,”
Mimeo.
Varian, H. R. (1974): “Equity, envy, and efficiency,” Journal of Economic Theory, 9, 63–91.
Vohra, R. V. (2011): Mechanism Design: A Linear Programming Approach, Cambridge
University Press.
Zhou, Y. and S. Serizawa (2018): “Strategy-proofness and efficiency for non-quasi-linear
and common-tiered-object preferences: Characterization of minimum price rule,” Gamesand Economic Behavior, 109, 327–363.

47

A

Proof of Claim 3

Before we start the proof of Claim 3, we point out a technical property of non-negative
income effect preferences. The claim below shows a form of monotonicity of demand setswith non-negative income effect preferences.
Claim 4 Let p, p0 ∈ R3+ be price vectors such that p0a = p0b < pa = pb . For each Ri ∈ R+ , if
D(Ri , p) ∩ M 6= ∅, then D(Ri , p0 ) ⊆ D(Ri , p).
Proof :Let D(Ri , p) ∩ M 6= ∅. Then, by p0a = p0b < pa = pb , 0 ∈/ D(Ri , p0 ). Assume forcontradiction that D(Ri , p0 )\D(Ri , p) 6= ∅. Then, by 0 ∈/ D(Ri , p0 ), without loss of generality,
let a ∈ D(Ri , p0 ) and a ∈/ D(Ri , p).
By a ∈ D(Ri , p0 ) and p0b < pb , (a, p0a ) Ri (b, p0b ) Pi (b, pb ). This implies p0a < V Ri (a, (b, pb )).
Thus, δ := V Ri (a, (b, pb ))−p0a > 0. By Ri ∈ R+ and δ > 0, (b, pb −δ) Ri (a, V Ri (a, (b, pb ))−δ).
By D(Ri , p) ∩ M 6= ∅ and a ∈/ D(Ri , p), we have b ∈ D(Ri , p) and (b, pb ) Pi (a, pa ).
The latter implies V Ri (a, (b, pb )) < pa = pb . Thus, pb − δ = pb − (V Ri (a, (b, pb )) − p0a ) >pb − (pb − p0a ) = p0a = p0b .
By the definition of δ, V Ri (a, (b, pb )) − δ = p0a . Thus by pb − δ > p0b , (b, p0b ) Pi (b, pb −δ) Ri (a, V Ri (a, (b, pb )) − δ) = (a, p0a ). This contradicts a ∈ D(Ri , p0 ).

Proof of Claim 3
Proof : Let R ∈ (R+ )4 and S(R) := {i ∈ N : R is discounting combination for i}. If S(R)is empty, then the claim follows because Z min (R) is non-empty. As we discussed just above
Claim 3, if S(R) is non-empty, then |S(R)| ≤ 2. Further, if S(R) = {i, j}, then R is a
discounting combination for i and j with respect to the same discounting combination. So,
we consider two cases.
Case 1. S(R) = {i, j}. Note that there is a common discounting combination T ∈ T for
agents i and j. By Claim 2, we have pmin (R) = pT . Since R is a discounting combination
for two agents, for every k ∈ N = {1, 2, 3, 4}, we must have Rk ∈ T with Ri = Rj . Thus,
by Definition 11 , for every k ∈ N = {1, 2, 3, 4}, D(Rk , pT ) = {0, a, b}, and D(Ri , pT ) =D(Rj , pT ) = {a, b}.
Consider an object allocation (a1 , a2 , a3 , a4 ) such that ai , aj ∈ {a, b} and for each k ∈N \ {i, j}, ak = 0. Then, (a1 , a2 , a3 , a4 ) satisfies Conditions (1) and (2) of the claim for this48

case.
Case 2. S(R) = {i}. Let the discounting combination of i be T := {Rk : k 6= i} ∈ T . By
Claim 2, we havepmin (R) = pT .

(4)

Also, by (b) of Definition 11, we have
Dk (Rk , pT ) = {0, a, b}k ∈ N \ {i}.

(5)Consider an object allocation (a1 , a2 , a3 , a4 ) such that ai ∈ D(Ri , pT ) and {a1 , a2 , a3 , a4 } ={0, a, b}. Then, since S(R) = {i}, the object allocation (a1 , a2 , a3 , a4 ) satisfies Condition (1)of the claim. To show Condition (2) of the claim, we consider two subcases.
Case 2a. Suppose D(Ri , pT ) ∩ M 6= ∅. Then, by Claim 4 we get ai ∈ D(Ri , pT ) ⊆D(Ri , pT ). Thus, by Equations (4) and (5), we have ((a1 , pTa1 ), . . . , (a4 , pTa4 )) ∈ Z min (R).
Thus, (a1 , a2 , a3 , a4 ) also satisfies Condition 2.
/ S(R).
Case 2b. Suppose D(Ri , pT ) ∩ M = ∅, i.e., D(Ri , pT ) = {0}. Choose any k ∈Then, k 6= i. Consider any object allocation (b1 , b2 , b3 , b4 ) satisfying {b1 , b2 , b3 , b4 } = {0, a, b}
such that bk = ak and bi = 0. By D(Ri , pT ) = {0}, by Equations (4) and (5), we get((b1 , pTb1 ), · · · , (b4 , pTb4 )) ∈ Z min (R). Thus, (a1 , a2 , a3 , a4 ) also satisfies Condition 2.
This exhausts all the cases and completes the proof.

49



B

Supplementary Appendix

The supplementary appendix contains two sections. In the first section, we provide a desirable mechanism satisfying no subsidy on the quasilinear domain. This mechanism is not
the MWEP mechanism. In the second section, we modify the first-price auction so that it
satisfies equal treatment of equals.

B.1 Non-MWEP desirable mechanisms in quasilinear domain
We reproduce a desirable mechanism satisfying no subsidy from Tierney (2019). The mechanism is defined for a simple case of three objects: M := {a, b, c} and five agents: N :={1, 2, 3, 4, 5}. Before formally defining the mechanism, we emphasize two points: (1) the
mechanism we define works similar to the family of mechanisms defined in Section 5, but
a careful look will reveal that there are significant differences; (2) even though we give one
desirable mechanism satisfying no subsidy in the quasilinear domain, it can be extended to a
family of desriable mechanisms satisfying no subsidy (containing the mechanism of Tierney(2019) but excluding the MWEP mechanism). We elaborate on these two points at the endof this section.
To define this mechanism formally, first we pick up four quasi-linear preferences to specify
a “discounting combination”. This is shown in Table 2. Denote the quasilinear preference
corresponding to valuation functions v α , v β , v γ , v λ as Rα , Rβ , Rγ , Rλ respectively.
a

b

c

vα

2

3

4

v

β

2

3



v

γ



3

4

vλ

2



4

Table 2: Four quasilinear preferences -  > 0 but arbitrarily close to zero
Denote T ≡ {Rα , Rβ , Rγ , Rλ }. The mechanism we describe works in the class of allquasilinear preferences RQ . For any i ∈ N , we say a profile of preferences R ≡ (R1 , . . . , R5 ) ∈(RQ )5 is a discounting combination for agent i if the preferences of agents other thanagent i coincide with T , i.e., {Rj : j 6= i} = T . We say a preference profile R ∈ (RQ )5 is
discounting if R is a discounting combination for some agent i.

50

Before describing the mechanism, we make a comment about discounting preference profiles.
min
Claim 5 If R ∈ (RQ )5 is discounting, pmin(R) = 3, pmin
= 4.
a (R) = 2, pb
cProof : Consider the suggested price vector p with pa = 2, pb = 3, pc = 4. If R is discounting,at least four agents have the null object in their demand set at p. Further, each object isdemanded by some agent at p. Hence, p is clearly a WEP. To see that it is the minimum
WEP, consider a price vector p0 ≤ p. In that case, if price of at least two objects are lower
at p0 than p, then there are at least four agents who do not demand the null object at p0 .
Since the number of objects is only three, p0 cannot be a WEP. Hence, price of exactly one
object, say x, is lower at p0 than p. But then, |{i ∈ N : {x} = D(Ri , p)}| > 1, contradicting
the fact p0 is a WEP.



We now give the analogue of Claim 3 without a proof.
Claim 6 For each R ∈ (RQ )5 , there exists an object allocation (a1 , . . . , a5 ) such that {a1 , . . . , a5 } =L and for each i ∈ N ,1. if R is a discounting combination for agent i with {Rj : j 6= i} = T , then ai ∈D(Ri , pT ), where pTa = 1, pTb = 2, pTc = 3,
2. if R is not a discounting combination for agent i, then there exists a minimum Walminminrasian equilibrium price allocation ((b1 , pmin(R) suchb1 (R)), . . . , (b5 , pb5 (R))) ∈ Z

that bi = ai .
Proof : Let R ∈ (R+ )5 and S(R) := {i ∈ N : R is discounting combination for i}. If S(R)is empty, then the claim follows because Z min (R) is non-empty. If S(R) is non-empty, then|S(R)| ≤ 2 by the definition of discounting combination. So, we consider two cases.
Case 1. S(R) = {i, j}. Since R is a discounting combination for two agents, for every k ∈ N ,we must have Rk ∈ T . Also, Ri = Rj ∈ T and by definition of T and pT , there must exist two
objects in M , say {x, y}, such that {x, y} ⊆ D(Ri , pT ) = D(Rj , pT ). Let M \ {x, y} = {z}and k be an agent such that z ∈ D(Rk , pmin (R)) – Claim 5 and Definition of T ensures thatsuch an agent k ∈ N \ {i, j} exists. Consider an object allocation (a1 , a2 , a3 , a4 , a5 ) such thatai , aj ∈ {x, y}, {ak } = z and for each h ∈ N \{i, j, k}, ah = 0. Thus, ai ∈ D(Ri , pT ) and aj ∈min
D(Rj , pT ). By Claim 5, pmin(R) = 3, pmin(R) = 4. Hence, ai ∈ D(Ri , pmin (R))
a (R) = 2, pb
c51

and aj ∈ D(Rj , pmin (R)). By definition, z ∈ D(Rk , pmin (R)). Also, for every Rh ∈ T ,min
we have 0 ∈ D(Rh , pmin (R)). As a result, the allocation ((a1 , pmin
a1 (R), . . . , (a5 , pa5 (R)))

is a minimum Walrasian equilibrium price allocation for R. Hence, the object allocation(a1 , a2 , a3 , a4 , a5 ) satisfies the assertions of the claim.
Case 2. S(R) = {i}. Hence, T = {Rk : k 6= i}. By Claim 5, pmin (R) is such thatfor every k ∈ N \ {i}, we have D(Rk , pmin (R)) = {0, x, y} for some x, y ∈ {a, b, c} and{a, b, c} ⊆ ∪k6=i D(Rk , pmin (R)). There are two subcases to consider now.
Case 2a.

Suppose D(Ri , pmin (R)) ∩ M 6= ∅.

Then, by the definition of quasilinear

preferences and pT , D(Ri , pT ) ⊆ D(Ri , pmin (R)). Further, since pT < pmin (R), we have0∈
/ D(Ri , pT ). Let x ∈ D(Ri , pT ) ⊆ D(Ri , pmin (R)) and {y, z} := M \ {x}. By {a, b, c} ⊆∪k6=i D(Rk , pmin (R)), there are j, k ∈ N \ {i} such that y ∈ D(Rj , pmin (R)) and z ∈D(Rk , pmin (R)). Then, bi = x, bj = y, bk = z, and bh = 0 for all h ∈/ {i, j, k} is an obmin
minject allocation such that ((b1 , pmin(R).
b1 (R)), . . . , (bn , pbn (R))) ∈ Z

Case 2b. Suppose D(Ri , pmin (R)) ∩ M = ∅, i.e., D(Ri , pmin (R)) = {0}. We also knowthat for every k ∈ N \ {i}, we have D(Rk , pmin (R)) = {0, x, y} for some x, y ∈ {a, b, c} and{a, b, c} ⊆ ∪k6=i D(Rk , pmin (R)). Since |N \ {i}| = 4, for every k ∈ N \ {i} and for every
min
min
(R)
x ∈ D(Rk , pmin (R)), there exists an allocation ((b1 , pminb1 (R)), . . . , (bn , pbn (R))) ∈ Z

such that bk = x. Hence, we can choose any ai ∈ D(Ri , pT ) and allocate objects in{0, a, b, c} \ {ai } among agents in N \ {i} in such a way that every agent in N \ {i} receives an object in the demand set and satisfy the assertions of the claim.
This exhausts all the cases and completes the proof.

Claim 6 shows that for discounting combination T , at every preference profile R ∈ (RQ )5 ,we can identify an object allocation satisfying (1) and (2) of Claim 6. Again, there may be
more than one such object allocation, but we identify one such object allocation at every R
and use it to formally define our mechanism.23
Definition 16 Given the discounting combination T , the MWEP mechanism with discounting combination T is denoted by f T and defined as follows: for every R ∈ (RQ )5 ,23

It is straightforward to extend this mechanism to a family of mechanisms by specifying a set of discounting

combinations as in Section 5.

52

(aT1 (R), . . . , aT5 (R)) is an object allocation satisfying Claim 6, and for every i ∈ N
pTT
if R is a discounting combination for i,ai (R)T
ti (R) =pmin (R) othewise,
aT
i (R)

where pT is the price vector defined as pTa = 1, pTb = 2, pTc = 3.
It is clear that f T satisfies individual rationality, equal treatment of equals, no wastage,and no subsidy. Just like Proposition 1, we can show that f T is strategy-proof (we skip thesimilar proof).
Proposition 2 The mechanism f T is strategy-proof.
Clearly, f T is not the MWEP mechanism since pT < pmin (R) whenever R is discounting. Hence, this establishes the fact that the MWEP mechanism is not the only desirable
mechanism satisfying no subsidy in the quasilinear domain.
Though the mechanism f T looks similar to the family of mechanisms defined in Section
5, there are significant differences. First, note that the mechanism in Definition 16 required
three objects and five agents (whereas the mechanism in Section 5 has two objects and four
agents). It is not possible to define the mechanism in Definition 16 with two objects. The
preferences in discounting combination T in this section are quasilinear preferences and they
are different than the discounting combinations specified in Definition 11. Further, unlike
property (b) of Definition 11, the discounting combination in this section does not require
existence of a price vector p̄T such that D(Ri , p̄T ) = L for each Ri ∈ T . Finally, note thatminat a discounting preference R in this section, pmin(R) = 3, pmin(R) = 4, whicha (R) = 2, pb
cis unlike in Section 5, where prices of both the objects were the same (this was required forstrategy-proofness with non-negative income effects). These differences indicate that the setof desirable mechanisms satisfying no subsidy is quite difficult to characterize in an arbitraryrich domain, and their characteristics vary from quasilinear domain to non-negative income
effect domain. Further, in the quasilinear domain, the set of desirable mechanisms satisfying
no subsidy is not a singleton, and quite rich.
As we discussed earlier, the mechanism f T can be extended to a family of mechanisms.
Indeed, all we need is a discounting combination which inherits some properties of the discounting combination T such that Claim 6 works. Each such discounting combination defines
a desriable mechanism satisfying no subsidy. This will contain as a special case f T . Eachmechanism in this family is desirable and satisfies no subsidy but it is not the MWEP
mechanism.
53

B.2 A modification of first-price auction
Consider an example with a single object and quasilinear preferences. With symmetric agents(i.e., agents having independent and identical distribution of values), a symmetric BayesianNash equilibrium strategy of the first price auction is increasing and continuous functionb(·) of valuations - for an exact expression of this function, see Krishna (2009). Consider
the mechanism such that for each valuation profile v = (v1 , . . . , vn ), the outcome of the bid
profile (b(v1 ), . . . , b(vn )) of the first price auction is chosen. Call this mechanism the firstprice based mechanism. It is Bayesian incentive compatible. Though, the first-price based
mechanism satisfies no subsidy, ex-post individual rationality, and no wastage, it fails tosatisfy ETE (unless, we break ties using uniform randomization). To see this, if two agents
have same value, they bid the same amount in the first-price based mechanism. If there is
no randomization to break ties, only one of those agents wins the object at his bid amount,whereas the other agent gets zero payoff. Since bid amount is less than the value in thefirst-price based mechanism, the winner gets positive payoff, and this violates ETE.
However, this can be rectified in two ways. First, whenever there is tie for the winningbid, all the winning agents get the object with equal probability. This introduces uniform
randomization, and ETE is now satisfied. Hence, the randomized first-price based mechanism
is Bayesian incentive compatible, satisfies ex-post IR, ETE, no wastage, and no subsidy.
Obviously, there are profiles of values where such a first-price based mechanism generates
more revenue than the Vickrey mechanism - winning bid in the first-price auction may behigher than the second highest value.24
An alternate approach to restoring ETE in the first-price based mechanism is to modify
it in a deterministic manner whenever there is a tie in the winning bids. Consider a profile ofvalues (v1 , . . . , vn ) such that more than one agent has bid the highest amount, say, B. Notethat this bid B corresponds to value b−1 (B). In such a case, we break the winning agent
tie deterministically by giving the object (with probability 1) to one of the winning agents.
Further, we ask him to pay his value b−1 (B). This ensures that the winner and the losing
agents all get a payoff of zero, and thus, it restores ETE. More formally, the mechanism
corresponding to this modified first-price based mechanism is the following.
1. Agents submit their values (v1 , . . . , vn ).
2. If there is a unique highest valued agent i, he is given the object and he pays b(vi ),where b is the unique symmetric Bayesian equilibrium bidding function of the first-price24

It is well known that the expected revenue from both the auctions is the same.

54

auction.
3. If there are more than one highest valued agents, then any one of them is given theobject and is asked to pay his value.
Notice that this only modifies the mechanism corresponding to the first-price auction atzero measure profiles of values. Hence, the modified first-price based mechanism is Bayesian
incentive compatible. Further, it is deterministic, satisfies ETE, no wastage, no subsidy, andex-post IR. Because of the same reasons given for first-price auction, there are profiles ofvalues where such a modified first-price based mechanism generates more revenue than the
Vickrey mechanism.
This illustrates that we cannot relax strategy-proofness to Bayesian incentive compatibility in our results.

55