HIAS-E-136

Non-obvious manipulability and eﬃciency in package
assignment problems with money for agents withincome eﬀects and hard budget constraints
Hiroki Shinozaki
Hitotsubashi University

December 2023

Hitotsubashi Institute for Advanced Study, Hitotsubashi University
2-1, Naka, Kunitachi, Tokyo 186-8601, Japan
tel:+81 42 580 8668 http://hias.hit-u.ac.jp/
HIAS discussion papers can be downloaded without charge from:https://hdl.handle.net/10086/27202
https://ideas.repec.org/s/hit/hiasdp.html

Non-obvious manipulability and eﬃciency in package
assignment problems with money for agents withincome eﬀects and hard budget constraints∗
Hiroki Shinozaki†
December 18, 2023

Abstract
We study a problem of assigning packages of objects to agents with money. We
allow agents to have utility functions that exhibit income eﬀects or face hard budget
constraints. It is already known that one of income eﬀects and hard budget constraints lead to the non-existence of a rule satisfying strategy-proofness, eﬃciency,
individual rationality, and no subsidy (Dobzinski et al., 2012; Kazumura and Serizawa, 2016; Baisa; 2020, Malik and Mishra, 2021, etc.). Given such negative results,
we search for rules satisfying non-obvious manipulability (Troyan and Morrill, 2020),
an incentive property weaker than strategy-proofness, together with the other threeproperties. First, we identify a necessary and suﬃcient condition for a rule satisfying
eﬃciency, individual rationality, and no subsidy to be non-obviously manipulable.
By using the ﬁrst result, we show that a slight modiﬁcation of a (truncated) pay as
bid rule satisﬁes non-obvious manipulability, eﬃciency, individual rationality, andno subsidy.

JEL Classiﬁcation Numbers. D44, D47, D71, D82

Keywords. Non-obvious manipulations, Eﬃciency, Strategy-proofness, Non-quasilinear utilities, Hard budget constraints, Package auctions∗

The author gratefully acknowledges ﬁnancial support from the Japan society for the Promotion of
Sciences (23K18777).
†
Hitotsubashi Institute for Advanced Study, Hitotsubashi University. Email: shinozakiecon@gmail.com

1

1

Introduction

We consider a package assignment problem with money, where a package may involve
several objects. We allow each object type to have several copies, or there is only a single
object. Examples of our model includes package auctions such as spectrum auctions,airport auctions, privatization auctions, etc., as well as single object auctions. In practicalauctions, agents’ payments are typically large compared their incomes and budgets, andso both income eﬀects and budget constraints are pervasive (Bulow et al., 2017). We allow
agents to have utility functions that exhibit income eﬀects or face hard and private budget
constraints.
A (consumption) bundle is a pair consisting of a package and a payment. An allocation
speciﬁes each agent’s bundle. A domain is a class of utility functions. An (allocation) rule
is a mapping from a set of utility proﬁles to the set of allocations.
A report of a utility function is a proﬁtable manipulation if there is other agents’ utility
functions under which an agent gets better oﬀ by reporting it than the truth-telling. A
rule is strategy-proof if no report of each agent is a proﬁtable manipulation. An allocation
Pareto dominates another allocation if no agent gets worse oﬀ, the revenue of the ownerof the objects does not decrease, and the utility of some agent or the revenue gets strictly
improved. A rule is eﬃcient if an outcome allocation of the rule is not Pareto dominated byany other allocation. A rule is individually rational if no agent ﬁnds his outcome allocationof the rule worse than receiving no object with the payment of zero. A rule satisﬁes no
subsidy if the payment of each agent is always non-negative.
The above four properties are basic requirements, and have been extensively studied in
the literature (Chew and Serizawa, 2007; Dobzinski et al., 2012; Kazumura and Serizawa,
2016; Le, 2018; Baisa, 2020; Malik and Mishra, 2021, etc). Unfortunately, it is alreadyknown that in a package assignment model, when agents have utility functions that either
exhibits income eﬀects or face hard budget constraints, there is no rule that satisﬁes thefour properties (Kazumura and Serizawa, 2016; Baisa, 2020; Malik and Mishra, 2021,
Kazumura, 2022; Shinozaki et al., 2022 for income eﬀects; Dobzinski et al., 2012; Le, 2018
for hard budget constraints).
Given impossibility results, there are two typical approaches to further the research.
One is to ﬁnd restricted domains on which there is (not) a rule satisfying the desirable properties (Kazumura and Serizawa, 2016; Baisa, 2020; Malik and Mishra, 2021; Kazumura,2

2022; Shinozaki et al., 2022). The other approach is to relax one of the properties (Hafair etal., 2012; Baisa, 2017, 2018; Baisa and Essig Aberg, 2021; Shinozaki, 2023), which we willtake in this paper. In particular, we relax strategy-proofness to non-obvious manipulability (Morrill and Troyan, 2020), a weaker incentive property than strategy-proofness, andinvestigate rules satisfying non-obvious manipulability, eﬃciency, individual rationality,and no subsidy.
In order for a proﬁtable manipulation to be successful, an agent has to know the otheragents’ utility functions and to understand the details of the rule. However, real-life people
often lack such information on other agents’ utility functions and ability to engage in contingent reasoning (Li, 2017). This observation leads to the idea that it may be unnecessary
for a rule to prevent all possible proﬁtable manipulations, as strategy-proofness does.
Troyan and Morrill (2020) introduce the notion of obvious manipulations that is easy
to recognize and execute successfully. Formally, a proﬁtable manipulation is obvious if
the best case utility from the manipulation is greater than the best case utility from thetruth-telling, or the worst case utility from the manipulation is greater than the worst caseutility from the truth-telling. Troyan and Morrill (2020) provide a foundation of obvious
manipulations by showing that a proﬁtable manipulation is obvious if and only if evena cognitively limited agent who does not understand the details of a rule can recognizethat it is a proﬁtable manipulation. A rule is not obviously manipulable if no proﬁtable
manipulation is obvious. Thus, a non-obviously manipulable rule prevents agents frommanipulations that are easy to recognize and execute successfully. Note that non-obvious
manipulability is weaker than strategy-proofness.
First, we derive a necessary and suﬃcient condition for a rule satisfying eﬃciency,
individual rationality, and no subsidy to be non-obviously manipulable. Note that undera rule satisfying no subsidy, the best bundle among all the bundles that may be available
to a rule (we call it the best bundle) is the one at which an agent receives all the objects
with the payment of zero.1 Then, we show that a necessary and suﬃcient condition fora rule satisfying eﬃciency, individual rationality, and no subsidy to satisfy non-obvious
manipulability is that, for each agent, the best case utility from the truth-telling is theutility from the best bundle (Theorem 1).
We exploit a necessary and suﬃcient condition obtained in Theorem 1 to develop a
1

We assume both money monotonicity meaning less payments make an agent better oﬀ and object
monotonicity meaning more objects make him better oﬀ.

3

new rule satisfying non-obvious manipulability, eﬃciency, individual rationality, and no
subsidy. To this end, we ﬁrst ﬁnd a rule satisfying eﬃciency, individual rationality, andno subsidy, and then modify it so as to satisfy non-obvious manipulability on the basis of
Theorem 1.
Note that in our setting of income eﬀects and hard budget constraints, both the valuations of the package (the willingness to pay at the bundle with no object and the paymentof zero) and the budget (the ability to pay) are the important information of a utility
function. A truncated valuation of a package is the smaller of the valuation of the package
and the budget, which reﬂects both the information. A counterpart of a well-known pay
as bid rule in our setting is deﬁned as follows. A rule is a truncated pay as bid rule if the
packages are allocated to the agents so as to maximize the sum of truncated valuations,and each agent pays the truncated valuation of a package that he obtains. We show thatany truncated pay as bid rule satisﬁes eﬃciency, individual rationality, and no subsidy(Proposition 1).
A lesson learned from Theorem 1 is that if the best case utility from the truth-tellingis equal to the utility from the best bundle, then a rule satisfying eﬃciency, individual
rationality, and no subsidy is non-obviously manipulable. Thus, we modify a truncatedpay as bid rule so that the best case utility from the truth-telling is the utility from thebest bundle. A rule is a modiﬁed (truncated ) pay as bid rule if whenever there is an agent
who has the suﬃciently large valuations compared with the other agents, he receives all
the objects with the payment of zero and all the other agents receives and pays nothing,and otherwise, its outcome allocation is equivalent to that under a truncated pay as bid
rule.2 We establish that any modiﬁed pays as bid rule satisﬁes non-obvious manipulability,
eﬃciency, individual rationality, and no subsidy (Theorem 2).
It is widely recognized that a (truncated) pay as bid rule is easy to manipulate, andTroyan and Morrill (2020) formalize this idea by showing that it is obviously manipulable.
An interesting point of Theorem 2 would be that a slight modiﬁcation of a (truncated)
pay as bid rule (a modiﬁed pay as bid rule) satisﬁes a weak incentive property, namely
non-obvious manipulability.
We claim the advantages of a modiﬁed pay as bid rule compared with other standard
rules. Indeed, a truncated Vickrey rule (or its modiﬁcation deﬁned in the same way as a2

Note that this deﬁnition is informal because we do give the precise meaning of “suﬃciently large
valuations compared with the other agents”. For the formal deﬁnition of the rule, see Section 4.3.

4

modiﬁed pay as bid rule) violates eﬃciency (Proposition 2), and so a modiﬁed pay as bid
rule outperforms a truncated (or modiﬁed) Vickrey rule in terms of eﬃciency. A pay as
bid rule also outperforms a Warlasian rule (also known as a uniform-price rule) in termsof an application range because a Warlasian rule is often not well-deﬁned due to the nonexistence of a Warlasian equilibrium allocation (Gul and Stacchetti, 1999; Baldwin et al.,2023). We will discuss these points in detail in Section 5.
The paper is organized as follows. Section 2 gives a literature review. Section 3 introduces the model. Section 4 presents the main results. Section 5 discusses the advantage ofa modiﬁed pay as bid rule compared with other standard rules. Section 6 gives concluding
remarks. The proofs are relegated to the Appendix.

2

Related literature

2.1

Object allocation problem with money

The fundamental result in package assignment problems with money is that if utility functions are quasi-linear, i.e., if utility functions neither exhibit income eﬀects nor face hardbudget constraints, then the Vickrey rules are the only rules satisfying strategy-proofness,eﬃciency, individual rationality, and no subsidy (Holmström, 1979; Chew and Serizawa,
2007). There are two branches of research that attempt to extend this result to non-quasilinear settings.
The ﬁrst branch of research considers agents with income eﬀects but without hardbudget constraints. In this model, if agents receive several objects as in this paper, thentypically no rule satisﬁes strategy-proofness, eﬃciency, individual rationality, and no subsidy (Kazumura and Serizawa, 2016; Baisa, 2020; Malik and Mishra, 2021; Kazumura,2022; Shinozaki et al., 2022). In contrast, if there is a single object or agents receive at
most one object, then the minimum price Warlasian rules of Demange and Gale (1985)
are the only rules satisfying the four properties (Saitoh and Serizawa, 2008; Sakai, 2008;
Morimoto and Serizawa, 2015, etc.).
The second branch considers agents with hard budget constraints but without income
eﬀects. If agents’ budgets are private information as in this paper, no rule satisﬁes the four
properties even in a single object model (Dobzinski et al., 2012; Le, 2018; etc.). Note thatthe impossibility result holds even in a single object setting, which contrasts the results
5

for agents with income eﬀects but without hard budget constraints. In contrast, if agents’budgets are public information, then the clinching auctions of Ausubel (2004) are the only
rules satisfying the four properties (Dobzinski et al., 2012). Note that in our results werequire a certain domain richness condition that excludes a public budget case.
This paper is motivated from the impossibility results in both the branches of research,and belongs to both. A contribution of this paper to both the branches is to obtaina positive existence result by relaxing strategy-proofness to non-obvious manipulability(Theorem 2) in a general model that includes both the income eﬀects model and the hardbudget constraints model as specical cases
Several authors have studied the consequences of relaxing (or dropping) one of the four
properties to escape from impossibility results (Hafalir et al., 2012; Baisa, 2017, 2018;
Baisa and Essig Aberg, 2021; Shinozaki, 2023). Hafalir et al. (2012), Baisa (2017, 2018),
and Baisa and Essig Aberg (2021) show that once we weaken strategy-proofness to a
weak incentive property such as Nash implementation (Hafalir et al., 2012; Baisa, 2017),
implementation in iterated elimination of weakly dominated strategies (Baisa, 2018), or
implementation in undominated strategies (Baisa and Essig Aberg, 2021), we can ﬁndrules satisfying their respective weak incentive properties, eﬃciency (or a weak eﬃciency
property in Hafalir et al. (2017) and Baisa and Essig Aberg (2021)), individual rationality,and no subsidy. This paper complements this line of research by studying a consequenceof relaxing strategy-proofness to non-obvious manipulability, a weak incentive property
diﬀerent from theirs. Also, Shinozaki (2023) shows the possibility of a rule satisfying
strategy-proofness, eﬃciency, and individual rationality by giving up no subsidy instead ofrelaxing strategy-proofness.

2.2

Non-obvious manipulability

Since Troyan and Morrill (2020) introduced the concept of obvious manipulations, several
authors have investigated non-obvious manipulability in various models (Aziz and Lam,
2021; Arribillaga and Bonifacio, 2024 for a voting model; Ortega and Segal-Halevi, 2022
for a cake-cutting model; Psomas and Verma, 2022 for a probabilistic assignment model
without money; Troyan, 2022 for an assignment model without money; Arribillaga andRisma, 2023 for a matching model with contracts, Archbold et al., 2023a,b for a social
choice model with money for quasi-linear utilities).
6

Notably, Troyan and Morrill (2020) study non-obvious manipulability in package assignment problems with money, and show that in an identical objects model with quasi-linear
utilities, a minimum uniform-price rule (also known as a minimum price Warlasian rule) is
non-obviously manipulable, while a pay as bid rule is obviously manipulable. Note that for
quasi-linear utilities (and as we will show for utilities with income eﬀects and hard budget
constraints in Propositions 1 and 3), both a minimum uniform-price rule and a pay as bid
rule satisfy eﬃciency, individual rationality, and no subsidy. The ﬁrst result of this paper(Theorem 1) extends their results by deriving a necessary and suﬃcient condition for arule satisfying the three properties to be non-obviously manipulable, and indeed, it implies
their results as corollaries.
Troyan and Morrill (2020) and Archbold et al. (2023a) study a bilateral trade model
which is closely related to a package assignment model with money, and show that no rulesatisﬁes non-obvious manipulability, eﬃciency, individual rationality, and weak budgetbalance. A positive result in this paper (Theorem 2) is in contrast to their negative results.

3

Model

There are n ≥ 2 agents and m ≥ 1 types of objects. Let N = {1, . . ., n} denote the setof agents, and M = {1, . . ., m} the set of object types. Each object type a ∈ M has
q a ∈ N copies. Let q = (q a )a∈M . A package of objects that an agent i ∈ N receives isxi ∈ (N ∪ {0})m . Let X = {xi ∈ (N ∪ {0})m : xi ≤ q}.3 Let 0 = (0, . . ., 0) ∈ X. A
payment that an agent i ∈ N makes is ti ∈ R. The (consumption) set of an agent i ∈ N
is X × R. A (consumption) bundle of an agent i ∈ N is a pair zi = (xi , ti ) ∈ X × R.
Our model includes a single object allocation model (m = 1 and q = 1), a multi-unit object
allocation model (m = 1 and q ≥ 2), and a combinatorial object allocation model (m ≥ 2
and q = (1, . . ., 1)) as special cases.
An agent i ∈ N has a utility function ui : X × R → R ∪ {−∞} such that for somebi ∈ R++ ∪ {∞}, we have that for each zi = (xi , ti ) ∈ X × R, if ti ≤ bi , then ui (zi ) > −∞,and if ti > bi , then ui (xi , ti ) = −∞. Note that for each xi ∈ X, ui (xi , 0) > − ∞. For
notational convenience, for each xi ∈ X, let ui (xi , ∞) = −∞.
3

Throughout the paper, we employ the following notations on the vector inequalities: For each pairx, y ∈ Rm , x ≥ y if and only if xa ≥ y a for each a ∈ M , and x > y if and only if x ≥ y and x ̸= y, i.e.,xa ≥ y a for each a ∈ M with at least one strict inequality.

7

We may impose the following properties on a utility function.
Money monotonicity. For each xi ∈ M and each pair ti , t′i ∈ R with ti < t′i ≤ bi , wehave ui (xi , ti ) > ui (xi , t′i ).
Object monotonicity. For each pair xi , x′i ∈ X with xi > x′i and each ti ∈ R with ti ≤ bi ,we have ui (xi , ti ) > ui (x′i , ti ).
Finiteness. For each zi ∈ X × R and each xi ∈ X, if ui (zi ) ≥ ui (xi , bi ), then there isti ∈ R such that ui (zi ) ≤ ui (xi , ti ).
Continuity. For each xi ∈ X, ui (xi , ·) is continuous on (−∞, bi ].4
Let U denote the class of all utility functions satisfying the above four properties. Our
generic notation for a class of utility functions satisfying the four properties is U . Thus,
U ⊆ U . We call U a domain.
Given ui ∈ U , zi ∈ X × R, and xi ∈ X with ui (zi ) ≥ ui (xi , bi ), by ﬁniteness and continuity, there is a payment ti ∈ R such that ui (zi ) = ui (xi , ti ). By money monotonicity,such a payment is unique. We call the unique payment ti such that ui (zi ) = ui (xi , ti ) the
valuation of xi at zi for ui , and denote it by Vi (xi , zi ). Thus, ui (zi ) = ui (xi , Vi (xi , zi )).
For notational convenience, if ui (zi ) < ui (xi , bi ), then let Vi (xi , zi ) = ∞.
We introduce the four special classes of utility functions that have been studied extensively in the literature.
• A utility function ui is quasi-linear if there is a function vi : X → R+ such that (i)vi (0) = 0, (ii) for each pair xi , x′i ∈ X with xi > x′i , vi (xi ) > vi (x′i ), and (iii) for each(xi , ti ) ∈ X × R, ui (xi , ti ) = vi (xi ) − ti . Let U Q denote the class of all quasi-linear
utility functions. Note that if ui ∈ U Q , then bi = ∞, i.e., an agent faces no hardbudget constraint. Note also that if ui ∈ U Q , then for each pair xi , x′i ∈ X and eachti ∈ R, Vi (xi , (x′i , ti )) − ti = vi (xi ) − vi (x′i ). Thus, in particular, for each xi ∈ X,
Vi (xi , (0, 0)) = vi (xi ).
• A utility function ui faces (only) soft budget constraints if there is a (soft) budget
4

We only require that ui (xi , ·) be left-continuous at ti = bi .

8βi ∈ R++ ∪ {∞}, an interest rate r ∈ R++ , and a function vi : X → R+ such that(i) vi (0) = 0, (ii) for each pair xi , x′i ∈ X with xi > x′i , vi (xi ) > vi (x′i ), and (iii) for
each (xi , ti ) ∈ X × R,

ui (xi , ti ) =
vi (xi ) − ti

if ti ≤ βi ,vi (xi ) − βi − (1 + r)(ti − βi ) if ti > βi .

Let U SB denote the class of all utility functions that face soft budget constraints.
Note that if ui ∈ U SB , then bi = ∞. Note also that U Q ⊊ U SB .
• A utility function ui faces (only) hard budget constraints if there is a function
vi : X → R+ such that (i) vi (0) = 0, (ii) for each pair xi , x′i ∈ X with xi > x′i ,vi (xi ) > vi (x′i ), and (iii) for each (xi , ti ) ∈ X × R,

ui (xi , ti ) =
vi (xi ) − ti

if ti ≤ bi ,−∞

if ti > bi .

Let U HB denote the class of all utility functions that face hard budget constraints.
Note that U Q ⊊ U HB . Note also that U HB ∩ U SB = U Q .
• A utility function ui exhibits (only) income eﬀects if bi = ∞, i.e., hard budget constraints are never binding. Let U IE denote the class of all utility functions
that exhibit income eﬀects. Note that U Q ⊊ U IE and U SB ⊊ U IE . Note also that
U IE ∩ U HB = U Q .
A (feasible) object allocation is an n-tuple x = (xi )i∈N ∈ X n such that∑i∈N xi ≤ q.

Let X denote the set of object allocations. A (feasible) allocation is an n-tuple z =(zi )i∈N = (xi , ti )i∈N ∈ (X × R)n such that (xi )i∈N ∈ X .
A utility proﬁle is an n-tuple u = (ui )i∈N . Given u ∈ U n and i ∈ N , let u−i =(uj )j∈N \{i} .
An (allocation) rule on U n is a function f : U n → Z. Given a rule f on U n , let
xf : U n → X denote the object allocation rule associated with f , and tf : U n → Rn
the associated payment rule. Given a rule f on U n , u ∈ U n , and i ∈ N , let fi (u) =(xfi (u), tfi (u)) denote an outcome bundle of agent i for u under f .

9

We introduce the two incentive properties of rules. A report of a utility function u′i ∈ U
is a proﬁtable manipulation under a rule f on U n at ui ∈ U if there is u−i ∈ U n−1 suchthat ui (fi (u′i , u−i )) > ui (fi (ui , u−i )). The following property requires no proﬁtable manipulation exist under a rule.
Strategy-proofness. For each u ∈ U n , each i ∈ N , and each u′i ∈ U , ui (fi (u)) ≥ ui (fi (u′i , u−i )).

Morrill and Troyan (2020) introduce the concept of obvious manipulations. In words,
a report u′i is an obvious manipulation of a rule f on U n at ui if either the best caseutility from the manipulation is greater than that from the truth-telling, or the worst caseutility from the manipulation is greater than that from the truth-telling. Formally, a reportu′i ∈ U is an obvious manipulation of a rule f on U n at ui ∈ U if we have either5supu−i ∈U n−1

ui (fi (u′i , u−i )) >supu−i ∈U n−1

ui (fi (ui , u−i )),orinfu−i ∈U n−1

ui (fi (u′i , u−i )) >inf

u−i ∈U n−1

ui (fi (ui , u−i )),The following incentive property is introduced by Morrill and Troyan (2020), which
requires that no obvious manipulation exist under a rule.
Non-obvious manipulability. For each i ∈ N and each pair ui , u′i ∈ U , we havesupu−i

∈U n−1ui (fi (ui , u−i )) ≥

sup
u−i

∈U n−1ui (fi (u′i , u−i ))andinfn−1 ui (fi (ui , u−i )) ≥u−i ∈U

infn−1 ui (fi (u′i , u−i )).

u−i ∈U

Note that strategy-proofness implies non-obvious manipulability.
5

The original deﬁnition of an obvious manipulation in Morrill and Troyan (2020) compares the maximum
utility from a manipulation with the maximum utility from the truth telling in a model with ﬁnite outcomes,
and the minimum utilities. Because our model involves inﬁnite outcomes (allocations), the maximum
utilities and the minimum utilities may not be well-deﬁned. In order to avoid such technical diﬃculties,
as in Ortega and Segal-Halevi (2022), we employ the supremum and the inﬁmum operators. Note thatsuch a change of deﬁnition does not change the main results in this paper essentially. Indeed, even if we
employ the original deﬁnition of non-obvious manipulability in Troyan and Morrill (2020), with a minor
technical condition, the main results still hold.

10Given u ∈ U n and a pair of allocations z = (zi )i∈N = (xi , ti )i∈N ∈ Z and z ′ = (zi′ )i∈N =(x′i , t′i )i∈N ∈ Z, z Pareto dominates z ′ for u if (i) for each i ∈ N , ui (zi′ ) ≥ ui (zi ), (ii)
∑
∑
∑
∑
′
′
′
i∈N ti ≥i∈N ti , and (iii) for some i ∈ N , ui (zi ) > ui (zi ), ori∈N ti >i∈N ti .
The following property requires that a rule should select an allocation that is not Pareto
dominated by any other allocation.
Eﬃciency. For each u ∈ U n , there is no z ∈ Z that Pareto dominates f (u) for u.

The following property is a participation constraint, which requires that each agent
should ﬁnd his outcome bundle of a rule at least as desirable as (0, 0).
Individual rationality. For each u ∈ U n and each i ∈ N , ui (fi (u)) ≥ ui (0, 0).

Finally, the following property requires that the payment of each agent be non-negative.
No subsidy. For each u ∈ U n and each i ∈ N , tfi (u) ≥ 0.

The following fact is already known in the literature (Dobzinski et al., 2012; Kazumura
and Serizawa, 2016; Le, 2018; Baisa, 2020; Malik and Mishra, 2021, Kazumura, 2022;
Shinozaki et al., 2022).
Fact 1. (i) Let

∑

a∈M q

a

≥ 2. Let U ⊇ U IE . No rule on U n satisﬁes strategy-proofness,eﬃciency, individual rationality, and no subsidy.
(ii) Let U ⊇ U HB . No rule on U n satisﬁes strategy-proofness, eﬃciency, individual rationality, and no subsidy.
Fact 1 motivates us to give up one of the properties. In this paper, we relax strategyproofness to non-obvious manipulability, and search for a rule satisfying non-obvious manipulability, eﬃciency, individual rationality, and no subsidy.

4Main result

In this section, we give the main results of this paper.

11

4.1

Rich domain

In our main results, we require the following domain richness condition.
Deﬁnition 1. A domain U is rich if the following two conditions hold.
(i) For each α ∈ R++ , there is a quasi-linear utility function ui ∈ U ∩ U Q such that foreach pair xi , x′i ∈ X with xi > x′i , vi (xi ) − vi (x′i ) > α.
(ii) For each ε ∈ R++ , there is a quasi-linear utility function ui ∈ U ∩ U Q such that foreach xi ∈ X, vi (xi ) < ε.
The ﬁrst condition of richness states that a domain includes a quasi-linear utility function whose valuations are arbitrarily large. The second condition states that a domain
includes a quasi-linear utility function whose valuations are arbitrarily small.
Our domain richness condition is so mild that it covers almost all domains of interest.
For example, U , U Q , U SB , U HB , and U IE are all rich. Moreover, the class of all utility
functions that exhibit non-negative (or non-positive) income eﬀects, that satisfying thegross (or the net) substitutes condition (Kelso and Crawford,1982; Baldwin et al., 2023),
that satisfying the gross (or the net) complements condition (Rostek and Yoder, 2020;
Baldwin et al., 2023), that satisfying the single-intersection condition (Gul and Stacchetti,1999), any superset of one of the beforementioned domains, and any intersection or unionof the beforementioned domains are all rich. Note that our domain richness condition does
not cover the case of public budgets (Dobzinski et al., 2012; Lavi and May, 2012, etc.).

4.2

Necessary and suﬃcient condition

The ﬁrst main of this paper result gives a necessary and suﬃcient condition for a rule satisfying eﬃciency, individual rationality, and no subsidy to be non-obviously manipulable.
Theorem 1. Let U be a rich domain. A rule f on U n satisfying eﬃciency, individual
rationality, and no subsidy is non-obviously manipulable if and only if for each i ∈ N andeach ui ∈ U , supu−i ∈U n−1 ui (fi (ui , u−i )) = ui (q, 0).
To give a sketch of the proof of Theorem 1, we consider the worst case and the bestcase utilities from a report of a utility function under a rule satisfying eﬃciency, individual
rationality, and no subsidy. Fix an agent i ∈ N , his utility function ui , and a report u′i .
First, we consider the worst case utility of agent i from a report u′i . By richness, we canchoose quasi-linear utility functions of the other agents whose valuations are suﬃciently
12large compared with u′i . Then, eﬃciency implies that he receives no object (Lemma 3 inAppendix A.1), and the combination of individual rationality and no subsidy implies that
he makes the payment of zero (Lemma 1 in Appendix A.1). Thus, his utility is equal
to ui (0, 0). By individual rationality, this corresponds to the worst case utility from thereport u′i . Since u′i was arbitrary, any report gives the same worst case utility ui (0, 0), andthus he cannot improve the worst case utility by reporting a false utility function.
Then, we consider the best case utility from a report u′i . By richness, we can choose
a proﬁle of the other agents’ quasi-linear utility functions whose valuations are suﬃciently
small compared with u′i . Then, eﬃciency implies that he receives all the objects, i.e.,
receives q. By no subsidy, his payment is no smaller than 0. Thus, by money monotonicity
and object monotonicity, the best bundle among all the bundles that may be available toa rule (we call it the best bundle) is (q, 0). If the condition in Theorem 1 holds, then thebest case utility from the truth-telling is equivalent to the utility from the best bundle(q, 0), and so any report u′i cannot improve the best case utility from the truth-telling. In
contrast, if the condition does not hold, then the best case utility from the truth-telling issmaller than ui (q, 0), and by reporting a suﬃciently small u′i , the best case utility can be
improved from the truth-telling, i.e., a rule is obviously manipulable.

4.3

Modiﬁed pay as bid rule

Theorem 1 does not provide a closed-form characterization of the class of rules satisfying
non-obvious manipulability, eﬃciency, individual rationality, and no subsidy. Indeed, theclass of rules satisfying eﬃciency, individual rationality, and no subsidy is so broad that itis diﬃcult to obtain a tractable closed-form characterization of the class of rules satisfying
the four properties from Theorem 1. Thus, in this subsection, we instead present a speciﬁcrule that satisﬁes the four properties to show the existence of such a rule.
The design of our new rule satisfying the four properties relies on the two observations:
One is the properties of a truncated pay as bid rule that we will introduce shortly, and theother is derived from Theorem 1. Thus, we ﬁrst examine the properties of a truncated pay
as bid rule.
Given a utility function ui ∈ U and xi ∈ X, a truncated valuation of xi (at (0, 0))
for ui is deﬁned as ṽi (xi ) = min{Vi (xi , (0, 0)), bi }. A truncated valuation of xi reﬂects
the valuation Vi (xi , (0, 0)) of xi at (0, 0) and a budget bi , both of which constitute the13

important information of a utility function ui .
A truncated pay as bid rule is deﬁned as follows.
Deﬁnition 2. A rule f on U n is a truncated pay as bid rule if for each u ∈ U n ,xf (u) ∈ arg max
x∈X∑ṽi (xi ),i∈Nand for each i ∈ N ,tfi (u) = ṽi (xfi (u)).
The ﬁrst condition of the above deﬁnition says that the packages are assigned to theagents so as to maximize the sum of truncated valuations. The second one says that thepayment of each agent is his truncated valuation of a package that he obtains.
The next proposition reveals the desirable properties of a truncated pay as bid rule.
Notably, it satisﬁes eﬃciency. To the best of our knowledge, eﬃciency of a truncated pay
as bid rule in the presence of hard budget constraints is a new result. 6
Proposition 1. Let U ⊆ U . Any truncated pay as bid rule satisﬁes eﬃciency, individual
rationality, and no subsidy.
Troyan and Morrill (2020) show that a truncated pay as bid rule is obviously manipulable in a setting of identical objects (which corresponds to the case where a = 1) whenutility functions are quasi-linear. Although their setting is less general than ours, their argument carries over to any number of object types and any rich domain. Thus, we obtainthe following.
Fact 2. Let U be rich. Any truncated pay as bid rule is obviously manipulable.
Recall Theorem 1 shows that to ensure that the best case utility of each agent fromthe truth-telling is equal to the utility from the best bundle (q, 0) is a necessary andsuﬃcient condition for a rule satisfying eﬃciency, individual rationality, and no subsidy
to be non-obviously manipulable. Recall also Proposition 1 states that a truncated pay as
bid rule satisﬁes eﬃciency, individual rationality, and no subsidy. Thus, once we modify atruncated pay as bid rule so that the best case utility of each agent from the truth-tellingis equal to the utility from the best bundle (q, 0), such a rule is non-obviously manipulable.
6

Shinozaki et al. (2022) discuss that a truncated pay as bid rule satisﬁes the three properties if agents
do not face hard budget constraints, but say nothing about the case of hard budget constraints.

14

We need to modify a pay as bid rule carefully so that the above property holds without
damaging its nice eﬃciency property (and the other desirable properties as well). We
modify a truncated pay as bid rule as follows: If there is an agent who has suﬃciently
large truncated valuations and the valuations at (q, 0) compared with the other agents’
truncated valuations, then he receives (q, 0) and all the other agents do (0, 0) under a rule,and otherwise, an outcome allocation under a rule is equivalent to that under a truncatedpay as bid rule.
Deﬁnition 3. A rule f on U n is a modiﬁed (truncated) pay as bid rule if foreach u ∈ U n , if there is i ∈ N such that for each xi ∈ X\{0} and each x′i ∈ X\{q},min{ṽi (xi ), −Vi (x′i , (q, 0))} > (n−1) maxj∈N \{i} ṽj (q), then fi (u) = (q, 0) and fj (u) = (0, 0)
for each j ∈ N \{i}, and otherwise, f (u) is an outcome allocation of a truncated pay as
bid rule for u.
Note that the best case utility of each agent from the truth-telling under a modiﬁed pay
as bid rule is ui (q, 0). If an outcome allocation under a modiﬁed pay as bid rule coincides
with that under a truncated pay as bid rule, then it is eﬃcient by Proposition 1. If there isan agent who wins (q, 0) under an outcome allocation of a modiﬁed pay as bid rule, thenby the deﬁnition of the rule, he has so large valuations at (q, 0) compared with the otheragents’ truncated valuations that such an allocation will be eﬃcient. Thus, a modiﬁed pay
as bid rule will be eﬃcient. Also, individual rationality and no subsidy of a modiﬁed pay
as bid rule follow from Proposition 1.7 Thus, by Theorem 1, it also satisﬁes non-obvious
manipulability, and we obtain the following.
Theorem 2. Let U be a rich domain. Any modiﬁed pay as bid rule on U n satisﬁes nonobvious manipulability, eﬃciency, individual rationality, and no subsidy.

5

Discussion

In this section, we show the advantages of a modiﬁed pay as bid rule compared with otherstandard rules.

7

Note that for each i ∈ N , by money monotonicity and object monotonicity, ui (q, 0) > ui (0, 0).

15

5.1

Truncated Vickrey rule

First, we compare a modiﬁed pay as bid rule with a truncated Vickrey rule which extends
a Vickrey rule (Vickrey, 1961) for quasi-linear utility functions to our setting with income
eﬀects and hard budget constraints. A rule f on U n is a truncated Vickrey rule if foreach u ∈ U n ,xf (u) ∈ arg max
x∈X∑ṽi (xi ),i∈Nand for each i ∈ N ,tfi (u) = maxx∈X∑ṽj (xj ) −j∈N \{i}∑ṽj (xfj (u)).

j∈N \{i}It is well known that a Vickrey rules satisﬁes strategy-proofness, eﬃciency, individual
rationality, and no subsidy when utility functions are quasi-linear (Vickrey, 1961; Chew
and Serizawa, 2007). The next proposition states that in the presence of income eﬀects, any
truncated Vickrey rule violates eﬃciency, and in the presence of hard budget constraints,
it satisﬁes neither non-obvious manipulability nor eﬃciency.
Proposition 2. (i) Let

∑

a∈M q

a

≥ 2 and U = U IE . Any truncated Vickrey rule on U nsatisﬁes non-obvious manipulability, but violates eﬃciency.
∑(ii) Let U = U HB . If a∈M q a = 1, then any truncated Vickrey rule satisﬁes non-obvious∑
manipulability, but violates eﬃciency. If a∈M q a ≥ 2, then any truncated Vickrey rulesatisﬁes neither non-obvious manipulability nor eﬃciency.
Le (2018) gives an example which shows that a truncated Vickrey rule violates eﬃciency
in the presence of hard budget constraints. In the next example, we illustrate that atruncated Vickrey rule violates eﬃciency in the presence of income eﬀects but without
hard budget constraints.
Example 1. For simplicity, let n = 2, a = 1, and q = 2, but we can easily extend thefollowing discussion to a more general setting. Let f be a truncated Vickrey rule on (U IE )2 .
Let u1 ∈ U IE be such that V1 (1, (0, 0)) = 5, V1 (2, (0, 0)) = 6, and V1 (2, (1, 2)) = 5. Let
u2 ∈ U Q be such that for each x2 ∈ M , v2 (x2 ) = 2x2 . Then, by the deﬁnition of a truncatedVickrey rule, f1 (u) = (1, 2) and f2 (u) = (1, 1). Let z = (zi )i∈N = (xi , ti )i∈N ∈ Z be an
allocation such that z1 = (2, 5) and z2 = (0, −1). By V1 (2, (1, 2)) = 5, u1 (z1 ) = u1 (2, 5) =u1 (1, 2) = u1 (f1 (u)). By u2 ∈ U Q , u2 (z2 ) = u2 (0, −1) = 1 = v2 (1)−1 = u2 (f2 (u)). Further,16∑i∈N ti = 4 > 3 =∑fi∈N ti (u).

Thus, z Pareto dominates f (u) for u, and so f violateseﬃciency.
Note that in Proposition 2 (i), we consider the case of at least two objects. In thecase of a single object without hard budget constraints, a truncated Vickrey rule satisﬁes
strategy-proofness and eﬃciency (Saitoh and Serizawa, 2008; Sakai, 2008).
Theorem 2 and Proposition 2 together suggest that in the presence of income eﬀects,
a truncated pay as bid rule overcomes a truncated Vickrey rule in terms of eﬃciency, andin the presence of hard budget constraints, it does a truncated Vickrey rule in terms of
non-obvious manipulability and eﬃciency.
We omit the detail of the deﬁnition, but we can deﬁne a modiﬁed Vickrey rule in thesame way as a modiﬁed pay as bid rule. Then, we can show that a modiﬁed Vickrey rule isnon-obviously manipulable on any rich domain. However, it still violates eﬃciency. Indeed,in Example 1, we exhibit a utility proﬁle at which both agents 1 and 2 win an objec, andan outcome allocation of a truncated Vickrey rule is not eﬃcient. For such a utility proﬁle,a modiﬁed Vickrey rule produces the same outcome allocation as a truncated Vickrey
rule since several agents objects, and so a modiﬁed Vickrey rule violates eﬃciency. Thus, a
modiﬁed pay as bid rule outperforms a modiﬁed Vickrey rule in terms of eﬃciency. We notethat because it is diﬃcult to identify the set of utility proﬁles at which a truncated Vickrey
rule violates eﬃciency, it is unclear how we can achieve both non-obvious manipulability
and eﬃciency by modifying a truncated Vickrey rule in some way.

5.2

Warlasian rule

Warlasian rules, also known as uniform-price rules in a setting of identical objects (i.e.,a = 1), are also salient rules in the literature (Kelso and Crawford, 1982; Gul and Stacchetti, 1999; Rostek and Yoder, 2020; Baldwin et al., 2023, etc.). Given u ∈ U n , anallocation (zi )i∈N = (xi , ti )i∈N ∈ Z is a Warlasian equilibrium allocation for u if there′
is a price vector p ∈ Rm
+ such that for each i ∈ N , ti = p · xi , and for each xi ∈ X,

ui (zi ) ≥ ui (x′i , p · x′i ).8 A rule f on U n is a Warlasian rule if for each u ∈ U n , f (u) is a
Warlasian equilibrium allocation for u.
By the ﬁrst welfare theorem, any Warlasian rule is eﬃcient. Further, any Warlasian
rule satisﬁes individual rationality and no subsidy. However, not all Warlasian rules satisfy
8Given a pair x, y ∈ Rm , x · y is an inner produce ot x and y, i.e., x · y =

17

∑

a a
a∈M x y .

non-obvious manipulability. For example, a pay as bid rule in a single object setting (aﬁrst-price rule) is a Warlasian rule, but is obviously manipulable (Fact 2). The next
proposition states that there is a Warlasian rule satisfying non-obvious manipulability on
a rich domain where there always exists a Warlasian equilibrium allocation.
Proposition 3. Let U be a rich domain such that for each u ∈ U n , there is a Warlasianequilibrium allocation for u. There is a Warlasian rule on U that is non-obviously manipulable.
Thus, in terms of non-obvious manipulability, eﬃciency, individual rationality, andno subsidy, a Warlasian rule is as desirable as a modiﬁed pay as bid rule. However, one
drawback of a Warlasian rule is that the existence of a Warlasian equilibrium allocation
is not necessarily guaranteed, and thus a Warlasian rule may not be well-deﬁned. Indeed,even for quasi-linear utility functions, the existence of a Warlasian equilibrium allocation
is no longer guaranteed once a utility function in the domain violates the gross ( or thenet) substitutes condition (Gul and Stacchetti, 1999; Baldwin et al., 2023). Clearly, bothincome eﬀects and hard budget constraints further complicate the existence of a Warlasianequilibrium allocation. An advantage of a modiﬁed pay as bid rule compared with a
Warlasian rule is its broad application range. Indeed, it can be applied to any rich domainthat may not guarantee the existence of a Warlasian equilibrium allocation.

6

Conclusion

In this paper, in response to recent impossibility results for strategy-proofness, eﬃciency,
individual rationality, and no subsidy for agents with income eﬀects or hard budget constraints, we have relaxed strategy-proofness to non-obvious manipulability, and studied its
implications. As a result, we derived a necessary and suﬃcient condition for a rule satisfying eﬃciency, individual rationality, and no subsidy to be non-obviously manipulable(Theorem 1), and showed that a modiﬁed pay as bid rule satisﬁes non-obvious manipulability, eﬃciency, individual rationality, and no subsidy (Theorem 2).
We conclude this paper by giving a comment on future research. Recall that we discussed in Section 1 that strategy-proofness may be unnecessarily demanding as it requires
all proﬁtable manipulations be prohibited. Recall also that non-obvious manipulability is
motivated by an observation that real-life agents often lack the ability to engage in contin18

gent reasoning or do not have the access to the information of the other agents’ utilities.
Such a situation is plausible if a package auction that involves many objects is conducted
via a one-shot sealed-bid format, or the planner does not reveal the detail of the information of the rival bidders. However, practical auctions often involve only a few objects andare conducted via simple open format with the known rival bidders. Then, to study an“intermediate” incentive property between strategy-proofness and non-obvious manipulations would be an interesting direction of future research. The results and insights derived
in this paper will be helpful.

AppendixA

Proof of Theorem 1

In this section, we provide the proof of Theorem 1. Let f be a rule on U n satisfying
eﬃciency, individual rationality, and no subsidy.

A.1

The “if” partWe show the “if” part. We begin with the following three lemmas. First, the next lemmashows that if an agent receives no object, then his payment is equal to zero.
Lemma 1. Let u ∈ U n and i ∈ N . If xfi (u) = 0, then tfi (u) = 0.
Proof. Suppose xfi (u) = 0. By individual rationality, ui (0, tfi (u)) = ui (fi (u)) ≥ ui (0, 0).
Thus, by money monotonicity, tfi (u) ≤ 0. Thus, by no subsidy, we get tfi (u) = 0.
Given ui ∈ U and xi ∈ X\{0}, let h(·; ui , xi ) be a function from [0, bi ] to R such thatfor each ti ∈ [0, bi ], hi (ti ; ui , xi ) = ti − Vi (0, (xi , ti )).9
Lemma 2. Let ui ∈ U and xi ∈ X\{0}. Then, supti ∈[0,bi ] hi (ti , ui , xi ) < ∞.
Proof. By continuity of ui , hi (·; ui , xi ) is a continuous function on [0, bi ]. Since [0, bi ]is compact, hi ([0, bi ]; ui , xi ) is also compact. Thus, hi ([0, bi ]; ui , xi ) is bounded, and so
supti ∈[0,bi ] hi (ti ; ui , xi ) < ∞.
Note that by xi ≥ 0 and ti ≤ bi , object monotonicity and money monotonicity together imply
ui (xi , ti ) ≥ ui (0, bi ). Thus, Vi (0, (xi , ti )) < ∞.
919The next lemma states that given a utility function of an agent, there are utility functions of the other agents such that he receives no object.
Lemma 3. Let i ∈ N and ui ∈ U . There is u−i ∈ U n−1 such that xfi (ui , u−i ) = 0.
Proof. Let j ∈ N \{i}. By Lemma 2 and richness, we can choose uj ∈ U ∩ U Q such thatfor each xi ∈ X\{0} and each pair xj , x′j ∈ X with xj > x′j ,vj (xj ) − vj (x′j ) >sup hi (ti , ui , xi ).

(1)

ti ∈[0,bi ]For each k ∈ N \{i, j}, let uk = uj . We show xfi (u) = 0. By contradiction, supposexfi (u) ̸= 0. By individual rationality, tfi (u) ≤ bi . By no subsidy, tfi (u) ≥ 0. Thus, we havetfi (u) ∈ [0, bi ]. By (1) and xfi (u) ̸= 0,
vj (xfj (u) + xfi (u)) − vj (xfj (u)) > tfi (u) − Vi (0, fi (R)).

(2)

Let z = (zk )k∈N = (xk , tk )k∈N ∈ Z be an allocation such that zi = (0, Vi (0, fi (u))), zj =(xfj (u)+xfi (u), tfj (u)+vj (xfj (u)+xfi (u))−vj (xfj (u))), and for each k ∈ N \{i, j}, zk = fk (u).
Then, ui (zi ) = ui (fi (u)). We have uj (zj ) = vj (xfj (u)) − tfj (u) = uj (fj (u)). We also have∑(tk − tfk (u)) = Vi (0, fi (u)) − tfi (u) + vj (xfj (u) + xfi (u)) − vj (xfj (u)) > 0,k∈N

where the inequality follows from (2). Thus, z Pareto dominates f (u) for u, a contradiction
to eﬃciency.
We move on to the proof of the “if” part. Suppose that for each i ∈ N and each ui ∈ U ,we havesupu−i ∈U n−1

ui (fi (ui , u−i )) = ui (q, 0).

(3)

Let i ∈ N and ui , u′i ∈ U . For each u−i ∈ U n−1 , by no subsidy, fi (u′i , u−i ) ∈ X × R+ ,and so by money monotonicity and object monotonicity, ui (q, 0) ≥ ui (fi (u′i , u−i )). Combining this with (3), we get
supu−i∈U n−1ui (fi (ui , u−i )) = ui (q, 0) ≥

sup
u−i

∈U n−1ui (fi (u′i , u−i )).

By Lemma 3, there is u−i ∈ U n−1 such that xfi (u′i , u−i ) = 0. By Lemma 1, fi (u′i , u−i ) =20

(0, 0). Thus, by individual rationality,infu′−i ∈U n−1

ui (fi (ui , u′−i )) ≥ ui (0, 0) = ui (fi (u′i , u−i )).

(4)

Also, by individual rationality and fi (u′i , u−i ) = (0, 0),infu′−i ∈U n−1

ui (fi (u′i , u′−i )) = ui (0, 0) = ui (fi (u′i , u−i )).

(5)

Combining (4) and (5), we getinfu′−i ∈U n−1

ui (fi (ui , u′−i )) ≥inf

u′−i ∈U n−1

ui (fi (u′i , u′−i )),■as desired.

A.2

The “only if” part

Next, we show the “only if” part. We show the contrapositive. Suppose that for somei ∈ N and some ui ∈ U , we have supu−i ∈U n−1 ui (fi (ui , u−i )) ̸= ui (q, 0). By no subsidy, foreach u−i ∈ U n−1 , fi (ui , u−i ) ∈ X × R+ , and so ui (fi (ui , u−i )) ≤ ui (q, 0). Thus, we havesupu−i ∈U n−1 ui (fi (ui , u−i )) < ui (q, 0). By continuity of ui , there is ε ∈ R++ suﬃciently close
to zero such thatsupu−i ∈U n−1

ui (fi (ui , u−i )) < ui (q, ε).

By richness, there is u′i ∈ U ∩ U Q such that vi′ (q) < ε. Let j ∈ N \{i}. By richness
and object monotonicity of u′i , there is uj ∈ U ∩ U Q such that for each pair xi , x′i ∈ Xwith xi > x′i , vj (q) < vi′ (xi ) − vi′ (x′i ). For each k ∈ N \{i, j}, let uk = uj . By eﬃciency,xi (u′i , u−i ) = q. By individual rationality, tfi (u′i , u−i ) ≤ vi′ (q) < ε. Thus,
supu′−i ∈U n−1

ui (fi (ui , u′−i )) < ui (q, ε) < ui (fi (u′i , u−i )) ≤supu′−i ∈U n−1

ui (fi (u′i , u′−i )).
■Thus, f is obviously manipulable.

21

B

Proof of Proposition 1

Let f be a truncated pay as bid rule on U n . Note that no subsidy follows from the deﬁnition of the rule. Thus, we show the other two properties.

Individual rationality.

Let u ∈ U n and i ∈ N .

Suppose ui (0, 0) ≥ ui (xfi (u), bi ).

Then, by the deﬁnition of the valuation, we have ui (xfi (u), Vi (xfi (u), (0, 0))) = ui (0, 0). By
tfi (u) = min{Vi (xfi (u), (0, 0)), bi } ≤ Vi (xfi (u), (0, 0)), ui (fi (u)) ≥ ui (xfi (u), Vi (xfi (u), (0, 0))).
Combining these, we get ui (fi (u)) ≥ ui (0, 0). Suppose instead ui (xfi (u), bi ) > ui (0, 0), thenVi (xfi (u), (0, 0)) = ∞. Thus, we have tfi (u) = min{Vi (xfi (u), (0, 0)), bi } = bi . Thus, we getui (fi (u)) = ui (xfi (u), bi ) > ui (0, 0).
Efficiency. Let u ∈ U n . Let z = (zi )i∈N = (xi , ti )i∈N ∈ Z be an allocation such that foreach i ∈ N , ui (zi ) ≥ ui (fi (u)). To show that z does not Pareto dominate f (u) for u, we∑∑fneed to show that i∈N ti ≤i∈N ti (u). The proof consists of several claims.
Claim 1. For each i ∈ N , ti ≤ Vi (xi , fi (R)).
Proof. Let i ∈ N . Suppose ui (fi (u)) ≥ ui (xi , bi ). By the deﬁnition of the valuation, we
have ui (fi (u)) = ui (xi , Vi (xi , fi (u))). Thus, by ui (zi ) ≥ ui (fi (u)), ui (zi ) ≥ ui (xi , Vi (xi , fi (u))).
By money monotonicity, this implies that ti ≤ Vi (xi , fi (u)). Suppose instead ui (fi (u)) < ui (xi , bi ).
Then, Vi (xi , fi (u)) = ∞, and so ti < Vi (xi , fi (u)).
Claim 2. For each i ∈ N , ti ≤ bi .
Proof. Let i ∈ N . Recall ui (zi ) ≥ ui (fi (u)). By individual rationality, ui (fi (u)) ≥ ui (0, 0).
By bi > 0, ui (0, 0) > − ∞. Combining these, we get ui (zi ) > − ∞. Thus, ti ≤ bi .
Claim 3. For each i ∈ N , Vi (xi , fi (R)) ≤ Vi (xi , (0, 0)).
Proof. Let i ∈ N . Suppose ui (0, 0) ≥ ui (xi , bi ). By individual rationality, ui (fi (u)) ≥ ui (0, 0).
Combining these, we get ui (fi (u)) ≥ ui (xi , bi ). Thus, by the deﬁnition of valuation, we haveui (0, 0) = ui (xi , Vi (xi , (0, 0))) and ui (fi (u)) = ui (xi , Vi (xi , fi (u))). Thus, by individual rationality,ui (xi , Vi (xi , fi (u))) = ui (fi (u)) ≥ ui (0, 0) = ui (xi , Vi (xi , (0, 0))).

22

Thus, by money monotonicity, Vi (xi , fi (R)) ≤ Vi (xi , (0, 0)). Suppose instead ui (0, 0) < ui (xi , bi ).
Then, Vi (xi , (0, 0)) = ∞, and so Vi (xi , fi (R)) ≤ Vi (xi , (0, 0)).
Claim 4. For each i ∈ N , ti ≤ ṽi (xi ).
Proof. Let i ∈ N . We have{}{}ti ≤ min Vi (xi , fi (u)), bi ≤ min Vi (xi , (0, 0)), bi = ṽi (xi ),where the ﬁrst inequality follows from Claims 1 and 2, and the second one from Claim 3.
Now, we complete the proof. We have
∑
i∈N

ti ≤

∑

ṽi (xi ) ≤i∈N∑ṽi (xfi (u)) =

i∈N

∑ f
ti (u),
i∈N

where the ﬁrst inequality follows from Claim 4, the second one from the deﬁnition of an
object allocation rule, and the equality from the deﬁnition of a payment rule. Thus, we∑∑f■
get i∈N ti ≤i∈N ti (u), and so z does not Pareto dominate f (u) for u.

C

Proof of Theorem 2

Let f be a modiﬁed pay as bid rule on U n . Note that no subsidy follows from the deﬁnitionof the rule. Thus, we show that f satisﬁes the other three properties.
Efficiency. Let u ∈ U n . By Proposition 1, if f (u) is an outcome allocation of a truncatedpay as bid rule for u, then f (u) is eﬃcient for u. Suppose that there is i ∈ N such thatfi (u) = (q, 0), and for each j ∈ N \{i}, fj (u) = (0, 0). By the deﬁnition of the rule, foreach xi ∈ X\{q}−Vi (xi , (q, 0)) > (n − 1) max ṽj (q).
j∈N \{i}(1)

Let z = (zj )j∈N = (xj , tj )j∈N ∈ Z be an allocation such that for each j ∈ N , uj (zj ) ≥ uj (fj (u)).
∑∑
To show that z does not Pareto dominate f (u) for u, we show that j∈N tfj (u) ≥j∈N tj .
By object monotonicity and bi ∈ R++ , ui (q, 0) > ui (xi , bi ). Then,ui (zi ) ≥ ui (fi (u)) = ui (q, 0) = ui (xi , Vi (xi , (q, 0))),23

where the last equality follows from ui (q, 0) > ui (xi , bi ) and the deﬁnition of the valuation.
Thus, by money monotonicity,ti ≤ Vi (xi , (q, 0)).

(2)

For each j ∈ N \{i}, uj (zj ) ≥ uj (fj (u)) = uj (0, 0), which implies
tj ≤ ṽj (xj ).
Then, by (2) and (3),∑tj ≤ Vi (xi , (q, 0)) +(3)∑ṽj (xj ).

(4)j∈N \{i}j∈N

If xi = q, then for each j ∈ N \{i}, xj = 0, and so ṽj (xj ) = 0. Thus,∑tj ≤ Vi (q, (q, 0)) = 0 ≤

j∈N

∑ f
tj (u),
j∈N

where the ﬁrst inequality follows from (4), and the last inequality from no subsidy. If
xi ̸= q, then∑tj ≤ Vi (xi , (q, 0)) + (n − 1) max ṽj (q) < 0 ≤j∈N \{i}j∈N∑ ftj (u),
j∈N

where the ﬁrst inequality follows from (4) and object monotonicity, the second one from∑∑f(1), and the last one from no subsidy. Thus, in either case, j∈N tj ≤j∈N tj (u), andso z does not Pareto dominate f (u) for u.
Individual rationality. Let u ∈ U n and i ∈ N . If fi (u) is an outcome bundle of agent
i for u under a truncated pay as bid rule, then by Proposition 1, ui (fi (u)) ≥ ui (0, 0). Otherwise, by the deﬁnition of the rule, fi (u) ∈ {(q, 0), (0, 0)}. Thus, ui (fi (u)) ≥ ui (0, 0).
Non-obvious manipulability. Let i ∈ N and ui ∈ U . By object monotonicity andbi ∈ R++ , for each xi ∈ X\{0}, ṽi (xi ) > 0. Let xi ∈ X\{q}. Again, by object monotonicity and bi ∈ R++ , ui (q, 0) > ui (xi , bi ). Thus, by the deﬁnition of the valuation and object
monotonicity,ui (xi , Vi (xi , (q, 0))) = ui (q, 0) > ui (xi , 0).

24

Thus, by money monotonicity, Vi (xi , (q, 0)) < 0, or equivalently, −Vi (xi , (q, 0)) > 0. Thus,by richness, there is u−i ∈ (U ∩ U Q )n−1 such that for each xi ∈ X\{0} and each x′i ∈ X\{q},(n − 1) maxj∈N \{i} ṽj (q) < min{ṽi (xi ), −Vi (x′i , (q, 0))}. Thus, by the deﬁnition of the rule,fi (u) = (q, 0). Note that by no subsidy, for each u′−i ∈ U n−1 , fi (ui , u′−i ) ∈ X × R+ . Thus,by money monotonicity and object monotonicity,
supu′−i ∈U n−1

ui (fi (ui , u′−i )) = ui (fi (u)) = ui (q, 0).

Note that we have already shown that f satisﬁes eﬃciency, individual rationality, and no
subsidy. Thus, by Theorem 1, f is non-obviously manipulable.

D■

Proof of Proposition 2

In this section, we prove Proposition 2.

D.1

Proposition 2 (i)Let f be a truncated Vickrey rule on (U IE )n . We have already shown in Example 1 that it
violates eﬃciency. Thus, we show that it is non-obviously manipulable. Since the proof issimilar to that of the “if” part of Theorem 1, we only give an informal sketch of the proof.
Let i ∈ N and ui ∈ U IE . Then, we can choose u−i ∈ (U IE )n−1 whose valuations of q at
(0, 0) are arbitrarily small. Thus, by the deﬁnition of a truncated Vickrey rule, the bestcase utility from the truth-telling is ui (q, 0), and so applying the same discussion as the “if”
part of Theorem 1, we can conclude that agent i cannot improve the best case utility byreporting a false utility function. Also, for each u′i ∈ U IE , we can choose u′−i ∈ (U IE )n−1
whose valuations at (0, 0) are so large compared with u′i that fi (u′i , u′−i ) = (0, 0). It is
straightforward to verify that a truncated Vickrey rule on any domain U satisﬁes individual
rationality and no subsidy. Thus, as in the proof of the “if” part of Theorem 1, we can showthat the worst case utility from any report u′i is ui (0, 0), and so agent i cannot improve
the worst case utility by misreporting his utility function.

25

■

D.2

Proposition 2 (ii)

Le (2018) provides an example which shows that a truncated Vickrey rule on (U HB ) vi∑
olates eﬃciency. Thus, we here show that if a∈M q a = 1, then any truncated Vickrey∑
rule on (U HB )n is non-obviously manipulable, while if a∈M q a ≥ 2, then it is obviously
manipulable. Let f be a truncated Vickrey rule on (U HB ).
∑Suppose a∈M q a = 1. Let i ∈ N and ui ∈ U HB . By object monotonicity and bi ∈ R++ ,ṽi (1) > 0. Thus, we can choose u−i ∈ (U HB )n−1 such that maxj∈N \{i} ṽj (1) < ṽi (1), andmaxj∈N \{i} ṽj (1) can be arbitrarily small. Thus, the best case utility of agent i from thetruth-telling is ui (1, 0), and so he cannot improve the best case utility by misrepresenting
his utility function. Also, by the same discussion as in the proof of Proposition 2 (i), hecannot improve the worst case utility from the truth-telling by misrepresenting his utility
function. Thus, f is non-obviously manipulable.
∑
Next, suppose a∈M q a ≥ 2. For simplicity, let n = 2, a = 1, and q = 2, but thefollowing discussion extends to a more general setting. Let u1 ∈ U HB be such that v1 (1) =1, v1 (2) = 2, and b1 = 1. Then, ṽ1 (2) = ṽ1 (1) = 1. Then, for each u2 ∈ U HB , by ṽ2 (1) > 0,
xf1 (u1 , u2 ) ≤ 1. Thus, supu2 ∈U u1 (f1 (u1 , u2 )) = u1 (1, 0) = 1. Let u′1 ∈ U HB be such thatv1′ (1) = 1, v1′ (2) = 2, and b′1 = ∞. Then, supu2 ∈U u1 (f1 (u′1 , u2 )) = u1 (2, 0) = 2. Thus,
sup u1 (f1 (u′1 , u2 )) = 2 > 1 = sup u1 (f1 (u1 , u2 )).

u2 ∈U

u2 ∈U

■

Thus, f is non-obviously manipulable.

E

Proof of Proposition 3

In this section, we prove Proposition 3. Given u ∈ U n and i ∈ N , let Q =

∑

a∈M q

a

and

Ṽ−i = maxj∈N \{i} ṽj (q).
First, we show that if for each xi ∈ X\{0}, ṽi (xi ) > QṼ−i , and for each xi ∈ X\{q},Vi (xi , (q, QṼ−i )) < 0, then an allocation z = (zj )j∈N ∈ Z such that zi = (q, QṼ−i ), and foreach j ∈ N \{i}, zj = (0, 0) is a Warlasian equilibrium allocation for u. Let p ∈ Rm
+ be aprice vector such that pa = Ṽ−i for each a ∈ M . Then, p · q = QṼ−i . For each xi ∈ X\{q},by Vi (xi , (q, QṼ−i )) < 0 ≤ p · xi , we have ui (q, p · q) = ui (q, QṼ−i ) > ui (xi , p · xi ). For∑
each j ∈ N \{i} and each xj ∈ X\{0}, by ṽj (xj ) ≤ Ṽ−i ≤ ( a∈M q a )Ṽ−i = p · xj , we have26

uj (0, 0) ≥ uj (xj , p · xj ). Thus, z is a Warlasian equilibrium allocation for u.
Then, we construct a Warlasian rule that will satisfy non-obvious manipulability. Let f
be a rule on U n such that for each u ∈ U n , if there is i ∈ N such that for each xi ∈ X\{0},ṽi (xi ) > QṼ−i , and for each xi ∈ X\{q}, Vi (xi , (q, QṼ−i )) < 0, then fi (u) = (q, QṼ−i ) andfor each j ∈ N \{i}, fj (u) = (0, 0), and otherwise, f (u) is a Warlasian equilibrium allocation for u. Note that by the assumption that for each u ∈ U n , there is a Warlasianequilibrium allocation for u, the rule f is well-deﬁned. Further, by the discussion in theprevious paragraph, f is a Warlasian rule.
We ﬁnally show that f is non-obviously manipulable. Let i ∈ N and ui ∈ U . Note that
any Warlasian rule satisﬁes no subsidy, and so does f . Thus, for each u−i ∈ U n−1 , by no
subsidy of f , fi (ui , u−i ) ∈ X × R+ . Thus, by money monotonicity and object monotonicity, for each u−i ∈ U n−1 , ui (fi (ui , u−i )) ≤ ui (q, 0). Let ε ∈ R++ . Note that by object monotonicity of ui and bi ∈ R++ , for each xi ∈ X\{q}, Vi (xi , (q, 0)) < 0. Thus, by continuity ofui and bi ∈ R++ , we can choose δ ∈ R++ suﬃciently close to 0 such that δ < bi , ui (q, δ) +ε > ui (q, 0), and for each xi ∈ X\{q}, Vi (xi , (q, δ)) < 0. Again, by object monotonicity andbi ∈ R++ , for each xi ∈ X\{0}, ṽi (xi ) > 0. Thus, by richness, there is u−i ∈ U n−1 suchthat for each xi ∈ X\{0}, QṼ−i < min{δ, ṽi (xi )}. For each xi ∈ X\{q}, by QṼ−i < δ < bi ,ui (q, QṼ−i ) > ui (q, δ) > ui (xi , bi ), which implies Vi (xi , (q, QṼ−i )) < Vi (xi , (q, δ)) < 0. Thus,by the deﬁnition of the rule, fi (u) = (q, QṼ−i ). By QṼ−i < δ and ui (q, δ) + ε > ui (q, 0),ui (fi (u)) + ε > ui (q, δ) + ε > ui (q, 0). Since ε ∈ R++ was arbitrary, we havesupu−i ∈U n−1

ui (fi (ui , u−i )) = ui (q, 0).

Since any Warlasian rule satisﬁes eﬃciency, individual rationality, and no subsidy, so does
f . Thus, by Theorem 1, f is non-obviously manipulable.

■

References[1] Ausubel, L. M. (2004), “An eﬃcient ascending-bid auction for multiple objects.”
American Economic Review , 94(5): 1452–1475.
[2] Archbold, T., B. de Keijzer, and C. Ventre (2023a), “Non-obvious manipulability forsingle-parameter agents and bilateral trade.” In: Proceedings of the 22nd International

27

Conference on Autonomous Agents and Multiagent Systems (AAMAS2023).
[3] Archbold, T., B. de Keijzer, and C. Ventre (2023b), “Non-obvious manipulability
in extensive-form mechanisms: The revelation principle for single-parameter agents.”
In: Proceedings of the 32nd International Joint Conference on Artiﬁcial Intelligence(IJCAI-23).
[4] Arribillaga, R. P. and A. G. Bonifacio (2024), “Obvious manipulations of tops-onlyvoting rules.” Games and Economic Behavior , 143: 12–24.
[5] Arribillaga, R. P. and E. Risma (2023), “Obvious manipulations in matching with andwithout contracts.” Working paper.
[6] Aziz, H. and A. Lam (2021), “Obvious manipulability of voting rules.” In: Fotakis,
D. and D. Riós Insua (eds), Algorithmic Decision Theory: 179–193, Springer, Cham.
[7] Baisa, B. (2017), “Auction design without quasilinear preferences.” Theoretical Economics, 12(1): 53–78.
[8] Baisa, B. (2018), “A detail-free and eﬃcient auction for budget constrained bidders.”
Working paper.
[9] Baisa, B. (2020), “Eﬃcient multi-unit auctions for normal goods.” Theoretical Economics, 15(1): 361–413.
[10] Baisa, B. and S. Essig Aberg (2021), “Quantifying the ineﬃciency of multi-unit auctions for normal goods.” Working paper.
[11] Baldwin, E., O. Edhan, R. Jagadeesan, P. Klemperer, and A. Teytelboym (2023), “Theequilibrium existence duality: Equilibrium with indivisibilities and income eﬀects.”
Journal of Political Economy, 131(6): 1440–1476.
[12] Bulow, J., J. Levin, and P. Milgrom (2017), “Winning play in spectrum auctions.” In:
Bichler, M. and J. K. Goeree (eds), Handbook of spectrum auction design, Chapter
31, pp. 689–712, Cambridge University Press.
[13] Chew, S. H. and S. Serizawa (2007), “Characterizing the Vickrey combinatorial auction
by induction.” Economic Theory, 33(2): 393–406.

28

[14] Demange, G. and D. Gale (1985), “The strategy structure of two-sided matchingmarkets.” Econometrica, 53(4): 873–888.
[15] Dobzinski, S., R. Lavi, and N. Nisan (2012), “Multi-unit auctions with budget limits.”
Games and Economic Behavior , 74(2): 486–503.
[16] Gul, F. and E. Stacchetti (1999), “Warlasian equilibrium with gross substitutes.”
Journal of Economic Theory, 87(1): 95–124.
[17] Hafalir, I. E., R. Ravi, and A. Sayedi (2012), “A near Pareto optimal auction withbudget constraints.” Games and Economic Behavior , 74(2): 699–708.
[18] Holmström, B. (1979), “Groves’ scheme on restricted domains.” Econometrica, 47(5):1137–1144.
[19] Kazumura, T. (2022), “When can we design eﬃcient and strategy-proof rules in package assignment problems?” Kyoto University, Graduate School of Economics Discussion Paper Series No. E-21-008.
[20] Kazumura, T. and S. Serizawa (2016), “Eﬃciency and strategy-proofness in object
assignment problems with multi-demand preferences.” Social Choice and Welfare,47(3): 633–663.
[21] Kelso, A. S. and V. P. Crawford (1982), “Job matching, coalition formation, and grosssubstitutes.” Econometrica, 50(6): 1483–1504.
[22] Lavi, R. and M. May (2012), “A note on the incompatibility of strategy-proofness andPareto-optimality in quasi-linear settings with public budgets.”[23] Le, P. (2018), “Pareto optimal budgeted combinatorial auctions.” Theoretical Economics, 13(2): 831–868.
[24] Li, S. (2017), “Obviously strategy-proof mechanisms.” American Economic Review ,107(11): 3257–3287.
[25] Malik, K. and D. Mishra (2021), “Pareto eﬃcient combinatorial auctions: Dichotomous preferences without quasilinearity.” Journal of Economic Theory, 191: 105128.

29

[26] Morimoto, S. and S. Serizawa (2015), “Strategy-proofness and eﬃciency with nonquasi-linear preferences: A characterization of minimum price Warlasian rule.” Theoretical Economics, 10(2): 445–487.
[27] Ortega, J. and E. Segal-Halevi (2022), “Obvious manipulations in cake-cutting.” Social
Choice and Welfare, 59: 969–988.
[28] Psomas, A. and P. Verma (2022), “Fair and eﬃcient allocations without obvious manipulations.” Working paper.
[29] Rostek, M. and N. Yoder (2020), “Matching with complementary contracts.” Econometrica, 88(5): 1793–1827.
[30] Saitoh, H. and S. Serizawa (2008), “Vickrey allocation rule with income eﬀect.” Economic Theory, 35(2): 391–401.
[31] Sakai, T. (2008), “Second price auctions on general preference domains: Two characterizations.” Economic Theory, 37(2): 347–356.
[32] Shinozaki, H. (2023), “Eﬃciency and strategy-proofness in multi-unit object allocation
problems with non-quasi-linear preferences.” Economics Letters, 223: 110989.
[33] Shinozaki, H., T. Kazumura, and S. Serizawa (2022), “Multi-unit object allocation
problems with money for (non)decreasing incremental willingness to pay: Impossibility
and characterization theorems.” ISER Discussion paper No. 1097.
[34] Troyan, P. (2022), “Non-obvious manipulability of the rank-minimizing mechanism.”
Working paper.
[35] Troyan, P. and T. Morrill (2020), “Obvious manipulations.” Journal of Economic
Theory, 185: 104970.
[36] Vickrey, W. (1961), “Counterspeculation, auctions, and competitive sealed tenders.”
Journal of Finance, 16(1): 8–37.

30