OSIPP Discussion Paper : DP-2024-E-003

Strategy-proof allocation problem withhard budget constraints and income effects:
weak efficiency and fairness
May 24, 2024
Yuya Wakabayashi1
JSPS Research Fellow (DC2), Graduate School of Economics, Osaka University

Ryosuke Sakai2
Assistant professor, School of Engineering, Tokyo Institute of Technology

Hiroki Shinozaki3
Specially Appointed Assitant Professor, Hitotsubashi Institute for Advanced Study,
Hitotsubahi University

Abstract: We consider the single-object allocation problem with monetary transfers. Agents
have hard budgets and their utility functions may exhibit income effects. We characterize
truncated Vickrey rules with endogenous reserve prices by constrained efficiency or weak
envy-freeness for equals, in addition to individual rationality, no subsidy for losers, andstrategy-proofness. The same characterization result hold even if we replace weak envy
freeness for equals with other fairness conditions; equal treatment of equals, envy-freeness,
and anonymity in welfare.
JEL classification: D47, D63, D82
Keywords: Single-object allocation problem, Non-quasi-linear preference, Hard budget
constraint, Efficiency, Fairness, Strategy-proofness, Vickrey rule with reserve prices

1

Email: u690485a@ecs.osaka-u.ac.jp
Email: sakai.r.al@m.titech.ac.jp
3
Email: shinozaki.hiroki@r.hit-u.ac.jp2Strategy-proof allocation problem withhard budget constraints and income eﬀects:
weak eﬃciency and fairness∗
Yuya Wakabayashi †Ryosuke Sakai ‡Hiroki Shinozaki §May 24, 2024

Abstract
We consider the single-object allocation problem with monetary transfers. Agents
have hard budgets and their utility functions may exhibit income eﬀects. When hardbudget constraints exist, it is known that eﬃciency and strategy-proofness are incompatible along with individual rationality and no subsidy. Our objectives are (i)to explore which forms of partial eﬃciency are compatible with strategy-proofness,and (ii) to investigate strategy-proof rules that satisfy some fairness conditions, instead of eﬃciency. We focus on constrained eﬃciency as a weak eﬃciency condition,and on weak envy-freeness for equals as a fairness condition. We introduce truncatedVickrey rules with endogenous reserve prices. Some of them may fail to satisfy either
constrained eﬃciency, weak envy-freeness for equal, or strategy-proofness. In order tosatisfy the properties, we impose additional conditions:exclusive tie-breaking rules,
non-negligible reserve prices, and prioritized tie-breaking rules, respectively. First
we show that the truncated Vickrey rule with endogenous reserve prices and with an
exclusive and prioritized tie-breaking rule are the only rules satisfying constrained
eﬃciency, individual rationality, no subsidy for losers, and strategy-proofness. Next
we show that the truncated Vickrey rules with non-negligible endogenous reserve
prices and with a prioritized tie-breaking rule are the only rules satisfying weak
envy-freeness for equals, individual rationality, no subsidy for losers and strategyproofness. This characterization also holds when replacing weak envy-freeness forequals with equal treatment of equals or envy-freeness. Moreover, if endogenous
reserve prices are upper anonymous, then the same result holds for anonymity inwelfare.

JEL classification: D47, D63, D82.
Keywords: Single-object allocation problem, Non-quasi-linear preference, Hard budget constraint, Eﬃciency, Fairness, Strategy-proofness, Vickrey rule with reserve prices.
∗

We thank to financial support from the Japan Society for the Promotion of Science (22J01525,
22KJ1785, 23KJ1453, 23K18777).
†
Graduate School of Economics, Osaka University. Email: u690485a@ecs.osaka-u.ac.jp‡
School of Engineering, Tokyo Institute of Technology. Email: sakai.r.al@m.titech.ac.jp§
Hitotsubashi Institute for Advanced Study, Hitotsubashi University. Email: shinozaki.hiroki@r.hitu.ac.jp1

1

Introduction

In real-life auctions, participants often face budget constraints, which is the maximum
amount of money they can spend on auctioned objects. An important example of budgetconstrained auctions is a spectrum license auction (Bulow et al. 2009), where firms mustput aside money in advance to acquire spectrum licenses. The presence of budget constraints significantly complicates firms’ bidding strategies and challenges the applicationof existing theoretical frameworks that do not consider budget constraints.
It is one of crucial goals for auctioneers to allocate objects eﬃciently to agents. Moreover, to accurately evaluate eﬃciency based on true preferences, auctioneers require
strategy-proofness, where reporting true utility functions becomes a dominant strategy.
If utility functions are quasi-linear, and so there is no budget constraint, then the Groves
rules are the only rules satisfying eﬃciency and strategy-proofness (Holmström, 1979).
However, Dobzinski et al. (2012) demonstrate that if private budgets exist, which undermines quasi-linearity of utility functions, then no rule satisfies these conditions alongwith individual rationality and no subsidy.
Building upon the seminal work of Dobzinski et al. (2012), subsequent literature
has investigated budget-constrained auctions, striving to achieve positive results. There
are various approaches to reconcile the conflict between eﬃciency and strategy-proofness.
One approach is to restrict the domain of preferences. Dobzinski et al. (2012) showthat if budgets are public information, then there is a rule satisfying eﬃciency, individual
rationality, no subsidy, and strategy-proofness. Mackenzie and Zhou (2022) also establish
a similar positive result when budgets are private information, but payments are discrete
and agents demand at most one object (unit-demand).
Alternatively, some studies opt to compromise either eﬃciency or strategy-proofness.
Le (2018) relaxes these conditions and constructs a rule that satisfies eﬃciency andstrategy-proofness for “almost all preferences” in addition to individual rationality andno subsidy.
We must note that the studies mentioned above do not account for the income eﬀects
experienced by agents. In large-scale auctions such as spectrum license auctions, substantial payments can diminish agents’ capacity to aﬀord certain complementary goods
related to the auctioned objects, thereby leading to significant income eﬀects. Thus, thepresence of income eﬀects, alongside budget constraints, constitutes a crucial aspect ofreal-life auctions. However, there is limited literature on non-quasi-linear utility due tothe complexities introduced by income eﬀects in the analysis.
In this paper, we consider an environment where both budget constraints and income eﬀects are present, aiming to derive positive results by relinquishing eﬃciency. One
natural approach to achieving positive results is to moderate eﬃciency. While full eﬃciency is incompatible with strategy-proofness, certain degrees of partial eﬃciency may
be reconcilable. Our primary objective is to explore which forms of partial eﬃciency arecompatible with strategy-proofness, while ensuring individual rationality and no subsidy.
2

As an alternative approach, we impose fairness conditions, instead of eﬃciency, suchas envy-freeness, anonymity in welfare, equal treatment of equals, and others. Althoughsociety often prioritizes these fairness conditions, there is limited literature examining
budget-constrained auctions that simultaneously satisfy fairness conditions and maintainstrategy-proofness. Our secondary objective is to investigate whether there is a rule thatsatisfies certain fairness conditions and strategy-proofness, in addition to individual rationality and no subsidy.

1.1

ResultWe consider the single-object allocation problem with monetary transfers. Each agent
has a utility function which depends on the assignment of the object and the payment.
Our formulation is so general that agents’ utility functions can exhibit income eﬀect.
Additionally, each agent has a hard budget constraint, wherein payments exceeding thebudget render their utility as negative infinity. We call the set of utility functions thedomain. A utility profile is a vector consisting agents’ utility functions. An allocation
specifies who gets the object and how much agents pay.
The willingness to pay is called the valuation. We define the minimum between thewillingness to pay and the budget as the truncated valuation. When receiving the object
and paying the budget is strictly better than receiving no object with no payment foran agent, we say that the budget constraint is binding. This is because in this case, thetruncated valuation is equal to the budget.
A rule is a mapping from a set of utility profiles to the set of allocations. A rule satisfies
individual rationality if each agent’s outcome is at least as good as receiving no object andpaying nothing. A rule satisfies no subsidy for losers if each agent who receives no object
makes the nonnegative payment. We focus on weak envy-freeness for equals as a fairness
condition, introduced by Sakai (2013a). It requires that if two agents with identical utility
functions diﬀer in outcome (one being a winner, the other a loser), then the loser does
not prefer the winner’s outcome. This condition is so weak that it is implied by manyother fairness conditions, such as equal treatment of equals, envy-freeness, anonymity inwelfare, and so on.
When budget constraints exist, Vickrey rules may violate individual rationality because some agent may pay the money exceeding his/her budget. To address this issue,
Le (2018) proposed truncated Vickrey rules, which realize the outcome of a Vickery rule
where inputs are truncated valuations, not valuations. He demonstrates that this rulesatisfies eﬃciency and strategy-proofness for almost all utility profiles. However, whenthese properties need to be guaranteed for all profiles, Le’s formulation is insuﬃcient.
Therefore, we introduce a truncated Vickrey rule with endogenous reserve prices by extending the truncated Vickrey rule. In this extended version, each agent’s reserve price isdetermined endogenously by other agents’ utility functions.
In the presence of budget constraints, achieving both eﬃciency and strategy-proofness,3

in addition to individual rationality and no subsidy for losers, is impossible. However,
we can aim for certain degrees of partial eﬃciency. To pursue this goal, we decompose
eﬃciency into three conditions. The first condition is within budget, which mandates
that each agent’s payment does not exceed their budget. The second condition is nowastage, which ensures that the object is always assigned to an agent. The third condition
is constrained eﬃciency, which demands that no reallocation can improve both agents’
welfare and revenue simultaneously. In this study, we forgo no wastage and focus ondeveloping a rule that satisfies within budget and constrained eﬃciency, in addition toindividual rationality, no subsidy for losers, and strategy-proofness.
All truncated Vickrey rules with endogenous reserve prices satisfy within budget, individual rationality, and no subsidy for losers. However, some of them fail to satisfy either
constrained eﬃciency, weak envy-freeness for equals, or strategy-proofness. Whether these
conditions hold depends on the chosen tie-breaking rules and endogenous reserve prices.
Achieving strategy-proofness requires a tie-breaking rule to satisfy a prioritized condition. In this condition, if ties exist, the agent whose budget constraint is binding wins theobject. Furthermore, constrained eﬃciency necessitates a tie-breaking rule satisfying an
exclusive condition. The condition requires that when ties exist, the agent whose budget
constraint is not biding loses the object.
Attaining weak envy-freeness for equals requires endogenous reserve prices to satisfy
non-negligibility condition. The non-negligibility requires that for an agent, his/her reserve
price is strictly larger than the maximum truncated valuation among other agents if theother agent with the highest truncated valuation has the binding budget constraint.
Our first results are about eﬃciency. We show that the truncated Vickrey rules withendogenous reserve prices and with an exclusive and prioritized tie-breaking rule are theonly rules satisfying constrained eﬃciency, individual rationality, no subsidy for losers,
and strategy-proofness. Furthermore, we show that such rules always violate no wastage,
which prove the incompatibility between eﬃciency and strategy-proofness along with individual rationality and no subsidy for losers.
Our second results are about fairness. We show that the truncated Vickrey ruleswith non-negligible endogenous reserve prices and with a prioritized tie-breaking rule are
the only rules satisfying weak envy-freeness for equals, individual rationality, no subsidy
for losers, and strategy-proofness. We also show that the same result holds even whenreplacing weak envy-freeness for equals with equal treatment of equals or envy-freeness.
Furthermore, if endogenous reserve prices are upper anonymous, then the same result
holds for anonymity in welfare.

1.2

Related literature

Our contributions include (i) allowing agents to have hard budget constraints and (ii)considering fair and strategy-proof auctions. Previous studies often focus on one factor
while neglecting the other, resulting in limited research that considers both. Furthermore,4

our study stands out due to its consideration of non-quasi-linear utility functions, which
has been often overlooked in existing research. In the following, we explain the existing
literature about each factor, respectively.
Budget-constrained auctions: On the no income eﬀect domain with homogenous
objects, Dobzinski et al. (2012) show that when utility functions exhibit constant marginalvaluation and budgets are private information, then there is no rule satisfying eﬃciency,
individual rationality, no subsidy, and strategy-proofness. However, they also establishthat when budgets are public information, the modified version of Ausubel’s (2004) clinching auction satisfies these conditions, and moreover it is unique if there are two agents.
However, on the domain violating constant marginal valuation, the impossibility result
returns even if budgets are public information (Lavi and May 2012; Ting and Xing 2012;
Yi 2023).
There are some extensions of the result of Dobziski et al. (2012). Fiat et al. (2011)
consider single-valued preferences, which include preferences exhibiting constant marginalvaluation as a special case. In this situation, they show that when budgets are public
information, single-valued combinatorial auctions satisfy eﬃciency, individual rationality,
no subsidy, and strategy-proofness. Hirai and Sato (2023) study about polymatroidal environments, where the feasible allocations of objects are restricted by some monotone andsubmodular function. In this situation, they show that if budgets are public information,then polyhedral clinching auctions satisfy eﬃciency, individual rationality, no subsidy,
and strategy-proofness.
Mackenzie and Zhou (2022) investigate the situation where budgets are private information but each agent demands at most one object (unit-demand). On the no income
eﬀect domain with homogenous objects, they show that if payments are discrete, then eﬃcient pendulum auctions satisfy eﬃciency, individual rationality, no subsidy, and obvious
strategy-proofness.
On the no income eﬀect domain with heterogenous objects, Dütting, Henzinger, andStarnberger (2015) establish the negative result. They show that even when budgets are
public information, there is no rule satisfying eﬃciency, individual rationality, no subsidy,
and strategy-proofness. In contrast with their result, Aggarwal et al. (2009) establish thepositive result by limiting preferences to those with unit-demand. On the no income
eﬀect and unit demand domain with heterogenous objects, they show that when budgets
are private information and utility profiles are in general position,1 the stable matchingrule satisfies these four conditions. Dütting, Henzinger, and Weber (2015) also show thepositive result by extending the result of Aggarwal et al. (2009).
Some studies give up eﬃciency or strategy-proofness, while keeping private budgets.
On the greedy domain with heterogenous objects, Le (2017) shows that the iterative second price auctions are the only rules satisfying non-wastefulness, symmetry, non-bossiness,
individual rationality, no subsidy, and strategy-proofness. He also shows that no rule1

This condition excludes the situation where two agents have the same budget simultaneously.

5satisfies these conditions on the general domain. On the single-minded domain withheterogenous objects, Le (2018) shows that truncated VCG rules satisfy eﬃciency andstrategy-proofness for almost all preferences in addition to individual rationality and no
subsidy. Moreover, he shows that a rule satisfying these conditions is a truncated VCG
rule almost everywhere. When objects are heterogenous and agents’ preferences exhibit
income eﬀects, Shinozaki (2023) shows that modified pay as bid rules satisfy eﬃciency,
individual rationality, no subsidy, and non-obvious manipulability.
Fair and strategy-proof auctions: When agents have quasi-linear preferences andthere is a single object, Sakai (2013b) shows that the second price auction with a reserve
price is the only rule satisfying weak eﬃciency, non-imposition and strategy-proofness. For
the case of homogenous objects, Basu and Mukherjee (2022) characterize the same ruleby anonymity in welfare, non-imposition, strategy-proofness, and some mild conditions.
On the general domain including the quasi-linear domain, Sakai (2013a) shows thatwhen there is a single object, the Vickrey rule is characterized by no wastage, weak envyfreeness for equals, non-imposition, and strategy-proofness. Adachi (2014) shows the same
result adding to welfare continuity for the case of homogenous objects.
On the general domain with a single object, Kazumura et al. (2017) shows that
Vickrey rules with reserve prices are the only rule satisfying anonymity in welfare, loser
payment independence, and strategy-proofness.
On the quasi-linear domain with heterogenous objects, Ashlagi and Serizawa (2012)
show that the Vickrey rule is the only rule satisfying no wastage, anonymity in welfare,individual rationality, no subsidy for losers and strategy-proofness. On the same domain,
Ohseto (2006) characterizes the rules that satisfy no wastage, envy-freeness and strategyproofness.
Note that all of the studies mentioned here do not consider hard budget constraints.

1.3

Organization

The structure of this paper is as follows: Section 2 presents the fundamental componentsof the model. Following this, in Section 3, we introduce truncated Vickrey rules with endogenous reserve prices. Section 4 explains the results, comprising three parts concerning
strategy-proofness, weak eﬃciency, and fairness. Lastly, Section 5 provides a conclusion.
All proofs are relegated to Appendix.

2

The model

There are n agents and a single object. Let N = {1, 2, · · · , n} be the set of agents. We
denote consuming the object and not consuming the object by 1 and 0, respectively. A
typical (consumption) bundle for agent i is a pair zi = (xi , ti ) ∈ {0, 1} × R, where xi isthe consumption of the object and ti is the payment for agent i.
6Each agent has a utility function ui : {0, 1} × R → R ∪ {−∞} such that (i) ui (0, 0) = 0
and (ii) there is a budget bi ∈ R+ ∪ {∞} such that for each xi ∈ {0, 1} and each ti ∈ R, if
ti ≤ bi , then ui (xi , ti ) ̸= −∞, and otherwise, ui (xi , ti ) = −∞. For the sake of convenience,
if ti = ∞, then we let ui (xi , ti ) = −∞. We denote by U a typical class of utility functions,and call it a domain. We make the following assumptions.
1. Finiteness: If ui (1, bi ) ≤ 0, then there is vi ∈ R+ such that ui (1, vi ) = 0.
2. Money monotonicity: For each xi ∈ {0, 1} and each ti , t′i ∈ R, if ti < t′i ≤ bi , thenui (xi , ti ) > ui (xi , t′i ).
3. Object desirability: For each ti ∈ R with ti ≤ bi , ui (1, ti ) > ui (0, ti ).
Let U C be the set of all utility functions satisfying the above three properties, and call it
the classical domain. Given ui ∈ U C , we call vi defined by finiteness a valuation for ui .
Moreover, for the sake of notational convenience, if ui (1, bi ) > 0, then let vi = ∞. Notethat by money monotonicity, the valuation vi is uniquely determined. We call min{vi , bi }a truncated valuation for ui . If vi = ∞, we say that agent i’s budget constraint isbinding. Given ui ∈ U C and ti ∈ R, we define the compensation for ui from ti byci (ti ) > 0 such that ci (ti ) = ti − bi if ti > bi , and ui (0, ti − ci (ti )) = ui (1, ti ) otherwise.
Throughout the paper, we consider a domain included by the classical domain, that is,
U ⊆ UC.
A utility profile is an n-tuple of agents’ utility functions u = (u1 , . . . , un ) ∈ U n .
Given i ∈ N and N ′ ⊆ N , let u−i = (uj )j̸=i and u−N ′ = (uj )j∈N \N ′ . Given a utility profileu ∈ U n , let!
"
N (u) =i ∈ N : min{vi , bi } ≥ max min{vj , bj }j̸=ibe the set of the agents who have the highest truncated valuation, and let!
"∞
N (u) = i ∈ N : min{vi , bi } ≥ max min{vj , bj } and vi = ∞ .
j̸=ibe the set of the agents in N (u) whose budget constraint is binding.
#A feasible object assignment is an n-tuple x = (x1 , . . . , xn ) such that i∈N xi ≤ 1.
n
Let
# X be the set of all feasible object assignments, that is, X = {(x1 , . . . , xn ) ∈ {0, 1} :i∈N xi ≤ 1}. An allocation is a pair of a feasible object assignment and a vectorof payments, z = ((x1 , x2 , . . . , xn ), (t1 , t2 , . . . , tn )) ∈ X × Rn . We denote the set of all
allocations by Z = X × Rn . Given z ∈ Z and i ∈ N , zi = (xi , ti ) denotes the bundle ofagent i.
A rule is a mapping f = (x, t) : U n → Z. Given a rule f and a utility profile u ∈ U n ,agent i’s bundle under f at u is denoted by fi (u) = (xi (u), ti (u)). Given i ∈ N andu−i ∈ U n−1 , let U W (u−i ) = {ui ∈ U : xi (ui , u−i ) = 1} be the set of i’s utility functions forwhich he/she wins the object, and let U L (u−i ) = U \ U W (u−i ).
7′Given u ∈ U n , an allocation z ∈ Z#is eﬃcient# for u if there is no z ∈ Z such that′′(i) for each i ∈ N , ui (zi ) ≥ ui (zi ), (ii) i∈N ti ≥ i∈N ti , and (iii) at least one inequalityin (i) and (ii) holds strictly. We say that z ′ dominates z for u if z ′ satisfies (i), (ii), and(iii) above. We similarly define eﬃciency as a condition imposed on a rule.

• Eﬃciency: For each u ∈ U n , f (u) is eﬃcient for u.
Next we define a weak fairness condition introduced by Sakai (2013a). It says that
if two agents with identical utility functions diﬀer in outcome (one being a winner, theother a loser), then the loser does not prefer the winner’s outcome.
• Weak envy-freeness for equals: For each u ∈ U n and each i, j ∈ N , if ui = uj ,xi (u) = 0 and xj (u) = 1, then ui (fi (u)) ≥ ui (fj (u)).
Weak envy-freeness for equals is so weak that it is implied by many fairness conditions.
All of the conditions below are stronger than weak envy-freeness for equals.
• Equal treatment of equals: For each u ∈ U n and each i, j ∈ N , if ui = uj , thenui (fi (u)) = ui (fj (R)).
• Envy-freeness: For each u ∈ U n and each i, j ∈ N , ui (fi (u)) ≥ ui (fj (u)).
• Anonymity in welfare: For each u, u′ ∈ U n and each i, j ∈ N , if ui = u′j , uj = u′i ,and u−{i,j} = u′−{i,j} , then ui (fi (u)) = ui (fj (u′ )).
Finally, we introduce basic properties.
• Individual rationality: For each u ∈ U n and each i ∈ N , ui (fi (u)) ≥ 0.
• No subsidy for losers: For each u ∈ U n and each i ∈ N , if xi (u) = 0, thenti (u) ≥ 0.
• Strategy-proofness: For each u ∈ U n , each i ∈ N and each u′i ∈ U , ui (fi (u)) ≥ui (fi (u′i , u−i )).

3

Truncated Vickrey rules with endogenous reserve
pricesIn this section, we introduce truncated Vickrey rules with endogenous reserve prices. First
we define a Vickrey rule (Vickrey 1961; Saitoh and Serizawa 2008; Sakai 2008).2
2

In their definitions, the object is always assigned to some agent with the maximum valuation. However, in our definition, if ties exist, the object could not be assigned to any agent. In this sense, ourdefinition does not precisely correspond to theirs.

8Definition 1. A rule f on U n is a Vickrey rule if for each u ∈ U n and each i ∈ N ,$0 if vi < maxj̸=i vj
xi (u) =,1 if vi > maxj̸=i vj
andti (u) =$0
maxj̸=i vj

if xi (u) = 0.
if xi (u) = 1

A Vickrey rule may violate individual rationality. To see this, let f be a Vickrey rule,and let u ∈ U n and i ∈ N be such that vi > maxj̸=i vj > bi . Then, by definition, fi (u) =(1, maxj̸=i vj ). However, since ti (u) exceeds his/her budget bi , ui (fi (u)) = −∞, which isa violation of individual rationality. To overcome this problem, Le (2018) introduces atruncated Vickrey rule.
Definition 2. A rule f on U n is a truncated Vickrey rule if for each u ∈ U n and eachi ∈ N,$
0 if min{vi , bi } < maxj̸=i min{vj , bj }xi (u) =,1 if min{vi , bi } > maxj̸=i min{vj , bj }andti (u) =$0
if xi (u) = 0.
maxj̸=i min{vj , bj } if xi (u) = 1

Any truncated Vickrey rule f satisfies individual rationality because for each u ∈ U n
and each i ∈ N with xi (u) = 1, ti (u) ≤ min{vi , bi }. Note that if there is no budget
constraint for each agent, that is, bi = ∞ for each i ∈ N , then a truncated Vickrey rulecoincides with a Vickrey rule.
Finally we introduce a truncated Vickrey rule with endogenous reserve prices, which
is a generalization of a truncated Vickrey rule.
Given i ∈ N , i’s (reserve) price function is ri : U n−1 → R∪{∞}, whose outputs are
independent of i’s utility functions. A (reserve) price function profile r = (r1 , . . . , rn )is an n-tuple of price functions for each agent. Let R be a set of price function profiles.
Definition 3. Given a price function profile r ∈ R, a rule f on U n is a truncatedVickrey rule with endogenous reserve prices r if for each u ∈ U n and each i ∈ N ,$0 if min{vi , bi } < max{maxj̸=i min{vj , bj }, ri (u−i )}xi (u) =,(V-i)
1 if min{vi , bi } > max{maxj̸=i min{vj , bj }, ri (u−i )}andti (u) =$0
if xi (u) = 0.
max{maxj̸=i min{vj , bj }, ri (u−i )} if xi (u) = 1
9(V-ii)

4

Results

This section consists of four subsections. In the first subsection, we investigate strategyproof rules. In contrast to the case without budget constraints, some truncated Vickrey
rules with endogenous reserve prices may violate strategy-proofness. Consequently, weestablish a necessary and suﬃcient condition for these rules to satisfy strategy-proofness.
Subsequently, we characterize the rules that satisfy individual rationality, no subsidy for
losers, and strategy-proofness.
In the second subsection, we investigate weak eﬃcient rules. We first show that efficiency is decomposed by three conditions: within budget, no wastage, and constrained
eﬃciency. Next we show a necessary and suﬃcient condition for truncated Vickrey ruleswith endogenous reserve prices to satisfy constrained eﬃciency, and characterize theserules by constrained eﬃciency, individual rationality, no subsidy, and strategy-proofness.
Finally we show that these rules always violate no wastage, which shows the incompatibility between eﬃciency and strategy-proofness.
In the third subsection, we investigate fair rules. We characterize the rules satisfying
weak envy-freeness for equals, individual rationality, no subsidy for losers, and strategyproofness. We also show that the same characterization result holds even if we replace
weak envy-freeness for equals with the other fairness conditions; equal treatment of equals,
envy-freeness, and anonymity in welfare.
In the last subsection, we investigate the independence of the properties.
Before going to these subsections, we provide some conditions on a domain. We first
introduce a unbounded truncated valuations condition. It says that the set of truncatedvaluations of a domain has no upper bound. The class of these domains includes many
economically meaningful domains; the no income eﬀect domain, the positive income eﬀect
domain, and so on. They also include the cases where agents face no budget constraints(namely, bi = ∞ for each ui ∈ U ), but not include the cases with public budget constraints.
Definition 4. A domain U satisfies unbounded truncated valutions if for eacha ∈ R+ , there is ui ∈ U such that a < min{vi , bi }.
Next we introduce a small compensation condition. It says that for any two distinct
payments, there exists a utility function such that the change of the compensation does
not exceed the change of the payment.
Definition 5. A domain U satisfies small compensation if for each ti > 0 and eacht′i < ti , there is ui ∈ U such that 0 < ci (t′i ) − t′i < ti − t′i .
Thirdly we introduce a density condition. It says that for each non-negative two
numbers, there exists a utility function whose truncated valuation is between the two
numbers. Moreover, if the budget constraint is binding, we say that the strong density
condition is satisfied.
10

Definition 6. A domain U satisfies density if for each a, b ∈ R+ with a < b, there
is ui ∈ U such that a < min{vi , bi } < b. Furthermore, if there is ui ∈ U such thata < min{vi , bi } < b and vi = ∞, we say that U satisfies strong density.
Note that the above two conditions are stronger than the unbounded truncated valuations condition.3 Also note that the strong density condition excludes the quasi-linear
domain and the no hard budget domain.
Finally we introduce a positive budget condition. The domain includes only utility
functions whose budgets are positive.
Definition 7. A domain U satisfies positive budget if for each ui ∈ U , bi > 0.
Note that this conditions is about the restriction of a domain, while the first three
conditions are about richness of a domain.

4.1

Strategy-proofness

In Definition 3, we specify no tie-breaking rule, that is, for each u ∈ U n and each i ∈ N ,when min{vi , bi } = max{maxj̸=i min{vj , bj }, ri (u−i )}, it is possible that either xi (u) = 0
or xi (u) = 1. For some tie-breaking rule, a truncated Vickrey rule with endogenous reserve
prices does not satisfy strategy-proofness.
To see this, let f be a truncated Vickrey rule with endogenous reserve prices r. Leti ∈ N , u−i ∈ U n−1 and ri∗ (u−i ) = max{maxj̸=i min{vj , bj }, ri (u−i )}. Let ui , u′i ∈ U besuch that ui (1, bi ) > 0, min{vi , bi } = ri∗ (u−i ), and min{vi′ , b′i } > ri∗ (u−i ). By ui (1, bi ) >0, vi = ∞. By min{vi′ , b′i } > r∗ (u−i ), fi (u′i , u−i ) = (1, r∗ (u−i )). By vi = ∞, bi =min{vi , bi } = ri∗ (u−i ), and so fi (u′i , u−i ) = (1, bi ). By ui (1, bi ) > 0, ui (fi (u′i , u−i )) > 0.
Thus, if xi (u) = 0, then by fi (u) = (0, 0), ui (fi (u′i , u−i )) > 0 = ui (fi (u)). Hence, fviolates strategy-proofness.
In the above case, if we set xi (u) = 1, then we can avoid the strategical action of agent
i to report u′i . Thus, strategy-proofness requires that the agent with vi = ∞ has a higher
priority when ties exist. We formally define this tie-braking rule. We say that a truncatedVickrey rule f with endogenous reserve prices r has a prioritized tie-breaking rule
if for each u ∈ U and each i ∈ N , if min{vi , bi } = max{maxj̸=i min{vj , bj }, ri (u−i )} andvi = ∞, then xi (u) = 1. The prioritized tie-breaking rule is shown to be a necessary andsuﬃcient conditions to satisfy strategy-proofness.
Proposition 1. Let U ⊆ U C satisfy unbounded truncated valuations. Let f on U n bea truncated Vickrey rule with endogenous reserve prices r. Then, f satisfies strategyproofness if and only if f has a prioritized tie-breaking rule.
To see this, let a ∈ R+ . If U satisfies density, it is obviously rich. If U satisfies small compensation, letui ∈ U be such that 0 < ci (a+1)−(a+1) < (a+2)−(a+1). Then, by ui (0, (a+1)−ci (a+1)) = ui (1, a+1)and (a + 1) − ci (a + 1) < 0, ui (1, a + 1) > 0, and so min{vi , bi } ≥ a + 1 > a. Thus, U is rich.
311

Our second result is a characterization of the rules satisfying individual rationality, no
subsidy for losers, and strategy-proofness.4
Proposition 2. Let U ⊆ U C satisfy unbounded truncated valuations. Then, a rule fon U n satisfies individual rationality, no subsidy for losers, and strategy-proofness if andonly for each i ∈ N , there is a price function ri : U n−1 → R ∪ {∞} such that for eachu−i ∈ U n−1 ,(i-a) for each ui ∈ U ,xi (u) =$0
1

if min{vi , bi } < ri (u−i ),if min{vi , bi } > ri (u−i )(i-b) for each ui ∈ U , if min{vi , bi } = ri (u−i ) and vi = ∞, then xi (u) = 1,(ii) for each ui ∈ U ,ti (u) =4.2$

0ri (u−i )if xi (u) = 0.
if xi (u) = 1

Weak eﬃciency

First, we show that eﬃciency can be decomposed by three conditions.
Proposition 3. Let u ∈ U n and z ∈ Z. Then, z is eﬃcient for u if and only if(i) for each i ∈ N , ti ≤ bi ,#(ii)
i∈N xi = 1, and(iii) there is no z ′ ∈ Z such that#′i∈N xi =#i∈N xi and it dominates z for u.

For the conditions in Proposition 3, we call (i) within budget, (ii) no wastage, and(iii) constrained eﬃciency. We similarly define these conditions as those imposed ona rule.
• Within budget: For each u ∈ U n and i ∈ N , ti (u) ≤ bi .
#• No wastage: For each u ∈ U n , i∈N xi (u) = 1.

• Constrained eﬃciency: For each u ∈ U n , f (u) is constrained eﬃcient for u.
Corollary 1. Let U ⊆ U C . Then, a rule f on U n satisfies eﬃciency if and only if itsatisfies within budget, no wastage, and constrained eﬃciency.
4

Mukherjee (2014), Nisan (2007), and Sprumont (2013) show the similar results when the domain isquasi-linear and there is no budget constraint.

12

Similarly to strategy-proofness, for some tie-breaking rule, a truncated Vickrey rulewith endogenous reserve prices may violate constrained eﬃciency.
To see this, let f be a truncated Vickrey rule with endogenous reserve prices r,
and let u ∈ U n and i ∈ N be such that vi ̸= ∞ and N ∞ (u) ̸= ∅. Let ri∗ (u−i ) =max{maxj̸=i min{vj , bj }, ri (u−i )}. Assume xi (u) = 1. By xi (u) = 1, i’s truncated valuations is the highest, that is, i ∈ N (u). Let j ∈ N ∞ (u) be another agent whose truncatedvaluation is the highest. Then, min{vi , bi } = ri∗ (u−i ) ≥ min{vj , bj } = min{vi , bi }, and somin{vi , bi } = min{vj , bj } = ri∗ (u−i ). By vi ̸= ∞, ui (1, ri∗ (u−i )) = ui (0, 0), and by vj = ∞,uj (1, ri∗ (u−i )) > uj (0, 0). By fi (u) = (1, ri∗ (u−i )) and fj (u) = (0, 0), reallocation between
i and j dominates the original allocation f (u). Thus, f violates constrained eﬃciency.
In the above illustration, if we exclude the agent i from the candidates who win theobjects, then we can avoid the reallocation which undermines constrained eﬃciency. We
formally define this tie-breaking rule. A truncated Vickrey rule with endogenous reserve
prices r has an exclusive tie-breaking rule if for each u ∈ U n and each i ∈ N , ifmin{vi , bi } = max{maxj̸=i min{vj , bj }, ri (u−i )}, vi ̸= ∞, and N ∞ (u) ̸= ∅, then xi (u) = 0.
Proposition 4. Let U ⊆ U C . Let f on U n be a truncated Vickrey rule with endogenous
reserve prices r. Then, f satisfies constrained eﬃciency if and only if f has an exclusive
tie-breaking rule.
Next we characterize truncated Vickrey rule with endogenous reserve prices by constrained eﬃciency, individual rationality, no subsidy for losers, and strategy-proofness.
Theorem 1. Let U ⊆ U C satisfy small compensation and positive budget. Then, a rule
f on U n satisfies constrained eﬃciency, individual rationality, no subsidy for losers, andstrategy-proofness if and only if it is a truncated Vickrey rule with endogenous reserve
prices and with an exclusive and prioritized tie-breaking rule.
If the positive budget condition is violated, then there exists a rule that satisfies thefour properties but not a truncated Vickrey rule.
Example 1. Let U ⊆ U n satisfy small compensation but violate positive budget. Let
f on U n be such that for each i ∈ N , there is ri : U n−1 → R ∪ {∞} such that it
satisfies the conditions in Proposition 2, and for each u ∈ U n , (i) if min{vi , bi } = ri (u−i ),vi ̸= ∞, and N ∞ (u) ̸= ∅, then xi (u) = 0 and (ii) if maxj̸=i min{vj , bj } = 0, then ri (u−i ) <maxj̸=i min{vj , bj } = 0. Then, f satisfies constrained eﬃciency, individual rationality, no
subsidy for losers, and strategy-proofness. However, by (ii), f is not a truncated Vickrey
rule with endogenous reserve prices.
The final result shows that no wastage is incompatible with the four properties.
Proposition 5. Let U ⊆ U C satisfy small compensation, strong density, and positive
budget. Let f on U n be a truncated Vickrey rule with endogenous reserve prices r andwith an exclusive and prioritized tie-breaking rule. Then, f violates no wastage.
13

Since eﬃciency implies both no wastage and constrained eﬃciency, it is incompatible
with individual rationality, no subsidy for losers, and strategy-proofness.
Corollary 2. Let U ⊆ U n satisfy small compensation, strong density, and positive budget.
There is no rule on U n that satisfies eﬃciency, individual rationality, no subsidy for losers,
and strategy-proofness.

4.3

Fairness

In general, a truncated Vickrey rule with endogenous reserve prices may not satisfy weak
envy-freeness for equals. To see this, consider a simple case with n = 2. Let f be atruncated Vickrey rule with endogenous reserve prices r, and let u ∈ U 2 be such thatu1 = u2 and u1 (1, b1 ) = u2 (1, b2 ) > 0. By definition, v1 = v2 = ∞. Assume x1 (u) = 0 andx2 (u) = 1. Then, by definition f1 (u) = (0, 0) and f2 (u) = (1, max{min{v1 , b1 }, r2 (u1 )}).
By v1 = ∞, t2 (u) = max{b1 , r2 (u1 )}. If b1 ≥ r2 (u1 ), then by u1 (1, b1 ) > 0 and f1 (u) =(0, 0), u1 (f2 (u)) = u1 (1, b1 ) > 0 = u1 (f1 (u)). Thus, f violates weak envy-freeness forequals.
This simple example gives us an intuitive reason why the truncated Vickrey rule does
not work for weak envy-freeness for equals. In the above situation, since agent 2’s reserve
price is no more than his/her payment, that is, r2 (u1 ) ≤ b1 = t2 (u), the truncatedVickrey rule realizes so low payment for agent 2 that agent 1 envies agent 2. To handle
this problem, it seems to be a good way to increase the agent 2’s reserve price, that is,
to set r2 (u1 ) > b1 . Then, since agent 2’s payment increases, agent 1 will no longer envy
agent 2.
Formally, we define this condition. We say that a price function profile r is nonnegligible if for each i ∈ N and each u−i ∈ U n−1 , if there is j ∈ N \ {i} such thatmin{vj , bj } = maxk̸=i min{vk , bk } and vj = ∞, then ri (u−i ) > maxk̸=i min{vk , bk }.
We show that the non-negligibility condition is a necessary and suﬃcient condition fortruncated Vickrey rule with endogenous reserve prices and with a prioritized tie-breaking
rule to satisfy weak envy-freeness for equals.
Theorem 2. Let U ⊆ U C satisfy unbounded truncated valuations. Then, a rule f on
U n satisfies weak envy-freeness for equals, individual rationality, no subsidy for losers,
and strategy-proofness if and only if it is a truncated Vickrey rule with non-negligible
endogenous reserve prices r and with a prioritized tie-breaking rule.
We show that the same characterization result holds even if we replace weak envyfreeness for equals with equal treatment of equals or envy-freeness.
Proposition 6. Let U ⊆ U C satisfy unbounded truncated valuations. Let f on U n be atruncated Vickrey rule with non-negligible endogenous reserve prices r. Then, f satisfies
equal treatment of equals and envy-freeness.
14

Since equal treatment of equals and envy-freeness imply weak envy-freeness for equals,
by Theorem 2 and Proposition 6, we can get the following result.
Corollary 3. Let U ⊆ U C satisfy unbounded truncated valuations. Then, the following
three statements are equivalent.
(i) A rule f on U n is a truncated Vickrey rule with non-negligible endogenous reserve
prices r and with a prioritized tie-breaking rule.
(ii) A rule f on U n satisfies equal treatment of equals, individual rationality, no subsidy
for losers, and strategy-proofness.
(iii) A rule f on U n satisfies envy-freeness, individual rationality, no subsidy for losers,
and strategy-proofness.
As for anonymity in welfare, we need an additional condition on reserve prices. A
price function profile r ∈ R is upper anonymous if for each u, u′ ∈ U n and i, j ∈ Nsuch that ui = u′j , uj = u′i , and u−{i,j} = u′−{i,j} , when ri (u−i ) > maxk̸=i min{vk , bk },ri (u−i ) = rj (u′−j ).
Theorem 3. Let U ⊆ U C satisfy density. Then, a rule f on U n satisfies anonymity inwelfare, individual rationality, no subsidy for losers, and strategy-proofness if and only if it
is a truncated Vickrey rule with upper anonymous and non-negligible endogenous reserve
prices r and with a prioritized tie-breaking rule.

4.4

Independence

Given ui ∈ U and δ, let viδ be such that (i) if ui (1, bi ) ≤ ui (0, δ), then ui (1, viδ ) = ui (0, δ),and (ii) if ui (1, bi ) > ui (0, δ), then viδ = ∞. This is a valuation for ui evaluated at (0, δ).
Definition 8. Given a price function profile r, a rule f on Rn is a truncated Vickrey
rule with endogenous reserve prices r and an entry fee δ if for each u ∈ U n andeach i ∈ N ,$0 if min{viδ , bi } < max{maxj̸=i min{vjδ , bj }, ri (u−i )}xi (u) =,1 if min{viδ , bi } > max{maxj̸=i min{vjδ , bj }, ri (u−i )}andti (u) =$δ
if xi (u) = 0.
δ
max{maxj̸=i min{vj , bj }, ri (u−i )} if xi (u) = 1

We consider the independence of the properties. Let U satisfy small compensationand positive budget, and let f on U n be a truncated Vickrey rule with endogenous reserve
prices r and an entry fee δ.
15• Dropping constrained eﬃciency: Assume f has a prioritized tie-breaking rule andδ = 0, but the tie-breaking rule is not exclusive. Then, by Proposition 2 andTheorem 1, f satisfies individual rationality, no subsidy for losers and strategyproofness, but not constrained eﬃciency.
• Dropping weak envy-freeness for equals: Assume f has a prioritized tie-breaking ruleand δ = 0, but r violates non-negligibility. Then, by Proposition 2 and Theorem
2, f satisfies individual rationality, no subsidy for losers and strategy-proofness, but
not weak envy-freeness for equals.
The above rule f also violates other fairness conditions: equal treatment of equals, envy
freeness, and anonymity in welfare.
• Dropping individual rationality: Assume f has an exclusive and prioritized tie-breaking
rule, r satisfies non-negligibility, and δ > 0. Then, f satisfies constrained eﬃciency,
weak envy-freeness for equals, no subsidy for losers and strategy-proofness, but not
individual rationality.
• Dropping no subsidy for losers: Assume f has an exclusive and prioritized tie-breaking
rule, r satisfies non-negligibility, and δ < 0. Then, f satisfies constrained eﬃciency,
weak envy-freeness for equals, individual rationality and strategy-proofness, but not
no subsidy for losers.
• Dropping strategy-proofness: Assume for some ui ∈ U , vi = ∞.5 Assume f has an
exclusive tie-breaking rule, r satisfies non-negligibility and δ = 0, but f has a nonprioritized tie-breaking rule. Then, by Propositions 1, 4, 6, f satisfies constrained
eﬃciency, weak envy-freeness for equals, individual rationality and no subsidy for
losers, but not strategy-proofness. When for each ui ∈ U , vi ̸= ∞, pay as bid rules
satisfy all the properties except for strategy-proofness.
The above three results also holds for equal treatment of equals and envy-freeness,
instead of weak envy-freeness for equals. Moreover, if r is upper anonymous, the same
results holds for anonymity in welfare.

5

Conclusion

We consider the single-object allocation problem with hard budget constraints and income eﬀects, and show that truncated Vickrey rules with endogenous reserve prices canbe characterized by constrained eﬃciency or weak envy-freeness for equals, along withindividual rationality, no subsidy for losers, and strategy-proofness. We leave the problem
for the case of homogenous or heterogenous objects as an open question.
5

If for each ui ∈ U , vi ̸= ∞, f always has a prioritized tie-breaking rule.

16

Appendix: proofs
Proposition 1. Let U ⊆ U C satisfy unbounded truncated valuations. Let f on U n bea truncated Vickrey rule with endogenous reserve prices r. Then, f satisfies strategyproofness if and only if f has a prioritized tie-breaking rule.
Proof. Only if: Assume f satisfies strategy-proofness. Let u ∈ U n and i ∈ N be suchthat min{vi , bi } = max{maxj̸=i min{vj , bj }, ri (u−i )} and vi = ∞. Suppose xi (u) = 0. By(V-ii), fi (u) = (0, 0). Let ri∗ (u−i ) = max{maxj̸=i min{vj , bj }, ri (u−i )}. By min{vi , bi } =ri∗ (u−i ) and vi = ∞, ui (1, ri∗ (u−i )) > ui (0, 0). Let u′i ∈ U be such that min{vi′ , b′i } >ri∗ (u−i ). By (V-i) and (V-ii), fi (u′i , u−i ) = (1, ri∗ (u−i )). Thus, by fi (u) = (0, 0) andui (1, ri∗ (u−i )) > ui (0, 0), ui (fi (u′i , u−i )) > ui (fi (u)). However, this contradicts strategyproofness.
If: Assume f has a prioritized tie-breaking rule. Suppose f violates strategy-proofness.
Then, there are u ∈ U n , i ∈ N , and u′i ∈ U such that ui (fi (u′i , u−i )) > ui (fi (u)). Letri∗ (u−i ) = max{maxj̸=i min{vj , bj }, ri (u−i )}. By ui (fi (u′i , u−i )) > ui (fi (u)) and (V-ii),
xi (u) ̸= xi (u′i , u−i ). If xi (u′i , u−i ) = 0, then ui (0, 0) > ui (fi (u)), and so by xi (u) = 1,ri∗ (u−i ) = ti (u) > min{vi , bi }. However, this contradicts (V-i). Hence, xi (u′i , u−i ) =1, and so xi (u) = 0. By ui (fi (u′i , u−i )) > ui (fi (u)), ui (1, ri∗ (u−i )) > ui (0, 0). Byxi (u) = 0 and (V-i), min{vi , bi } ≤ ri∗ (u−i ). By ui (1, ri∗ (u−i )) > ui (0, 0), ri∗ (u−i ) ≤min{vi , bi }, and so min{vi , bi } = ri∗ (u−i ). By ui (1, ri∗ (u−i )) > ui (0, 0) and ri∗ (u−i ) =min{vi , bi }, ui (1, min{vi , bi }) > ui (0, 0), which implies vi = ∞. However, by xi (u) = 0
and min{vi , bi } = ri∗ (u−i ), this contradicts that f has a prioritized tie-breaking rule.
Lemma 1. Let U ⊆ U C satisfy unbounded truncated valuations. A rule f on U n satisfies
individual rationality and strategy-proofness if and only if for each i ∈ N , there is a pairof price functions ri : U n−1 → R ∪ {∞} and ri : U n−1 → R ∪ {∞} such that for eachu−i ∈ U n−1 ,(i-L) ri (u−i ) = ∞ if U L (u−i ) = ∅, and ri (u−i ) ≤ 0 if U L (u−i ) ̸= ∅,(i-W) ri (u−i ) = ∞ if U W (u−i ) = ∅, and ri (u−i ) ≤ inf ui ∈U W (u−i ) min{vi , bi } if U W (u−i ) ̸= ∅,(ii) for each ui ∈ U ,xi (u) =$01

if ui (0, ri (u−i )) > ui (1, ri (u−i )),if ui (0, ri (u−i )) < ui (1, ri (u−i ))(iii) for each ui ∈ U ,ti (u) =$ri (u−i )ri (u−i )17

if xi (u) = 0.
if xi (u) = 1

Proof. Only If: Assume f satisfies individual rationality and strategy-proofness. Leti ∈ N and u−i ∈ U n−1 .
First, we show that for each ui , u′i ∈ U , if xi (ui , u−i ) = xi (u′i , u−i ), then ti (ui , u−i ) =ti (u′i , u−i ). Let ui , u′i ∈ U be such that xi (ui , u−i ) = xi (u′i , u−i ). Suppose, without lossof generality, that ti (ui , u−i ) < ti (u′i , u−i ). By individual rationality, ti (u′i , u−i ) ≤ b′i .
Hence, by xi (ui , u−i ) = xi (u′i , u−i ) and ti (ui , u−i ) < ti (u′i , u−i ) ≤ b′i , u′i (fi (ui , u−i )) >u′i (fi (u′i , u−i )). However, this contradicts strategy-proofness. Thus, ti (ui , u−i ) = ti (u′i , u−i ).
Let ri : U n−1 → R ∪ {∞} and ri : U n−1 → R ∪ {∞} be such that for each u−i ∈ U n−1 ,$ti (ui , u−i ) if there exists ui ∈ U L (u−i )ri (u−i ) =,∞if U L (u−i ) = ∅$ti (ui , u−i ) if there exists ui ∈ U W (u−i )ri (u−i ) =.
∞if U W (u−i ) = ∅Note that, by the statement shown in the previous paragraph, these functions are uniquely
defined and satisfy (iii).
Next, we show (i). If U L (u−i ) = ∅ and U W (u−i ) = ∅, then by definition, ri (u−i ) =ri (u−i ) = ∞. Assume U L (u−i ) ̸= ∅ and U W (u−i ) ̸= ∅. For each ui ∈ U L (u−i ), by fi (u) =(0, ri (u−i )) and ui (fi (u)) ≥ 0 (individual rationality), ri (u−i ) ≤ 0. For each ui ∈ U W (u−i ),by fi (u) = (1, ri (u−i )) and ui (fi (u)) ≥ 0 (individual rationality), ri (u−i ) ≤ min{vi , bi },and so ri (u−i ) ≤ inf ui ∈U W (u−i ) min{vi , bi }.
Finally, we show (ii). Let ui ∈ U . First assume ui (0, ri (u−i )) > ui (1, ri (u−i )). Suppose xi (u) = 1. By (iii), fi (u) = (1, ri (u−i )). If U L (u−i ) = ∅, then by definition,ri (u−i ) = ∞, and so ui (0, ri (u−i )) = −∞. However, this contradicts ui (0, ri (u−i )) >ui (1, ri (u−i )). Hence, U L (u−i ) ̸= ∅. Let u′i ∈ U L (u−i ). By (iii), fi (u′i , u−i ) = (0, ri (u−i )).
By ui (0, ri (u−i )) > ui (1, ri (u−i )), fi (u) = (1, ri (u−i )), and fi (u′i , u−i ) = (0, ri (u−i )),ui (fi (u′i , u−i )) > ui (fi (u)). However, this contradicts strategy-proofness. Hence, xi (u) = 0.
Next assume ui (1, ri (u−i )) > ui (0, ri (u−i )). Suppose xi (u) = 0. By (iii), fi (u) =(0, ri (u−i )). If U W (u−i ) = ∅, then by definition, ri (u−i ) = ∞, and so ui (1, ri (u−i )) =−∞. However, this contradicts ui (1, ri (u−i )) > ui (0, ri (u−i )). Hence, U W (u−i ) ̸= ∅.
Let u′i ∈ U W (u−i ). By (iii), fi (u′i , u−i ) = (1, ri (u−i )). By ui (1, ri (u−i )) > ui (0, ri (u−i )),fi (u) = (0, ri (u−i )), and fi (u′i , u−i ) = (1, ri (u−i )), ui (fi (u′i , u−i )) > ui (fi (u)). However,this contradicts strategy-proofness. Hence, xi (u) = 1.
If: Assume that for each i ∈ N , there exist ri : U n−1 → R ∪ {−∞} and ri : U n−1 →R ∪ {+∞} satisfying (i), (ii), and (iii).
Individual rationality: Let u ∈ U n and i ∈ N . First assume xi (u) = 0. By (iii), fi (u) =(0, ri (u−i )). By U L (u−i ) ̸= ∅ and (i-L), ri (u−i ) ≤ 0, and so ui (fi (u)) ≥ ui (0, 0) = 0.
Next assume xi (u) = 1. By (iii), fi (u) = (1, ri (u−i )). By U W (u−i ) ̸= ∅ and (i-W),ri (u−i ) ≤ min{vi , bi }, and so ui (fi (u)) ≥ ui (1, min{vi , bi }) ≥ 0.
18

Strategy-proofness: Let u ∈ U n , i ∈ N and u′i ∈ U . If xi (u) = xi (u′i , u−i ), then bydefinition, fi (u) = fi (u′i , u−i ), and so ui (fi (u)) = ui (fi (u′i , u−i )). Thus, we assume xi (u) ̸=xi (u′i , u−i ). If xi (u) = 0 and xi (u′i , u−i ) = 1, then by (ii), ui (0, ri (u−i )) ≥ ui (1, ri (u−i )),and by (iii), fi (u) = (0, ri (u−i )) and fi (u′i , u−i ) = (1, ri (u−i )). These expressions implyui (fi (u)) ≥ ui (fi (u′i , u−i )). Similarly, if xi (u) = 1 and xi (u′i , u−i ) = 0, then ui (fi (u)) =ui (1, ri (u−i )) ≥ ui (0, ri (u−i )) = ui (fi (u′i , u−i )).
Proposition 2. Let U ⊆ U C satisfy unbounded truncated valuations. Then, a rule fon U n satisfies individual rationality, no subsidy for losers, and strategy-proofness if andonly for each i ∈ N , there is a price function ri : U n−1 → R ∪ {∞} such that for eachu−i ∈ U n−1 ,(i-a) for each ui ∈ U ,xi (u) =$0
1

if min{vi , bi } < ri (u−i ),if min{vi , bi } > ri (u−i )(i-b) for each ui ∈ U , if min{vi , bi } = ri (u−i ) and vi = ∞, then xi (u) = 1,(ii) for each ui ∈ U ,ti (u) =$0ri (u−i )if xi (u) = 0.
if xi (u) = 1

Proof. Only If: Assume f satisfies individual rationality, no subsidy for losers, andstrategy-proofness. Let i ∈ N . By Lemma 1, there exist ri : U n−1 → R ∪ {∞} andri : U n−1 → R ∪ {∞} such that they satisfy the conditions in the proposition. Let
u−i ∈ U n−1 . If U L (u−i ) ̸= ∅, by Lemma 1 (i-L), ri (u−i ) ≤ 0. Thus, for each ui ∈ U L (u−i ),by no-subsidy for losers, ri (u−i ) = ti (u) = 0. Hence, (ii) holds.
Next we show (i-a) for ri . Let ui ∈ U . First assume min{vi , bi } < ri (u−i ). Suppose xi (u) = 1. Then, fi (u) = (1, ri (u−i )). By min{vi , bi } < ri (u−i ) = ti (u), ui (0, 0) >ui (fi (u)). However, this contradicts individual rationality, and so xi (u) = 0. Next assume min{vi , bi } > ri (u−i ). Suppose xi (u) = 0. By U L (u−i ) ̸= ∅, ti (u) = ri (u−i ) = 0.
Thus, fi (u) = (0, 0). If U W (u−i ) = ∅, then by Lemma 1 (i-W), ri (u−i ) = ∞. However, this contradicts min{vi , bi } > ri (u−i ), and so U W (u−i ) ̸= ∅. Let u′i ∈ U W (u−i ).
Then, fi (u′i , u−i ) = (1, ri (u−i )). By min{vi , bi } > ri (u−i ), fi (u′i , u−i ) = (1, ri (u−i )), andfi (u) = (0, 0), ui (fi (u′i , u−i )) > ui (fi (u)). However, this contradicts strategy-proofness,and so xi (u) = 1.
Finally, we show (i-b) for ri . Let ui ∈ U be such that min{vi , bi } = ri (u−i ) andvi = ∞. Suppose xi (u) = 0. Then, fi (u) = (0, 0). By vi = ∞, min{vi , bi } = bi andui (1, bi ) > 0. By bi = ri (u−i ) and fi (u) = (0, 0), ui (1, ri (u−i )) > ui (fi (u)). Let u′i ∈ U
be such that min{vi′ , b′i } > ri (u−i ). Then, by (i-a) and (ii), fi (u′i , u−i ) = (1, ri (u−i )).
By ui (1, ri (u−i )) > ui (fi (u)) and fi (u′i , u−i ) = (1, ri (u−i )), ui (fi (u′i , u−i )) > ui (fi (u)).
However, this contradicts strategy-proofness. Hence, xi (u) = 1.
19

If: Assume that for each i ∈ N , f has a price function ri : U n−1 → R ∪ {∞}satisfying (i) and (ii). By (ii), f satisfies no subsidy for losers. Thus, we show thatf satisfies individual rationality and strategy-proofness. Let ri : U n−1 → R ∪ {∞} andri : U n−1 → R∪{∞} be such that for each u−i ∈ U n−1 , ri (u−i ) = ri (u−i ), and ri (u−i ) = ∞if U L (u−i ) = ∅ and ri (u−i ) = 0 if U L (u−i ) ̸= ∅. By Lemma 1, it suﬃces to show that ri
and ri satisfy the conditions in the proposition. Let i ∈ N and u−i ∈ U n−1 .
First we show Lemma 1 (i). By the definition of ri , (i-L) is obvious. We show (i-W).
If U W (u−i ) ̸= ∅, then for each ui ∈ U W (u−i ), by xi (u) = 1 and (i-a), ri (u−i ) ≤ min{vi , bi },and so ri (u−i ) ≤ inf ui ∈U W (u−i ) min{vi , bi }. Suppose U W (u−i ) = ∅ but ri (u−i ) ̸= ∞. Letui ∈ U be such that min{vi , bi } > ri (u−i ). By (i-a), xi (u) = 1. However, this contradicts
U W (u−i ) = ∅. Hence, if U W (u−i ) = ∅, then ri (u−i ) = ∞.
Next we show Lemma 1 (ii). Let ui ∈ U . First assume ui (0, ri (u−i )) > ui (1, ri (u−i )).
If U L (u−i ) = ∅, then ri (u−i ) = ∞, and so ui (0, ri (u−i )) = −∞. However, this contradictsui (0, ri (u−i )) > ui (1, ri (u−i )). Thus, U L (u−i ) ̸= ∅, and so ri (u−i ) = 0. By ui (0, 0) >ui (1, ri (u−i )), min{vi , bi } < ri (u−i ). By (i-a), xi (u) = 0. Next assume ui (0, ri (u−i )) <ui (1, ri (u−i )). If U L (u−i ) = ∅, then by U W (u−i ) = U , xi (u) = 1. Hence, assume U L (u−i ) ̸=∅. By the definition of ri , ri (u−i ) = 0. By ui (0, 0) < ui (1, ri (u−i )), min{vi , bi } > ri (u−i ),or min{vi , bi } = ri (u−i ) and vi = ∞. Hence, by (i-a) and (i-b), xi (u) = 1.
Finally we show Lemma 1 (iii). Since ri (u−i ) = 0 if U L (u−i ) ̸= ∅, the result follows
from (ii).
Proposition 3. Let u ∈ U n and z ∈ Z. Then, z is eﬃcient for u if and only if(i) for each i ∈ N , ti ≤ bi ,#(ii)
i∈N xi = 1, and(iii) there is no z ′ ∈ Z such that#′i∈N xi =#i∈N xi and it dominates z for u.

Proof. Only if: Assume z is eﬃcient for u. Since (iii) is obvious, we show (i) and (ii).
First we show (i). Suppose there is i ∈ N such that ti > bi . Then, for ε > 0,ui (xi , ti + ε) = ui (xi , ti ). Thus, #((xi , ti + ε), z−i ) dominates z #for u, a contradiction.
Next we show (ii). Suppose i∈N xi = 0. Let j ∈ N . By i∈N xi = 0, xj = 0. By (i),tj ≤ bj , and so uj (1, tj ) > uj (zj ). Hence, ((1, tj ), z−j ) dominates z for u, a contradiction.
′
If: Assume (i), (ii), and (iii) hold. Suppose z is not# eﬃcient#for u. Then, there is z ∈ Z′′such that (a) for each i ∈ N , ui (zi ) ≥ ui (zi ), (b) i∈N ti ≥ i∈N ti , and (c) at least one
inequality holds# strictly.
#
#
#
#
′
By (iii), i∈N x′i ̸= i∈N xi . By (ii), i∈N
x
=
1,
and
so
x
=
0.
By
i
i
i∈N
i∈N xi =#1, there is i ∈ N such that xi = 1. By j∈N x′j = 0, x′i = 0. By ti ≤ bi , ui (zi ) =ui (0, ti − ci (ti )). By x′i = 0 and ui (zi′ ) ≥ ui (zi ) = ui (0, ti − ci (ti )), t′i ≤ ti − ci (ti ). For′each= xj = 0#and uj (zj′ ) ≥ uj (zj ), t′j ≤ tj . Thus, by ci (ti ) > 0,
# j ′∈ N \ {i}, by xj #j∈N tj ≤ (ti − ci (ti )) +j̸=i tj <j∈N tj . However, this contradicts (b).

20

Lemma 2. Let u ∈ U n and z ∈ Z be such that z satisfies within budget for u. Then, z
is constrained eﬃcient for u if and only if when there is i ∈ N such that xi = 1, for eachj ∈ N \ {i}, uj (zj ) ≥ uj (1, tj + ci (ti )).
Proof. Only if: Assume there is i ∈ N such that xi = 1. Let j ∈ N \ {i}. By xi = 1,
xj = 0. Suppose uj (1, tj +ci (ti )) > uj (zj ). By the definition of ci , ui (0, ti −ci (ti )) ≥ ui (zi ).
Thus, ((0, ti − ci (ti )), (1, tj + ci (ti )), z−{i,j} ) dominates z for u, a contradiction.
If: Assume that if there is i ∈ N such that xi = 1, then for each j ∈ N \ {i}, uj (zj ) ≥′uj (1, tj +#ci (ti )). Suppose
z is not constrained eﬃciency for u. Then, there## is′ z ∈#Z such′′that (i) i∈N xi = i∈N xi , (ii) for each i ∈ N , ui (zi ) ≥ ui (zi ), (iii) i∈N ti ≥ i∈N ti ,and (iv) at least one inequality holds strictly.
First we show for some i ∈ N , x′i ̸= xi . Suppose for each i ∈ N ,#x′i = xi . For# each′′′′i ∈ N , by ti ≤ bi , xi = xi , and ui (zi ) ≥ ui (zi ), ti ≤ ti . Thus, by #i∈N ti ≥ #i∈N ti ,for each i ∈ N , t′i = ti . Hence, for each i ∈ N , ui (zi′ ) = ui (zi ) and i∈N t′i = i∈N ti .
However, these equalities contradict# (iv). ′##′′# Since for some i ∈ N , xi ̸= xi , i∈N xi = 1 or i∈N xi = 1. Hence, by (i), i∈N xi =i∈N xi = 1.
#
we derive a contradiction. Since for some i ∈ N , x′i ̸= xi and i∈N xi =# Finally,′′′i∈N xi = 1, there are i, j ∈ N such that (xi , xj ) = (1, 0) and (xi , xj ) = (0, 1). By′′′ui (zi ) ≥ ui (zi ) = ui (0, ti −ci (ti )) and xi = 0, ti ≤ ti −ci (ti ). By tj ≤ bj and uj (zj′ ) ≥ uj (zj ),t′j ≤ bj . By (ii) and the assumption, uj (zj′ ) ≥ uj (zj ) ≥ uj (1, tj + ci (ti )), and so by tj ≤ bj ,t′j ≤ bj , and x′j = 1, t′j ≤ tj + ci (t#k ∈ N \ {i, j}, by x′k = xk = 0 andi ). For each#uk (zk′ ) ≥ uk (zk ), t′k ≤ tk . Hence, by k∈N t′k ≥ k∈N tk , t′i = ti − ci (ti ), t′j = tj + ci (ti ),′′and# for′ each# k ∈ N \ {i, j}, tk = tk . Thus, for each k ∈ N , uk (zk ) = uk (zk ) andk∈N tk =k∈N tk . However, these equalities contradict (iv).

Proposition 4. Let U ⊆ U C . Let f on U n be a truncated Vickrey rule with endogenous
reserve prices r. Then, f satisfies constrained eﬃciency if and only if f has an exclusive
tie-breaking rule.
Proof. Only if: Assume f satisfies constrained eﬃciency. Let u ∈ U n and i ∈ N be suchthat min{vi , bi } = max{maxj̸=i min{vj , bj }, ri (u−i )}, vi ̸= ∞, and N ∞ (u) ̸= ∅. Supposexi (u) = 1. Let ri∗ (u−i ) = max{maxj̸=i min{vj , bj }, ri (u−i )}. By min{vi , bi } = ri∗ (u−i )and vi ̸= ∞, i ∈ N (u) \ N ∞ (u). Let j ∈ N ∞ (u). By i ∈ N (u) \ N ∞ (u), i ̸= j.
By i, j ∈ N (u), min{vi , bi } = min{vj , bj }. By min{vi , bi } = min{vj , bj } and i ̸= j,
min{vi , bi } ≥ ri∗ (u−i ) ≥ min{vj , bj } = min{vi , bi }, and so, min{vi , bi } = min{vj , bj } =ri∗ (u−i ). By ri∗ (u−i ) = min{vi , bi } and (V-ii), ti (u) = min{vi , bi }. By ti (u) = min{vi , bi }and vi ̸= ∞, ui (fi (u)) = ui (0, 0). By ti (u) ≤ bi , ui (0, ti (u) − ci (ti (u))) = ui (fi (u)), and so
by ui (fi (u)) = ui (0, 0), ci (ti (u)) = ti (u). By ti (u) = min{vj , bj }, ci (ti (u)) = min{vj , bj }.
By j ∈ N ∞ (u), vj = ∞, and so uj (1, min{vj , bj }) > 0. Thus, by ci (ti (u)) = min{vj , bj }and fj (u) = (0, 0), uj (1, tj (u) + ci (ti (u))) > uj (fj (u)). However, by Lemma 2, thiscontradicts constrained eﬃciency.
21

If: Assume f has an exclusive tie-breaking rule. Suppose f violates constrained eﬃciency.
Then, by Lemma 2, there are u ∈ U n and i, j ∈ N with i ̸= j such that xi (u) = 1 anduj (1, tj (u) + ci (ti (u))) > uj (fj (u)). Let ri∗ (u−i ) = max{maxj̸=i min{vj , bj }, ri (u−i )}. By(V-i) and i ̸= j, min{vi , bi } ≥ ri∗ (u−i ) ≥ min{vj , bj }. By min{vi , bi } ≥ ri∗ (u−i ) = ti (u),ui (fi (u)) ≥ ui (0, 0). By ti (u) ≤ bi , ui (0, ti (u) − ci (ti (u))) = ui (fi (u)). By ui (0, ti (u) −ci (ti (u))) = ui (fi (u)) ≥ ui (0, 0), ci (ti (u)) ≥ ti (u). By uj (1, tj (u) + ci (ti (u))) > uj (fj (u))
and fj (u) = (0, 0), ci (ti (u)) ≤ min{vj , bj }. Hence, min{vj , bj } ≥ ci (ti (u)) ≥ ti (u) ≥min{vj , bj }, and so ci (ti (u)) = ti (u) = min{vj , bj }. By ci (ti (u)) = ti (u), ui (0, 0) =ui (fi (u)), and so min{vi , bi } = ti (u) and vi ̸= ∞. By ci (ti (u)) = min{vj , bj }, uj (1, tj (u) +ci (ti (u))) > uj (fj (u)), and fj (u) = (0, 0), vj = ∞. By min{vj , bj } = ti (u) = min{vi , bi }and i ∈ N (u), j ∈ N (u). By vj = ∞, j ∈ N ∞ (u). However, by xi (u) = 1, min{vi , bi } =ri∗ (u−i ), and vi ̸= ∞, this contradicts that f has an exclusive tie-breaking rule.

Theorem 1. Let U ⊆ U C satisfy small compensation and positive budget. Then, a rule
f on U n satisfies constrained eﬃciency, individual rationality, no subsidy for losers, andstrategy-proofness if and only if it is a truncated Vickrey rule with endogenous reserve
prices and with an exclusive and prioritized tie-breaking rule.
Proof. Since “if” part follows from Propositions 2 and 4, we only show “only if” part.
Assume f satisfies constrained eﬃciency, individual rationality, no subsidy for losers, andstrategy-proofness. By Proposition 2, for each i ∈ N , there is a price function ri : U n−1 →R ∪ {∞} satisfying the conditions in the proposition.
By Propositions 1 and 4, to prove the result, it suﬃces to show that f is a truncatedVickrey rule with endogenous reserve prices r, that is, for each i ∈ N and u−i ∈ U n−1 ,ri (u−i ) ≥ maxj̸=i min{vj , bj }.
Suppose there are i ∈ N and u−i ∈ U n−1 such that ri (u−i ) < maxj̸=i min{vj , bj }. Let
j ∈ N \ {i} be such that min{vj , bj } = maxk̸=i min{vk , bk }. Let ui ∈ U be such thatri (u−i ) < ci (ri (u−i )) < min{vj , bj }.6
First we show xi (u) = 1. If ri (u−i ) > bi , then by bi ≥ 0, ci (ri (u−i )) = ri (u−i ) − bi ≤ri (u−i ). However, this contradicts ri (u−i ) < ci (ri (u−i )), and so ri (u−i ) ≤ bi . By ri (u−i ) ≤bi , ui (0, ri (u−i ) − ci (ri (u−i ))) = ui (1, ri (u−i )). By ri (u−i ) < ci (ri (u−i )), ui (1, ri (u−i )) >ui (0, 0). By ui (1, ri (u−i )) > ui (0, 0), ri (u−i ) < min{vi , bi }, or ri (u−i ) = min{vi , bi } andvi = ∞. Thus, by Proposition 2 (i-a) and (i-b), xi (u) = 1.
Finally we derive a contradiction. By xi (u) = 1 and Proposition 2 (ii), fi (u) =(1, ri (u−i )). By ti (u) = ri (u−i ) and ci (ri (u−i )) < min{vj , bj }, uj (1, ci (ti (u))) > 0. By
xi (u) = 1, xj (u) = 0, and so fj (u) = (0, 0). Thus, by uj (1, ci (ti (u))) > 0 and fj (u) =(0, 0), uj (1, tj (u) + ci (ti (u))) > uj (fj (u)). However, by Lemma 2, this contradicts constrained eﬃciency.
Proposition 5. Let U ⊆ U C satisfy small compensation, strong density, and positive
budget. Let f on U n be a truncated Vickrey rule with endogenous reserve prices r andwith an exclusive and prioritized tie-breaking rule. Then, f violates no wastage.
6

By small compensation, ui exists.

22

Proof. Let u ∈ U n be such that for each i, j ∈ N , ui = uj and vi = ∞. Given i ∈ N andũ−i ∈ U n−1 , let ri∗ (ũ−i ) = max{maxj̸=i min{ṽj , b̃j }, ri (ũ−i )}. For each i ∈ N , by vi = ∞,∗∗min{v#
i , bi } ≥ ri (u−i ) if and only if xi (u) = 1. If for each i ∈ N , min{vi , bi } < ri (u−i ),then i∈N xi (u) = 0, and so f violates no wastage. Assume there is i ∈ N such thatmin{vi , bi } ≥ ri∗ (u−i ). Then, xi (u) = 1. Let j ∈ N \ {i}. By xi (u) = 1, xj (u) = 0, andso min{vj , bj } < rj∗ (u−j ). Let u′j ∈ U be such that min{vj , bj } < min{vj′ , b′j } < rj∗ (u−j )and vj′ = ∞.7 By min{vj′ , b′j } < rj∗ (u−j ), xj (u′j , u−j ) = 0. For each k ∈ N \ {j}, by
min{vk , bk } = min{vj , bj } < min{vj′ , b′j } ≤ rk∗ (u′j , u−{k,j} ), xk (u′j , u−j ) = 0. Hence, fviolates no wastage.
Theorem 2. Let U ⊆ U C satisfy unbounded truncated valuations. Then, a rule f on U nsatisfies weak envy-freeness for equals, individual rationality, no subsidy for losers, andstrategy-proofness if and only if it is a truncated Vickrey rule with some non-negligible
endogenous reserve prices r and with a prioritized tie-breaking rule.
Proof. Only if: Let f satisfy weak envy-freeness for equals, individual rationality, no
subsidy for losers, and strategy-proofness. By Proposition 2, for each i ∈ N , there is someprice function ri : U n−1 → R ∪ {∞} satisfying the conditions in the proposition.
First, we show that for each i ∈ N and each u−i ∈ U n−1 , ri (u−i ) ≥ maxj̸=i min{vj , bj }.
Let i ∈ N and u−i ∈ U n−1 . Suppose that for some j ∈ N \ {i}, min{vj , bj } > ri (u−i ).
By ri (u−i ) < min{vj , bj }, uj (1, ri (u−i )) > 0. Let ui ∈ U be such that ui = uj . Then, bymin{vi , bi } = min{vj , bj } > ri (u−i ), Proposition 2 (i-a) and (ii), fi (u) = (1, ri (u−i )). Byxi (u) = 1, xj (u) = 0, and so by Proposition 2 (ii), fj (u) = (0, 0). Thus, by uj (1, ri (u−i )) >0 and fi (u) = (1, ri (u−i )), uj (fi (u)) > uj (fj (u)). However, by uj = ui , this contradicts
weak envy-freeness for equals. Hence, ri (u−i ) ≥ maxj̸=i min{vj , bj }.
For each i ∈ N and each u−i ∈ U n−1 , by ri (u−i ) ≥ maxj̸=i min{vj , bj }, ri (u−i ) =max{maxj̸=i min{vj , bj }, ri (u−i )}. Hence, by Proposition 2, f is a truncated Vickrey rulewith endogenous reserve prices r and with a prioritized tie-breaking rule.
Finally, we show that r is non-negligible. Let i ∈ N and u−i ∈ U n−1 , and let
j ∈ N be such that min{vj , bj } = maxk̸=i min{vk , bk } and vj = ∞. Suppose ri (u−i ) ≤maxk̸=i min{vk , bk }. Let ri∗ (u−i ) = max{maxk̸=i min{vk , bk }, ri (u−i )}. Then, by min{vj , bj } =maxk̸=i min{vk , bk } ≥ ri (u−i ), ri∗ (u−i ) = min{vj , bj }. Let ui ∈ U be such that ui = uj . Bymin{vj , bj } = ri∗ (u−i ), vj = ∞, and ui = uj , min{vi , bi } = ri∗ (u−i ) and vi = ∞. Thus, aprioritized tie-breaking rule requires xi (u) = 1. By Proposition 2 (ii), ti (u) = ri∗ (u−i ) =min{vj , bj }. By vj = ∞, fi (u) = (1, bj ). By xi (u) = 1, xj (u) = 0. By xj (u) = 0 and
Proposition 2 (ii), fj (u) = (0, 0). By vj = ∞, uj (1, bj ) > 0. Thus, by fi (u) = (1, bj ) andfj (u) = (0, 0), uj (fi (u)) > uj (fj (u)). However, this contradicts weak envy-freeness forequals.
If: Let f be a truncated Vickrey rule with non-negligible endogenous reserve prices r
and with a prioritized tie-breaking rule. Since f satisfies all the conditions in Proposition
7

By strong density, u′j exists.

23

2, it satisfies individual rationality, no subsidy for losers, and strategy-proofness. Hence,
we show that f satisfies weak envy-freeness for equals.
Let u ∈ U and i, j ∈ N be such that ui = uj , xi (u) = 0 and xj (u) = 1. By xj (u) = 1,i ̸= j and (V-i), min{vj , bj } ≥ max{maxk̸=j min{vk , bk }, rj (u−j )} ≥ min{vi , bi }. By ui =
uj , the above inequalities hold with equality, and so min{vi , bi } = maxk̸=j min{vk , bk } ≥rj (u−j ). Thus, by non-negligibility, vi ̸= ∞, and so by definition, vi ≤ bi . Hence,max{maxk̸=j min{vk , bk }, rj (u−j )} = vi . By xi (u) = 0, xj (u) = 1, and (V-ii), fi (u) = (0, 0)
and fj (u) = (1, vi ). Thus, by the definition of vi , ui (fi (u)) = ui (fj (u)).
Proposition 6. Let U ⊆ U C satisfy unbounded truncated valuations. Let f on U n be atruncated Vickrey rule with non-negligible endogenous reserve prices r. Then, f satisfies
equal treatment of equals and envy-freeness.
Proof. Since envy-freeness implies equal treatment of equals, we only show envy-freeness.
Let u ∈ U n and i, j ∈ N . If xi (u) = xj (u) = 0, by fi (u) = fj (u) = (0, 0), ui (fi (u)) =ui (fj (u)). If xi (u) = 1 and xi (u) = 0, then by fj (u) = (0, 0) and individual rationality, ui (fi (u)) ≥ ui (fj (u)). Assume xi (u) = 0 and xj (u) = 1. Given k ∈ N , letrk∗ (u−k ) = max{maxh̸=k min{vh , bh }, rk (u−k )}. By xj (u) = 1, fj (u) = (1, rj∗ (u−j )). Byi ̸= j, min{vi , bi } ≤ rj∗ (u−j ). If min{vi , bi } < rj∗ (u−j ), by fi (u) = (0, 0) and fj (u) =(1, rj∗ (u−j )), ui (fi (u)) > ui (fj (u)). Assume min{vi , bi } = rj∗ (u−j ). By min{vi , bi } =rj∗ (u−j ), min{vi , bi } = maxk̸=j min{vk , bk }. By min{vi , bi } = rj∗ (u−j ) ≥ rj (u−j ) andnon-negligibility, vi ̸= ∞, and so ui (1, min{vi , bi }) = ui (0, 0). Thus, by fi (u) = (0, 0),fj (u) = (1, rj∗ (uj )), and rj∗ (u−j ) = min{vi , bi }, ui (fi (u)) = ui (fj (u)).
Theorem 3. Let U ⊆ U C satisfy density. Then, a rule f on U n satisfies anonymity inwelfare, individual rationality, no subsidy for losers, and strategy-proofness if and only if it
is a truncated Vickrey rule with upper anonymous and non-negligible endogenous reserve
prices r and with a prioritized tie-breaking rule.

Proof. Only if: Let f satisfy anonymity in welfare, individual rationality, no subsidy
for losers, and strategy-proofness. By Theorem 2, f is a truncated Vickrey rule with
non-negligible reserve prices r and with a prioritized tie-breaking rule. Thus, we show
r is upper anonymous. Let u, u′ ∈ U n and i, j ∈ N be such that ui = u′j , uj = u′i ,
u−{i,j} = u′−{i,j} , and ri (u−i ) > maxk̸=i min{vk , bk }. Suppose ri (u−i ) ̸= rj (u′−j ). Givenk ∈ N and ũ−k ∈ U n−1 , let rk∗ (ũ−k ) = max{maxh̸=k min{ṽh , b̃h }, rk (ũ−k )}.
First, we show ri∗ (u−i ) ̸= rj∗ (u′−j ). By ri (u−i ) > maxk̸=i min{vk , bk }, ri∗ (u−i ) = ri (u−i ).
If rj (u′−j ) ≤ maxk̸=j min{vk′ , b′k }, then by ri∗ (u−i ) = ri (u−i ) > maxk̸=i min{vk , bk } andrj∗ (u′−j ) = maxk̸=j min{vk′ , b′k } = maxk̸=i min{vk , bk }, ri∗ (u−i ) > rj∗ (u′−j ). If rj (u′−j ) >maxk̸=j min{vk′ , b′k }, then by ri (u−i ) ̸= rj (u′−j ), ri∗ (u−i ) = ri (u−i ), and rj∗ (u′−j ) = rj (u′−j ),ri∗ (u−i ) ̸= rj∗ (u′−j ).
Next, we derive a contradiction. Without loss of generality, assume ri∗ (u−i ) > rj∗ (u′−j ).
Let ũi = ũ′j ∈ U be such that ri∗ (u−i ) > min{ṽi , b̃i } = min{ṽj′ , b̃′j } > rj∗ (u′−j ).8 Then, by
8

By density, ũi exists.

24

definition, fi (ũi , u−i ) = (0, 0) and fj (ũ′j , u′−j ) = (1, rj∗ (u′−j )). By min{ṽi , b̃i } > rj∗ (u′−j ),ũi (1, rj∗ (u′−j )) > ũi (0, 0), and so ũi (fj (ũ′j , u−j )) > ũi (fi (ũi , u−i )). However, this contradicts
anonymity in welfare.
If: Let f be a truncated Vickrey rule with upper anonymous and non-negligible endogenous reserve prices r and with a prioritized tie-breaking rule. By Theorem 2, f satisfies
individual rationality, no subsidy for losers, and strategy-proofness. Thus, we show fsatisfies anonymity in welfare.
Let u, u′ ∈ U n and i, j ∈ N be such that ui = u′j , uj = u′i , and u−{i,j} = u′−{i,j} .
Given k ∈ N and ũ−k ∈ U n−1 , let rk∗ (ũ−k ) = max{maxh̸=k min{ṽh , b̃h }, rk (ũ−k )}. By
maxk̸=i min{vk , bk } = maxk̸=j min{vk′ , b′k } and upper anonymity of r, ri∗ (u−i ) = rj∗ (u′−j ).
If xi (u) = xj (u′ ), then by ri∗ (u−i ) = rj∗ (u′−j ), fi (u) = fj (u′ ), and so ui (fi (u)) = ui (fj (u′ )).
Assume xi (u) ≠ xj (u′ ). Without loss of generality, assume xi (u) = 1 and xj (u′ ) = 0.
By xi (u) = 1, min{vi , bi } ≥ ri∗ (u−i ), and by xj (u′ ) = 0, min{vj′ , b′j } ≤ rj∗ (u′−j ). By
min{vi , bi } = min{vj′ , b′j } and ri∗ (u−i ) = rj∗ (u′−j ), min{vi , bi } = ri∗ (u−i ) = rj∗ (u′−j ) =min{vj′ , b′j }. By xi (u) = 1 and ri∗ (u−i ) = min{vi , bi }, fi (u) = (1, min{vi , bi }). By xj (u′ ) =0, fj (u′ ) = (0, 0). By xj (u′ ) = 0, min{vj′ , b′j } = rj∗ (u′−j ), and a prioritized tie-breaking
rule, vj′ ̸= ∞. By vi = vj′ ̸= ∞, ui (1, min{vi , bi }) = ui (0, 0). By fi (u) = (1, min{vi , bi }),fj (u′ ) = (0, 0), and ui (1, min{vi , bi }) = ui (0, 0), ui (fi (u)) = ui (fj (u′ )).

References[1] Adachi, T. (2014), Equity and the Vickrey allocation rule on general preference
domains, Social Choice and Welfare, 42, 813–830.
[2] Aggarwal, G., S. Muthukrishnan, D. Pál, M. Pál (2009), General auction mechanism
for search advertising, In the 18th International Conference on World Wide Web(WWW’09), Madrid, Spain, 241–250.
[3] Ashlagi, I., S. Serizawa (2012), Characterizing Vickrey allocation rule by anonymity,
Social Choice and Welfare, 38, 53-542.
[4] Ausubel, L. (2004), An eﬃcient dynamic auction for heterogenous commodities.
American Economic Review, 96, 602–629.
[5] Basu, R., C Mukherjee (2022), Characterization of Vickrey auction with reserve pricefor multiple objects, Review of Economic Design, forthcoming.
[6] Bulow, J., J. Levin, P. Milgrom (2009), Winning play in spectrum auctions. Technicalreport, National Bureau of Economic Research.
[7] Dobzinski, S., R. Lavi, N. Nisan (2012), Multi-unit auctions with budget limits.
Games and Economic Behavior, 74, 486–503
25

[8] Dütting, P., M. Henzinger, M. Starnberger (2015), Auctions with heterogeneous items
and budget limits. ACM Transactions on Economics and Computation, 4, 4:1–4:17.
[9] Dütting, P. M. Henzinger, I. Weber (2015), An Expressive Mechanism for Auctions
on the Web. ACM Transactions on Economics and Computation, 4, 1:1-1:34.
[10] Fiat, A., S. Leonardi, J. Saia, P. Sankowski (2011), Single valued combinatorial auctions with budgets. In: the 12th ACM Conference on Electronic Commerce (EC’11),
San Jose, California, 223–232.
[11] Hirai, H., R. Sato (2023), Polyhedral Clinching Auctions for Indivisible Goods, In:
the 19th International Conference on Web and Internet Economics (WINE 2023),
Shanghai, China, 366–383.
[12] Holmström, B. (1979), Groves’ scheme on restricted domains. Econometrica, 47,
1137–1144.
[13] Kazumura, T., D. Mishra, S. Serizawa (2017), Mechanism design without quasilinearity. ISER Discussion Paper, No. 1005, Osaka University.
[14] Lavi, R., M. May (2012), A note on the incompatibility of strategy-proofness andPareto-optimality in quasi-linear settings with public budgets. Economic Letters, 115,
100–103.
[15] Le, P. (2017), Mechanisms for combinatorial auctions with budget constraints. Review
of Economic Design, 21, 1–31.
[16] Le, P. (2018), Pareto optimal budgeted combinatorial auctions. Theoretical Economics, 13, 831–868.
[17] Mukherjee, C. (2014), Fair and group strategy-proof good allocation with money,
Social Choice and Welfare, 42, 289–311[18] Mackenzie A., Y. Zhou (2022), Tract housing, the core, and pendulum auctions.
Graduate school of Economics Discussion paper series, No. E-22-005, Kyoto University.
[19] Nisan, N. (2007), Introduction to mechanism design (for computer scientists). In:
N. Nisan, T. Rougarden, E. Tardos, V. Vazirani (Eds.), Algorithmic Game Theory,
Cambridge University Press, New York, USA, 209–241.
[20] Sakai, T. (2008), Second price auctions on general preference domains: two characterizations. Economic Theory, 37, 347–356.
[21] Sakai, T. (2013a), An equity characterization of second price auctions when preferences may not be quasilinear, Review of Economic Design, 17, 17–26.
26

[22] Sakai, T. (2013b), Axiomatizations of second price auctions with a reserve price,
International Journal of Economic Theory, 9, 255-265.
[23] Saitoh, H., S. Serizawa (2008), Vickrey allocation rule with income eﬀect. Economic
Theory, 35, 391–401.
[24] Shinozaki, H. (2023), Non-obvious manipulability and eﬃciency in package assignment problems with money for agents with income eﬀects and hard budget constraints. HIAS Discussion Paper Series, No. HIAS-E-136, Hitotsubashi University.
[25] Sprumont, Y. (2013), Constrained-optimal strategy-proof assignment: Beyond theGroves mechanisms, Journal of Economic Theory, 148, 1102–1121.
[26] Ting, H.F., X. Xiang (2012), Multi-unit auctions with budgets and non-uniform
valuations. In: the 23rd International Symposium on Algorithms and Computation(ISAAC 2012), Taipei, Taiwan, 669–678.
[27] Vickrey, W. (1961), Counterspeculation, auctions, and competitive sealed tenders.
Journal of Finance, 16, 8–37.
[28] Yi, J. (2023), A note on the impossibility of multi-unit auctions with budgetconstrained bidders. Review of Economic Design, forthcoming.

27