Discussion Paper No. 1005

MECHANISM DESIGNWITHOUT QUASILINEARITY

Tomoya Kazumura
Debasis Mishra
Shigehiro Serizawa

June 2017

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

Mechanism design without quasilinearity ∗Tomoya Kazumura, Debasis Mishra, and Shigehiro Serizawa †June 8, 2017
Abstract
This paper studies a model of mechanism design with transfers where agents’ preferences need not be quasilinear. In such a model, (1) we characterize dominant strategy
incentive compatible mechanisms using a monotonicity property; (2) we establish arevenue uniqueness result: for every dominant strategy implementable allocation rule,
there is a unique payment rule that can implement it; and (3) we show that every
dominant strategy incentive compatible, individually rational, and revenue-maximizing
mechanism must charge zero transfer for the worst alternative (outside option). These
results are applicable in a wide variety of problems (single object auction, multiple
object auction, public good provision etc.) under suitable richness of type space. In
particular, our results can be applied to models where preferences of agents are arbitrarily small perturbations of quasilinear preferences and illustrate the (non)-robustness ofsome of the classic results in mechanism design with quasilinearity. We show various
applications of our results.
Keywords. incentive compatibility; individual rationality; monotonicity; non-quasilinear
preferences; revenue equivalence
JEL Code. D82, D44, D40.
∗

We are grateful to Sushil Bikhchandani, Juan Carlos Carbajal, Arunava Sen and participants at the Vanderbilt Mechanism Design Conference, 2016, Singapore Management University Workshop on Mechanism Design, 2016 for useful comments. We gratefully acknowledge financial support from the Joint Usage/ResearchCenter at ISER, Osaka University and the Japan Society for the Promotion of Science (Kazumura, 14J05972;
Serizawa, 15J01287, 15H03328, 15H05728). Part of this research was carried out when Debasis Mishra wasvisiting ISER, Osaka University. He acknowledges hospitality and support of ISER, Osaka University.
†
Kazumura: Graduate School of Economics, University of Tokyo, 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.jp

1

1 Introduction
Standard models of mechanism design with transfers assume that agents have quasilinear
preferences. This is highlighted in two recent books on this topic (Vohra, 2011; Borgers et al.,2015), which extensively describe the research frontier of mechanism design theory under thequasilinearity assumption. However, there are ample reasons to believe that agents in reallife may not have quasilinear preferences. For instance, consider the sale of a high-valued
object such as spectrum bandwidth in an auction. In such a setting, bidders usually havebudget constraints and often borrow from banks to pay the deficit amount. Such budget
constraints make the preferences non-quasilinear. More generally, income effects in many
problems lead to non-quasilinear preferences. One of the important reasons to study a modelof mechanism design without quasilinearity is its appeal of being “detail-free”. A model withquasilinearity assumes too much knowledge of the designer about the utility function of theagents. Hence, any result with this assumption will be vulnerable to the standard critiquethat the mechanism design is not detail-free.
A primary objective of this paper is to test the robustness of some of the foundational
results in mechanism design to the quasilinearity assumption. We analyze a model of mechanism design with transfers where preferences of agents over transfers need not be quasilinear. In particular, agents have classical (continuous and monotonic in transfers) preferences(types) over the entire set of consumption bundles - a consumption bundle consists of an alternative and a transfer amount. Thus, we consider a model without an explicit assumption
on the functional form of the utility functions of agents.
We provide two broad classes of results. The first class of results cover a variety ofimportant problems: single object auction, multiple object auction, public good provision
problem etc. If the type space has some richness, we provide a simple monotonicity condition
which along with the taxation principle is necessary and sufficient for a mechanism to be(dominant strategy) incentive compatible. 1 Further, we establish a revenue uniquenessresult: for every implementable allocation rule, there is a unique payment rule such thatthe corresponding mechanism is incentive compatible. Though we do not have revenue
equivalence in our model, our results can be interpreted as a counterpart of the monotonicity
and revenue equivalence results for the quasilinear type spaces.2
1

The taxation property simply requires that if the allocation decision at two types is the same, then thepayment decision must also be the same. While this terminology is somewhat non-standard, we borrow itfrom Vohra (2011).
2
We discuss the literature in detail later, but remind the reader that such characterization results inthe quasilinear type spaces form the core for any optimization exercise (for instance, expected revenue
maximization).

2

We discuss the precise richness of type space required for our results later. One of theinteresting type spaces where our results apply is the following. Take the set of all quasilinear
preferences in a standard mechanism design problem (say, in a multi-object auction problem)and perturb these set of preferences to allow for small (potentially, arbitrarily small) amountof non-quasilinearity. Our monotonicity characterization and revenue uniqueness theorem
apply to such type spaces. This shows how some of the benchmark results in mechanism
design change even with slight perturbation of quasilinearity.
We also study the implication of individual rationality without quasilinearity. To remind,
a straightforward consequence of revenue equivalence in quasilinear environment is that a arevenue maximizing incentive compatible and individually rational mechanism charges zerotransfer for allocating the worst alternative. We show robustness of this result in any nonquasilinear type space even though revenue equivalence may not hold.
In an application of these results, we explore how a generalization of the well known
VCG mechanism may not be dominant strategy incentive compatible in type spaces with
non-quasilinear preferences. We also provide a simple proof of dominant strategy incentive
compatibility of a celebrated mechanism due to Demange and Gale (1985) for a particularprivate good provision problem.
Our second set of results work for problems where each agent has two possible alternatives to be allocated: for instance, in a single object auction problem, every agent is either
allocated the object or not. Other examples include monopoly pricing, bilateral trade, deciding provision of a single public good etc. For these problems, we can relax our richness oftype space to an appropriate notion of convexity. Under such convex domain of preferences,
we provide an extension of the characterization in Myerson (1981) to type spaces without
quasilinearity. We apply this result to some specific problems.
Our first application of this result is a problem where a seller is selling an object to a single
buyer with non-quasilinear preferences. We derive the optimal (expected revenue maximizing
and individually rational) incentive compatible mechanism for this problem. Even though thepreference of the buyer is non-quasilinear, the optimal mechanism is similar to the quasilinear
case. In the optimal mechanism, the seller posts a (monopoly) reserve price (based on theprior) and the buyer buys the object if his willingness to pay is higher than the reserve price.
If the willingness to pay is less than the reserve price, then the buyer does not buy the object
and no transfers are made. We emphasize that these results are obtained even though we do
not have revenue equivalence in this framework.
We then analyze the problem of finding an expected revenue maximizing mechanism when
there are multiple buyers. Unlike the single buyer case, this problem becomes intractable3

to analyze. In a restricted class of mechanisms, we show some qualitative properties of the
optimal mechanism by using our two-alternative characterization.
Finally, we apply our results to the design of incentive compatible and anonymous mechanisms for allocating a single indivisible object among a set of agents. Anonymity requires aminimal amount of fairness. It is a compelling desiderata in fair allocation literature (Thomson, 2016). Under a mild condition on the payment of losing agents (agents who are notallocated the object), we provide a complete characterization of incentive compatible andanonymous mechanisms. These mechanisms are analogues of the Vickrey auction with agentspecific reserve prices - see a related auction and its analysis in Yamashita (2015) for thequasilinear model. Our characterization provides an axiomatic treatment of this class of
mechanisms using our results.
The rest of the paper is organized as follows. We introduce our model in Section 2 anddefine our type space in Section 3. We present our general results on monotonicity andrevenue uniqueness in Section 4. We present specific results for the two alternatives case in
Section 4.2 and compare our results to results with quasilinear preferences in Section 4.3.
We present the implications of incentive compatibility and individual rationality in Section
5. Section 6 presents various applications of our results. We discuss the connection of ourwork with the literature in Section 7. We conclude in Section 8. All our missing proofs arein the Appendix A at the end. Appendix B is supplementary and contains discussions andpreliminary results on optimal single object auction design with many agents.

2 The model
Let A be a finite set of alternatives. The (consumption) bundles are Z = A × R, where atypical element z ≡ (a, t) corresponds to alternative a ∈ A and transfer t ∈ R. Throughout
the paper, t will be interpreted as the amount paid by an agent to the designer, i.e., a negative
t will indicate that the agent receives a transfer of −t.
There is a single agent and his preference over Z is defined by a preference ordering overZ. The single agent assumption is for convenience and all our results extend to the multiple
agents case with dominant strategy as the solution concept. For any preference ordering R
over Z, we denote its strict part as P and the indifference part as I. A preference ordering
R over Z is classical if it satisfies the following assumptions:
1. Money monotonicity. for every t > t0 and for every a ∈ A, we have (a, t0 ) P (a, t).
2. Continuity. for every z ∈ Z, the sets {z 0 ∈ Z : z 0 R z} and {z 0 ∈ Z : z R z 0 } areclosed.
4

3. Possibility of compensation. for every z ∈ Z and for every b ∈ A, there exists t
and t0 such that z R (b, t) and (b, t0 ) R z.
A quasilinear preference is classical. In particular, a preference R is quasilinear if there
exists v ∈ R|A| such that for every a, b ∈ A and t, t0 ∈ R, (a, t) R (b, t0 ) if and only if
va − t ≥ vb − t0 . Usually, v is referred to as the valuation of the agent. The idea of valuation
may be generalized as follows for classical preferences.
Definition 1 The valuation of the agent with preference R for alternative a ∈ A at bundlez ∈ Z is defined as V R (a, z), which uniquely solves(a, V R (a, z)) I z.
So, V R (a, z) is the amount of transfer needed to make the agent (with preference R)
indifferent between consuming a with this transfer and z. An illustration of the valuationis shown in Figure 1. In the figure, the two horizontal lines correspond to two alternativesR
V R (a; z)

Better than zaWorse than zbz ≡ (b; t)Figure 1: Valuation at a preferencea and b. The horizontal lines indicate transfer amounts. Hence, the two lines are the entire
set of consumption bundles of the agent. A preference R 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 actuallyconsists of two points - z ≡ (b, t) and (a, V R (a, z)) as shown. Part of the curve in Figure
1 which lies outside the two consumption bundle lines is useless and has no meaning - it is
only displayed for convenience. Since we will use such figures throughout the paper, it isimportant to clarify these issues.
The next fact shows that a valuation always exists.
5Fact 1 (Kazumura and Serizawa (2016)) For every a ∈ A, for every z ∈ Z, and forevery classical R, the valuation V R (a; z) exists.
Proof : By finiteness, there exist transfers t, t0 such that (a, t) R z R (a, t0 ). By money
monotonicity and continuity, there must exist a unique t00 such that (a, t00 ) I z.

For any R and for any z ∈ Z, the valuations at bundle z with preference R is a vector
in R|A| and will be denoted by V R (z) ≡ {V R (a, z)}a∈A . The collection of all such (nonintersecting) indifference vectors for all z describe the preference ordering R.

3 Type space
In this section, we introduce our type space by specifying the richness required for our results.
Later, in Section 4, we establish our main results on this type space. Later, we show how
the richness required can be relaxed if |A| = 2.

3.1 Order respecting preferences
Fix a vector v ∈ R|A| . For every a, b ∈ A, if (a, va ) I (b, vb ), we say v belongs to anindifference class of preference R. The set of all vectors in R|A| which form an indifferenceclass of preference R is denoted by I(R). An equivalent way to describe R is to describe
I(R). Note that the elements of I(R) are distinct component-wise, i.e., for all v, v 0 ∈ I(R),va 6= va0 for all a ∈ A. Further, the elements of I(R) can be ordered (since indifference
vectors do not intersect), i.e., for every v, v 0 ∈ I(R), we have va > va0 if and only if vb > vb0
for all a, b ∈ A.
In almost all mechanism design problems, there is an exogenous preference over alternatives. For instance, in the multi-unit auction problem, getting k units at a price is preferred
to getting k 0 < k units at the same price (assuming free disposal). One way to model thisis to impose an exogenous ordering on the set of alternatives such that the alternative ofgetting k units is strictly preferred to k 0 units. To cover such large class of problems in ourtype space, we assume that there is a partial order  on the set of alternatives A. A vectorv ∈ R|A| respects  if for every a, b ∈ A, we havea  b ⇒ va > vb .
Definition 2 A preference relation R respects a strict partial order  if every v ∈ I(R)respects . A domain R of preference relations is order respecting if there exists  suchthat every R ∈ R respects .
6

We will usually denote an order respecting domain as R to indicate that every R ∈ R
respects the partial ordering .
c≻b≻a(c; t)R

V (c; (b; t))c
V R (c; (a; t))

V R (b; (c; t))(b; t)b
V R (b; (a; t))

V R (a; (c; t))a(a; t)V R (a; (b; t))Figure 2: Indifference vectors in order respecting domain
An equivalent way to state this domain restriction is the following. Consider R which
respects  and pick a ∈ A and t ∈ R. Then, for every b ∈ A, we have V R (b, (a, t)) < t, if
a  b. Hence, a domain R is order respecting if there exists  such that for every R ∈ R,
for every t ∈ R and every a, b ∈ A, we havea  b implies V R (b, (a, t)) < t.
In particular, if we arrange the alternatives according to the specified ordering  frombottom to top, the points along the indifference vector shift to the right as we move along .
This is illustrated in Figure 2 for three alternatives and the relation  defined as c  b  a(though  is shown to be a complete relation here, this need not be the case). The preference
relation R, whose indifference vectors are shown in Figure 2, respects .
Order respecting domains capture many interesting problems. They were introduced
in Bikhchandani et al. (2006) for quasilinear domains, and ours is an extension to nonquasilinear domains. 3 We list their applicability below:•  is empty. Then, there are no restrictions in preferences over alternatives. This captures public decision problems, where the set of alternatives is a set of public projects-  being empty represents the fact that there is no restriction on the preferences overpublic projects at a given transfer level.
3

There is a minor difference between our definition and the definition in Bikhchandani et al. (2006) they allow for indifferences in  but we do not allow indifferences. We make this assumption for technicalreasons.

7•  is a complete ordering. This can capture a situation where there is a set of homogeneous objects (set of alternatives in this example) and there is no restriction on thenumber of units that an agent can consume. More units are better for the agents. So,
alternatives can be completely ranked by the number of units. The complete ordering
can also capture common-object-ranking preferences in multi-object allocation problem
with unit demand (Zhou and Serizawa, 2016).
•  is a partial ordering. This can capture multiple heterogeneous objects sale (set ofalternatives in this example), where agents can have unit demand (Morimoto andSerizawa, 2015) or multiple demand as in combinatorial auctions with package bidding (Ausubel and Milgrom, 2002). If they have unit demand, then the only restrictionis that every object is strictly preferred to no object. If agents demand more than one
object, then the only restriction is that a subset of a set of objects is less preferredthan the original set of objects. The partial ordering can also capture “common-tieredobject-ranking” preferences in the unit demand model of Zhou and Serizawa (2016).

3.2 Richness
Our results will work in order respecting domains satisfying some amount of richness. To
understand our richness, first consider the set of quasilinear preferences respecting a partial
order  - denote this as Q . A typical preference R in Q is shown in Figure 3, where we
see that the indifference vectors of R are “parallel” to each other. In particular, if we considerv, v̂ ∈ I(R), then (vx − vy ) − (v̂x − v̂y ) = 0 for all x, y ∈ A. Hence, the domain Q satisfies
the richness that for any two vectors v, v̂ which are “parallel” to each other and respect ,there is a preference relation R ∈ Q such that v, v̂ ∈ I(R).
a≻b≻c≻d

a
b
c

v

v^
d
(vx − vy ) − (^vx − v^y ) = 0 8 x; yFigure 3: A quasilinear preference
Our richness requires a slight strengthening of this idea. Call two vector v, v̂ ∈ R|A| as8-parallel for some  > 0 if for every x, y ∈ A, we have|(vx − vy ) − (v̂x − v̂y )| < .
We say v, v̂ ∈ R|A| are pairwise consistent for  if (a) v, v 0 respect  and (b) either v > v̂ orv < v̂.
Suppose v and v̂ are pairwise consistent and  > 0 is very close to zero, then v and v̂ are-parallel means that they are “close to” parallel. In general, we will not require  to be close
to zero.
Definition 3 An order respecting domain R satisfies -two-point (TP ) richness forsome  > 0 if for every pair of -parallel v, v 0 ∈ R|A| which are pairwise consistent for ,
there is a preference R ∈ R such that v, v 0 ∈ I(R).
Our main results will use this richness in order respecting domains. The quasilinear domain of preferences Q does not satisfy this richness since it does not have enough variety
of preferences required by TP richness. Later, we give specific examples of order respecting domains that satisfy TP richness - this includes domains which are arbitrarily small
perturbations of Q . Below, we illustrate TP richness further though an example.
Pick any v and v̂ which are pairwise consistent and -parallel for some  > 0. First, it iseasy to see that there are infinitely many preferences R respecting  such that v, v̂ ∈ I(R)- this is because we have infinitely many ways to choose other indifference vectors. Ourcondition TP richness requires just one preference R respecting  to be part of the domainsuch that v, v̂ ∈ I(R). Next, we construct one specific preference R̄ respecting  andsatisfying v, v̂ ∈ I(R̄) - this is obviously not the only way to satisfy TP richness.
The preference R̄ is constructed by specifying the indifference vectors of R̄. For all v 00 < v,
we have v 00 ∈ I(R̄) if and only if vx00 − vy00 = vx − vy for all x, y ∈ A. For all v 00 > v̂, we havev 00 ∈ I(R̄) if and only if vx00 − vy00 = v̂x − v̂y for all x, y ∈ A. For all v ≤ v 00 ≤ v̂, we havev 00 ∈ I(R̄) if and only if there exists α ∈ [0, 1] such that v 00 = αv + (1 − α)v̂. Informally,
indifference vectors to the left of v are parallel to v, to the right of v̂ are parallel to v̂, and
it is a “convex combination” of indifference vectors of v and v̂ between v and v̂. It is clearthat R̄ exists and respects . A pictorial description of R̄ is given in Figure 4.

4 Monotonicity and incentive compatibility
We now define the notion of incentive compatibility we use. For the one agent model, we
refer to it as simply incentive compatibility, but when this is extended to the multi-agent
model, we will be using dominant strategy incentive compatibility.
9d≻b≻c≻a
Convex hull of v; v^vv^ Parallel to v^ dParallel to v

c

b

a
R̄
Figure 4: TP richness - construction of R̄

4.1 Incentive compatibility and revenue uniqueness
Let R be any subset of classical preferences - we will refer to R as the domain. A mechanism(f, p) is a pair, where f : R → A and p : R → R. Throughout, we will assume that f isonto - most of the results and their proofs can be modified in a straightforward way if f is
not onto.
The mechanisms we consider here are direct mechanisms and restriction to such mechanisms is due to the revelation principle.
Definition 4 A mechanism (f, p) is incentive compatible if for every R, R̂ ∈ R, wehave(f (R), p(R)) R (f (R̂), p(R̂)).
The following monotonicity property will be shown to be necessary for incentive compatibility.
Definition 5 A mechanism (f, p) is monotone if for every R, R̂ ∈ R with f (R) ≡ a and(f (R̂), p(R̂)) ≡ z, we have
V R (a, z) ≥ V R̂ (a, z).
10An illustration is shown in Figure 5. Take any pair of preferences R and R̂ and suppose the^R^

V R (a; z)

V R (a; z)R
a = f (R)^b = f (R)^z ≡ (b; p(R))

Figure 5: Illustration of monotonicity
mechanism chooses consumption bundle z at R̂. Then, monotonicity requires that valuation
for f (R) at z is larger for R than for R̂. There is another natural way to interpret themonotonicity condition. Suppose the mechanism chooses the alternative a at R. Now,
consider another preference R̂ such that V R̂ (a, z) > V R (a, z), where z does not involve
alternative a. In other words, agent’s liking for the outcome at R compared to z increases
from R to R̂. Then, monotonicity requires (f (R̂), p(R̂)) 6= z.
As we show later, this monotonicity condition collapses to the standard weak monotonicity
or 2-cycle monotonicity condition if the domain is the quasilinear type space - see Section
4.3 for detailed discussions. We show next that monotonicity along with a simple condition
on payments is equivalent to incentive compatibility.
We present this simple necessary condition for incentive compatibility next. It is usuallyreferred to as the “taxation principle”, and states that whenever the allocation decision of amechanism is the same at two preferences, the payment decision has to be the same.
Definition 6 A mechanism (f, p) satisfies the taxation principle if for every R, R0 withf (R) = f (R0 ), we have p(R) = p(R0 ).
An alternate way to state the taxation principle is the following.
Fact 2 A mechanism (f, p) satisfies the taxation principle if and only if there exists a map
κ : A → R such that for every R ∈ R , we have p(R) = κ(f (R)).
It is clear that incentive compatibility implies the taxation principle. We show below
monotonicity and taxation principle are sufficient for incentive compatibility.

11

Theorem 1 Suppose R is an order respecting domain satisfying TP  richness for some > 0, where  is some strict partial order over A. Let (f, p) be a mechanism defined overR . Then, the following statements are equivalent.
1. (f, p) is incentive compatible.
2. (f, p) is monotone and satisfies taxation principle.
Theorem 1 is the counterpart of monotonicity based characterizations found in the quasilinear domains - we discuss the precise connection in Section 4.3. Roughly, the counterpartof Theorem 1 will require monotonicity along with a revenue equivalence (envelope) formula,which is much stronger than taxation principle. In other words, in Theorem 1, we succeeded
to show that monotonicity and a weaker requirement of taxation principle are sufficient toobtain incentive compatibility in domains satisfying TP richness.
Since quasilinearity plays a crucial role to derive revenue equivalence formula, one might
expect that revenue equivalence does not hold without quasilinearity. In fact, we show thatrevenue uniqueness holds.
Theorem 2 Suppose R is an order respecting domain satisfying TP  richness for some > 0, where  is some strict partial order over A. If (f, p) and (f, p0 ) are two incentive
compatible mechanisms defined on R , then p = p0 .
The quasilinear type space does not satisfy TP richness, and hence, Theorems 1 and
2 do not apply to quasilinear type space. However, these theorems help us understandthe structure of incentive compatible mechanisms if the designer does not know the precise
nature preferences of the agent over consumption bundles.
In Section 6, we give some applications of Theorems 1 and 2 to specific problems.

4.2 Incentive compatibility with two alternatives
In this section, we focus on the case where |A| = 2. Besides covering a wider variety of applications, the two alternatives setting is important because it corresponds to a canonical classof models in mechanism design studied under quasilinearity assumption. Under quasilinearity, if there are two alternatives, valuation of one of the alternatives can always be scaled tozero and the only private information of an agent is his valuation for the other alternative.
As a result, the type of an agent becomes one-dimensional. One-dimensional type spaces are
ubiquitous in mechanism design literature, and their study parallels the single object auction

12

analysis in Myerson (1981). Hence, analysis of the two alternatives case can be interpreted
as an extension of the one-dimensional mechanism design to non-quasilinear preferences.
For simplicity, we represent the set of alternatives as A = {0, 1}. Given a classicalpreference relation R, we define the willingness to pay of an agent at transfer t as
W P (R, t) := V R (1; (0, t)) − t.
Notice that the reference consumption bundle is (0, t) - hence, willingness to pay W P (R, t) isthe extra transfer needed to make the agent indifferent between (0, t) and (1, t + W P (R, t)).
Since V R exists, W P (R, ·) exists.
Definition 7 A domain of preferences R satisfies WP-convexity if for every t ∈ R, theset {W P (R, t) : R ∈ R} is an interval.
We allow for the fact that the interval {W P (R, t) : R ∈ R} is open - for instance,
R or R++ . WP-convexity property is a much weaker requirement than the TP richness
condition used in Theorem 1. For instance, the set of all quasilinear preferences satisfy
WP-convexity, but it will not satisfy TP richness. Further, note that we do not need orderrespecting domains here. We now provide a characterization which is closer to the standard
Myersonian results in quasilinear domains.
Theorem 3 Suppose A = {0, 1} and R satisfies WP-convexity. If (f, p) is a mechanism
defined on R, then the following statements are equivalent.
1. (f, p) is incentive compatible.
2. There exists a real number τ 0 such that(a) WP-monotonicity. for every R, R0 ∈ R with f (R) = 1, we have
h
i
0
0
0
W P (R , τ ) > W P (R, τ ) ⇒ f (R0 ) = 1.
(b) Payment formula. for every R ∈ R,
p(R) = τ 0 + f (R) · τ 1 ,where τ 1 := inf{W P (R0 , τ 0 ) : R0 ∈ R, f (R0 ) = 1}.
We make some remarks about Theorem 3.

13

1. Though Condition 2(b) in Theorem 3 is stronger than Condition 2(b) in Theorem
1, WP-monotonicity is weaker than monotonicity. We discuss this issue in detail in
Section 4.3, where we also emphasize the fact that WP-monotonicity and monotonicity
are equivalent in quasilinear type space.
2. Theorem 3 hints at dramatic reduction in the informational requirement of mechanisms
in the two-alternatives model. Every mechanism must announce a pair of numbers - τ 0
and τ 1 . Then, it only elicits W P (R, τ 0 ) information from the agent. If W P (R, τ 0 ) > τ 1 ,then the object is allocated at price τ 0 + τ 1 . If W P (R, τ 0 ) < τ 1 , then the object is notallocated and the agent pays τ 0 .
3. Condition 2(b) should not be confused as a revenue equivalence result. This is because
the monotonicity condition depends on the choice of τ 0 . To be more precise, suppose
we have an incentive compatible mechanism (f, p) defined by f and τ 0 , then τ 1 andp are determined by these two parameters. If we fix f and consider τ̄ 0 := τ 0 + ∆ forsome ∆ ∈ R, does that define a new incentive compatible mechanism? The answer is
not clear. This is because though f is satisfies monotonicity at τ 0 , it may fail to be
monotone at τ̄ 0 . This is not an issue in the quasilinear type space because WP values
do not depend on transfer amount, and hence, if f satisfies monotonicity at τ 0 , it alsosatisfies at τ̄ 0 .
To highlight the last remark further, we show below that in the two-alternative model,
the revenue uniqueness result can be restored under different richness requirements than
Theorem 2. To do so, we introduce the notion of positive income effect. We define it using
the notion of willingness to pay. As transfer increases, positive income effect requires thatwillingness to pay must decrease.
Definition 8 A classical preference R exhibits positive income effect if for all t, t0 ∈ Rwith t > t0 , we have W P (R, t0 ) > W P (R, t).
The set of all classical types with positive income effect is denoted as R++ .
We now state the revenue uniqueness result under positive income effect.
Theorem 4 Suppose A = {0, 1} and R ⊇ R++ . If (f, p) and (f, p0 ) are incentive compatible
mechanisms then p = p0 .

14

4.3 Comparison to quasilinear type space
We now formally compare our results to analogous results in the quasilinear type space.
The comparison below highlights how our results extend and generalize existing results withquasilinearity. As defined earlier, a quasilinear preference can be represented by a valuation vector in R|A| . Denote the valuation attached to quasilinear preferences R, R0 , R00 , . . .
as v, v 0 , v 00 , . . . respectively. Let V ⊆ R|A| be the domain of valuations in the quasilinear
preference domain. Notice that two valuation vectors which differ by the same constant ineach component represent the same preference over consumption bundles.
In describing the results from the quasilinear domain literature, we assume that A is
finite and the mechanisms are deterministic. But some of the results stated below also holdfor non-finite A and randomized mechanisms.
Monotonicity on quasilinear domain. Our monotonicity condition reduces to the following condition in quasilinear domains. Take two valuation vectors v, v 0 ∈ R|A| and denotethe underlying quasilinear preferences corresponding to them as R, R0 respectively. Consider
a mechanism (f, p) and denote f (R) = a and f (R0 ) = b. Note that0

V R (a, (b, p(R0 ))) = va − vb + p(R0 ) and V R (a, (b, p(R0 ))) = va0 − vb0 + p(R0 ).
0Hence, our monotonicity condition is: V R (a, (b, p(R0 ))) ≥ V R (a, (b, p(R0 ))), which is equivalent to requiring va − vb ≥ va0 − vb0 . This is the familiar (weak) monotonicity or 2-cycle
monotonicity condition from the quasilinear domain literature (Bikhchandani et al., 2006;
Saks and Yu, 2005; Ashlagi et al., 2010). Hence, in quasilinear domain, monotonicity of themechanism reduces to the monotonicity of the allocation rule f .
Mechanism characterization. The monotonicity condition becomes too weak in the quasilinear domain, and hence, the taxation principle needs to be significantly strengthened to be
sufficient to imply incentive compatibility. We report two results from quasilinear domains
to compare them with our results. The first result is due to Jehiel et al. (1999) and Myerson(1981) (for the single object auction environment) - we report a version of this result given
in Ashlagi et al. (2010), which can be shown using subgradient techniques of convex functions (Rockafellar, 1970). To state this fact, we slightly abuse notation to write a mechanism(f, p) on a quasilinear type space with domain of valuations V ⊆ R|A| as maps: f : V → A
and p : V → R.

15

Fact 3 (Jehiel et al. (1999); Ashlagi et al. (2010)) Suppose (f, p) is a mechanism defined on a convex domain of valuations V ⊆ R|A| . Then, the following statements are equivalent.
1. (f, p) is incentive compatible.
2. (a) f is monotone.
(b) for every v, v 0 ∈ V, we have0p(v) = p(v ) + [vf (v) − vf0 (v0 ) ] −Z 1

0

ψ v ,v (z)dz,

0v 0 ,v

where ψ (z) = (v − v 0 ) · If (v0 +z(v−v0 )) for all z ∈ [0, 1] and for every v 00 ∈ V, If (v00 )is the indicator vector in R|A| , where the component corresponding to f (v 00 ) is set
to 1 and all other components are zero.
Fact 3 generalizes analogous results for two alternatives case in Myerson (1981) - Myerson
develops this result in the single object auction framework. Statement 2(b) implies that if wehave two incentive compatible mechanisms with the same allocation rule, (f, p) and (f, p0 ),then p(v) = p0 (v) for some v implies that p = p0 . This is usually referred to as the revenue
equivalence formula or the envelope formula (Milgrom and Segal, 2002; Krishna and Maenner,2001). Contrast this to our Theorem 2, which states that in order respecting non-quasilinear
type spaces satisfying TP -richness for some  > 0, we have revenue uniqueness, i.e., if
we have two incentive compatible mechanisms (f, p) and (f, p0 ) using the same allocation
rule, then p = p0 . Thus, the conclusion of Theorem 2 is significantly stronger than revenue
equivalence.
We can contrast our Theorem 1 with Fact 3. Theorem 1 characterizes incentive compatibility by monotonicity of mechanism and the taxation principle. On the other hand, Fact
3 characterizes incentive compatibility using monotonicity of allocation rule and the revenue
equivalence formula, which is significantly stronger than the taxation principle. The richnessof our non-quasilinear type space allows us to use the monotonicity of the mechanism alongwith a simple condition on payments in Theorem 1 to characterize incentive compatibility.
Later, we show that arbitrarily small perturbation of quasilinear type space satisfies our richness condition. Theorems 1, 2, and Fact 3 show how the results change with such arbitrarily
small perturbations.
Allocation rule characterization. In the quasilinear domain, due to the separability(and linearity) of the payment from the allocation rule, one can focus attention on theimplementability question.
16

Definition 9 An allocation rule f is implementable if there exists a payment rule p suchthat (f, p) is incentive compatible.
In quasilinear domain, if we know that f is implementable, then due to Fact 3, there isan explicit way to compute payments using f (up to an additive constant). The following
fact answer the question: when is an allocation rule implementable?
Fact 4 (Saks and Yu (2005); Ashlagi et al. (2010)) Suppose closure of V is convex
and f is an onto allocation rule defined on V. Then, f is implementable if and only if it ismonotone.
Fact 4 was first shown for order respecting quasilinear domains in Bikhchandani et al.
(2006). Though Theorem 1 seems like an extension of their result to non-quasilinear domains,
it should not be confused as an analogue of Fact 4. There are two important differences:(1) Theorem 1 is a characterization of incentive compatible mechanisms using monotonicity of the mechanism and Fact 4 is a characterization of implementable allocation rules inquasilinear domains using monotonicity of allocation rule; (2) Theorem 1 uses richness of
non-quasilinear domain and it does not apply to quasilinear domains.
Monotonicity versus WP-monotonicity. The monotonicity condition is somewhat symmetric in quasilinear domain. Consider the same example as above. For R and R0 withf (R) = a, f (R0 ) = b, we have a pair of monotonicity conditions:0

V R (a, (b, p(R0 ))) ≥ V R (a, (b, p(R0 )))0V R (b, (a, p(R))) ≥ V R (b, (a, p(R))).
In quasilinear domain, both these conditions are equivalent to:va − vb ≥ va0 − vb0 .
This equivalence of the pair of monotonicity conditions need not hold in non-quasilinear
environment since R and R0 can be arbitrary. Note that WP-monotonicity in Theorem 3
only uses one side of monotonicity. Hence, WP-monotonicity in Theorem 3 is weaker thanthe monotonicity condition in Theorem 1. In quasilinear domain, monotonicity is equivalent
to WP-monotonicity, which is the condition identified in Myerson (1981).

5 Individual rationality
In this section, we investigate the implication of individual rationality along with incentive
compatibility in domain of classical preferences. We focus attention to order respecting
17

domains, though the result in this section holds beyond the order respecting domains. For
every , we assume the existence of a worst alternative in A according to , and denote it
by a0 . For instance, in the auctioning of one or more objects, a0 will refer to the alternative
where the agent is not assigned any object. For the public good provision problem, a0 may
refer to the alternative where no public good is provided.
We further assume that the outside option of the agent is (a0 , 0), i.e., get the alternativea0 at zero transfer.
Definition 10 A mechanism (f, p) is individually rational if for every R in the domain((f (R), p(R)) R (a0 , 0).
The following lemma gives necessary and sufficient conditions for individual rationality similar conditions are well known with quasilinear preferences.
Lemma 1 Suppose (f, p) is an incentive compatible mechanism. It is individually rational
if and only if for every R with f (R) = a0 , we have p(R) ≤ 0.
Proof : For every R with f (R) = a0 , individual rationality implies that (a0 , p(R)) R (a0 , 0).
This implies that p(R) ≤ 0. For the converse, consider any R. By ontoness of the mechanism,
there is some R0 such that f (R0 ) = a0 . Now, note that(f (R), p(R)) R (a0 , p(R0 )) R (a0 , 0),
where the first relation follows from incentive compatibility and the second relation follows
from the fact that p(R0 ) ≤ 0. Hence, (f, p) is individually rational.
In the quasilinear domain, a straightforward consequence of Lemma 1 is the following.
Take an incentive compatible and individually rational mechanism (f, p) and construct another mechanism (f, p̃) as follows: p̃(R) = p(R) − κ(a0 ) for all R, where κ(a0 ) (computed
using the taxation principle) is the payment of the worst alternative a0 in the mechanism(f, p). By Lemma 1, κ(a0 ) is non-positive, and hence, p̃(R) ≥ p(R) for all R. Further, inthe quasilinear domain, (f, p̃) remains incentive compatible. An immediate benefit of thisargument is that if we are interested in maximizing revenue among all incentive compatible
and individually rational mechanisms, we can look at those mechanisms which price theworst alternative at zero.
Unfortunately, the above argument fails in non-quasilinear type space since (f, p̃) may
not be incentive compatible without quasilinearity - for instance, in order respecting domains
satisfying TP richness, (f, p̃) cannot be incentive compatible due to our revenue uniqueness18

theorem (Theorem 2). Remarkably, the following result still holds in non-quasilinear typespaces.
Theorem 5 Let R be an order respecting domain with a0 being the worst element according
to . For every incentive compatible and individually rational mechanism (f, p) on R , there
is an incentive compatible and individually rational mechanism (f˜, p̃) on R such that
1. for every R with f˜(R) = a0 , we have p̃(R) = 0,
2. for every R, we have p̃(R) ≥ p(R).
Two important remarks are in order: (a) f and f˜ in Theorem 5 may be quite different
allocation rules - this is in contrast to quasilinear domains, where we could construct (f˜, p̃)such that f˜ = f ; (b) Theorem 5 does not require any assumption on richness of type space.
Theorem 5 thus assures us that even in non-quasilinear type space, if we are interested in
maximizing revenue among all incentive compatible and individually rational mechanisms,
we can look at those mechanisms which price the worst alternative at zero.
We formalize this implication to revenue maximizing mechanism in a general model witha domain satisfying TP richness now. The following lemma holds true in such domains.
Lemma 2 Suppose R satisfies TP richness. If (f, p) is a mechanism defined on R , thenit is incentive compatible if and only if for every R, R0 ∈ Rp(R) =

inf

V R̂ (f (R), (f (R0 ), p(R0 ))) =R̂:f (R̂)=f (R)sup

V R̂ (f (R), (f (R0 ), p(R0 ))).

R̂:f (R̂)=f (R0 )Now, fix the worst alternative a0 according to . Suppose (f, p) is an incentive compatible
mechanism in R (which satisfies TP richness). Then, by taxation principle, there is a map
κ : A → R such that t(R) = κ(f (R)) for all R ∈ R . Lemma 2 then implies that for any
a 6= a0 , we must haveκ(a) = inf V R̂ (a, (a0 , κ(a0 ))).
R̂:f (R̂)=a

Further, individual rationality implies κ(a0 ) ≤ 0 (Lemma 1). Finally, Theorem 5 implies
that if (f, p) is a revenue maximizing mechanism then it must set κ(a0 ) = 0 and hence, forall a 6= a0 , we must haveκ(a) = inf V R̂ (a, (a0 , 0)).
R̂:f (R̂)=a

While finding the revenue maximizing mechanism in this general model may be hard,
our results provide some properties of such a mechanism. For the simple (two alternative)

19

setting of single object allocation to an agent, we use these findings to derive the revenue
maximizing mechanism in Section 6.2.
Unfortunately, we do not know if this finding extends to a model with multiple agents- this is unlike Theorems 1, 2, and 3, which extend in a natural manner to a model withmultiple agents. The main difficulty in extending Theorem 5 to a model with multiple
agents is that when we change the allocation decision of one agent, it may require changes inallocation decision of other agents. As a result, even if we improve the revenue of one agent,
we may end up decreasing revenue from other agents. We discuss these difficulties in moredetail in the context of single object auction in Appendix B.

6 Applications
In this section, we give several applications of our results. We provide a brief preview ofthese applications.
In Section 6.1, we identify specific order respecting domains satisfying TP richness. By
applying Theorems 1 and 2, we show how foundational results in quasilinear type spaceschange when we consider type spaces which are arbitrarily small perturbations of quasilinear
type space.
In Section 6.2, we apply Theorem 3 to derive a revenue maximizing mechanism for aseller selling a single object to a single agent.
In Section 6.3, we consider the problem of allocating a single object to n agents using an anonymous and dominant strategy incentive compatible mechanism. We propose
an extension of a Groves class of mechanisms to non-quasilinear preferences for this typespace, and apply Theorem 3 to characterize it using anonymity, dominant strategy incentive
compatibility, and a condition on the payment of losing agents.
In Section 6.4, we consider the problem of allocating m objects to n agents, each of whom
can be assigned at most one object (unit demand preferences). Using our Theorem 1, weshow that a naive generalization of the Vickrey-Clarke-Groves (VCG) mechanism may not
be dominant strategy incentive compatible if preferences of agents are not quasilinear. We
then provide a simple proof of dominant strategy incentive compatibility of a mechanism
proposed by Demange and Gale (1985) in this problem.

6.1 Perturbations of quasilinearity
As we had observed earlier, Theorems 1 and 2 do not apply to quasilinear domains. We
show below that these results apply to domains that are “perturbations” of the quasilinear
20

domain. This shows that even with arbitrarily small perturbation of quasilinear domain, we
get revenue uniqueness instead of revenue equivalence. Further, the nature of monotonicity
characterization changes even with a slight perturbation of quasilinearity.
We now define our notion of a perturbation. Fix a partial order  over A. Let a0 ∈ A be
the minimal element with respect to  - if  is empty, then set a0 equal to some alternative.
Let R and R0 be any pair of preferences respecting . Then, define the distance between
R and R0 as
0d(R, R0 ) := sup max |V R (a, (a0 , t)) − V R (a, (a0 , t))|.
t

a6=a0

Note that d(R, R0 ) ∈ R+ ∪ {+∞}. Further, d(R, R0 ) = d(R0 , R) and d(R, R0 ) = 0 if and only
if R = R0 .
Let D be the set of all classical preferences respecting . Let R ⊆ D be some orderrespecting domain. For every  > 0, define the -perturbation of R as
R, := {R ∈ D : ∃R0 ∈ R with d(R, R0 ) < .}.
Informally, R, contains all preferences in D which are within  distance from some
preference in R . Notice that R ⊂ R, .
We now describe a specific R such that R, satisfies TP -richness. This domain isderived from a problem with budget constrained agents but includes as a special case thequasilinear domain of preferences. Consider an agent who has a budget constraint B and if
the payment is less than B, then his preference is quasilinear, and is described by a valuation
vector ν ∈ R|A| which respects a partial order  over A. The interpretation of B is standard:
for any transfer above B, the agent borrows the extra amount with an interest rate r ≥ 0.
The interest rate r is fixed for the problem, and it is possible that r = 0 (in which case,
it corresponds to the problem without any budget constraint, and the domain becomes thequasilinear domain). Formally, the utility of the agent for any alternative a ∈ A and fortransfer t ≤ B isν(a) − t,and for transfer t > B isν(a) − B − (t − B)(1 + r).
Denote by R
r the set of all preferences representable by such (ν, B). As indicated aboveR
0 is the set of quasilinear preferences respecting . For an arbitrary r ≥ 0 and  > 0, the,
-perturbation of the domain R
r is denoted by Rr . Theorems 1 and 2 give us the following
result.

21

Proposition 1 Let (f, p) be a mechanism defined over R,r , where r ≥ 0 and  > 0. Then,the following statements are equivalent.
1. (f, p) is incentive compatible.
2. (f, p) is monotone and satisfies taxation principle.
Further, if (f, p) and (f, p0 ) are two incentive compatible mechanisms defined on R,r , thenp = p0 .
The proof of Proposition 1 shows that R,satisfies TP -richness, and then the resultrfollows from Theorems 1 and 2. Proposition 1 is showing that even with slight perturbationof quasilinearity, how the standard results from the quasilinear domain will change.

6.2 Screening with non-quasilinearity
The next two applications are for specific models of a private good provision. Consider aproblem where a seller is selling a single indivisible object to a single buyer - the seller has zeroutility for the object. Since the outcome is deterministic (either the buyer gets the object ornot), the set of alternatives can be written as A = {0, 1}, where 0 represents the alternative
where the buyer does not get the object and 1 represents the alternative where he gets theobject. The set of outcomes is Z := A × R, and the buyer (agent) has classical preferences
over Z. We consider the order respecting domain of preferences with respect to the order1  0, i.e., for any classical preference R and any transfer t, we assume (1, t) P (0, t).
For any classical preference R, we remind that the willingness to pay of buyer type R at
t is
W P (R, t) := V R (1; (0, t)) − t∀ t ∈ R.

So, W P (R, t) is the amount that makes a buyer of type R indifferent between not getting
the object at transfer t and getting the object at transfer t + W P (R, t). Since 1  0 andevery R respecting , we have W P (R, t) > 0 for all R and for all t.
We now define the type space we work with in this model. We denote by Rc the set of
all order respecting classical preferences in this model.
Definition 11 A type space R ⊆ Rc satisfies strong WP-convexity if for every t ∈ R,
there exists βt > 0 such that
{W P (R, t) : R ∈ R} = (0, βt ).
22

Theorem 3 requires the type space to satisfy WP-convexity. Strong WP-convexity requires not only WP-convexity but also the fact that the interval of WPs at any t, must
be of the form (0, βt ), where βt > 0. Hence, the result in Theorem 3 can still be applied.
In quasilinear domain, this richness will boil down to requiring that the valuation of theagent for the object lies in an open interval with lower support at zero. The definition above
generalizes this richness to an arbitrary subset of classical type space.
Suppose R is the domain of preferences (type space). A mechanism (f, p) in this caseconsists of an allocation rule f : R → {0, 1} and p : R → R. In this section, we investigate
the issue of expected revenue maximizing mechanism design. We search over all incentive
compatible and individually rational mechanisms.
Definition 12 A mechanism (f, p) is individually rational if for every R ∈ R,
(f (R), p(R)) R (0, 0).
To compute expected payment from a mechanism, we need to have a prior over the typesof the agents. By Theorem 3, a mechanism only needs information about the willingness
to pay of the agent at one point (which will be determined as a part of the optimization
exercise). Hence, the expected payment can be computed by using prior information on
willingness to pay (WP). For every transfer τ ∈ R, we assume that WP values are drawn
independently from a distribution. We denote it by Gτ at transfer τ . Hence, Gτ (y) will
denote the probability that the agent has a type R such that W P (R, τ ) ≤ y. We also
assume that at every τ ∈ R, Gτ admits a positive density function, which we denote by gτ .
The expected revenue from a mechanism M ≡ (f, p) is denoted as ρ(M ). This will becomputed using the prior. If we are given a type space R, we will denote by M(R) the
set of all incentive compatible and individually rational mechanisms. We will say that amechanism M ∈ M(R) is optimal in type space R if
ρ(M ) ≥ ρ(M 0 ) for all M 0 ∈ M(R).
We assume that f is onto and apply Theorem 3 now - this is without loss of generality, since an optimal mechanism must be onto. By Theorem 3, every incentive compatible
mechanism is described by τ 0 and f . By Theorem 5, every optimal mechanism must have
τ 0 = 0. Hence, we only look at incentive compatible mechanisms such that τ 0 = 0. Again
using Theorem 3, the only unknown parameter is τ 1 . For a mechanism with τ 0 = 0 and afixed τ 1 , Theorem 3 implies that the expected revenue isτ 1 (1 − G0 (τ 1 )).
23

Standard first order condition implies that the optimal choice of τ 1 must solve
τ1 =1 − G0 (τ 1 ).
g0 (τ 1 )By strong WP-convexity, the possible values of τ 1 lie in (0, β0 ). Choosing τ 1 → 0 gives an
expected revenue of → 0. Similarly, choosing τ 1 → β0 gives an expected revenue of → 0.
Hence, the corner solutions are ruled out.
We impose the standard hazard rate condition.
g0 (y)
Assumption MHR: G0 satisfies monotone hazard rate (MHR) condition if 1−Gis
0 (y)non-decreasing in y.
0 (y)If G0 satisfies MHR condition, then y = 1−G
has a unique solution. Denote this unique
g0 (y)∗
solution as r .

Definition 13 A mechanism (f, p) is a r∗ -reserve price mechanism if for all R ∈ R,
hi
W P (R, 0) > r∗ ⇒ f (R) = 1hi∗
W P (R, 0) < r ⇒ f (R) = 0
p(R) = f (R) · r∗
In a r∗ -reserve price mechanism, whenever the object is sold, the agent pays r∗ . Whenthe object is not sold, he pays 0. The object is sold to the agent at price r∗ if his willingness
to pay at 0 is larger than r∗ . If the willingness to pay at 0 is less than r∗ , then the object is
not sold to the agent. Hence, an r∗ -reserve price mechanism only requires WP informationof agents at zero transfer. Our discussions in this section has shown that an r∗ -reserve pricemechanism is an optimal mechanism under the MHR assumption. We document this fact as
a proposition.
Proposition 2 Suppose R satisfies strong WP-convexity and G0 satisfies the MHR condition. Then, an r∗ -reserve price mechanism is an optimal mechanism in M(R).
Proposition 2 shows that the optimal mechanism for selling an indivisible object to one
buyer is still very similar to the quasilinear domain. As we observed in remarks following
Theorem 3, revenue equivalence may not hold in these models. In that sense, it is interestingthat we are able to provide a solution of the optimal mechanism. Unfortunately, this is nolonger true in the multiple agents case. We give a detailed analysis of the multiple agentscase under additional assumptions in Appendix B, where we illustrate some of the difficulties
in extending Proposition 2.
24

6.3 A characterization of anonymous auctions
We now discuss an application of Theorem 3 for the many agents case. There is a single
indivisible object to be allocated among n agents. In our application, the designer is a social
planner who is interested in allocating the object fairly. We use a minimal notion of fairness,
which we call anonymity - outcomes of agents should not depend on their identities. We
characterize the class of anonymous and dominant strategy incentive compatible mechanisms
satisfying an additional property called the loser payment independence (LPI) - LPI requiresthat whenever an agent does not receive an object, his transfer amount is the same. This
class of mechanisms can be thought to be a generalization of the class of Groves mechanisms
for the quasilinear domains to this setting.
Formally, the set of agents is denoted by N := {1, . . . , n}. The type of each agent i ∈ N
is a classical preference R over the consumption bundles Z = {0, 1} × R, and we also assume(as in previous subsection) that these classical preferences are order respecting with respectto , where 1  0. Let R denote any subset of such order respecting classical preferences.
An allocation rule is a map f : Rn → N ∪ {0}, where choosing 0 indicates not giving theobject to any of the agents. Notationally, at every type profile R ≡ (R1 , . . . , Rn ) ∈ Rn , wewill write fi (R) ∈ {0, 1} to denote if agent i gets the object at type profile R. We use thestandard notation R−i to denote a profile of types that does not include the type of agent i.
The payment rule of agent i is a map pi : Rn → R. We will denote by p ≡ (p1 , . . . , pn ) acollection of payment rules. A mechanism is a tuple (f, p). The standard notion of dominant
strategy incentive compatibility is defined as follows.
Definition 14 A mechanism (f, p) is dominant strategy incentive compatible (DSIC)
if for every i ∈ N , for every R−i ∈ Rn−1 , and for every Ri , Ri0 ∈ R, we have(fi (Ri , R−i ), pi (Ri , R−i )) Ri (fi (Ri0 , R−i ), pi (Ri0 , R−i )).
We are interested in allocating the object using a fair mechanism. The notion of fairness
we impose is the following.
Definition 15 A mechanism (f, p) is anonymous if for every i, j ∈ N , for every R−ij ∈Rn−2 , and for every Ri , Rj ∈ R, we have(fi (Ri , Rj , R−ij ), pi (Ri , Rj , R−ij )) Ii (fj (Ri0 , Rj0 , R−ij ), pj (Ri0 , Rj0 , R−ij )),(fj (Ri , Rj , R−ij ), pi (Ri , Rj , R−ij )) Ij (fi (Ri0 , Rj0 , R−ij ), pj (Ri0 , Rj0 , R−ij )),where Ri0 = Rj and Rj0 = Ri .
25

Roughly, anonymity requires that identities of agents cannot be used to allocate andprice the object. Specifically, it requires that if preferences of i and j are permuted (keeping
preferences of other agents fixed), then i should be indifferent between his consumption
bundle at the old profile and j’s consumption bundle at the new profile.
We now define a class of auctions, which we call the adjusted Vickrey auction with avariable reserve price. This is an extension of the Vickrey auction defined for this problem
by Saitoh and Serizawa (2008). We can think of our mechanism as a class of Clarke-Groves
mechanisms (Clarke, 1971; Groves, 1973) for allocating a single object with classical preferences. These mechanisms are defined by an anonymous but variable reserve price map:r : Rn−1 → R.
For every agent i, the reserve price of agent i at a profile (Ri , R−i ) is r(R−i ). These mechanisms also specify τ 0 ∈ R, which is the payment of any losing agent. To define the mechanism,
we define the following notations. Given a reserve price map r, at every profile R ∈ Rn ,defineW (R; r) := {i ∈ N : W P (Ri , τ 0 ) ≥ max(r(R−i ), max W P (Rj , τ 0 ))}
j6=i

∗

0

W (R; r) := {i ∈ N : W P (Ri , τ ) > max(r(R−i ), max W P (Rj , τ 0 ))}.
j6=i

Note that if W ∗ (R; r) is non-empty, then it is a singleton. Further, W (R; r) are the setof agents who have the highest willingness to pay (at τ 0 ) and whose willingness to pay (atτ 0 ) is higher than their respective reserve prices. Now, we describe the mechanism. The
mechanism is a little complicated to describe because of tie-breaking issues. Informally, it
fixes a reserve price for each agent for every type profile of other agents. At every typeprofile, it considers the set of agents who have the highest WP at τ 0 and allocates the object
to one of these agents if his willingness to pay is larger than the reserve price. Agents who do
not win the object pay τ 0 but if an agent wins the object then he pays τ 0 plus the maximumof his reserve price and the highest willingness to pay of other agents. One way to interpret
τ 0 is that before the start of the auction, the auctioneer charges τ 0 (if τ 0 is negative, thisis a subsidy but if τ 0 is positive, this is an entry-fee) to all the agents, and then conducts a
Vickrey auction with variable reserve price.
Definition 16 The mechanism (f ∗ , p∗ ) is an adjusted Vickrey auction with a variable reserve price (AVVR) mechanism if there exists a real number τ 0 ∈ R and a map
r : Rn−1 → R such that at every type profile R ∈ Rn , we have
• if W (R; r) = ∅, then fi∗ (R) = 0 for all i ∈ N ,26

• if i ∈ W ∗ (R; r), then fi∗ (R) = 1, and• if fi∗ (R) 6= 0, then i ∈ W (R; r),and for every i ∈ N ,p∗i (R) = τ 0 + fi∗ (R) · max r(R−i ), max W P (Rj , τ 0 ) .
j6=i

An example will clarify the AVVR mechanism. Consider N = {1, 2} and an AVVR
mechanism with τ 0 = 0. We define the reserve price map r : R → R as follows: for every
R ∈ R,
1r(R) :=.
W P (R, 0)
1
The AVVR mechanism allocates the object to agent 1 if W P (R1 , 0) > max(W P (R2 , 0), W P (R
)
2 ,0)
1
and to agent 2 if W P (R2 , 0) > max(W P (R1 , 0), W P (R1 ,0) ). It does not allocate the object toany agent otherwise. The allocation is shown in Figure 6.

Agent 2 wins

W P (R2 ; 0)
Agent 1 wins
No saleNo saleW P (R1 ; 0)Figure 6: Allocation in an AVVR mechanism
The fact that AVVR mechanism uses personalized reserve prices distinguishes it fromother mechanisms studied in this literature where mostly fixed reserve prices have beenstudied (Sakai, 2013a). 4
4

Yamashita (2015) discusses such personalized reserve price Vickrey auctions for quasilinear environment,
but his objective is quite different.

27

Payments in the AVVR mechanism is like a Vickrey auction with personalized reserve
price - winning agent pays the maximum of his reserve price and the second highest willingness to pay (plus the τ 0 amount). Usually, in an incentive compatible mechanism, τ 0 could
depend on the agent and the reports of other agents. But the AVVR mechanism uses simpler
payments for losing agents. In general, we restrict our analysis below to such mechanisms.
Definition 17 A mechanism (f, p) satisfies loser payment independence (LPI) if
there exists a real number τ 0 such that for every i ∈ N and for every R ∈ Rn with fi (R) = 0
we have pi (R) = τ 0 .
Note that LPI does not restrict τ 0 to be zero or non-negative. Zero payment for losers
or no-subsidy for losers is used as an axiom in the literature on auction design without
quasilinearity - see for instance Saitoh and Serizawa (2008); Sakai (2013a); Morimoto andSerizawa (2015). LPI allows us some flexibility in setting the payment of the losers, and our
AVVR mechanisms may not satisfy no-subsidy for losers but satisfy LPI.
We are now ready to state the characterization result for AVVR mechanism - it is provedin the Appendix using the n-agent extension of Theorem 3.
Theorem 6 Suppose R is a classical type space satisfying strong WP-convexity. Let (f, p)
be a mechanism defined on Rn . Then, the following statements are equivalent.
1. (f, p) is DSIC, anonymous, and satisfies LPI.
2. (f, p) is an AVVR mechanism.
The proof in Theorem 6 constructs one reserve price map given a DSIC, anonymousmechanism satisfying LPI. But there can be other choices for the reserve price map also.
Any such choice leads to an AVVR mechanism. Theorem 6 extends and strengthens acharacterization of Vickrey auction in the quasilinear domain by Ashlagi and Serizawa (2012),
who use anonymity, DSIC, individual rationality, and no-subsidy for losers as their axioms.
In contrast, our characterization is valid for non-quasilinear domains and uses less restrictive
LPI axiom in place of individual rationality and no-subsidy for losers.

6.4 VCG may not work
In Section 6.3, we showed that a natural extension of a class of Groves mechanisms continues
to be DSIC in the single object allocation model. One of the reasons such an extension
worked was that each agent had just two alternatives: either getting the object or not. In
28this section, we show that such an extension may not work if each agent had more than twoalternatives.
How can we define an extension of the Vickrey-Clarke-Groves (VCG) mechanism in thissetting if agents have classical preferences? We propose a naive extension. Let N be a finite
set of agents. Let A be a finite set of alternatives that any agent i ∈ N can be allocated.
For simplicity of exposition, we assume existence of an alternative a0 and a partial order such that a  a0 for all a ∈ A. The preferences we consider here will respect such a partial
order .
Let R denote the set of classical preferences over A × R respecting . A mechanism will
allocate a collection of alternatives (a1 , . . . , an ) at each profile of preferences, where ai is thealternative allocated to agent i. Notice that there may be restrictions on such allocations for instance, in the public good problems, we may impose ai = aj for all i, j ∈ N ; for private
good allocation problems where no agent can be assigned the same alternative except a0(e.g., the unit-demand multi-object allocation problem discussed in Section 6.4.1), we may
impose ai 6= aj for all i, j ∈ N if ai , aj 6= a0 . Let A ⊆ An be the set of all feasible allocationsof alternatives to agents.
A mechanism is a pair (f, p), where the allocation rule f is a map f : (R )n → A andp ≡ (p1 , . . . , pn ) is a collection of payment rules, where pi : (R )n → R is the payment rule
for agent i. At any preference profile R, fi (R) is the alternative assigned to agent i andpi (R) is the payment of agent i. As usual, a mechanism (f, p) is dominant strategy incentive
compatible (DSIC) if for all i ∈ N , for all R−i , and for all Ri , Ri0 , we have(fi (Ri , R−i ), pi (Ri , R−i )) Ri (fi (Ri0 , R−i ), pi (Ri0 , R−i )).
Note that with these n-agent notations, our definitions of monotonicity and the results in
Theorems 1 and 2 extend in a straightforward manner.
Consider a profile of preferences R ≡ (R1 , . . . , Rn ). For each agent i ∈ N , we consider|A|
the valuation vector {V Ri (a, (a0 , 0))}a∈A . We denote this vector as vi ∈ R+ , where we notethat vi (a0 ) = 0. If Ri is quasilinear, vi will exactly correspond to the valuation of agent i foralternatives in A. Denote the VCG payment of agent i with quasilinear preference profile
vcg
5
corresponding to v ≡ (v1 , . . . , vn ) as pvcg
i (v) and his alternative allocation as fi (v) ∈ A.
The generalized VCG mechanism (f, p ≡ (p1 , . . . , pn )) for classical preference profile R is
now defined as: for all i ∈ N ,fi (R) := fivcg (v);pi (R) := pvcg
i (v).

5

Informally, the VCG mechanism allocates objects such that the total valuation of agents is maximized.
The payment of each agent is his externality to other agents - see Vohra (2011) or Borgers et al. (2015) for
a formal definition.

29

When there are two alternatives A = {a0 , a}, the generalized VCG mechanism is DSIC.
Indeed Saitoh and Serizawa (2008) investigate the problem of allocating multiple homogeneous objects where each agent can consume at most one unit, and show that the generalized
VCG is DSIC. In their model, every agent is either allocated an object (a) or not allocatedany object (a0 ). For the public good provision problem (where, you either provide the public
good (a) or not (a0 )), Hashimoto and Saitoh (2010) show that the generalized VCG mechanism is DSIC. It is not difficult to verify that for |A| = 2, the generalized VCG mechanism
satisfies WP-monotonicity and the payment formula of Theorem 3 (take τ 0 = 0 for eachagent). Hence, by Theorem 3, it is DSIC. 6
We show below that this feature of the generalized VCG mechanism breaks down if|A| > 2. In particular, we consider a particular private good allocation problem, and showthat the generalized VCG mechanism violates monotonicity in that problem.
6.4.1 Unit demand multi-object allocation
In this section, we consider a private good allocation problem, where a designer has mobjects to allocate, denoted by M := {a, b, c, . . .}. There are n agents (buyers), denoted by
N := {1, . . . , n}. Each agent can receive at most one object (unit-demand preference). Let
A ≡ M ∪ {a0 }, where a0 is the null object, which is assigned to any agent who does notreceive any object in M . Each agent i has classical preference Ri over A × R respecting thepartial order : a  a0 for all a ∈ M . 7
We first show that in this model, the generalized VCG may not be DSIC by showingthat it violates monotonicity. For this, consider M = {a, b} and three agents N = {1, 2, 3}.
For this, we consider two classical preference profiles: (R1 , R2 , R3 ) and (R̂1 , R2 , R3 ). The
corresponding valuations for each alternative at (a0 , 0) are shown in Table 1.
It is not difficult to see that the total valuation-maximizing allocation at profile (R1 , R2 , R3 )assigns agent 1 object b, agent 2 object a and agent 3 object a0 . Hence,
f1 (R1 , R2 , R3 ) = b, f2 (R1 , R2 , R3 ) = a, f3 (R1 , R2 , R3 ) = a0 .
Similarly, for profile (R̂1 , R2 , R3 ), we have
f1 (R̂1 , R2 , R3 ) = a, f2 (R1 , R2 , R3 ) = a0 , f3 (R1 , R2 , R3 ) = b.
6

It is enough to show that the generalized VCG mechanism is DSIC in the domain which includes allclassical preferences, and this type space satisfies WP-convexity assumption in Theorem 3.
7This is a well-studied problem in quasilinear domain - applications include allocation of public housing
in cities, allocation of advertisement slots on a search page of a keyword and so on. We refer to Kazumura
et al. (2017) for more applications of this problem.

30

V (·, (a0 , 0))
V R2 (·, (a0 , 0))
V R3 (·, (a0 , 0))

a0
0
0
0

a
5
4
3

b
8
5
6

V R̂1 (·, (a0 , 0))

0

5

4

R1

Table 1: Valuations at (a0 , 0)
We only compute the payments of agent 1, which can be done by computing his externalities on other agents. We only do it at profile (R̂1 , R2 , R3 ). Routine calculations show:
p1 (R̂1 , R2 , R3 ) = 4. Hence, agent 1 is allocated (a, 4) at preference profile (R̂1 , R2 , R3 ) and hegets object b at preference profile (R1 , R2 , R3 ). We now argue that R1 and R̂1 can be chosen
in a way such that monotonicity is violated.
So far, we have not used any other feature of the classical preferences except their valuations at (a0 , 0). Hence, it is possible to choose R1 and R̂1 such that V R1 (b, (a, 4)) <V R̂1 (b, (a, 4)) - this is shown in Figure 7. This is a violation of monotonicity. Thus, byTheorem 1, the generalized VCG mechanism violates DSIC.
^V R1 (b; (a; 4)) < V R1 (b; (a; 4))

R1(b; 4)(b; 8)

^1 R
^1
R

R1

(a; 4)

b = f1 (R1 ; R2 ; R3 )^ 1 ; R2 ; R3 )a = f1 ( R(a; 5)a0(a0 ; 0)Figure 7: Violation of monotonicity by the generalized VCG mechanism
We emphasize that the generalized VCG mechanism satisfies the taxation principle in all
problems. Hence, monotonicity is a key condition for the generalized VCG mechanism tosatisfy incentive compatibility. In other words, the generalized VCG mechanism is DSIC ina problem if and only if it satisfies monotonicity in that problem.

31

6.4.2 The minimum Walrasian equilibrium price mechanism
We now turn our attention to a mechanism proposed by Demange and Gale (1985) in the unitdemand multi-object allocation problem discussed in the previous section. This mechanism
is DSIC. It also inherits all the properties of the VCG mechanism from the quasilinear
preference domain - for instance, it is Pareto efficient and individually rational.
|A|
To define this mechanism, we will need some extra notations. A price vector π ∈ R+
defines a price for every object with πa0 = 0. At any price vector π, let D(Ri , π) := {a ∈ A :(a, πa ) Ri (b, πb ) ∀ b ∈ A} denote the demand set of agent i with preference Ri .
An object allocation is an n-tuple (a1 , . . . , an ) ∈ An such that no real (non-null) object is
assigned to two agents, i.e., ai 6= aj for all i, j with ai , aj 6= 0.
Definition 18 An object allocation (a1 , . . . , an ) and a price vector π is a Walrasian equilibrium at a preference profile R ≡ (R1 , . . . , Rn ) if
1. ai ∈ D(Ri , π) for all i ∈ N and2. for all a ∈ M with ai 6= a for all i ∈ N , we have πa = 0.
We refer to π defined above as a Walrasian equilibrium price vector.
A Walrasian equilibrium price vector π is a minimum Walrasian equilibrium pricevector at preference profile R if for every Walrasian equilibrium price vector π 0 at R, wehave πa ≤ πa0 for all a ∈ A. Demange and Gale (1985) prove that a Walrasian equilibrium
exists at every preference profile R, and the set of Walrasian equilibrium price vectors forms
a compact lattice. We denote the minimum Walrasian equilibrium price vector at R as
π min (R).
Although the minimum Walrasian equilibrium price vector is unique at every preference
profile, there may be multiple supporting object allocation - all these object allocations must
be indifferent to all the agents. To handle this multiplicity problem, we introduce somenotation. Let Z min (R) denote the set of all allocations at a minimum Walrasian equilibrium
at preference profile R. Note that if ((a1 , . . . , an ), π) ∈ Z min (R) then π = π min (R). The
minimum Walrasian equilibrium price mechanism is defined as follows.
Definition 19 A mechanism (f, p) is a minimum Walrasian equilibrium price (MWEP)
mechanism if (f (R), p(R)) ∈ Z min (R) ∀ R.
We reprove the following result.
Proposition 3 (Demange and Gale (1985)) Every MWEP mechanism is DSIC.
32

The proof is provided in Appendix A. The original proof of Proposition 3 in Demange
and Gale (1985) is quite involved. A simpler proof is provided in Morimoto and Serizawa(2015). Their proof uses a characterization of MWEP in terms of demand sets of agents.
We use the necessity part of this characterization along with our Theorem 1 to establish aneven simpler proof of Proposition 3.
The unit demand multi-object allocation problem is the only known problem in the nonquasilinear preference environment where the generalized VCG mechanism does not workand still a Pareto efficient and DSIC mechanism exists. A natural future research agenda
will be to investigate problems where we can find Pareto efficient and DSIC mechanisms - inthe literature review (in Section 7), we report various existing impossibility results in that
direction. We hope that our Theorem 1 will be useful to map this frontier of possibility andimpossibility.

7 Related literature
The literature on mechanism design with quasilinearity is long, and almost impossible todescribe exhaustively. We discussed some relevant papers in detail in Section 4.3, but referto the reader to two excellent books on this topic (Vohra, 2011; Borgers et al., 2015). After
Myerson (1981), a long literature has focused on extending his monotonicity and revenue
equivalence characterizations to various models with multidimensional type space, wheremore than two alternatives are allocated and agents have values for each of those alternatives.
Because of quasilinearity, the allocation rule and payment rule of a mechanism appear inseparable form in the utility function of the agent. This allows one to provide separatecharacterization of implementable allocation rules (i.e., allocation rules for which payment
rules can be found to make the tuple incentive compatible) and the class of payment rulesthat implement an implementable allocation rule. The former is characterized by a simple
monotonicity property - results in that spirit appear in Jehiel et al. (1999); Bikhchandani
et al. (2006); Saks and Yu (2005); Ashlagi et al. (2010); Cuff et al. (2012); Muller et al.
(2007); Mishra and Roy (2013); Mishra et al. (2014); Carbajal and Müller (2015). 8 The
latter is characterized by a revenue equivalence (or envelope theorem) formula - results in thatspirit are in Krishna and Maenner (2001); Milgrom and Segal (2002); Chung and Olszewski(2007); Heydenreich et al. (2009). These results exploit the geometric structure induced byquasilinearity, and make use of convex analysis machinery (Rockafellar, 1970). A paper by
8

These papers (a) extend Myerson’s monotonicity condition to multidimensional environment and (b)simplify a complicated monotonicity characterization of Rochet (1987).

33

Carbajal and Ely (2013) establishes that revenue equivalence may not hold in some problems
even with quasilinearity - this is due to non-convex and non-differentiable nature of valuation
function. They further show that in specific problems where revenue equivalence fails, one
can still do revenue maximization using revenue inequalities.
In the absence of quasilinearity, it is not possible to provide separate characterizationof monotonicity and revenue equivalence since the allocation and payment are no longer
separable. Our monotonicity condition is indeed a condition on the mechanism, but reduces
to the monotonicity condition on allocation rule used in quasilinear type spaces. Unlike
the quasilinear type space, we find revenue uniqueness of incentive compatible mechanisms
in our benchmark rich classical type space. Our revenue uniqueness is driven by the nonquasilinearity of preferences and the underlying richness of the type space that we assume.
Unlike the literature, we do not (and cannot) rely on convex analysis techniques. A crucial
difference of our model and that of the literature on quasilinear preferences is that we assume
no functional form of utility functions. Our restriction on type spaces are on the primitivesof the model, which is the classical preferences.
There is a short but important literature on mechanism design with non-quasilinear preferences. The closest paper to ours is Kos and Messner (2013). They derive a necessary
condition for incentive compatibility in a model with non-quasilinearity. Their condition isa generalization of the cycle monotonicity condition in Rochet (1987) for quasilinear preferences. They show that their condition is not sufficient for incentive compatibility. In
contrast, our monotonicity condition is significantly weaker than their condition and is anecessary and sufficient condition for incentive compatibility along with the taxation principle. However, we focus on deterministic mechanisms assuming some richness in type space,
and Kos and Messner (2013) do not make such assumptions.
Baisa (2017) considers the single object auction model and allows for randomization ina model with non-quasilinear preferences. He introduces a novel mechanism in his setting
and studies its optimality properties (in terms of revenue maximization). Garratt and Pycia(2016) study the bilateral trading model with non-quasilinear preferences and allows for randomization. Further, their solution concept is Bayesian incentive compatibility. Their main
finding is that for generic set of non-quasilinear preferences, the Myerson-Satterthwaite impossibility result (Myerson and Satterthwaite, 1983) on bilateral trading disappears. Unlike
both these papers, we do not consider randomization and our solution concept is different
from them. More importantly, we have a more general model of non-quasilinear preferences,albeit with deterministic mechanisms, which covers many problems of interest. In a recent
paper, Noldeke and Samuelson (2015) analyze principal-agent problem and matching prob-

34

lem with non-quasilinear preferences. They establish a certain implementation duality using
abstract convex analysis techniques, which allows them to extend results from quasilinear
type spaces. Our results are specific to deterministic mechanisms, which is not assumedin Noldeke and Samuelson (2015). The objectives of our paper and that of Noldeke andSamuelson (2015) are quite different, and hence, the results are quite different.
There is a literature on axiomatic treatment of mechanisms in models without quasilinearity. This literature identifies specific mechanisms in different problems with classicalpreferences and axiomatically characterizes these mechanisms. The central axiom in this literature is dominant strategy incentive compatibility, but it is often accompanied by Pareto
efficiency, individual rationality, and other axioms. As discussed earlier, a seminal paper inthis literature is Demange and Gale (1985), who consider the unit demand multi-object allocation problem without quasilinearity and define the MPWE mechanism. They show that
the MPWE mechanism is stable and dominant strategy incentive compatible. Morimotoand Serizawa (2015) characterize the MPWE mechanism using Pareto efficiency, individual
rationality, incentive compatibility, and other axioms on payments - see an extension of thischaracterization in a smaller type space in Zhou and Serizawa (2016). These characterizations require a type space that is rich in a strong sense - often, a type space that includes allclassical preferences. Saitoh and Serizawa (2008); Sakai (2008) define the generalization of
Vickrey auction in the single object auction model with non-quasilinear preferences. They
characterize the Vickrey auction in a rich non-quasilinear type space using incentive compatibility, Pareto efficiency, individual rationality, and no-subsidy for losers - see also Ashlagi
and Serizawa (2012) for an analogous characterization of Vickrey auction in the quasilinear
domain. Sakai (2013b) and Adachi (2014) characterize the same generalized Vickrey auction mechanism using incentive compatibility, continuity, and some fairness axioms. Sakai(2013a) considers an extension of this generalized Vickrey auction with reserve price, andcharacterizes it using incentive compatibility, weak Pareto efficiency, and zero-payment for
losers. The mechanism we propose for allocating an object is more general than the auctionin Sakai (2013a) since it has personalized reserve prices for every agent which vary withpreferences of other agents. Hashimoto and Saitoh (2010) defines the generalization of the
Pivotal mechanism in the single public good provision model with non-quasilinear preferences
and characterize it using Pareto efficiency, incentive compatibility, and an equity axiom.
When the set of preferences include all or a very rich class of non-quasilinear preferences,
impossibility results exist in various problems. Several authors have shown that no incentive
compatible and Pareto efficient mechanism exists that satisfy other mild axioms - Kazumura and Serizawa (2016) show this for multi-object auction problems where agents can

35be allocated more than one object; Baisa (2016) shows this for homogeneous object allocation problems; Ma et al. (2016) shows a similar result for public good provision problem andDobzinski et al. (2012); Lavi and May (2012) show similar results for hard budget-constrained
auction of a single object. Pareto efficiency along with other axioms play a crucial role insuch impossibility results. Unlike these papers, we do not impose any extra condition besides incentive compatibility. Moreover, we also cover domains where possibility exists with
Pareto efficiency and other axioms.
Summarizing, the main differences between this literature and our paper is that (a)we have results for a very general class of problems whereas each paper in this literature
focuses on a particular mechanism defined on a specific problem; (b) our focus on axiomaticcharacterization of a class of mechanisms for single object allocation illustrates the use ofa particular general result - in particular, our AVVR class of mechanisms are more generalthan any specific mechanism discussed in the literature.
There is a literature in auction theory and algorithmic game theory on single object
auctions with budget-constrained bidders - see Che and Gale (2000); Pai and Vohra (2014);
Ashlagi et al. (2010); Lavi and May (2012). Carbajal and Mualem (2017) considers thebudget-constrained single object auction problem. They extend Rochet’s cycle monotonicity (Rochet, 1987) characterization to their problem under additional conditions, and findconditions under which revenue equivalence holds. The budget-constraint in these papers
introduces a particular form of non-quasilinearity in preferences of agents. Further, thebudget-constraint in these models is hard, i.e., the utility from any payment above the budget is minus infinity. This assumption is not satisfied by the preferences considered in ourmodel. Hence, we cannot apply our results to these models directly. However, if we consider
soft budget-constraints (where agents can borrow from banks at an interest rate), then our
results on the two-alternatives case will apply to some of these models.
In a companion paper (Kazumura et al., 2017), we investigate the question of revenue
maximizing auction by a seller who is selling multiple objects to agents who can buy atmost one object. The minimum Walrasian equilibrium price mechanism is shown to berevenue-optimal in a class of mechanisms satisfying dominant strategy incentive compatibility, individual rationality and some other reasonable axioms. The technique used in that
paper is quite different from the current paper. Moreover, the problem studied in that paper is very specific and involves axioms other than incentive compatibility and individual
rationality.

36

8 Conclusion
We have presented a systematic analysis of the structure of incentive compatible mechanisms
when agents have non-quasilinear preferences. Our characterization results give novel insights
into the complex nature of incentive constraints in this model. It also explores the tractabilityof performing optimization with non-quasilinear preferences. Our results are detail-free in thesense that they do not assume any particular functional form of non-quasilinear preferences.
We apply our results to some of the models where similar results with quasilinear preferences
have been successfully applied. While we were successful in some of them, we only havepartial answers in others. This shows the delicate nature of incentive compatible mechanisms
as we move from quasilinear preferences to general classical preferences.
A troubling feature of mechanisms in non-quasilinear type spaces is the informational
requirement - preferences over infinite number of consumption bundles have to be elicited.
Mechanisms that only elicit finite amount of information must be studied and its performancemust be compared with a general mechanism. This will be crucial to apply mechanism
design theory to type spaces without quasilinearity. We leave this important issue as anarea of future research. Another area of future research will be to find specific models of
non-quasilinear type spaces and apply our results in such models.

37

Appendix A: Omitted proofs
Proofs of Section 4 and Section 5
Proof of Theorem 1
Proof : Suppose (f, p) is incentive compatible. Consider any R, R0 with f (R) = f (R0 ) = a.
By incentive compatibility(a, p(R)) R (a, p(R0 )) and (a, p(R0 )) R0 (a, p(R)).
Money monotonicity of classical preferences implies that p(R) = p(R0 ). Hence, define forevery a ∈ A, κ(a) := p(R) for some R ∈ R with f (R) = a. Hence, taxation principle holds.
Pick R, R0 ∈ R such that f (R) = a, f (R0 ) = b. By incentive compatibility(a, κ(a)) R (b, κ(b)) I (a, V R (a, (b, κ(b)))).
Hence, κ(a) ≤ V R (a, (b, κ(b))). But incentive compatibility also implies
0(a, V R (a, (b, κ(b)))) I 0 (b, κ(b)) R0 (a, κ(a)).
0Hence, κ(a) ≥ V R (a, (b, κ(b))). Combining these two observations, we get0

V R (a, (b, κ(b))) ≥ V R (a, (b, κ(b))).
Hence, (f, p) is monotone.
We now establish the converse implication. Suppose (f, p) is monotone and there exists
κ : A → R such that for every R, p(R) = κ(f (R)).
Assume for contradiction that there is a preference R such that f (R) = a and anotherpreference R0 such that f (R0 ) = b 6= a but (b, κ(b)) P (a, κ(a)). This implies that κ(a) >V R (a, (b, κ(b))). By monotonicity,00

V R (a, (b, κ(b))) ≥ V R (a, (b, κ(b))) and V R (b, (a, κ(a))) ≥ V R (b, (a, κ(a))).
Since κ(a) > V R (a, (b, κ(b))), we get κ(b) < V R (b, (a, κ(a))).
Choose 0 > 0 but arbitrarily close to zero, and let v ∈ R|A\{a}| be such that for eachc 6= a,(κ(b)
if c = bvc =0min(V R (c, (b, κ(b))), V R (c, (b, κ(b)))) − 0 if c 6= b.

38

Define the set of preferences R∗ as follows:R∗ := {R̂ ∈ R : V R̂ (c, (b, κ(b))) = vc ∀ c ∈/ {a, b}}.
Now, we do the proof in many steps.
Step 1. We first show that R∗ is non-empty. To do so, consider the following vector
v 00 ∈ R|A| as follows:(vc
if c 6= avc00 =R
R0
0min(V (a, (b, κ(b))), V (a, (b, κ(b)))) −  if c = a.
Next, we show that for sufficiently small 0 > 0, v 00 respects . We consider various cases.
Case 1. Suppose b  c, where c 6= b. Now,0vb00 = κ(b) > min(V R (c, (b, κ(b))), V R (c, (b, κ(b)))) > vc00 ,where the first inequality comes from the fact that R and R0 respect . If c  b, then0

vc00 = min(V R (c, (b, κ(b))), V R (c, (b, κ(b)))) − 0 > κ(b) = vb00 ,where the inequality follows because R and R0 respect  and 0 is sufficiently close to zero.
Case 2. Suppose c  d, where c, d 6= b. Then,00vc00 = min(V R (c, (b, κ(b))), V R (c, (b, κ(b))))−0 > min(V R (d, (b, κ(b))), V R (d, (b, κ(b))))−0 = vd00 ,where the strict inequality follows from the fact that R and R0 respect .
This completes all the cases, and establishes the fact that v 00 respects . By TP richness, there is R̂0 ∈ R such that v 00 ∈ I(R̂0 ). 9 Since vc00 = vc for all c 6= a, we get that R∗ 6= ∅.
Step 2. In this step, we show that f (R̂) ∈ {a, b} for all R̂ ∈ R∗ . To see this, supposef (R̂) = c ∈/ {a, b}. By f (R0 ) = b and monotonicity, we get that V R̂ (c, (b, κ(b))) = vc ≥0
V R (c, (b, κ(b))), which contradicts the definition of v.
9TP richness ensures existence of a preference which has two pairwise consistent and -parallel as indifference vectors. If we are only given one such indifference vector, we can choose another indifference vector
trivially such that both are pairwise consistent and and -parallel. Then, we can apply TP richness trivially.

39

Step 3. In this step, we construct two vectors which are pairwise consistent for  and-parallel, where  > 0 is as defined in the statement of the theorem. To do so, we first defineη :=V R̂ (a, (b, κ(b))).

supR̂∈R∗ :f (R̂)=b

To see that η is well defined and finite, consider the preference R̂0 ∈ R∗ constructed at theend of Step 1. By Step 2, f (R̂0 ) ∈ {a, b}. If f (R̂0 ) = a, then monotonicity implies that00va00 = V R̂ (a, (b, κ(b))) ≥ V R (a, (b, κ(b))).
But this contradicts the definition of va00 . Hence, f (R̂0 ) = b. Finally, for every R̂ ∈ R∗
with f (R̂) = b, monotonicity implies that V R (a, (b, κ(b))) ≥ V R̂ (a, (b, κ(b))). Hence, η ≤V R (a, (b, κ(b))). This establishes that η is a finite real number. Note thatη ≤ V R (a, (b, κ(b))) < κ(a).

(1)

Now, since R is TP rich, for every pair of -parallel v 0 , v 00 ∈ R|A| which are pairwise
consistent for , there is a preference R00 such that v 0 , v 00 ∈ I(R00 ). Choose, ∗ ∈ (0, 3 ) andarbitrarily close to zero. Let v ∗ be such that for each c ∈ A,(
η − ∗ if c = avc∗ =vc
otherwise.
Since η is well defined, there exists R̂ ∈ R∗ such that V R̂ (a, (b, κ(b))) is arbitrarily close to η.
By the definition of R∗ and the fact that 0 , ∗ is arbitrarily close to zero, we get v ∗ respects.
Let u∗ be such that for each c ∈ A,u∗c := vc∗ + κ(a) − va∗ = vc∗ + κ(a) − η + ∗ .
Since v ∗ respects , we have u∗ respects . Further, since κ(a) > η (Inequality 1), we getthat u∗ > v ∗ . Finally, for any x, y ∈ A, we have[vx∗ − vy∗ ] − [u∗x − u∗y ] = 0.
Thus, v ∗ and u∗ are -parallel and pairwise consistent. By TP richness, there is a preferenceR∗ ∈ R such that v ∗ , u∗ ∈ I(R∗ ). Notice that R∗ ∈ R∗ .

40

Step 4. In this step, we construct two more vectors which are -parallel and pairwise
consistent for . Let v ∗∗ ∈ R|A| be a vector defined as follows: for each c ∈ A,(
va∗ + 2∗ = η + ∗ if c = avc∗∗ =
vc∗
otherwise.
Let u∗∗ ∈ R|A| be a vector defined as follows: for each c ∈ A,(u∗a = κ(a) if c = au∗∗
c =u∗c + ∗otherwise.
Since v ∗ and u∗ respect  and pairwise consistent, and ∗ is arbitrarily close to zero, we getthat v ∗∗ and u∗∗ respect  and pairwise consistent. Further, for any x, y ∈ A \ {a}, we have
∗∗
∗
∗
∗
∗
[vx∗∗ − vy∗∗ ] − [u∗∗x − uy ] = [vx − vy ] − [ux − uy ] = 0.

For each x ∈ A \ {a}, we have
∗∗
∗
∗
∗
∗
∗
∗
∗
[va∗∗ − vx∗∗ ] − [u∗∗a − ux ] = [va − vx + 2 ] − [ua − (ux +  )] = 3 < ,

where the strict inequality followed from the choice of ∗ ∈ (0, 3 ). Therefore, v ∗∗ and u∗∗are -parallel. By TP richness, there is a preference R∗∗ ∈ R such that v ∗∗ , u∗∗ ∈ I(R∗∗ ).
Notice that R∗∗ ∈ R∗ .
The two preferences R∗ and R∗∗ are illustrated in Figure 8.
Step 5. In this step, we show that f (R∗ ) = b and f (R∗∗ ) = a. By definition, R∗ , R∗∗ ∈ R∗ ,∗and by Step 2, f (R∗ ), f (R∗∗ ) ∈ {a, b}. Note that V R (a, (b, κ(b))) = va∗ = η − ∗ < η. By the∗definition of η, there is R̂ ∈ R∗ with f (R̂) = b such that V R̂ (a, (b, κ(b))) > V R (a, (b, κ(b))).
By monotonicity, f (R∗ ) 6= a. Hence, f (R∗ ) = b.
∗∗
Next, V R (a, (b, κ(b))) = va∗∗ = η + ∗ > η. By definition of η, f (R∗∗ ) 6= b. Hence,f (R∗∗ ) = a.
This leads us to a contradiction as follows:
∗

∗∗

∗
∗
R
(b, (a, κ(a))).
V R (b, (a, κ(a))) = u∗∗b = ub +  > ub = V

By monotonicity, f (R∗ ) = b and f (R∗∗ ) = a gives us a contradiction.
Proof of Theorem 2

41Figure 8: Illustration of R∗ and R∗∗
Proof : Suppose (f, p) and (f, p0 ) are two incentive compatible mechanisms. Theorem 1
implies that there are two maps κ : A → R and κ0 : A → R such that for all R, p(R) =κ(f (R)) and p0 (R) = κ0 (f (R)).
Pick a, b ∈ A such that b  a. Since (f, p) is incentive compatible, for any R withf (R) = a, we have(b, V R (b, (a, κ(a)))) I (a, κ(a)) R (b, κ(b)).
This implies that V R (b, (a, κ(a))) ≤ κ(b). But b  a implies that V R (b, (a, κ(a))) > κ(a).
Hence, κ(b) > κ(a).
A consequence of this observation is that the vector v, defined as vc = κ(c) for all c ∈ A,
respects . Similarly, the vector v 0 , defined as vc0 = κ0 (c) for all c ∈ A respects .
Now, if κ(a) = κ0 (a) for every a ∈ A, then we are done. So suppose κ(a) 6= κ0 (a) for somea ∈ A. Without loss of generality, assume that κ(a) > κ0 (a). First we show that κ(b) > κ0 (b)for all b ∈ A. Assume for contradiction, κ(b) ≤ κ0 (b) for some b ∈ A. Let v ∈ R|A| be suchthat va ∈ (κ0 (a), κ(a)), vb = κ(b), and vc < κ(c) for all c 6= a, b. Notice that we can take sucha v so that it respects . By TP  richness, there is R ∈ R such that v ∈ I(R).
For each c 6= b,(b, κ(b)) P (c, κ(c)).
Thus, incentive compatibility of (f, p) implies f (R) = b. However, since(a, κ0 (a)) P (b, κ(b)) R (b, κ0 (b)),
42

incentive compatibility of (f, p0 ) implies f (R) 6= b. This is a contradiction. Hence, κ(b) >κ0 (b) for all b ∈ A.
Define δ = mina∈A [κ(a) − κ0 (a)] and let δ = κ(a∗ ) − κ0 (a∗ ) for some a∗ ∈ A. Choose
0 > 0 but arbitrarily close to zero. We define two vectors now:v 0 (a∗ ) = κ0 (a∗ ),v 0 (a) = κ0 (a) +0∀ a 6= a∗ .
2

0
∀ a 6= a∗ .
2Note that v 0 and v respect  since κ0 respects  and 0 is arbitrarily close to zero. Further,since δ > 0 and 0 is arbitrarily close to zero v > v 0 . Finally, for any a, b ∈ A,v(a∗ ) = κ0 (a∗ ) + δ = κ(a∗ ),v(a) = κ0 (a) + δ − | v(a) − v(b) − v 0 (a) − v 0 (b) | ≤ 0 .
Since 0 was chosen arbitrarily close to zero, v and v 0 are -parallel. Then, TP richness
guarantees that there is a preference R ∈ R such that v, v 0 ∈ I(R).
But incentive compatibility of (f, p0 ) implies f (R) 6= a∗ - this follows since v 0 ∈ I(R) and0v 0 (a∗ ) = κ0 (a∗ ), v 0 (a) = κ0 (a) + 2 for all a 6= a∗ . On the other hand, incentive compatibilityof (f, p) implies f (R) = a∗ . This follows from the fact v ∈ I(R) andv(a∗ ) = κ0 (a∗ ) + δ = κ(a∗ ), v(a) = κ0 (a) + δ −0< κ(a) for all a 6= a∗ .
2This is a contradiction.

Proof of Theorem 3
Proof : Suppose (f, p) is incentive compatible. The fact that (f, p) is WP-monotone andthere exists a map κ : A → R such that p(R) = κ(f (R)) for all R ∈ R follow fromidentical arguments as in Theorem 1 - note here that monotonicity in Theorem 1 implies
WP-monotonicity. 10
We show the payment formula. By incentive compatibility for any R ∈ R with f (R) = 1,
we have(1, κ(1)) R (0, κ(0)) I (1, V R (1, (0, κ(0)))),
which implies that
κ(1) ≤V R (1, (0, κ(0))).

inf
R∈R:f (R)=110Note that the TP richness requirement in Theorem 1 is not required to show the necessity of monotonicity and the taxation principle.

43

Let
` :=

V R (1, (0, κ(0))).

inf
R∈R:f (R)=1

We show that κ(1) = `.
Assume for contradiction κ(1) < `. By ontoness, there exists a preference R such thatf (R) = 1. Note that V R (1, (0, κ(0))) ≥ `. By ontoness, there is a preference R̂ such thatf (R̂) = 0. Incentive compatibility of (f, p) implies that V R̂ (1, (0, κ(0))) ≤ κ(1).
Now, since V R̂ (1, (0, κ(0))) ≤ κ(1) < ` ≤ V R (1, (0, κ(0))), by WP-convexity, there is a R̃such that V R̃ (1, (0, κ(0))) ∈ (κ(1), `). Since V R̃ (1, (0, κ(0))) > κ(1), incentive compatibilityof (f, p) implies that f (R̃) = 1. But V R̃ (1, (0, κ(0))) < ` and f (R̃) = 1 contradicts thedefinition of `.
This shows that κ(1) = `. But note that`=

inf
R∈R:f (R)=1=

inf

V R (1, (0, κ(0)))

W P (R, κ(0)) + κ(0)R∈R:f (R)=1= κ(0) +inf

W P (R, κ(0)).

R∈R:f (R)=1

Then, setting τ 0 ≡ κ(0) and τ 1 ≡ inf R∈R:f (R)=1 W P (R, τ 0 ), gives us the desired payment
formula property.
Now, for the converse, suppose (f, p) is WP-monotone and satisfies Property 2(b) of theclaim. Pick R with f (R) = 1 and assume for contradiction (0, τ 0 ) P (1, τ 0 + τ 1 ). Then,τ 0 + τ 1 > V R (1, (0, τ 0 )) = W P (R, τ 0 ) + τ 0 , which implies τ 1 > W P (R, τ 0 ). This violates
the definition of τ 1 .
Next, pick R with f (R) = 0 and assume for contradiction (1, τ 1 + τ 0 ) P (0, τ 0 ). Then,
τ 0 > V R (0, (1, τ 0 + τ 1 )). As a result, V R (1, (0, τ 0 )) > τ 0 + τ 1 or W P (R, τ 0 ) > τ 1 . By
definition of τ 1 , there is R0 with f (R0 ) = 1 and W P (R0 , τ 0 ) arbitrarily close to τ 1 . In
particular, we can choose R0 such that W P (R0 , τ 0 ) < W P (R, τ 0 ) (this can be done because
W P (R, τ 0 ) > τ 1 and WP-convexity). But f (R0 ) = 1 and f (R) = 0 while W P (R0 , τ 0 ) <W P (R, τ 0 ) violates WP-monotonicity, giving us the desired contradiction.
Proof of Theorem 4
Proof : Let f be an onto allocation rule on R, where R++ ⊆ R. Note that since R++ ⊆ R,
the domain R satisfies WP-convexity - this follows from the fact that for every t and α ∈ R++ ,there exists a positive income effect preference R with W P (R, t) = α. Hence, Theorem 3
holds in domain R.
44

If (f, p) and (f, p0 ) are incentive compatible mechanisms, then by Theorem 3, there exists
real numbers τ 0 and τ̄ 0 such that for all R ∈ R, p(R) = τ 0 and p0 (R) = τ̄ 0 if f (R) = 0. We
show that τ 0 = τ̄ 0 , and by Theorem 3, we will be done.
Assume without loss of generality τ 0 < τ̄ 0 . For every R ∈ R, let p(R) = τ 0 + τ 1 and
p0 (R) = τ̄ (0) + τ̄ (1) if f (R) = 1, where τ 1 and τ̄ 1 are as defined in Theorem 3. We consider
two possible cases.
Case 1. Suppose τ̄ 1 ≥ τ 1 . Construct a positive income effect classical type R such that
W P (R, τ̄ 0 ) = τ̄ 1 − ,

W P (R, τ 0 ) = τ̄ 1 + ,

for some arbitrarily small  > 0. Notice that W P (R, τ̄ 0 ) < W P (R, τ 0 ). Since R consists ofall positive income effect classical types, such a R exists. Since W P (R, τ̄ 0 ) < τ̄ 1 , Theorem 3
implies that f (R) = 0. But W P (R, τ 0 ) > τ̄ 1 ≥ τ 1 implies f (R) = 1. This is a contradiction.
Case 2. Suppose τ̄ 1 < τ 1 . Construct a positive income effect classical type R such that
W P (R, τ̄ 0 ) = τ̄ 1 + ,

W P (R, τ 0 ) = τ 1 − ,for some arbitrarily small  > 0. Notice that since  > 0 can be chosen arbitrarily small,W P (R, τ 0 ) > W P (R, τ̄ 0 ), and since the type space consist of all positive income effect types,
such a R exists.
Since W P (R, τ̄ 0 ) > τ̄ 1 , Theorem 3 implies that f (R) = 1. On the other hand, since
W P (R, τ 0 ) < τ 1 , we have f (R) = 0. This is a contradiction.
Contradictions in all possible cases establish that τ 0 = τ̄ 0 . Hence, p = p0 .

Proof of Theorem 5
Proof : Suppose (f, p) is an incentive compatible mechanism. Note that by Theorem 1,
there exists a map κ : A → R such that p(R) = κ(f (R)) for all R. 11 By Lemma 1, we knowthat κ(a0 ) ≤ 0. If κ(a0 ) = 0, then we are done. Hence, assume that κ(a0 ) < 0.
We now define another mechanism by defining another map κ̃ : A → R as follows. We
first set κ̃(a0 ) = 0. Now, we define the rest of the values of κ̃ inductively. Denote A \ {a0 } ≡{a1 , . . . , aK } and without loss of generality assume that κ(a1 ) ≤ κ(a2 ) ≤ . . . ≤ κ(aK ).
11This is a necessary condition for incentive compatibility and does not requires the TP richness ofTheorem 1.

45

Now, we have defined κ̃(a0 ) = 0. Define κ̃(a1 ) as:κ̃(a1 ) := inf{V R (a1 , (a0 , κ̃(a0 ))) : f (R) = a1 }.
Having defined κ̃(a1 ), . . . , κ̃(ak ), we define κ̃(ak+1 ) as:κ̃(ak+1 ) := inf{V R (ak+1 , (aj , κ̃(aj ))) : f (R) = ak+1 and aj ∈ {a0 , a1 , . . . , ak }}.
The mechanism (f˜, p̃) is defined using κ̃ as follows. For every R, the agent chooses oneof the best bundles in{(a0 , 0), (a1 , κ̃(a1 )), . . . , (aK , κ̃(aK ))}according to R, where ties are broken in favor of higher indexed alternative. More formally,
M (R) := {(aj , κ̃(aj )) : (aj , κ̃(aj )) R (ak , κ̃(ak )) ∀ ak ∈ A}.
Then, f˜(R) = a` if a` ∈ M (R) and ` ≥ j for all aj ∈ M (R).
Suppose the chosen best bundle at R is (ak , κ̃(ak )), then f˜(R) = ak and p̃(R) = κ̃(ak ).
Trivially, this mechanism is incentive compatible since (f˜(R), p̃(R)) ∈ M (R) for all R. Further, since κ̃(a0 ) = 0, Lemma 1 implies that it is individually rational. We now complete theproof by showing p̃(R) ≥ p(R) for all R.
Step 1. In this step, we show that κ̃(a) ≥ κ(a) for all a ∈ A. By definition κ̃(a0 ) > κ(a0 ).
Also, by incentive compatibility of (f, p), for every R with f (R) = a1 , we have κ(a1 ) ≤V R (a1 , (a0 , κ(a0 ))). Since κ̃(a0 ) = 0 > κ(a0 ), we get κ(a1 ) < V R (a1 , (a0 , 0)). Hence, we getκ(a1 ) ≤inf
R:f (R)=a1

V R (a1 , (a0 , 0)) = κ̃(a1 ).

Now, assume that κ(aj ) ≤ κ̃(aj ) for all j ∈ {1, . . . , k}. We establish that κ(ak+1 ) ≤κ̃(ak+1 ). Pick any R such that f (R) = ak+1 . For every aj ∈ {a0 , a1 , . . . , ak }, incentive
compatibility of (f, p) implies thatκ(ak+1 ) ≤ V R (ak+1 , (aj , κ(aj ))).
As a result, we getκ(ak+1 ) ≤ inf{V R (ak+1 , (aj , κ(aj ))) : f (R) = ak+1 , aj ∈ {a0 , a1 , . . . , ak }.
By induction, κ(aj ) ≤ κ̃(aj ) for all aj ∈ {a0 , a1 , . . . , ak }. This implies that for every R withf (R) = ak+1 and for every aj ∈ {a0 , a1 , . . . , ak },V R (ak+1 , (aj , κ(aj ))) ≤ V R (ak+1 , (aj , κ̃(aj ))).
46

But then,κ(ak+1 ) ≤ inf{V R (ak+1 , (aj , κ̃(aj ))) : f (R) = ak+1 , aj ∈ {a0 , a1 , . . . , ak }} = κ̃(ak+1 ).
This completes the proof of this step.
Step 2. We complete the proof in this step. Consider R and denote f (R) = ak . By
definition, κ̃(ak ) ≤ V R (ak , (aj , κ̃(aj ))) for all j < k. Hence, (ak , κ̃(ak )) R (aj , κ̃(aj )) for all
j < k. By our tie-breaking rule for defining f˜, we have f˜(R) 6= aj for all j < k. Hence,f˜(R) = a` , where ` ≥ k. Butp̃(R) = κ̃(a` ) ≥ κ(a` ) ≥ κ(ak ) = p(R).
This completes the proof.

Proof of Lemma 2
Proof : Suppose (f, p) is incentive compatible. By Theorem 1, there exists κ : A → R suchthat p(R) = κ(f (R)) for all R. Just as in the proof of Theorem 2, we can show that for any
a, b ∈ A with b  a, we have κ(b) > κ(a).
A consequence of this observation is that the vector v, defined as vc = κ(c) for all c ∈ A,
respects . Now, pick any a ∈ A. Choose any  > 0 but arbitrarily close to zero. Then,the vector v 0 defined as vc0 = vc for all c 6= a and va0 = va + , also respects . Hence, byTP richness, there is a preference R such that v 0 ∈ I(R). Note that for any b 6= a, we have(a, κ(a)) P (b, κ(b)). Hence, incentive compatibility implies that f (R) = a. By definition ofv and v 0 , we get that for all b 6= a,
V R (a, (b, κ(b))) = κ(a) + .
Since  was arbitrarily close to zero, by letting  → 0, we getκ(a) =inf

V R (a, (b, κ(b))) for all b ∈ A.

R:f (R)=a

Similarly, we can define v 00 as vc00 = vc −  for all c 6= a and va00 = va . Note that forsufficiently small  > 0, v 00 respects . Hence, by TP richness, there is a preference R00 suchthat v 00 ∈ I(R00 ). Note that for any b 6= a, we have (a, κ(a)) P 00 (b, κ(b)). Hence, incentive
compatibility implies that f (R00 ) = a. By definition of v and v 00 , we get that for all b 6= a,00

V R (b, (a, κ(a))) = κ(b) − .
47

Since  > 0 was arbitrarily close to zero, by letting  → 0, we getκ(b) =00

V R (b, (a, κ(a))).

sup
R00 :f (R00 )=a

For the converse, choose any R, R0 ∈ R and we get,p(R) ≤ V R (f (R), (f (R0 ), p(R0 ))).
Hence, (f (R), p(R)) R (f (R0 ), p(R0 )). This shows that (f, p) is incentive compatible.

Proofs of Section 6
Proof of Proposition 1
Proof : We show that R,satisfies TP -richness, and the result follows from Theorems 1
rand 2. Pick v, v 0 ∈ R|A| such that v, v 0 are -parallel and pairwise consistent for . Assume
without loss of generality that v < v 0 . We first construct a preference R ∈ Rr . This is doneby specifying ν and B. We let B to be a large positive number such that B > maxa∈A v 0 (a).
We let ν(a0 ) = 0 and ν(b) = v(b) − v(a0 ) for all b 6= a0 . So, R ∈ Rr is a preference generated
0
from this choice of (ν, B). Similarly, define R as follows: B is same as before but ν 0 (a0 ) = 0
and ν 0 (b) = v 0 (b) − v 0 (a0 ) for all b 6= a0 . Hence, (ν 0 , B) defines R0 ∈ Rr . Notice that since v
00
and v are -parallel, d(R, R ) < .
Now, we construct another preference R̄ as follows. This is done by specifying the indifference vectors of R̄. For all v 00 < v, we have v 00 ∈ I(R̄) if and only if v 00 ∈ I(R). For all
v 00 > v 0 , we have v 00 ∈ I(R̄) if and only if v 00 ∈ I(R0 ). For all v ≤ v 00 ≤ v 0 , we have v 00 ∈ I(R̄)
if and only if there exists α ∈ [0, 1] such that v 00 = αv + (1 − α)v 0 . Informally, indifference
vectors to the left of v coincide with the indifference vector of R, to the right of v 0 coincidewith the indifference vector of R0 , and it is a “convex combination” of indifference vectors of
R and R0 between v and v 0 . It is clear that R̄ exists and belongs to R .
The fact that d(R̄, R) <  follows from the fact that v and v 0 are -parallel and d(R, R0 ) <. We formalize this intuition below. Choose any a 6= a0 .
0
For t < v(a0 ), V R (a, (a0 , t)) − V R̄ (a, (a0 , t)) = 0. For t > v 0 (a0 ), V R (a, (a0 , t)) −V R̄ (a, (a0 , t)) = 0. Now, for the final case, consider t ∈ [v(a0 ), v 0 (a0 )]. Suppose α ∈ [0, 1] is48

such that t = αv(a0 ) + (1 − α)v 0 (a0 ). Note that B > t. Hence,
V R (a, (a0 , t)) − V R̄ (a, (a0 , t))= [v(a) + t − v(a0 )] − [αv(a) + (1 − α)v 0 (a)]= [v(a) − v(a0 ) + αv(a0 ) + (1 − α)v 0 (a0 )] − [αv(a) + (1 − α)v 0 (a)]= (1 − α)([v(a) − v(a0 )] − [v 0 (a) − v 0 (a0 )])< ,
where the second equality follows from the definition of t and the inequality follows from thefact that v and v 0 are -parallel and α ∈ [0, 1]. Hence, d(R, R̄) < .
Proof of Theorem 6
Proof : One direction is easy and skipped. For the other direction, we propose a straightforward extension of Theorem 3 to the n-agent case. For completeness, we state the result
without a proof.
Theorem 7 (n-agent Theorem 3) Suppose R is a classical type space satisfying strong
WP-convexity and (f, p) is a mechanism defined on Rn . Then, (f, p) is DSIC if and only if
for every agent i ∈ N , there exists a map τi0 : Rn−1 → R such that for every R−i ∈ Rn−1 ,• WP-Monotonicity. for every Ri , Ri0 ∈ R with fi (Ri , R−i ) = 1,
h
i
0
0
0
W P (Ri , τi (R−i )) > W P (Ri , τi (R−i )) ⇒ fi (Ri0 , R−i ) = 1,
• Payment formula. for every Ri ∈ R,
pi (Ri , R−i ) = τi0 (R−i ) + fi (Ri , R−i ) · τi1 (R−i ),where τi1 (R−i ) = inf{W P (Ri0 , τi0 (R−i )) : Ri0 ∈ R, fi (Ri0 , R−i ) = 1}.
Though Theorem 7 is a simple extension of Theorem 3 to the multi-agent case, it shows
the informational complexity of an incentive compatible mechanism in the multi-agent model.
Now, τi0 and τi1 are maps that depend on the preferences of other agents. As a result, themechanism must elicit infinite number of willingness to pay of each agent. In contrast, a
one-agent incentive compatible mechanism only elicits one value of willingness to pay.
Now, let (f, p) be a DSIC, anonymous mechanism on a rich classical type space R satisfying LPI. By Theorem 7 and LPI property, there exists τ 0 such that for every i ∈ N and49

for all R ∈ R, fi (R) = 0 implies pi (R) = τ 0 and fi (R) = 1 implies pi (R) = τ 0 + τi1 (R−i ),where τi1 (R−i ) is as defined in Theorem 7. We now do the proof in three steps.
Step 1. Consider the following property.
Definition 20 A mechanism (f, p) satisfying LPI (at τ 0 ) is restricted WP-efficient if
for all R ∈ R with fi (R) = 1 for some i ∈ N , we have W P (Ri , τ 0 ) ≥ W P (Rj , τ 0 ) for allj ∈ N.
We show that (f, p) is restricted WP-efficient. Assume for contradiction that there is a typeprofile R such that fi (R) = 1 and W P (Ri , τ 0 ) < W P (Rj , τ 0 ) for some j 6= i. Consider
Ri0 = Rj . By definition W P (Ri0 , τ 0 ) > W P (Ri , τ 0 ) and monotonicity in Theorem 7 implies
that fi (Ri0 , Rj , R−ij ) = 1. Further, W P (Ri0 , τ 0 ) > W P (Ri , τ 0 ) ≥ τi1 (R−i ). By anonymity,(1, τ 0 + τi1 (R−i )) Ij (0, τ 0 ) Ij (1, τ 0 + W P (Rj , τ 0 )).
This implies that τi1 (R−i ) = W P (Rj , τ 0 ) = W P (Ri0 , τ 0 ), a contradiction.
Step 2. In this step, we define the reserve price map. Consider two agents i and j. Fix
a type R0 ∈ R and R−ij ∈ Rn−1 . Notationally, whenever we write a type profile in thisstep, we first write the type of agent i, followed by the type of agent j, and then R−ij . We
first show that there is Ri ∈ R such that fi (Ri , R0 , R−ij ) = 1 if and only if there is Rj ∈ Rsuch that fj (R0 , Rj , R−ij ) = 1. To show this, suppose fi (Ri , R0 , R−ij ) = 1. By Theorem
7, we can choose Ri such that W P (Ri , τ 0 ) > τi1 (R0 , R−ij ). Now, consider the type profile(R0 , Rj , R−ij ), where Rj = Ri . If fj (R0 , Rj , R−ij ) = 0, then anonymity implies(1, τ 0 + W P (Rj , τ 0 )) Ij (0, τ 0 ) Ij (1, τ 0 + τ 1 (R0 , R−ij )).
But this implies that τi1 (R0 , R−ij ) = W P (Rj , τ 0 ) = W P (Ri , τ 0 ), a contradiction.
Hence, there is Ri ∈ R such that fi (Ri , R0 , R−ij ) = 1 if and only if there is Rj ∈ R suchthat fj (R0 , Rj , R−ij ) = 1. Now, suppose that there is Ri ∈ R such that fi (Ri , R0 , R−ij ) = 1.
We show that τi1 (R0 , R−ij ) = τj1 (R0 , R−ij ). First, note that by strong WP-convexity and Theorem 7, we can assume W P (Ri , τ 0 ) > max{τi1 (R0 , R−ij ), τj1 (R0 , R−ij )} without loss of generality. Consider the type profile (R0 , Rj0 , R−ij ), where Rj0 = Ri . Note that since W P (Rj0 , τ 0 ) =W P (Ri , τ 0 ) > τj1 (R0 , R−ij ), by Theorem 7, fj (R0 , Rj0 , R−ij ) = 1. By anonymity,(1, τ 0 + τi1 (R0 , R−ij )) Ii (1, τ 0 + τj1 (R0 , R−ij )).
Hence, τi1 (R0 , R−ij ) = τj1 (R0 , R−ij ).
50

Now, if there is Ri ∈ R such that fi (Ri , R0 , R−ij ) = 1, then define r(R0 , R−ij ) =τi1 (R0 , R−ij ) = τj1 (R0 , R−ij ). If fi (Ri , R0 , R−ij ) = 0 for all Ri ∈ R, then define r(R0 , R−ij ) =βτ 0 , where we had assumed that the willingness to pay at transfer level τ 0 lies in (0, βτ 0 ).
Step 3. We now verify the three conditions in the definition of AVVR mechanism withrespect to the reserve price map r defined in Step 2. Fix a type profile R ∈ Rn .
First, suppose W (R; r) = ∅. Assume for contradiction for some i ∈ N , fi (R) = 1. Then,by definition, r(R−i ) = τi1 (R−i ). Hence, by Theorem 7, W P (Ri , τ 0 ) ≥ τi1 (R−i ) = r(R−i ).
Step 1 implies that W P (Ri , τ 0 ) ≥ W P (Rj , τ 0 ) for all j ∈ N . Hence, i ∈ W (R; r), which isa contradiction.
Second, let i ∈ W ∗ (R; r). Then, by definition of W ∗ (R; r), we have W P (Ri , τ 0 ) > r(R−i ).
If r(R−i ) = βτ 0 , then W P (Ri , τ 0 ) > βτ 0 , which contradicts the fact that W P values at τ 0 lie
in (0, βτ 0 ). Hence, r(R−i ) = τi1 (R−i ). This implies that W P (Ri , τ 0 ) > τi1 (R−i ). By Theorem
7, fi (R) = 1.
Finally, if fi (R) = 1 for some i ∈ N , then Theorem 7 implies W P (Ri , τ 0 ) ≥ τi1 (R−i ) =r(R−i ). Step 1 then implies that i ∈ W (R; r).
We conclude the proof by showing the payment in this mechanism coincides with thepayment formula given in the definition of the AVVR mechanism. By Theorem 7 and LPI, if
fi (R) = 0 then pi (R) = τ 0 . Further, if fi (R) = 1 then pi (R) = τ 0 + τi1 (R−i ) = τ 0 + r(R−i ).
We show that maxj6=i W P (Rj , τ 0 ) ≤ r(R−i ). To see this, suppose fi (R) = 1 and r(R−i ) <maxj6=i W P (Rj , τ 0 ). Then we can choose Ri0 such that τi1 (R−i ) = r(R−i ) < W P (Ri0 , τ 0 ) <maxj6=i W P (Rj , τ 0 ). By Theorem 7, fi (Ri0 , R−i ) = 1. But this contradicts restricted WPefficiency in Step 1. Hence, maxj6=i W P (Rj , τ 0 ) ≤ r(R−i ), and this showspi (R) = τ 0 + fi (R) · max r(R−i ), max W P (Rj , τ 0 ) .
j6=i

Proof of Proposition 3
Proof : Let RC be the set of all classical preferences. It is enough to show that every
MWEP mechanism is DSIC on the domain RC . Let (f, p) be an MWEP mechanism definedon RC . Since RC satisfies TP richness for any , by Theorem 1, it is enough to show that(f, p) satisfies taxation principle and monotonicity.
To establish this, we will need a result from the literature. Fix a type profile R ≡(R1 , . . . , Rn ) and a price vector π ∈ RA
+ with πa0 = 0. For any S ⊆ M , the demanders of51

S areU (S, π; R) := {i ∈ N : D(Ri , π) ∩ S 6= ∅}.
For any S ⊆ M , the exclusive demanders of S are
O(S, π; R) := {i ∈ N : D(Ri , π) ⊆ S}.
Morimoto and Serizawa (2015) show that if π is the minimum Walrasian equilibrium
price vector at R, then|O(S, π; R)| ≤ |S|∀S⊆M|U (S, π; R)| > |S|∀ S ⊆ M such that πa > 0 ∀ a ∈ S.

The first condition is clearly necessary - if the number of exclusive demanders of S is morethan |S|, then they cannot be assigned in any Walrasian equilibrium. The necessity of thesecond condition is non-trivial - intuitively, if the second condition is not true, we can reduce
the price of objects in S and get a new Walrasian equilibrium price, contradicting minimalityof π. 12Consider two type profiles (Ri , R−i ) and (Ri0 , R−i ) and denote π ≡ π min (Ri , R−i ) andπ 0 ≡ π min (Ri0 , R−i ). Suppose fi (Ri , R−i ) = a, fi (Ri0 , R−i ) = b. Consider the following sets:00M π<π := {x ∈ M : πx < πx0 },M π>π := {x ∈ M : πx > πx0 }.

00Note that πx > 0 for each x ∈ M π>π and πx0 > 0 for each x ∈ M π<π . Hence, a0 ∈
/
π<π 0
π>π 0
(M
∪M
). We prove the following claim.
00Claim 1 The following hold: (1) a ∈/ M π<π and (2) b ∈/ M π>π .
0

Proof : Suppose a ∈ M π<π . Since π 0 is the MWEP at (Ri0 , R−i ) and πx0 > 0 for each0x ∈ M π<π ,00

U (M π<π , π 0 ; (Ri0 , R−i )) ≥ |M π<π | + 1.
0

(2)
0

Denote N̂ := U (M π<π , π 0 ; (Ri0 , R−i )) \ {i}. Since prices of only objects in M π<π decrease
from π 0 to π and preferences of agents in N̂ do not change from (Ri , R−i ) to (Ri0 , R−i ), we00have N̂ ⊆ O(M π<π , π; (Ri , R−i )). But Inequality 2 implies that |N̂ | ≥ |M π<π |. This in0
turn implies that no agent outside N̂ can be assigned an object in M π<π in the MWEP π0
at (Ri , R−i ). But i ∈/ N̂ , a ∈ M π<π , and fi (Ri , R−i ) = a gives us a contradiction.
12

Morimoto and Serizawa (2015) show that these two conditions are necessary and sufficient for any pricevector to be the minimum Walrasian equilibrium price vector.

52

0

An analogous proof can be done for b ∈/ M π>π .



We now complete the proof in two steps.
00
Taxation principle. If a = b, then by Claim 1, a ∈/ M π<π ∪ M π>π . This implies that
πa = πa0 , and we are done.

Monotonicity. Suppose fi (Ri , R−i ) = a, fi (Ri0 , R−i ) = b. Assume for contradiction that0
V Ri (b, (a, πa )) < V Ri (b, (a, πa )). Since a ∈ D(Ri , π), we must have πb ≥ V Ri (b, (a, πa )) >00
V Ri (b, (a, πa )). Suppose πa0 ≤ πa , then b ∈ D(Ri0 , π 0 ) implies that πb0 ≤ V Ri (b, (a, πa0 )) <00
V Ri (b, (a, πa )) < πb . Hence, b ∈ M π>π , a contradiction to Claim 1.
0
Similarly, if πa0 > πa , we have a ∈ M π<π , a contradiction to Claim 1.
References
Adachi, T. (2014): “Equity and the Vickrey allocation rule on general preference domains,”
Social Choice and Welfare, 42, 813–830.
Ashlagi, I., M. Braverman, A. Hassidim, and D. Monderer (2010): “Monotonicity
and implementability,” Econometrica, 78, 1749–1772.
Ashlagi, I. and S. Serizawa (2012): “Characterizing Vickrey allocation rule byanonymity,” Social Choice and Welfare, 38, 531–542.
Ausubel, L. M. and P. Milgrom (2002): “Ascending auctions with package bidding,”
Frontiers of Theoretical Economics, 1, 1–42.
Baisa, B. (2017): “Auction design without quasilinear preferences,” Theoretical Economics,
12, 53–78.
——— (2016): “Efficient multi-unit auctions for normal goods,” Available at SSRN 2824921.
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.
Borgers, T., D. Krahmer, and R. Strausz (2015): An introduction to the theory ofmechanism design, Oxford University Press, USA.
53

Carbajal, J. C. and J. Ely (2013): “Mechanism design without revenue equivalence,”
Journal of Economic Theory, 148, 104–133.
Carbajal, J. C. and R. Müller (2015): “Implementability under monotonic transformations in differences,” Journal of Economic Theory, 160, 114–131.
Che, Y.-K. and I. Gale (2000): “The optimal mechanism for selling to a budgetconstrained buyer,” Journal of Economic Theory, 92, 198–233.
Chung, K.-S. and W. Olszewski (2007): “A non-differentiable approach to revenue
equivalence,” Theoretical Economics, 2, 1–19.
Clarke, E. (1971): “Multipart pricing of public goods,” Public Choice, 11, 17–33.
Cuff, K., S. Hong, J. A. Schwartz, Q. Wen, and J. Weymark (2012): “Dominant
strategy implementation with a convex product space of valuations,” Social Choice andWelfare, 39, 567–597.
Demange, G. and D. Gale (1985): “The strategy structure of two-sided matching markets,” Econometrica, 53, 873–888.
Dobzinski, S., R. Lavi, and N. Nisan (2012): “Multi-unit auctions with budget limits,”
Games and Economic Behavior, 74, 486–503.
Garratt, R. and M. Pycia (2016): “Efficient bilateral trade,” Working Paper, UCLA.
Groves, T. (1973): “Incentives in teams,” Econometrica, 41, 617–631.
Hashimoto, K. and H. Saitoh (2010): “Domain expansion of the pivotal mechanism,”Social Choice and Welfare, 34, 455–470.
Heydenreich, B., R. Muller, M. Uetz, and R. V. Vohra (2009): “Characterizationof revenue equivalence,” Econometrica, 77, 307–316.
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): “Multi-object auction design
without quasilinearity: Revenue maximization with no wastage,” ISER Discussion paper
No. 1001.

54

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.
Kos, N. and M. Messner (2013): “Incentive compatibility in non-quasilinear environments,” Economics Letters, 121, 12–14.
Krishna, V. and E. Maenner (2001): “Convex potentials with an application to mechanism design,” Econometrica, 69, 1113–1119.
Lavi, R. and M. May (2012): “A note on the incompatibility of strategy-proofness andpareto-optimality in quasi-linear settings with public budgets,” Economics Letters, 115,
100–103.
Ma, H., R. Meir, and D. C. Parkes (2016): “Social choice for agents with general Utilities,” in Proceedings of the 25th International Joint Conference on Artificial Intelligence(IJCAI’16), 345–351.
Milgrom, P. and I. Segal (2002): “Envelope theorems for arbitrary choice sets,” Econometrica, 70, 583–601.
Mishra, D., A. Pramanik, and S. Roy (2014): “Multidimensional mechanism design insingle peaked type spaces,” Journal of Economic Theory, 153, 103–116.
Mishra, D. and S. Roy (2013): “Implementation in multidimensional dichotomous domains,” Theoretical Economics, 8, 431–466.
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.
Carbajal, J.C. and A. Mualem (2017): “Revenues and budgets: Selling mechanisms forfinancially constraint buyers,” Working Paper.
Muller, R., A. Perea, and S. Wolf (2007): “Weak monotonicity and Bayes-Nashincentive compatibility,” Games and Economics Behavior, 61, 344–358.
Myerson, R. B. (1981): “Optimal auction design,” Mathematics of Operations Research,
6, 58–73.

55

Myerson, R. B. and M. A. Satterthwaite (1983): “Efficient mechanisms for bilateral
trading,” Journal of Economic Theory, 29, 265–281.
Noldeke, G. and L. Samuelson (2015): “The implementation duality,” Cowles Foundation Discussion Paper.
Pai, M. M. and R. Vohra (2014): “Optimal auctions with financially constrained buyers,”
Journal of Economic Theory, 150, 383–425.
Rochet, J. C. (1987): “A necessary and sufficient condition for rationalizability in a quasilinear context,” Journal of Mathematical Economics, 16, 191–200.
Rockafellar, R. T. (1970): Convex analysis, Princeton University Press, Princeton, New
Jersey.
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.
Saks, M. E. and L. Yu (2005): “Weak monotonicity suffices for truthfulness on convex
domains,” in Proceedings of 7th ACM Conference on Electronic Commerce, ACM Press,
286–293.
Thomson, W. (2016): “The theory of fair allocation,” Forthcoming, Princeton University
Press, Princeton, New Jersey.
Vickrey, W. (1961): “Counterspeculation, auctions, and competitive sealed tenders,” Journal of Finance, 16, 8–37.
Vohra, R. V. (2011): Mechanism design: A linear programming approach, Cambridge
University Press.

56

Yamashita, T. (2015): “Implementation in weakly undominated strategies: Optimality of
second-price auction and posted-price mechanism,” The Review of Economic Studies, 82,1223–1246.
Zhou, Y. and S. Serizawa (2016): “Strategy-proofness and efficiency for non-quasi-linear
common-tiered-object preferences: Characterization of minimum price rule,” ISER Discussion paper No. 971.

57

Appendix B: Optimal mechanism with many agentsIn this appendix, we explore how to extend the one-agent optimal mechanism analysis of
Section 6.2 to the multiple agent case. There are two difficulties in extending the analysis of
the one agent model.
1. First, the two parameters τi0 and τi1 will now depend on the preferences of agentsother than i - note that these are infinite dimensional objects. As a result, the onedimensionality nature of the problem in the one-agent case (Section 6.2) is lost. This
makes optimization difficult. To partially overcome this intractability issue, we focus
attention on a simpler class of mechanisms that we call WP-mechanisms and makesome observations about optimality inside this class.
2. The second problem with the multi-agent case is the payment to losing agents. To
remind, the analysis in Section 6.2 became tractable because the payment of the losing
agent (i.e., if an agent does not get the object) could be fixed to zero by Theorem 5.
The technique of Theorem 5 does not extend to the multiple agents case because when
there are more than one agent, the new mechanism constructed in Theorem 5 may notnecessarily be feasible. Since the losing agents’ payment cannot be fixed at zero, it
adds new problems to the optimization.
Below, we focus on a restricted class of mechanisms and show that standard Myersonian
techniques can be extended inside this class. This allows us to make some observations about
the nature of the expected revenue maximizing mechanism.
We say two type profiles R and R0 are WP-equivalent at t if W P (Ri , t) = W P (Ri0 , t)
for all i ∈ N . The following class of mechanisms fixes the payment of losing agents at somevalue and then elicits only the WP values of agents at that payment.
Definition 21 A mechanism (f, p) is a WP-mechanism if there exists a real number τ 0such that
1. fi (R) = 0 implies pi (R) = τ 0 for all R and for all i ∈ N ,2. fi (R) = fi (R0 ) and pi (R) = pi (R0 ) for all i ∈ N if R and R0 are WP-equivalent at τ 0 .
By Theorem 7, every WP-mechanism must announce a τ 0 (the amount a losing agentpays), and determines the allocation and transfer amounts based on the WP values of agentsat τ 0 . Given a value of τ 0 and a type profile R, we denote the profile of W P (R1 , τ 0 ), . . . , W P (Rn , τ 0 )58

as w(τ 0 ). For simplicity, we denote by fi (w(τ 0 )) the allocation fi (R) and by pi (w(τ 0 )) thetransfer pi (R).
By Theorem 7, the payment of agent i at this type profile ispi (w(τ 0 )) = τ 0 + τi1 (w−i (τ 0 ))fi (w(τ 0 )).
We need to compute the expected payment of each agent from a mechanism. For this, weassociate priors on the WP values at τ 0 . We assume that for every t ∈ R, the WP values att are drawn from some absolutely continuous distribution G(·; t) with density g(·; t) from a
support (0, β), where β ∈ R++ ∪ {∞} - note that the support of WP values is independentof t. 13 We also assume that G(·; t) is regular in the sense that for all w > w0 and for allt ≤ 0, we haveg(w0 ; t)g(w; t)≥.
1 − G(w; t)
1 − G(w; t)Using such a distribution, we compute the expected payment of agent from a WPmechanism (f, p) and denote it as ρi (f, p).
A mechanism (f, p) is individually rational if for every i ∈ N and every R, we have(fi (R), pi (R)) ≥ 0. The proof of Lemma 1 can be replicated to show that a DSIC mechanism(f, p) is individually rational if and only if the payment of losing agents is non-positive, i.e.,
for a WP-mechanism at τ 0 , we must have τ 0 ≤ 0.
A WP-mechanism (f, p) is an optimal WP-mechanism if it is DSIC and individually
rational, and for every DSIC and individually rational WP-mechanism (f 0 , p0 ) we haveXX
ρi (f, p) ≥ρi (f 0 , p0 ).
i∈N

i∈N

We provide a partial description of the optimal WP-mechanism below.
Theorem 8 An optimal WP-mechanism satisfies the following. There exists a non-positive
number τ 0 ≤ 0 such that• each agent is paid a subsidy −τ 0 ≥ 0 before he announces his type,0)• a reserve price r = φ−1 (0) is announced, where φ is the map φ(w) = w − 1−G(w;τfor
g(w;τ 0 )all w,• for all R,
13This assumption and the symmetry assumption can be changed without changing the qualitative natureof the results below.

59

– the object is not allocated and no transfers are made if W P (Ri , τ 0 ) < r ∀ i ∈ N ;– else it is allocated to an agent with highest W P (·; τ 0 ) value.
In the latter case, the winning agent i pays an amount equal to max(r, maxj6=i W P (Rj , τ 0 )).
Essentially, Theorem 8 says that the optimal WP-mechanism is the standard Vickrey
auction with the appropriate reserve price, but with two significant differences: (1) somesubsidy −τ 0 may have to be given to all the agents before the start of the auction; and (2)the Vickrey auction with reserve price is conducted with respect to the willingness to pay at
W P (·, τ 0 ).
Below, we provide a proof of Theorem 8 - once we use Theorem 7, it follows standard
Myersonian techniques. The computation of optimal value of τ 0 will depend on the particulars of the model. It seems unlikely that a particular recommendation of τ 0 can be made fora general enough class of models.
Proof of Theorem 8
Proof : A consequence of our result in Theorem 7 is that a DSIC and IR WP-mechanism iscompletely described by a real number τ 0 ≤ 0 and the allocation rule x (which only depends
on the WP values at τ 0 ).
Fix any such WP-mechanism that satisfies τ 0 ≤ 0. For simplicity, we will denote the WPof an agent i at the specified τ 0 as wi . At a profile of WP w, the payment of agent i is givenbyZwipi (w) = τ 0 + τi1 (w−i )fi (w) = τ 0 + wi fi (w) −fi (yi , w−i )dyi .
0Hence, expected payment of agent i with WP wi is given byZ
Z wi Z000
EP (wi ; τ ) = τ + wi fi (wi , w−i )g−i (w−i ; τ )dw−i −fi (yi , w−i )g−i (w−i ; τ 0 )dw−i dyi .
0
Z wi= τ 0 + wi EF (wi ; τ 0 ) −EF (yi ; τ 0 )dyi ,0where EF (yi ; τ 0 ) :=Rfi (yi , w−i )g−i (w−i ; τ 0 )dw−i for all yi . Hence, expected revenue from60

agent i is given by
Z β Z wiZ β000
EFi (yi ; τ 0 )dyi gi (wi ; τ 0 )dwi .
wi EFi (wi ; τ )gi (wi ; τ )dwi −
τ +
0
0
0
Z βZ βZ βgi (yi ; τ 0 )dyi EFi (wi ; τ 0 )dwi .
wi EFi (wi ; τ 0 )gi (wi ; τ 0 )dwi −= τ0 += τ0 +

0

0

Z β

Z β

wi EFi (wi ; τ 0 )gi (wi ; τ 0 )dwi −0= τ0 +0= τ0 +(1 − Gi (wi ; τ 0 ))EFi (wi ; τ 0 )dwi

0

Z β
Z β

wi

1 − Gi (wi ; τ 0 ) wi −EFi (wi ; τ 0 )gi (wi ; τ 0 )dwi
gi (wi ; τ 0 )φ(wi ; τ 0 )EFi (wi ; τ 0 )gi (wi ; τ 0 )dwi ,00i (wi ;τ )where φ(wi ; τ 0 ) := wi − 1−G
for all wi . Hence, expected revenue from the mechanismgi (wi ;τ 0 )is given by
X
XZ β
0
τ +
φ(wi ; τ 0 )EFi (wi ; τ 0 )gi (wi ; τ 0 )dwi

i∈N

i∈N
0

= nτ +0XZ β

0φ(wi ; τ )Zfi (wi , w−i )g−i (w−i ; τ 0 )dw−i gi (wi ; τ 0 )dwi

0= nτ 0 +

i∈N
Z
X


φ(wi ; τ 0 )fi (wi , w−i ) g(w; τ 0 )dw.

i∈N

For a fixed τ 0 ≤ 0, the second term in the above expression is maximized by the standard
Myersonian argument (under regularity, i.e., ) by maximizing virtual values - this leads us
the standard optimal mechanism in the symmetric case, which is a second price Vickrey
auction with a reserve price equal to φ−1 (0). This establishes the result.


61