Efficiency and strategy-proofness in object assignment problems with multi-demand preferences

Tomoya Kazumura¹ &
Shigehiro Serizawa²

2808 Accesses
15 Citations
Explore all metrics

Abstract

We consider the problem of allocating sets of objects to agents and collecting payments. Each agent has a preference relation over the set of pairs consisting of a set of objects and a payment. Preferences are not necessarily quasi-linear. Non-quasi-linear preferences describe environments where the wealth effect is non-negligible: the payment level changes agents’ willingness to pay for swapping sets. We investigate the existence of efficient and strategy-proof rules. A preference relation is unit-demand if given a payment level, for each set of objects, the most preferred one in the set is at least as good as the set itself; it is multi-demand if given a payment level, when an agent receives an object, receiving some additional object(s) makes him better off. We show that if a domain contains enough variety of unit-demand preferences and at least one multi-demand preference relation, and if there are more agents than objects, then no rule satisfies efficiency, strategy-proofness, individual rationality, and no subsidy for losers on the domain.

Strategy-proof mechanism design with non-quasi-linear preferences: ex-post revenue maximization for an arbitrary number of objects

Article Open access 04 June 2021

Overlapping multiple object assignments

Article 26 February 2016

Optimal multi-unit allocation with costly verification

Article 05 May 2023

Use our pre-submission checklist

Avoid common mistakes on your manuscript.

1 Introduction

We consider an object assignment problem with money. Each agent receives a (possibly empty) set of objects and, possibly, pays money for the set. He has a preference relation over the set of pairs consisting of a set of objects and a payment. An allocation specifies how the objects are allocated and how much each agent pays. An (allocation) rule is a mapping from a class of admissible preference profiles, which we call a “domain,” to the set of allocations. An allocation is efficient if, without reducing the total payment, no other allocation makes all agents at least as well off and at least one agent better off. A rule is efficient if it always selects an efficient allocation. A rule is strategy-proof if, for each agent, it is a weakly dominant strategy to report his true preferences. We investigate the existence of efficient and strategy-proof rules.

Our model can be viewed as a multi-object auction model. Much of the literature on auction theory assumes preferences to be “quasi-linear.” This means that the valuations over sets of objects are not affected by payment level. On the quasi-linear domain, the so-called “VCG rules” (Vickrey 1961; Clarke 1971; Groves 1973) are efficient and strategy-proof, and they are the only rules satisfying these properties (Holmström 1979).

As Marshall (1920) demonstrates, preferences are approximately quasi-linear if payments are sufficiently low. However, in important applications of auction theory such as spectrum license allocation, house allocation, etc., prices are often equal to or exceed agents’ annual revenues. Excessive payments for objects may impair an agent’s ability to purchase complements for an effective use of the objects, and thus may influence the benefit the agent derives from the objects. Another reason why preferences may not be quasi-linear is that an agent may need a loan to be able to pay high prices, and typically financial costs are nonlinear in borrowing.^{Footnote 1} $^{\text {,}}$ ^{Footnote 2}

Another common assumption is the “unit-demand” property.^{Footnote 3} It says that given a payment level, for each set of objects, the most preferred one in the set is at least as good as the set itself. For unit-demand preferences, there exists the minimum Walrasian equilibrium price, which is lower than any other Walrasian equilibrium price. Thus, on the “unit-demand domain,” minimum price Walrasian (MPW) rules are well-defined. A minimum price Walrasian (MPW) rule always selects an allocation associated with the minimum price Walrasian equilibria for each preference profile. The MPW rules are strategy-proof on the unit-demand domain (Demange and Gale 1985). It is straightforward to see that the MPW rules satisfy the following additional two properties: One is individual rationality, which says that each agent finds his assignment at least as desirable as getting no object and paying nothing. The other is no subsidy for losers, which says that the payment of an agent who receives no object is nonnegative. On the unit-demand domain, when there are more agents than objects, the MPW rules are the only rules satisfying efficiency, strategy-proofness, individual rationality, and no subsidy for losers (Morimoto and Serizawa 2015).^{Footnote 4}

Although the unit-demand assumption is suitable in some important cases such as house allocation, etc., in many other cases, some agents may well wish to receive more than one object, and indeed, many authors have analyzed such situations.^{Footnote 5}

Now, a natural question arises. On a domain that is neither quasi-linear nor unit-demand, do efficient and strategy-proof rules exist? This is the question we address. To state our result, we need an additional property of preferences. A preference relation satisfies the multi-demand property if given a payment level, when an agent receives an object, receiving some additional object(s) makes him better off. We show that when there are more agents than objects, on any domain that contains enough variety of unit-demand preferences and at least one multi-demand preference relation, no rule satisfies efficiency, strategy-proofness, individual rationality, and no subsidy for losers. In most impossibility results in the literature on strategy-proofness, the incompatibility of a list of properties of rules is established on a fixed domain.^{Footnote 6} On the other hand, our result is more general in the sense that the incompatibility of our properties holds on any domain containing enough variety of unit-demand preferences and some multi-demand preferences.

This article is organized as follows. In Sect. 2, we introduce the model and basic definitions. In Sect. 3, we introduce the unit-demand model and the richness condition. In Sect. 4, we define the minimum price Walrasian rule. In Sect. 5, we state our result and show the sketch of the proof. Sect. 6 concludes. All the proofs appear in the Appendix.

2 The model and definitions

There are $n\ge 2$ agents and $m\ge 2$ objects. We denote the set of agents by $N\equiv \{1,\dots ,n\}$ and the set of objects by $M\equiv \{1,\dots ,m\}$. Let $\mathcal {M}$ be the power set of M. With abuse of notation, for each $a\in M$, we may write a to mean $\{a\}$. Each agent receives a subset of M and pays some amount of money. Thus, the agents’ common consumption set is $\mathcal {M}\times \mathbb {R}$ and a generic (consumption) bundle for agent i is a pair $z_i=(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$. Let $\varvec{0}\equiv (\emptyset ,0)$.

Each agent i has a complete and transitive preference relation $R_i$ over $\mathcal {M}\times \mathbb {R}$. Let $P_i$ and $I_i$ be the strict and indifference relations associated with $R_i$. A typical class of preferences is denoted by $\mathcal {R}$. We call $\mathcal {R}^n$ a domain. The following are standard conditions of preferences.

Money monotonicity: For each $A_i\in \mathcal {M}$ and each pair $t_i,t'_i\in \mathbb {R}$ with $t_i<t'_i$, $(A_i,t_i)\mathrel {P_i}(A_i,t'_i)$.

First object monotonicity: For each $(\{a\},t_i)\in \mathcal {M}\times \mathbb {R}$, $(\{a\},t_i)\mathrel {P_i}(\emptyset ,t_i)$.

Possibility of compensation: For each $(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$ and each $A'_i\in \mathcal {M}$, there are $t'_i,t''_i\in \mathbb {R}$ such that $(A_i,t_i)\mathrel {R_i}(A'_i,t'_i)$ and $(A'_i,t''_i)\mathrel {R_i}(A_i,t_i)$.

Continuity: For each $z_i\in \mathcal {M}\times \mathbb {R}$, the upper contour set at $z_i$, $UC_i(z_i)\equiv \{z'_i\in \mathcal {M}\times \mathbb {R}:z'_i\mathrel {R_i}z_i\}$, and the lower contour set at $z_i$, $LC_i(z_i)\equiv \{z'_i\in \mathcal {M}\times \mathbb {R}:z_i\mathrel {R_i}z'_i\}$, are both closed.

Free disposal: For each $(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$ and each $A'_i\in \mathcal {M}$ with $A'_i\subseteq A_i$, $(A_i,t_i)\mathrel {R_i}(A'_i,t_i)$.

Definition 1

A preference relation is classical if it satisfies money monotonicity, first object monotonicity, possibility of compensation, and continuity.

Let $\mathcal {R}^C$ be the class of classical preferences. We call $(\mathcal {R}^{C})^n$ the classical domain. Let $\mathcal {R}^C_+$ be the class of classical preferences satisfying free disposal. Obviously, $\mathcal {R}^C_+\subsetneq \mathcal {R}^C$.

Lemma 1 holds for classical preferences. The proof is relegated to the Appendix.

Lemma 1

Let $R_i\in \mathcal {R}^C$ and $A_i,A'_i\in \mathcal {M}$. There is a continuous function $V_i(A'_i;(A_i,\cdot )):\mathbb {R}\rightarrow \mathbb {R}$ such that for each $t_i\in \mathbb {R}$, $(A'_i,V_i(A'_i;(A_i,t_i)))\mathrel {I_i}(A_i,t_i)$.

For each $R_i\in \mathcal {R}^C$, each $z_i\in \mathcal {M} \times \mathbb {R}$, and each $A_i\in \mathcal {M}$, we call $V_i(A_i;z_i)$ the valuation of $A_i$ at $z_i$ for $R_i$. By money monotonicity, for each $R_i\in \mathcal {R}^C$ and each pair $(A_i,t_i),(A'_i,t'_i)\in \mathcal {M}\times \mathbb {R}$, $(A_i,t_i)\mathrel {R_i}(A'_i,t'_i)$ if and only if $V_i(A'_i;(A_i,t_i))\le t'_i$.

Definition 2

A preference relation $R_i\in \mathcal {R}^C$ is quasi-linear if for each pair $(A_i,t_i),(A_i',t'_i)\in \mathcal {M}\times \mathbb {R}$ and each $t''_i\in \mathbb {R}$, $(A_i,t_i)\mathrel {I_i}(A_i',t'_i)$ implies $(A_i,t_i+t''_i)\mathrel {I_i}(A_i',t'_i+t''_i)$.

Let $\mathcal {R}^Q$ be the class of quasi-linear preferences. We call $(\mathcal {R}^Q)^n$ the quasi-linear domain. Obviously, $\mathcal {R}^Q\subsetneq \mathcal {R}^C$.

Remark 1

Let $R_i\in \mathcal {R}^Q$. Then,

(i)
there is a valuation function $v_i:\mathcal {M}\rightarrow \mathbb {R}_{+}$ such that $v_i(\emptyset )=0$, and for each pair $(A_i,t_i),(A_i',t'_i)\in \mathcal {M}\times \mathbb {R}$, $(A_i,t_i)\mathrel {R_i}(A_i',t'_i)$ if and only if $v_i(A_i')-t'_i\le v_i(A_i)-t_i$, and
(ii)
for each $(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$ and each $A'_i\in \mathcal {M}$, $\textit{V}_i(A'_i;(A_i,t_i))-t_i=v_i(A'_i)-v_i(A_i)$.

Now we define important classes of preferences. The following property formalizes the notion that given a payment level, an agent desires to consume at most one object.

Definition 3

A preference relation $R_i\in \mathcal {R}^C$ satisfies the unit-demand property if for each $(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$ with $|A_i|>1$, there is $a\in A_i$ such that $(a,t_i)\mathrel {R_i}(A_i,t_i)$.^{Footnote 7} $^{\text {,}}$ ^{Footnote 8}

The condition means that given a payment level, for each set of objects, the most preferred one in the set is at least as good as the set itself. Note that it is possible that when an agent with a unit-demand preference relation receives an object and his payment is fixed, an additional object makes him better off. However, this occurs only when he prefers the additional object to the original one. Figure 1 illustrates a unit-demand preference relation.

Let $\mathcal {R}^U$ be the class of unit-demand preferences. We call $(\mathcal {R}^U)^n$ the unit-demand domain. Obviously, $\mathcal {R}^U\subsetneq \mathcal {R}^C$.

We also consider a property that formalizes the notion that given a payment level, an agent desires to consume several objects.

Definition 4

A preference relation $R_i\in \mathcal {R}^C$ satisfies the multi-demand property if for each $(\{a\},t_i)\in \mathcal {M}\times \mathbb {R}$, there is $A_i\in \mathcal {M}$ such that $a\in A_i$ and $(A_i,t_i)\mathrel {P_i}(\{a\},t_i)$.

The condition says that given a payment level, when an agent receives an object, receiving some additional object(s) makes him better off. Note that given a payment level, even if an agent has a multi-demand preference relation, when he receives a set consisting of several objects, he may find it worse than each object in the set. Figure 2 illustrates a multi-demand preference relation.

Let $\mathcal {R}^M$ be the class of multi-demand preferences. We call $(\mathcal {R}^M)^n$ the multi-demand domain. The following are examples of preferences satisfying the multi-demand property.

Example 1:

k-object-demand preferences. Given $k\in \{1,\dots , m\}$, a preference relation $R_i\in \mathcal {R}^C$ satisfies the k-object-demand property if (i) for each $(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$ with $|A_i|<k$, and each $a\in M{\setminus } A_i$, $(A_i\cup \{a\},t_i)\mathrel {P_i}(A_i,t_i)$, and (ii) for each $(A_i,t_i)\in \mathcal {M}\times \mathbb {R}$ with $|A_i|\ge k$, there is $A'_i\subseteq A_i$ with $|A'_i|= k$ such that $(A'_i,t_i)\mathrel {R_i}(A_i,t_i)$.^{Footnote 9} Clearly, for each $k\in \{2,\dots , m\}$, preferences satisfying the k-object-demand property satisfy the multi-demand property.

Example 2:

Substitutes and complements. Suppose that the set of objects are divided into two non-empty sets K and L, and agent i with a preference relation $R_i$ views objects a and b as substitutes if both a and b are in the same set, and as complements if a and b are in different sets. For example, objects in K can be pens and objects in L can be notebooks. Formally, $R_i$ satisfies the following property: For each $A_i\in \mathcal {M}$ with $|A_i|> 1$ and each $t_i\in \mathbb {R}$, if $A_i\subseteq K$ or $A_i\subseteq L$, then there is $a\in A_i$ such that $(A_i,t_i)\mathrel {I_i}(a,t_i)$, and otherwise, for each $a\in A_i$, $(A_i,t_i)\mathrel {P_i}(a,t_i)$. Clearly, this preference relation $R_i$ satisfies the multi-demand property.

Some preferences in $\mathcal {R}^C$ violate both of the unit-demand property and the multi-demand property.

Example 3:

(Fig. 3). A preference relation violating the unit-demand property and the multi-demand property. Let $R_i\in \mathcal {R}^C$ be such that for each $a\in M$ and each $t_i\in \mathbb {R}$, $V_i(a;(\emptyset ,t_i))=t_i+5$, and for each $A_i\in \mathcal {M}$ with $|A_i|>1$, and each $t_i\in \mathbb {R}$,

$$\begin{aligned} V_i(A_i;(\emptyset ,t_i))= {\left\{ \begin{array}{ll} t_i+5&{}\text {if }t_i\ge -5,\\ \frac{1}{2}(t_i+5)&{}\text {otherwise}. \end{array}\right. } \end{aligned}$$

Then, for each pair $a,b\in M$ and each $t_i\in \mathbb {R}$ with $t_i<-5$, $V_i(\{a,b\};(\emptyset ,t_i))=\frac{1}{2}(t_i+5)>t_i+5=V_i(a;(\emptyset , t_i))=V_i(b;(\emptyset ,t_i))$, and thus, we have $(\{a,b\}, t_i+5)\mathrel {P_i}(a,t_i+5)\mathrel {I_i}(b,t_i+5)$. Thus, $R_i$ does not satisfy the unit-demand property. Moreover, for each $a\in M$, each $A_i\in \mathcal {M}$ with $a\in A_i$, and each $t_i\in \mathbb {R}$ with $t_i\ge -5$, $V_i(A_i;(\emptyset ,t_i))=t_i+5=V_i(a;(\emptyset ,t_i))$, and thus, we have $(A_i,t_i+5)\mathrel {I_i}(a,t_i+5)$. Thus, $R_i$ does not satisfy the multi-demand property.

An object allocation is an n-tuple $A\equiv (A_1,\ldots ,A_{n})\in \mathcal {M}^n$ such that $A_i\cap A_j=\emptyset $ for each $i,j\in N$ with $i\ne j$. We denote the set of object allocations by $\mathcal {A}$. A (feasible) allocation is an n-tuple $z\equiv (z_1,\dots ,z_{n})\equiv ((A_1,t_1),\dots ,(A_{n},t_{n}))\in (\mathcal {M}\times \mathbb {R})^n$ such that $(A_1,\dots ,A_{n})\in \mathcal {A}$. We denote the set of feasible allocations by Z. Given $z\in Z$, we denote the object allocation and the agents’ payments at z by $A\equiv (A_1,\dots ,A_n)$ and $t\equiv (t_1\dots , t_n)$, respectively, and we also write $z=(A,t)$.

A preference profile is an n-tuple $R\equiv (R_1,\ldots R_n)\in \mathcal {R}^n$. Given $R\in \mathcal {R}^n$ and $i\in N$, let $R_{-i}\equiv (R_j)_{j\ne i}$.

An allocation rule, or simply a rule on $\mathcal {R}^n$ is a function $f: \mathcal {R}^n\rightarrow Z$. Given a rule f and $R\in \mathcal {R}^n $, we denote the bundle assigned to agent i by $f_i(R)$ and we write $f_i(R)=(A_i(R),t_i(R))$.

Now, we introduce standard properties of rules. The efficiency notion here takes the planner’s preferences into account and assumes that he is only interested in his revenue. Formally, an allocation $z\equiv ((A_i,t_i))_{i\in N}\in Z$ is (Pareto-)efficient for $R\in \mathcal {R}^n$ if there is no feasible allocation $z'\equiv ((A_i',t'_i))_{i\in N}\in Z$ such that $(\text {i})\text { for each }i\in N,\;z_i'\mathrel {R_i}z_i\text {, }(\text {ii})\text { for some }j\in N,z_j'\mathrel {P_i}z_j, \text { and }(\text {iii})\sum _{i\in N}t'_i\ge \sum _{i\in N}t_i.$

The first property states that for each preference profile, a rule chooses an efficient allocation.

Efficiency: For each $R\in \mathcal {R}^n$, f(R) is efficient for R.

Remark 2

By money monotonicity and Lemma 1, the efficiency of allocation z is equivalent to the property that there is no allocation $z'\equiv ((A'_i,t'_i))_{i\in N}\in Z$ such that

(i$'$) for each $i\in N$, $z_i'\mathrel {I_i}z_i$, and (ii$'$) $\sum _{i\in N}t'_i>\sum _{i\in N}t_i$.

The second property states that no agent benefits from misrepresenting his preferences.

Strategy-proofness: For each $R\in \mathcal {R}^n$, each $i\in N$, and each $R'_i\in \mathcal {R}$, $f_i(R)\,R_i \,f_i(R'_i,R_{-i})$.

The third property states that an agent is never assigned a bundle that makes him worse off than he would be if he had received no object and paid nothing.

Individual rationality: For each $R\in \mathcal {R}^n$ and each $i\in N$, $f_i(R)\mathrel {R_i}\varvec{0}$.

The fourth property states that the payment of each agent is always nonnegative.

No subsidy: For each $R\in \mathcal {R}^n$ and each $ i\in N$, $t_i(R)\ge 0$.

The final property is a weaker variant of the fourth: If an agent receives no object, his payment is nonnegative.

No subsidy for losers: For each $R\in \mathcal {R}^n$ and each $i\in N$, if $A_i(R)=\emptyset $, $t_i(R)\ge 0$.

3 Unit-demand model and rich domains

In our model, potentially each agent can receive several objects. However, some authors study a model in which no agent can receive more than one object owing to some reason, say by regulations, or by physical reasons.^{Footnote 10} We call this model the unit-demand model, and refer to our model as the multi-demand model. Some important results are established in the unit-demand model, and they are related to our main result. Some of such results continue to hold in the multi-demand model when preferences are unit-demand, and others continue to hold only when domains include enough variety of unit-demand preferences. In this section, we introduce “richness” of domains in our model, which guarantees that a domain of the multi-demand model includes enough variety of unit-demand preferences.

In the unit-demand model, preferences are defined over $M\cup \{0\}\times \mathbb {R}$, where 0 means not receiving any object in M and is called null object. To distinguish classes of preferences in the multi-demand model and those in the unit-demand model, we denote a typical class of preferences in the unit-demand model by $\mathscr {R}$.

Money monotonicity, first object monotonicity, possibility of compensation, and continuity are defined in the unit-demand model in the same manner as defined in our model. Thus, in the unit-demand model, classical preferences are defined in the same manner.

Definition 5

A preference relation $R_i$ over $M\cup \{0\}\times \mathbb {R}$ is classical if it satisfies money monotonicity, first object monotonicity, possibility of compensation, and continuity.

Let $\mathscr {R}^C$ be the class of classical preferences in the unit-demand model.

In the unit-demand model, a feasible allocation is an n-tuple $ z=((x_i,t_i))_{i\in N}\in (M\cup \{0\}\times \mathbb {R})^{n}$ such that for each pair $i,j\in N$, $x_i=x_j$ implies $x_i=x_j=0$. As we mentioned, in the unit-demand model, no agent can receive more than one object. Other notions such as rules, properties of rules, etc., are defined in the same manner as defined in the multi-demand model.

To define the richness, we introduce the following notions, which connect preferences in the multi-demand model to those in the unit-demand model.

Definition 6

A preference relation $R_i$ in the multi-demand model induces a preference relation $R_i^{\prime }$ over $M\cup \{0\}\times \mathbb {R}$ if for each pair $(a,t_i),(b,t_i^{\prime })\in M\cup \{0\}\times \mathbb {R}$, $(a,t_i)\mathrel {R'_i}(b,t_i^{\prime })$ if and only if $(A_i,t_i)\mathrel {R_i}(A_i^{\prime },t_i^{\prime })$, where

$$\begin{aligned} A_i={\left\{ \begin{array}{ll} \{a\} &{} \text {if }a\in M, \\ \emptyset &{} \text {if }a=0, \end{array}\right. } \text { and }A_i^{\prime }= {\left\{ \begin{array}{ll} \{b\} &{} \text {if }b\in M, \\ \emptyset &{} \text {if }b=0. \end{array}\right. } \end{aligned}$$

Definition 7

A class of preferences $\mathcal {R}$ in the multi-demand model induces a class of preferences $\mathscr {R}$ over $M\cup \{0\}\times \mathbb {R}$ if (i) for each $R_i^{\prime }\in \mathscr {R}$, there is $ R_i\in \mathcal {R}$ that induces $R_i^{\prime }$, and (ii) for each $ R_i\in \mathcal {R}$, there is $R_i^{\prime }\in \mathscr {R}$ that is induced by $R_i$.

Remark 3

Each of $\mathcal {R}^{U}$, $\mathcal {R}_{+}^{U}$, and $\mathcal { R}^{U}{\setminus } \mathcal {R}_{+}^{U}$ induces $\mathscr {R}^{C}$.

Now, we introduce the richness of domain, which guarantees that a domain of the multi-demand model includes enough variety of unit-demand preferences so that they induce the class of classical preferences in the unit-demand model.

Definition 8

A class of preferences $\mathcal {R}$ is rich if $\mathcal {R\,}\cap \mathcal {\,R}^{U}$ induces $\mathscr {R}^{C}$.

By Remark 3, $\mathcal {R}^U$, $\mathcal {R}^U_+$, and $\mathcal {R}^U{\setminus }\mathcal {R}^U_+$ are rich.

4 Minimum price Walrasian rules

In this section we define the minimum price Walrasian rules and state several facts related to them.

Let $p\equiv (p^1,\ldots ,p^M)\in \mathbb {R}_{+}^m$ be a price vector. The budget set at p is defined as $B(p)\equiv \{(A_i,t_i)\in \mathcal { M}\times \mathbb {R}: t_i=\sum _{a\in A_i}p^a\}$. Given $R_i\in \mathcal {R}$, the demand set at p for $R_i$ is defined as $D(R_i,p)\equiv \{z_i\in B(p):\text {for each }z^{\prime }_i\in B(p),\,z_i\mathrel {R_i} z^{\prime }_i\}$.

Lemma 2

Let $R_i\in \mathcal {R}^U$ and $p\in \mathbb {R}^m_+$. (i) Suppose $p\in \mathbb {R}^m_{++}$. Then, for each $(A_i,t_i)\in D(R_i,p)$, $ |A_i| \le 1$. (ii) Let $A_i\in \mathcal {M}$ be such that $(A_i,\sum _{a\in A_i}p^a)\mathrel {R_i}(A^{\prime }_i,\sum _{a\in A^{\prime }_i}p^a)$ for each $ A^{\prime }_i\in \mathcal {M}$ with $|A^{\prime }_i|\le 1$. Then, $( A_i,\sum _{a\in A_i}p^a)\in D(R_i,p)$.

Definition 9

Let $R\in \mathcal {R}^n$. A pair $((A,t),p)\in Z\times \mathbb {R}_{+}^m$ is a Walrasian equilibrium (WE) for R if

$$\begin{aligned}&\text { W-i: for each }i\in N\text {, }(A_i,t_i)\in D(R_i,p),\text { and} \\&\text { W-ii: for each }a\in M,\text { if }a\notin A_i \text{ for } \text{ each } i\in N,\text { then, }p^a=0. \end{aligned}$$

Condition W-i says that each agent receives a bundle that he demands. Condition W-ii says that an object’s price is zero if it is not assigned to anyone. Given $R\in \mathcal {R}^n$, let W(R) and P(R) be the sets of Walrasian equilibria and prices for R, respectively.

Lemma 3

Let $R\in (\mathcal {R}^U)^n$ and $p\in P(R)$. (i) If $n>m$, then $ p^a>0 $ for each $a\in M$. (ii) There is $((A,t),p)\in W(R)$ such that $ |A_i|\le 1$ for each $i\in N $.

Let $R\in (\mathcal {R}^{U})^{n}$ and $R^{\prime }$ be preference profiles of the multi-demand and unit-demand models respectively such that for each $ i\in N$, $R_i^{\prime }$ is induced by $R_i$. For each $p\in P(R)$, by (ii) of Lemma 3, there is an allocation $((\{a_i\},t_i))_{i\in N}$ such that $(((\{a_i\},t_i))_{i\in N},p)\in W(R)$, and thus, $ (((a_i,t_i))_{i\in N},p)$ is a WE for $R^{\prime }$. On the other hand, for each $p\in \mathbb {R}_{+}^M$, if p is a WE price vector for $ R^{\prime }$, then there is an allocation $((a_i,t_i))_{i\in N}$ such that $(((a_i,t_i))_{i\in N},p)$ is a WE for $R^{\prime }$, and thus by (ii) of Lemma 2, $(((\{a_i\},t_i))_{i\in N},p)\in W(R)$. Therefore, the set of WE price vectors for R coincides with the set of WE price vectors for $R^{\prime }$.

In the unit-demand model, several results on Walrasian equilibrium are established. By the preceding argument, the same results continue to hold in our model for preferences satisfying the unit-demand property.

Fact 1

(Alkan and Gale 1990)^{Footnote 11} $^{\text {,}}$ ^{Footnote 12} For each $R\in (\mathcal {R}^U)^n$, a Walrasian equilibrium for R exists.

Fact 2

(Demange and Gale 1985) For each $R\in (\mathcal {R}^U)^n$, there is a unique minimum Walrasian equilibrium price vector, i.e., a vector $p\in P(R)$ such that for each $ p^{\prime }\in P(R)$, $p\le p^{\prime }$.^{Footnote 13}

Given $R \in {\mathcal {R}}^n$, a minimum price Walrasian equilibrium (MPWE) for R is a Walrasian equilibrium for R whose price is minimum. Given $R\in \mathcal {R}^n$, let $ p_{\min }(R)$ be the minimum Walrasian equilibrium price for R, and $Z_{\min }^W(R)$ be the set of Walrasian equilibrium allocations associated with $p_{\min }(R)$. Although there might be several minimum price Walrasian equilibria, they are indifferent for each agent, i.e., for each $R\in \mathcal {R}^n$, each pair $z,z^{\prime }\in Z_{\min }^W(R)$, and each $i\in N$, $z_i\mathrel {I_i}z^{\prime }_i$.

Definition 10

A rule f on $\mathcal {R}^n$ is a minimum price Walrasian (MPW) rule if for each $R\in \mathcal {R}^n$, $f(R)\in Z_{\min }^W(R)$.

It is easy to show that the MPW rules on $(\mathcal {R}^{U})^{n}$ satisfy efficiency, individual rationality, and no subsidy. Demange and Gale (1985) show that the MPW rules are strategy-proof on the classical domain in the unit-demand model. Our arguments above allow us to convert each MPWE allocation in the unit-demand model into an MPWE for a unit-demand profile in the multi-demand model. Moreover, all the minimum price Walrasian equilibria are indifferent for each agent. Thus, the result by Demange and Gale (1985) implies that for each rich class of preferences $\mathcal {R}\subseteq \mathcal {R}^{U}$, the MPW rules on $ \mathcal {R}^{n}$ also satisfy strategy-proofness in multi-demand model.

Morimoto and Serizawa (2015) shows that in the unit-demand model, when $n>m$, only the MPW rules satisfy efficiency, strategy-proofness, individual rationality, and no subsidy for losers on $(\mathscr {R}^{C})^{n}$. The following lemma states that in the multi-demand model, when $n>m$, efficient rules never assign more than one object to agents whose preferences satisfy the unit-demand property.

Lemma 4

(Single object assignment) Let $n>m$. Let $\mathcal {R}\subseteq \mathcal {R}^C$ and f be an efficient rule on $\mathcal {R}^n$. Let $R\in \mathcal {R}^n$ and $ i\in N$. If $R_i\in \mathcal {R}^U$, $|A_i(R)|\le 1$.

By Lemma 4, when $n>m$, for each $\mathcal {R}\subseteq \mathcal {R}^{U}$ that is rich, and each rule on $\mathcal {R}^{n}$ satisfying efficiency, it always assigns each agent at most one object. Thus, when $n>m $, for each $\mathcal {R}\subseteq \mathcal {R}^{U}$ that is rich, and each rule on $\mathcal {R}^{n}$ satisfying efficiency, strategy-proofness, individual rationality, and no subsidy for losers, there is a corresponding rule in the unit-demand model, and moreover, it is easy to see that the corresponding rule also satisfies the four properties. Thus, the result by Morimoto and Serizawa (2015) continues to hold in our model.

Fact 3

(Demange and Gale 1985 for (i); Morimoto and Serizawa 2015 for (ii)) Let $\mathcal {R}\subseteq \mathcal {R}^{U}$. (i) The minimum price Walrasian rules on $\mathcal {R}^{n}$ satisfy efficiency, strategy-proofness, individual rationality and no subsidy. (ii) Let $n>m$, and $\mathcal {R}$ be rich. Then, the minimum price Walrasian rules are the only rules on $ \mathcal {R}^{n}$ satisfying efficiency, strategy-proofness, individual rationality and no subsidy for losers.

5 Main result

In this section, first we state the main theorem. Next, we explain how we prove the theorem.

5.1 Impossibility result

We consider rich domains containing some multi-demand preferences and we investigate whether efficient and strategy-proof rules still exist on such domains. In marked contrast to Fact 3 in Sect. 3, the results are negative. Namely, if there are more agents than objects, and if the domain is rich and contains even a single multi-demand preference relation, then no rule on the domain satisfies efficiency, strategy-proofness, individual rationality and no subsidy for losers.

Theorem

Let $n>m$. Let $R_{0}\in \mathcal {R}^M$ and $ \mathcal {R}$ be a rich class of preferences such that $R_{0}\in \mathcal {R}$. Then, no rule on $\mathcal {R}^{n}$ satisfies efficiency, strategy-proofness, individual rationality and no subsidy for losers.

Corollary 1

Let $n>m$. Let $\mathcal {R}=\mathcal {R}^{U}\cup \mathcal {R}^M $. Then, no rule on $\mathcal {R}^{n}$ satisfies efficiency, strategy-proofness, individual rationality and no subsidy for losers.

Remark 4

The Corollary 1 is a standard form of impossibility results on strategy-proofness in that since Gibbard (1973) and Satterthwaite (1975), many impossibility results on strategy-proofness of this form are established. In such results, a domain is fixed and incompatibility of some properties of rules is established on this domain. Results of this form cannot be applied unless all the preferences in the fixed domain are deemed plausible. For example, the Corollary 1 cannot be applied unless all the preferences in $ \mathcal {R}^M$ in addition to $\mathcal {R}^{U}$ are deemed plausible. On the other hand, our Theorem can be applied as soon as in addition to a rich class of preferences $\mathcal {R}$, just one preference relation $R_{0}$ arbitrarily chosen from $\mathcal {R}^M$ is deemed plausible. Accordingly our Theorem can be applied to more variety of environments than Corollary 1. For example, consider an environment where $n=40$ , $m=20$ and there are only the preferences satisfying k-object-demand property for $k\in \{1,2,3,4,5\} $. The Theorem can be applied to this environment, but the Corollary 1 cannot be.

By Remark 3, we also have the following corollaries. These corollaries demonstrate the wide applicability of our results even more. In this paper, we do not maintain free disposal. However, it is a standard assumption for preferences. Corollary 2 states that our conclusion holds even if free disposal is assumed.

Corollary 2

Let $n>m$. Let $R_{0}\in \mathcal {R}^M$ and $ \mathcal {R}\equiv \mathcal {R}_{+}^{U}\cup \{R_{0}\}$. Then, no rule on $\mathcal {R} ^{n}$ satisfies efficiency, strategy-proofness, individual rationality and no subsidy for losers.

Free disposal is not a suitable assumption in some environment. Corollary 3 states that our conclusion holds even in such an environment.

Corollary 3

Let $n>m$. Let $R_{0}\in \mathcal {R}^M$ and $ \mathcal {R}\equiv (\mathcal {R}^{U}{\setminus } \mathcal {R}_{+}^{U})\cup \{R_{0}\}$. Then, no rule on $\mathcal {R}^{n}$ satisfies efficiency, strategy-proofness, individual rationality and no subsidy for losers.

Remark 5

In this paper, we assume that preferences are drawn from a common class of $\mathcal {R}$. If preferences of each agent are drawn from a class $\mathcal {R}_i$ that depends on the identity of the agent, our theorem can be strengthened as follows: Suppose that, for each $i\in N$, $\mathcal {R}_i$ is rich, and there are $j\in N$ and $R_j\in \mathcal {R}^M$ such that $R_j\in \mathcal {R}_j$. Then, when $n>m$, no rule on $\prod _{i\in N} \mathcal {R}_i$ satisfies efficiency, strategy-proofness, individual rationality and no subsidy for losers.

5.2 Sketch of the proof

5.2.1 Preliminary results

We state seven lemmas which we use in the sketch of the proof and in the formal proof. The proof of each lemma is relegated to the Appendix, or is omitted if it is straightforward.

Let $\mathcal {R}\subseteq \mathcal {R}^C$ be rich. Let f be a rule on $\mathcal {R}^n$ satisfying efficiency, strategy-proofness, individual rationality and no subsidy for losers. Lemma 5 states that if an agent receives no object, then his payment is zero. This is immediate from individual rationality and no subsidy for losers. Thus we omit the proof.

Lemma 5

(Zero payment for losers) Let $R\in \mathcal {R}^n$ and $i\in N$. If $A_i(R)=\emptyset $, $t_i(R)=0$.

Lemma 6 states that for each agent, his payment is at most the valuation, at $\varvec{0}$, of the set of objects that he receives. This is immediate from individual rationality. Thus, we omit the proof.

Lemma 6

For each $R\in \mathcal {R}^n$ and each $i\in N$, $t_i(R)\le V_i(A_i(R);\varvec{0})$.

Lemma 7 states that each object is assigned to some agent. This follows from efficiency, $n>m$, and first object monotonicity. We omit the proof.

Lemma 7

(Full object assignment) Let $n>m$. For each $R\in \mathcal {R}^n$ and each $a\in M$, there is $i\in N$ such that $a\in A_i(R)$.

Lemma 8 states a necessary condition for efficiency.

Lemma 8

(Necessary condition for efficiency) Let $R\in \mathcal {R}^n$ and $i,j\in N$ with $i\ne j$. Let $A_i,A_j\in \mathcal {M}$ be such that $A_i\cap A_j=\emptyset $ and $A_i\cup A_j\subseteq A_i(R)\cup A_j(R)$. Then, $V_i(A_i;f_i(R))+V_j(A_j;f_j(R)) \le t_i(R)+t_j(R)$.

Although no subsidy for losers itself tells us nothing about payment levels for non-empty sets of objects, Lemma 9 states that for each non-empty set of objects, there is a lower bound of the payment level for the set.

Lemma 9

(Payment lower bound) Let $n>m$. Let $R\in \mathcal {R}^n$ and $i\in N$. Let $R'_i\in \mathcal {R}\cap \mathcal {R}^U$ be such that for each $a\in M$ and each $t_i\in \mathbb {R}$, $V'_i(a;(\emptyset ,t_i))-t_i<\min _{j\in N{\setminus } \{i\}}V_j(a;\varvec{0})$.^{Footnote 14} Then, $t_i(R)\ge V'_i(A_i(R);\varvec{0})$.

By first object monotonicity, Lemma 9 implies that for each $R\in \mathcal {R}^n$ and each $i\in N$, if $|A_i(R)|=1$, then $t_i(R)\ge 0$.

Lemma 10 states that f coincides with an MPW rule on $(\mathcal {R}\cap \mathcal {R}^U)^n$. This is immediate from (ii) of Fact 3. Thus we omit the proof.

Lemma 10

Let $n>m$. For each $R\in (\mathcal {R}\cap \mathcal {R}^U)^n$, $f(R)\in Z^W_{\min }(R)$.

Given $i\in N$ and $R_{-i}\in \mathcal {R}^{n-1}$, we define the option set of agent i for $R_{-i}$ by

$$\begin{aligned} o_i(R_{-i})\equiv \{z_i\in \mathcal {M}\times \mathbb {R} :\exists R_i\in \mathcal {R} \text{ s.t. } f_i(R_i,R_{-i})=z_i\}. \end{aligned}$$

Lemma 11 states that (i) the option set does not contain more than one bundle with the same set of objects, and (ii) each agent receives one of the most preferred bundles in his option set. This is straightforward from strategy-proofness. Thus, we omit the proof.

Lemma 11

Let $i\in N$ and $R_{-i}\in \mathcal {R}^n$. (i) For each pair $(A_i,t_i),(A'_i,t'_i)\in o_i(R_{-i})$, if $A_i=A'_i$, then $t_i=t'_i$. (ii) For each $R_i\in \mathcal {R}$ and each $z_i\in o_i(R_{-i})$, $f_i(R_i,R_{-i})\mathrel {R_i}z_i$.

5.2.2 Three-agent and two-object example

Since the proof of the Theorem is very complicated, we relegate it to the Appendix. Here we demonstrate the ideas and techniques of the proof by applying them to a particular example in a three-agent and two-object setting. Let $M=\{a,b\}$ and $N=\{1,2,3\}$. In the formal proof, the preference relation $R_0$ is an arbitrary element of $\mathcal {R}^M$, but here we pick $R_0$ from $\mathcal {R}^{Q}\cap \mathcal {R}^M$. For concreteness, let

$$\begin{aligned} v_0(a)=20\text {, }v_0(b)=18\text { and }v_0(\{a,b\})=40. \end{aligned}$$

However, the idea of our proof does not depend on $R_0\in \mathcal {R}^{Q}$. We assume $R_0\in \mathcal {R}^{Q}$ only for simplicity of expression.

Let $\mathcal {R}\subseteq \mathcal {R}^{C}$ satisfy the richness and contain $R_0$. For example, let $\mathcal {R} \supseteq \mathcal {R}^U\cup \{R_0\}$. We suppose that there is a rule f on $\mathcal {R}^{3}$ satisfying efficiency, strategy-proofness, individual rationality and no subsidy for losers, and derive a contradiction.

Step A: Constructing a preference profile.

Let $R_1=R_0$. We construct $R_2\in \mathcal {R}^{U}$ and $R_{3}\in \mathcal {R}^{U}$ depending on $R_1$ so that a contradiction is derived. We define $R_2$ satisfying $V_2(a;\varvec{0})>v_1(\{a,b\})$ and^{Footnote 15}

$$\begin{aligned} V_2(b;\varvec{0})-V_2(\emptyset ;(b,0))<\min \{v_1(\{a,b\})-v_1(a),v_1(\{a,b\})-v_1(b)\}. \end{aligned}$$

For example, let $R_2\in \mathcal {R}^{U}$ be such that for each $A_2\in \mathcal {M} {\setminus } \{\emptyset \}$,

$$\begin{aligned} V_2(A_2;\varvec{0})&= {\left\{ \begin{array}{ll} 41 &{} \text {if }A_2=\{a\}, \\ 12 &{} \text {if }A_2=\{b\}, \\ 41 &{} \text {if }A_2=\{a,b\}, \end{array}\right. } V_2(A_2;(\emptyset ,-1))= {\left\{ \begin{array}{ll} 9 &{} \quad \text {if }A_2=\{a\}, \\ 10 &{} \quad \text {if }A_2=\{b\}, \\ 10 &{} \quad \text {if }A_2=\{a,b\}, \end{array}\right. } \\ V_2(A_2,(\emptyset ,-2))&= {\left\{ \begin{array}{ll} -1 &{} \text {if }A_2=\{a\}, \\ 9 &{} \text {if }A_2=\{b\}, \\ 9 &{} \text {if }A_2=\{a,b\}, \end{array}\right. } V_2(A_2;(\emptyset ,-3))= {\left\{ \begin{array}{ll} -2 &{} \quad \text {if }A_2=\{a\}, \\ 0 &{} \quad \text {if }A_2=\{b\}, \\ 0 &{} \quad \text {if }A_2=\{a,b\}. \end{array}\right. } \end{aligned}$$

We define $R_{3}$ satisfying $R_{3}\in \mathcal {R}^U\cap \mathcal {R}^{Q}$, and

$$\begin{aligned} v_{3}(a)=v_{3}(b)<\frac{3}{5}\min \{v_1(\{a,b\})-v_1(a),v_1(\{a,b\})-v_1(b)\}. \end{aligned}$$

For example, let $v_{3}(a)=v_{3}(b)=9$. Note that $V_2(a;\varvec{0} )>v_{3}(\{a,b\})$. Let $R\equiv (R_1,R_2,R_{3})$. Figure 4 illustrates R . $\square $

Step B: $A_2(R)\ne \emptyset $ .

Suppose by contradiction that $A_2(R)=\emptyset $. By Lemma 5, $ f_2(R)=\varvec{0}$. By Lemma 7, there is $i\ne 2$ such that $a\in A_i(R)$.

Let $A_i=\emptyset $ and $A_2=\{a\}$. Note that $A_i\cap A_2=\emptyset $ and $A_i\cup A_2\subseteq A_i(R)\cup A_2(R)$. If $i=1$, then $V_1(\emptyset ; f_1(R))\ge t_1(R)-40$. If $i=3$, then $V_3(\emptyset ;f_3(R))=t_3(R)-9$. Thus, $V_i(\emptyset ;f_i(R))\ge t_i(R)-40$. Since $V_2(a;\varvec{0})=41$,

$$\begin{aligned} V_i(A_i;f_i(R))+V_2(A_2;f_2(R))&=V_i(\emptyset ;f_i(R))+V_2(a;\varvec{0})\qquad&({\hbox {by } f_2(R)=\varvec{0}}) \\&\ge t_i(R)-40+41\\&>t_i(R)+t_2(R).&(\hbox {by }t_2(R)=0) \end{aligned}$$

Thus, by Lemma 8, efficiency is violated, a contradiction. $\square $

Step C: $A_1(R)=a$.

Substep C-1: $(a,9)\in o_1(R_{-1})$.

Let $R^{\prime }_1\in \mathcal {R}^U$ be such that

$$\begin{aligned} V_1^{\prime }(a;\varvec{0})>\max \{V_2(a;\varvec{0}),V_3(a; \varvec{0})\}\text { and }V_1^{\prime }(b;\varvec{0})<\min \{V_2(b; \varvec{0}),V_3(b;\varvec{0})\}. \end{aligned}$$

For example, let $R^{\prime }_1\in \mathcal {R}^U$ be such that

$$\begin{aligned} V_1^{\prime }(a;\varvec{0})=50\text {, }V_1^{\prime }(b;\varvec{0} )=1 \text { and }V_1^{\prime }(\{a,b\};\varvec{0})=50. \end{aligned}$$

Since $(R^{\prime }_1,R_{-1})\in (\mathcal {R}^U)^3$, by Lemma 10, $ f(R^{\prime }_1,R_{-1})\in Z_{\min }^{W}(R^{\prime }_1,R_{-1})$. Let $z\in Z$ be such that

$$\begin{aligned} z_1=(a,9)\text {,}\ z_2=(b,9)\text { and}\ z_3=\varvec{0}. \end{aligned}$$

Figure 5 illustrates $(R^{\prime }_1,R_{-1})$ and z.

Let $p\equiv (9,9)$. Then, $D(R^{\prime }_1,p)=\{\{a\}\}$, $ D(R_2,p)=\{\{b\}\}$, and $D(R_3,p)=\{\emptyset ,\{a\},\{b\}\}$. Thus $ (z,p)\in W(R^{\prime }_1,R_{-1})$, implying $p_{\min }(R^{\prime }_1 ,R_{-1})\le p$. If $p_{\min }^{a}(R^{\prime }_1,R_{-1})<9$ or $p_{\min }^{b}(R^{\prime }_1,R_{-1})<9$, then $0\notin D(R^{\prime }_1,p_{\min }(R^{\prime }_1,R_{-1}))$ and for each $i\in \{2,3\}$, $0\notin D(R_i,p_{\min }(R^{\prime }_1,R_{-1}))$, which implies $p_{\min }(R^{\prime }_1,R_{-1})\notin P(R^{\prime }_1,R_{-1})$, a contradiction. Thus, $ p_{\min }(R^{\prime }_1,R_{-1})=(9,9)$. Moreover, z is the only WE allocation supported by $p_{\min }(R^{\prime }_1,R_{-1})$. Thus, $ f_1(R^{\prime }_1,R_{-1})=z$, and hence, $f_1(R^{\prime }_1,R_{-1})=(a,9)\in o_1(R_{-1})$.

Substep C-2: $(b,10)\in o_1(R_{-1})$.

Let $R^{\prime \prime }_1\in \mathcal {R}^U$ be such that

$$\begin{aligned} V_1^{\prime \prime }(b;\varvec{0})>\max \{V_2(b;\varvec{0} ),V_3(b; \varvec{0})\}\text { and }V_1^{\prime \prime }(a;\varvec{0 })<\min \{V_2(a;\varvec{0}),V_3(a;\varvec{0})\}. \end{aligned}$$

For example, let $R^{\prime \prime }_1\in \mathcal {R}^U$ be such that

$$\begin{aligned} V_1^{\prime \prime }(a;\varvec{0})=1\text {, }V_1^{\prime \prime }(b; \varvec{0})=50\text { and }V_1^{\prime \prime }(\{a,b\};\varvec{0} )=50. \end{aligned}$$

Since $(R^{\prime \prime }_1,R_{-1})\in (\mathcal {R}^U)^3$, by Lemma 10, $f(R^{\prime \prime }_1,R_{-1})\in Z_{\min }^{W}(R^{\prime \prime }_1,R_{-1})$. Let $z^{\prime }\in Z$ be such that

$$\begin{aligned} z_1^{\prime }=(b,10),\ z_2^{\prime }=(a,9),\text { and}\ z_3^{\prime }= \varvec{0}. \end{aligned}$$

Figure 6 illustrates $(R^{\prime \prime }_1,R_{-1})$ and $z^{\prime }$.

Let $p^{\prime }\equiv (9,10)$. Then, $D(R^{\prime \prime }_1,p^{\prime })=\{\{b\}\}$, $D(R_2,p^{\prime })=\{\{a\},\{b\}\}$, and $D(R_3,p^{\prime })=\{\emptyset ,\{a\}\}$. Thus $(z^{\prime },p^{\prime })\in W(R^{\prime \prime }_1,R_{-1})$, implying $p_{\min }(R^{\prime \prime }_1,R_{-1})\le p^{\prime }$. If $p_{\min }^{a}(R^{\prime \prime }_1,R_{-1})<9$, then $ 0\notin D(R^{\prime \prime }_1,p_{\min }(R^{\prime \prime }_1,R_{-1}))$ and for each $i\in \{2,3\}$, $0\notin D(R_i,p_{\min }(R^{\prime \prime }_1,R_{-1}))$, which implies $p_{\min }(R^{\prime \prime }_1,R_{-1})\notin P(R^{\prime \prime }_1,R_{-1})$, a contradiction. Thus, $p_{\min }^{a}(R^{ \prime \prime }_1,R_{-1})=9$. If $p_{\min }^{b}(R^{\prime \prime }_1,R_{-1})<10$, then we have $D(R^{\prime \prime }_1,p_{\min }(R^{\prime \prime }_1,R_{-1}))=\{\{b\}\}$ and $D(R_2,p_{\min }(R^{\prime \prime }_1,R_{-1}))=\{\{b\}\}$, which further implies $p_{\min }(R^{\prime \prime }_1,R_{-1})\notin P(R^{\prime \prime }_1,R_{-1})$, a contradiction. Thus, $ p_{\min }(R^{\prime \prime }_1,R_{-1})=(9,10)$. Moreover, $z^{\prime }$ is the only WE allocation which is supported by $p_{\min }(R^{\prime \prime }_1,R_{-1})$. Thus, $f(R^{\prime \prime }_1,R_{-1})=z^{\prime }$, and hence, $f_1(R^{\prime \prime }_1,R_{-1})=(b,10)\in o_1(R_{-1})$.

Substep C-3: $A_1(R)=a$.

Since $A_2(R)\ne \emptyset $ by Step B, $|A_1(R)|\le 1$. If $ A_1(R)=\emptyset $, then by Lemma 5, we have $f_1(R)=\varvec{0}$, and thus, $f_1(R^{\prime }_1,R_{-1})\mathrel {P_1}f_1(R)$, which contradicts strategy-proofness. Thus, $A_1(R)=a$ or b, and therefore, by (i) of Lemma 11, $f_1(R)=(a,9)$ or (b, 10). Since $(a,9)\mathrel {P_1} (b,10)$, (ii) of Lemma 11 implies $f_1(R)=(a,9)$. $\square $

Step D: f(R) is not efficient for R.

By $A_2(R)\ne \emptyset $ and $A_1(R)=a$, $A_2(R)=b$. By Lemma 6, $ t_2(R)\le V_2(b;\varvec{0})=12$. By Lemma 9, $t_2(R)\ge 0$.

Let $z\equiv ((A_i,t_i))_{i\in N}\in Z$ be such that

$$\begin{aligned} z_1=(\{a,b\}, 29),\ z_2=(\emptyset , -3),\text { and}\ z_3=f_3(R). \end{aligned}$$

Figure 7 illustrates z.

Since $V_1(\{a,b\};f_1(R))=V_1(\{a,b\};(a,9))=29$, it is easy to see that $ z_1\mathrel {I_1}f_1(R)$ and $z_3\mathrel {I_3}f_3(R)$. Also by $t_2(R)\ge 0$ and $A_2(R)=b$, $z_2=(\emptyset ,-3)\mathrel {I_2}(b,0) \mathrel {R_2}f_2(R)$. Moreover, by $t_1(R)=9$ and $t_2(R)\le 12$,

$$\begin{aligned} \sum _{i\in N}t_i=29-3+t_3(R)=26+t_3(R)>\sum _{i\in M}t_i(R), \end{aligned}$$

implying that f(R) is not efficient for R, a contradiction. $\square $

We emphasize the difference between a (direct) proof of the Corollary 1 that one might write, and the proof of the Theorem that we have shown. To prove the Corollary 1 directly, we can freely pick preference profiles in $\mathcal { R}^U\cup \mathcal {R}^M$ to derive a contradiction. On the other hand, in the proof of the Theorem, we may only choose preferences from $\mathcal {R} ^U\cup \{R_0\}$. Moreover, the preference relation $R_0$, which could be anything in $\mathcal {R}^M$, forces us to construct profiles depending on $ R_0$, further complicating the process.

In the above sketch, $R_0\in \mathcal {R}^M$ is assumed to be quasi-linear, but the basic logic of the sketch works even in the case $R_0\in \mathcal {R} ^M\backslash \mathcal {R}^{Q}$.

In the formal proof in the Appendix, we have six steps. Steps A, B, C, and D correspond to Steps 1, 3, 4, and 6, respectively, of the formal proof. Steps 2 and 5 of the formal proof are necessary only for the more general case, so they do not appear in the above sketch.

6 Concluding remarks

In this article, we have considered an object assignment problem with money where each agent can receive more than one object. We focused on domains that contain enough variety of unit-demand preferences and some multi-demand preferences. We studied allocation rules satisfying efficiency, strategy-proofness, individual rationality, and no subsidy for losers, and showed that if the domain contains enough variety of unit-demand preferences and at least one multi-demand preference relation, and if there are more agents than objects, then no rule satisfies the four properties. As discussed in Sect. 1, we have been motivated by the search for efficient and strategy-proof rules on a domain which is not quasi-linear or unit-demand. Our result establishes the difficulty of designing efficient and strategy-proof rules on such a domain. We state three remarks on our result.

Maximal domain. Some literature on strategy-proofness investigates the existence of maximal domains on which there are rules satisfying desirable properties.^{Footnote 16} A domain $\mathcal {R}^n$ is a maximal domain for a list of properties of rules if there is a rule on $\mathcal {R}^n$ satisfying the properties, and for each $\mathcal {R}'\supsetneq \mathcal {R}$, no rule on $(\mathcal {R}')^n$ satisfies the properties. Our result is rather closer to maximal domain results than impossibility results of the form of the Corollary 1. However, our result does not imply that the unit-demand domain is a maximal domain for the four properties in the Theorem, since we add only multi-demand preferences to the rich domains and derive the non-existence of rules satisfying the four properties. In fact, what domains including $(\mathcal {R}^U)^n$ are maximal domains for the four properties is an open question.

However, we are sure that $(\mathcal {R}^U)^n$ is not a maximal domain for the four properties. For example, consider $R_i$ in Example 3 and let $\mathcal {R}\equiv \mathcal {R}^U\cup \{R_i\}$. Since $R_i$ does not satisfy the unit-demand property, $\mathcal {R}\supsetneq \mathcal {R}^U$. Note that for each $R_j\in \mathcal {R}$, each $A_j\in \mathcal {M}$ with $|A_j|>1$ and each $t_j\in \mathbb {R}$, if $t_j\ge 0$, then there is $a\in A_j$ such that $(a,t_j)\mathrel {I_j}(A_j,t_j)$. Thus, since each agent never pays negative amount of money under the minimum price Walrasian rules, and since they satisfy the four properties on the unit-demand domain, they also satisfy the four properties on $\mathcal {R}^n$. Hence, $(\mathcal {R}^U)^n$ is not a maximal domain for the four properties.

Although we do not find maximal domains for the four properties, the multi-demand class includes most of natural preferences outside the unit-demand class. Thus, our result implies that on most of natural domains properly including the unit-demand domain, if there are more agents than objects, we have an impossibility of designing rules satisfying the four properties.

Other properties. Efficiency is not the only property studied in the literature on auction theory. For example, some authors study strategy-proof and individually rational rules that achieve as much revenue as possible. Since efficiency takes the auctioneer’s revenue into account, efficiency is closely related to maximizing the auctioneer’s revenue. However, there may exist strategy-proof and individually rational rules that is not efficient but achieve as much revenue as possible.^{Footnote 17}

While efficiency takes the auctioneer’s revenue into account, some authors study another efficiency notion that takes only agents’ preferences into account.^{Footnote 18} An allocation is efficient with no deficit if (i) the sum of payments is nonnegative, and (ii) no other allocation with nonnegative sum of payments makes each agent at least as well off and at least one agent better off. Notice that efficiency is implied by efficiency with no deficit.^{Footnote 19} Thus, the Theorem holds even if we replace efficiency by efficiency with no deficit.

Identical objects. Some literature on object assignment problems also study the case in which the objects are identical.^{Footnote 20} In this paper, we do not make this assumption. When objects are not identical, the domain includes a greater variety of preference profiles than when objects are identical. This variety plays an important role in our proof. Therefore, our theorem does not exclude the possibility that when objects are identical, multi-demand preferences can be added to the unit-demand domain without preventing the existence of rules satisfying the four properties.

Notes

See Saitoh and Serizawa (2008) for numerical examples.
Ausubel and Milgrom (2002) also discuss the importance of the analysis under non-quasi-linear preferences. Also see Sakai (2008) and Baisa (2013) for more examples of non-quasi-linear preferences.
For example, see Andersson and Svensson (2014), Andersson et al. (2015), and Tierney (2015).
Note that the unit-demand domain contains non-quasilinear preferences, and thus the result by Holmström (1979) does not apply
For example, see Gul and Stacchetti (1999, 2000), Bikhchandani and Ostroy (2002), Pápai (2003), Ausubel (2004, 2006), Mishra and Parkes (2007), Vries et al. (2007), and Sun and Yang (2006, 2009, 2014).
For example, Gibbard (1973), Satterthwaite (1975), etc.
Given a set X, |X| denotes the cardinality of X.
Gul and Stacchetti (1999) define the unit-demand property for quasi-linear preferences. In their model, a preference relation $R_i\in \mathcal {R}^Q$ satisfies the unit-demand property if for each $A_i\in \mathcal {M}$ with $|A_i|>1$, $v_i(A_i)=\max _{a\in A_i}v_i(a)$.
In Gul and Stacchetti (1999), this notion is called $k-$ satiation.
For example, Alkan and Gale (1990), Demange and Gale (1985), etc.
Precisely, Alkan and Gale (1990) show the non-emptiness of the core in a two-sided matching model. However, the two-sided matching model includes the unit-demand model, and in the unit-demand model, non-emptiness of the core is equivalent to the existence of a Walrasian equilibrium.
Fact 1 is also shown by other authors. See, for example, Quinzii (1984), Gale (1984).
For each $p,p^{\prime }\in \mathbb {R}^m$, $p\le p^{\prime }$ if and only if for each $i\in \{1,\dots ,m\}$, $p^i\le p^{\prime i}$.
Notice that in each class of preferences satisfying the richness, there exists such a preference relation.
In this sketch, we assume that $M=\{a,b\}$ and $R_0\in \mathcal {R}^{Q}$ for the simplicity of expression. For a general multi-demand preference relation $R_0$, the RHS of the first inequality is set as the maximal difference between various $t_1$ in $[0,V_1(\{a,b\};\varvec{0})]$ and the valuation of empty set at $(\{a,b\},t_1)$ for $R_1$, i.e.,
$$\begin{aligned} \max _{t_1\in [ 0,V_1(\{a,b\};\varvec{0})]}\{t_1- V_1(\emptyset ;(\{a,b\},t_1))\}. \end{aligned}$$
For a general set M, the RHS is defined as $\overline{t}_1$ in the Appendix.
For a general multi-demand preference relation $R_0$, the RHS of the second inequality is set as the minimum value of the marginal valuations of the second object, i.e.,
$$\begin{aligned} \min \left\{ \min _{t_1\in [ 0,V_1(\{a\};\varvec{0})]} \{V_1(\{a,b\};(a,t_1))-t_1\},\min _{t_1\in [ 0,V_1(\{b\};\varvec{0})]}\{V_1(\{a,b\};(b,t_1))-t_1\}\right\} . \end{aligned}$$
For a general set M of objects, the RHS of the second inequality is defined as $\underline{t}_1$ in the Appendix.
For example, see Ching and Serizawa (1998), Berga and Serizawa (2000), Massó and Neme (2001), Ehlers (2002), etc.
For the single object case with quasi-linear preferences, Myerson type rules are not necessarily efficient but maximize the auctioneer’s revenue. See Myerson (1981).
For example, see Sprumont (2013).
The proof is as follows. Let $R\equiv (R_i)_{i\in N}$ be a preference profile. Suppose there is an allocation $z\equiv ((A_i,t_i))_{i\in N}$ that is efficiency with no deficit for R but not efficient for R. Then, there is an allocation $z'\equiv ((A'_i,t'_i))_{i\in N}$ such that
$$\begin{aligned} \text {for each }i\in N,\ z'_i\mathrel {R_i}z_i,\text { for some }j\in N,\ z'_j\mathrel {P_j}z_j,\text { and }\sum _{i\in N}t'_i\ge \sum _{i\in N}t_i. \end{aligned}$$
By condition (i) of efficiency with no deficit, we have $\sum _{i\in N}t_i\ge 0$. Thus, $\sum _{i\in N}t'_i\ge 0$. However, this implies that z is not efficient with no deficit for R, a contradiction.
For example, see Saitoh and Serizawa (2008), Ashlagi and Serizawa (2012), Adachi (2014), etc.
See Debreu (1959).
See Berge (1963).

References

Adachi T (2014) Equity and the Vickrey allocation rule on general preference domains. Social Choice Welfare 42:813–830
Article Google Scholar
Andersson T, Svensson L-G (2014) Non-manipulable house allocation with rent control. Econometrica 82:507–539
Article Google Scholar
Andersson T, Ehlers L, Svensson L-G (2015) Transferring ownership of public housing to existing tenants: a market design approach. J Econ Theory 165:643–671
Article Google Scholar
Alkan A, Gale D (1990) The core of the matching game. Games Econ Behav 2:203–212
Article Google Scholar
Ashlagi I, Serizawa S (2012) Characterizing Vickrey allocation rule by anonymity. Social Choice Welfare 38:531–542
Article Google Scholar
Ausubel LM (2004) An efficient ascending-bid auction for multiple objects. Am Econ Rev 94:1452–1475
Article Google Scholar
Ausubel LM (2006) An efficient dynamic auction for heterogeneous commodities. Am Econ Rev 96:602–629
Article Google Scholar
Ausubel LM, Milgrom PR (2002) Ascending auctions with package bidding. Front Theor Econ 1:1–42
Article Google Scholar
Baisa B (2013) Auction design without quasilinear preferences. Theor Econ (forthcoming)
Berga D, Serizawa S (2000) Maximal domain for strategy-proof rules with one public good. J Econ Theory 90:39–61
Article Google Scholar
Berge C (1963) Topological spaces. Macmillan, New York
Google Scholar
Bikhchandani S, Ostroy JM (2002) The package assignment model. J Econ Theory 107:377–406
Article Google Scholar
Ching S, Serizawa S (1998) A maximal domain for the existence of strategy-proof rules. J Econ Theory 78:157–166
Article Google Scholar
Clarke EH (1971) Multipart pricing of public goods. Public Choice 11:17–33
Article Google Scholar
de Vries S, Schummer J, Vohra RV (2007) On ascending Vickrey auctions for heterogeneous objects. J Econ Theory 132:95–118
Article Google Scholar
Debreu G (1959) Theory of value: an axiomatic analysis of economic equilibrium. Yale University Press, New Haven
Google Scholar
Demange G, Gale D (1985) The strategy structure of two-sided matching markets. Econometrica 53:873–888
Article Google Scholar
Ehlers L (2002) Coalitional strategy-proof house allocation. J Econ Theory 105:298–317
Article Google Scholar
Gale D (1984) Equilibrium in a discrete exchange economy with money. Int J Game Theory 13:61–64
Article Google Scholar
Gibbard A (1973) Manipulation of voting schemes: a general result. Econometrica 41:587–601
Article Google Scholar
Groves T (1973) Incentives in teams. Econometrica 41:617–631
Article Google Scholar
Gul F, Stacchetti E (1999) Walrasian equilibrium with gross substitutes. J Econ Theory 87:95–124
Article Google Scholar
Gul F, Stacchetti E (2000) The English auction with differentiated commodities. J Econ Theory 92:66–95
Article Google Scholar
Holmström B (1979) Groves’ scheme on restricted domains. Econometrica 47:1137–1144
Article Google Scholar
Marshall A (1920) Principles of economics. Macmillan, London
Google Scholar
Massó J, Neme A (2001) Maximal domain of preferences in the division problem. Games Econ Behav 37:367–387
Article Google Scholar
Mishra D, Parkes DC (2007) Ascending price Vickrey auctions for general valuations. J Econ Theory 132:335–366
Article Google Scholar
Morimoto S, Serizawa S (2015) Strategy-proofness and efficiency with non-quasi-linear preference: a characterization of minimum price Walrasian rule. Theor Econ 10:445–487
Article Google Scholar
Myerson RB (1981) Optimal auction design. Math Operat Res 6:58–73
Article Google Scholar
Pápai S (2003) Groves sealed bid auctions of heterogeneous objects with fair prices. Social Choice Welfare 20:371–385
Article Google Scholar
Quinzii M (1984) Core and competitive equilibria with indivisibilities. Int J Game Theory 13:41–60
Article Google Scholar
Sakai T (2008) Second price auctions on general preference domains: two characterizations. Econ Theory 37:347–356
Article Google Scholar
Saitoh H, Serizawa S (2008) Vickrey allocation rule with income effect. Econ Theory 35:391–401
Article Google Scholar
Satterthwaite MA (1975) Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions. J Econ Theory 10:187–217
Article Google Scholar
Sprumont Y (2013) Constrained-optimal strategy-proof assignment: beyond the groves mechanisms. J Econ Theory 148:1102–1121
Sun N, Yang Z (2006) Equilibria and indivisibilities: Gross substitutes and complements. Econometrica 74:1385–1402
Article Google Scholar
Sun N, Yang Z (2009) Double-track adjustment process for discrete markets with substitutes and complements. Econometrica 77:933–952
Article Google Scholar
Sun N, Yang Z (2014) An efficient and incentive compatible dynamic auction for multiple complements. J Polit Econ 122:422–466
Article Google Scholar
Tierney R (2015) Managing multiple commons: strategy-proofness and min-price Walras. Mimeo, New York
Google Scholar
Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Finance 16:8–37
Article Google Scholar

Download references

Acknowledgments

The authors are grateful to the editor, the associate editor and two anonymous referees for their many detailed and helpful comments. The preliminary version of this article was presented at the IDGP 2015 Workshop, the 2015 Conference on Economic Design, and the II MOMA Meeting. The authors thank participants at those conferences for their comments. They are also grateful to seminar participants at Shanghai University of Finance and Economics, University of Calfornia, Berkeley, and Waseda University for their comments. The authors specially thank Yuichiro Kamada, Fuhito Kojima, James Schummer, William Thomson, and Ryan Tierney for their detailed comments. This research was supported by the Joint Usage/Research Center at ISER, Osaka University. The authors acknowledge the Japan Society for the Promotion of Science (Kazumura, 14J05972; Serizawa, 15H03328 and 15H05728).

Author information

Authors and Affiliations

Graduate School of Economics, Osaka University, 1-7 Machikaneyama, Toyonaka, Osaka, 560-0043, Japan
Tomoya Kazumura
Institute of Social and Economic Research, Osaka University, 6-1, Mihogaoka, Ibaraki, Osaka, 567-0047, Japan
Shigehiro Serizawa

Authors

Tomoya Kazumura
View author publications
You can also search for this author in PubMed Google Scholar
Shigehiro Serizawa
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tomoya Kazumura.

Appendix: Proofs

1.1 A Proofs of Lemmas

Proof of Lemma 1:

First, we define $V_i(A'_i;(A_i,t_i))$ for each $t_i\in \mathbb {R}$. Take any $t_i\in \mathbb {R}$. Let $B\equiv \{t'_i\in \mathbb {R}:(A_i',t'_i)\mathrel {R_i}(A_i,t_i)\}$ and $W\equiv \{t'_i\in \mathbb {R}:(A_i,t_i)\mathrel {R_i}(A_i',t'_i)\}$. By possibility of compensation, $B\ne \emptyset $ and $W\ne \emptyset $. By continuity, B and W are both closed. By money monotonicity, B is bounded above and W is bounded below. Thus, $\overline{t}_i\equiv \max B$ and $\underline{t}_i\equiv \min W$ exist.

Suppose $\overline{t}_i>\underline{t}_i$. Then, by money monotonicity, $(A_i',\underline{t}_i)\mathrel {P_i}(A_i',\overline{t}_i)\mathrel {R_i}(A_i,t_i)$. This implies $\underline{t}_i\notin W$. This contradicts $\underline{t}_i= \min W$. Thus, $\overline{t}_i\le \underline{t}_i$.

Suppose $\overline{t}_i<\underline{t}_i$. Let $t'_i\in (\overline{t}_i,\underline{t}_i)$. By $t'_i<\underline{t}_i$, $t'_i\notin W$, that is, $(A_i,t_i)~R_{i}~(A_{i}^{\prime },t_{i}^{\prime })$ does not hold. By $t'_i>\overline{t}_i$, $t'_i\notin B$, that is, $(A_{i}^{\prime },t_{i}^{\prime })~R_{i}~(A_i,t_i)$ does not hold. This contradicts completeness. Thus, $\overline{t}_i=\underline{t}_i$.

Let $V_i(A'_i;(A_i,t_i))\equiv \overline{t}_i=\underline{t}_i$. Then, $B\cap W=\{V_i(A'_i;(A_i,t_i))\}$ and so $(A_i',V_i(A'_i;(A_i,t_i)))\mathrel {R_i}(A_i,t_i)$ and $(A_i,t_i)\mathrel {R_i}(A_i',V_i(A'_i;(A_i,t_i))),$ which implies $(A_i',V_i(A'_i;(A_i,t_i)))\mathrel {I_i}z_i$. Since $B\cap W$ is a singleton, such $V_i(A'_i;(A_i,t_i))$ is unique.

Finally, we show that the function $V_{i}(A_{i}^{\prime };(A_{i},\cdot ))$ is continuous. Note that it is sufficient to show that for each $s_{i}\in \mathbb {R}$, the function’s inverse images of $(-\infty ,s_{i}]$ and $[s_{i},+\infty )$ are both closed.^{Footnote 21} Take any $s_{i}\in \mathbb {R}$. Let $t_{i}\equiv V_{i}(A_{i};(A_{i}^{\prime },s_{i}))$. Then, by money monotonicity and continuity of $R_{i}$, the inverse images of $(-\infty ,s_{i}]$ and $[s_{i},+\infty )$ are $(-\infty ,t_{i}]$ and $[t_{i},+\infty )$ respectively, which are closed. Thus, $V_{i}(A_{i}^{\prime };(A_{i},\cdot ))$ is continuous. $\square $

Proof of (i) of Lemma 2:

Suppose that there is $(A_i,t_i)\in D(R_i,p)$ such that $|A_i|>1$. By $R_i\in \mathcal {R}^U$, there is $a\in A_i$ such that $(a,t_i)\mathrel {R_i}(A_i,t_i)$. By $(A_i,t_i)\in B(p)$, $t_i=\sum _{b\in A_i}p^b$. By $p\in \mathbb {R}^m_{++}$ and $|A_i|>1$, $p^a<\sum _{b\in A_i}p^b=t_i$. Thus, by first object monotonicity,

$$\begin{aligned} (a,p^a)\mathrel {P_i}(a,t_i)\mathrel {R_i}(A_i,t_i), \end{aligned}$$

which contradicts $(A_i,t_i)\in D(R_i,p)$. $\square $

Proof of (ii) of Lemma 2:

Let $A'_i\in \mathcal {M}$. If $|A'_i|\le 1$, then by the def. of $A_i$, $(A_i,\sum _{a\in A_i}p^a)\mathrel {R_i}(A'_i,\sum _{a\in A'_i}p^a)$. Suppose $|A'_i|>1$. By $R_i\in \mathcal {R}^U$, there is $a\in A'_i$ such that $(a,\sum _{b\in A'_i}p^b)\mathrel {R_i}(A_i,\sum _{b\in A'_i}p^b)$. By $p\in \mathbb {R}^m_{+}$ and money monotonicity, $(a,p^a)\mathrel {R_i}(a,\sum _{b\in A'_i}p^b)\mathrel {R_i}(A'_i,\sum _{b\in A'_i}p^b)$. Thus, by the def. of $A_i$,

$$\begin{aligned} \left( A_i,\sum _{b\in A_i}p^b\right) \mathrel {R_i}(a,p^a)\mathrel {R_i}\left( A'_i,\sum _{b\in A'_i}p^b\right) . \end{aligned}$$

Thus, $(A_i,\sum _{b\in A_i}p^b)\in D(R_i,p)$. $\square $

Proof of (i) of Lemma 3:

By contradiction, suppose that $n>m$ and $p^a=0$ for some $a\in M$. Then, by first object monotonicity, for each $i\in N$, $(a,p^a)\mathrel {P_i}\varvec{0}$. Thus, for each $i\in N$, $\varvec{0}\notin D(R_i,p)$, which implies that for each $((A,t),p)\in W(R)$, $A_i\ne \emptyset $. However, this contradicts $n>m$.$\square $

Proof of (ii) of Lemma 3:

By $p\in P(R)$, there is $(A,t)\in Z$ such that $((A,t),p)\in W(R)$.

Let $N^*=\{i\in N: |A_i|>1\}$ and $i\in N^*$. By $R_i\in \mathcal {R}^U$, there is $a\in A_i$ such that $(a,t_i)\mathrel {R_i}(A_i,t_i)$. By $(A_i,t_i)\in B(p)$, $t_i=\sum _{b\in A_i}p^b$. By $p\in \mathbb {R}^m_+$, $p^a\le \sum _{b\in A_i}p^b=t_i$. Thus, by money monotonicity, $(a,p^a)\mathrel {R_i}(a,t_i)\mathrel {R_i}(A_i,t_i)$, which implies $(a,p^a)\in D(R_i,p)$ and $p^{b}=0$ for each $b\in A_{i}\ \{a\}$. Hence, for each $i\in N^*$, there is $a_i\in A_i$ such that $(a_i,p^{a_i})\in D(R_i,p)$ and $p^{b}=0$ for each $b\in A_{i}\backslash \{a_{i}\}$.

Let $z'\in Z$ be such that for each $i\in N^*$, $z'_i=(a_i,p^{a_i})$, and for each $i\in N{\setminus } N^*$, $z'_i=(A_i,t_i)$. Then, each agent receives at most one object at $z'$, and clearly, $(z',p)\in W(R)$.$\square $

Proof of Lemma 4:

Suppose by contradiction that $R_i\in \mathcal {R}^U$ and $|A_i(R)|>1$. Then, there is $a\in A_i(R)$ such that $(a,t_i(R))\mathrel {R_i}f_i(R)$. By $|A_i(R)|>1$, there is $b\in A_i(R)$ such that $b\ne a$.

By $n>m$, there is $j\in N{\setminus } \{i\}$ such that $A_j(R)=\emptyset $. Let $z\equiv ((A_k,t_k))_{k\in N}\in Z$ be such that

$$\begin{aligned}&z_i=(a,t_i(R)),\\&z_j=(b, t_j(R)),\text { and}\\&z_k=f_k(R)\text { for each }k\in N{\setminus } \{i,j\}. \end{aligned}$$

Clearly, $\sum _{k\in N}t_k=\sum _{k\in N}t_k(R)$, and for each $k\in N {\setminus }\{i,j\}$, $z_k\mathrel {I_k}f_k(R)$. Moreover, $z_i=(a,t_i(R))\mathrel {R_i}f_i(R)$, and by first object monotonicity, $z_j=(b,t_j(R))\mathrel {P_j}f_j(R)$. This contradicts efficiency. $\square $

Proof of Lemma 8:

Suppose by contradiction that $V_i(A_i;f_i(R))+V_j(A_j;f_j(R))> t_i(R)+t_j(R)$. Let $z'\in Z$ be such that $z'_i=(A_i,V_i(A_i;f_i(R)))$, $z'_j=(A_j,V_j(A_j;f_j(R)))$, and for each $k\in N{\setminus }\{i,j\}$, $z'_k=f_k(R)$. Then $z'_k\mathrel {I_k}f_k(R)$ for each $k\in N$. Moreover, $V_i(A_i;f_i(R))+V_j(A_j;f_j(R))+\sum _{k\ne i,j}t_k(R) >\sum _{k\in N}t_k(R)$. By Remark 2, this contradicts efficiency. $\square $

Proof of Lemma 9:

(Fig. 8) Suppose by contradiction that $t_i(R)<V'_i(A_i(R);\varvec{0})$. If $A_i(R)=\emptyset $, then $t_i(R)<V'_i(\emptyset ;\varvec{0})=0$, which contradicts no subsidy for losers. Hence, $A_i(R)\ne \emptyset $.

Next, we show $A_i(R'_i,R_{-i})\ne \emptyset $. Suppose not. Then, by Lemma 5, $f_i(R'_i,R_{-i})=\varvec{0}$. By $t_i(R)<V'_i(A_i(R);\varvec{0})$, $f_i(R)\mathrel {P'_i}\varvec{0}=f_i(R'_i,R_{-i})$, which contradicts strategy-proofness. Hence $A_i(R'_i,R_{-i})\ne \emptyset $.

By $R'_i\in \mathcal {R}^U$, $A_i(R'_i,R_{-i})\ne \emptyset $, and Lemma 4, there is $a\in M$ such that $A_i(R'_i,R_{-i})=a$. Since $n>m$ and $A_i(R'_i,R_{-i})\ne \emptyset $, there is $j\in N{\setminus } \{i\}$ such that $A_j(R'_i,R_{-i})=\emptyset $. By Lemma 5, $f_j(R'_i,R_{-i})=\varvec{0}$. Thus, letting $s_i\equiv V'_i(\emptyset ;f_i(R'_i,R_{-i}))$,

This contradicts Lemma 8. $\square $

1.2 B Proof of Theorem

The proof of the Theorem has six steps.

Step 1: Constructing preferences.

Let $R_1\equiv R_{0}$. For each $a\in M$, let $\mathcal {M}_a\equiv \{A_1\in \mathcal {M}:a\in A_1\}$.

Claim 1: There is $\underline{t}_1\in \mathbb {R}$ such that $\underline{t}_1>0$ and

$$\begin{aligned} \underline{t}_1=\min _{a\in M}\min _{t_1\in [ 0,V_1(\{a\};\varvec{0})]}\max _{A_1\in \mathcal {M}_a}\{V_1(A_1;(a,t_1))-t_1\}. \end{aligned}$$

Proof

For each $a\in M$, let $g^a$ be a function on $\mathcal {M}_a\times \mathbb {R}$ such that for each $A_1\in \mathcal {M}_a$ and each $t_1\in \mathbb {R}$, $g^a(A_1,t_1)=V_1(A_1;(a,t_1))-t_1$, and let $g^a_{\max }$ be a function on $\mathbb {R}$ such that for each $t_1\in \mathbb {R}$, $g^a_{\max }(t_1)=\max _{A_1\in \mathcal {M}_a}g^a(A_1,t_1)$.

Note that by Lemma 1, for each $a\in M$, and each $A_1\in \mathcal {M}_a$, $g^a(A_1,\cdot )$ is continuous in $\mathbb {R}$. Thus, Berge’s maximum theorem implies that for each $a\in M$, $g^a_{\max }(\cdot )$ is also continuous in $\mathbb {R}$.^{Footnote 22} For each $a\in M$, since $[0,V_1(a;\varvec{0})]$ is compact, there is $\hat{t}_1^a\in [0,V_1(a;\varvec{0})]$ such that $g^a_{\max }(\hat{t}_1^a)=\min _{t_1\in [0,V_1(a;\varvec{0})]}g^a_{\max }(t_1)$. For each $a\in M$, let $\underline{t}_1^a\equiv g^a_{\max }(\hat{t}_1^a)$. Since M is finite, $\min \{\underline{t}_1^a:a\in M\}$ exists. Let $\underline{t}_1\equiv \min \{\underline{t}_1^a:a\in M\}$. Then,

$$\begin{aligned} \underline{t}_1=\min _{a\in M}\min _{t_1\in [0,V_1(a;\varvec{0})]}\max _{A_1\in \mathcal {M}_a}\{V_1(A_1;(a,t_1))-t_1\}. \end{aligned}$$

Next, we show ${\underline{t}}_1>0$. Let $a\in M$ be such that $\underline{t}_1=\max _{A_1\in \mathcal {M}_a}\{V_1(A_1;(a,\hat{t}_1^a))-\hat{t}_1^a\}$. By $R_1\in \mathcal {R}^M$, there is $\hat{A}_1\in \mathcal {M}_a$ such that $(\hat{A}_1,\hat{t}_1^a)\mathrel {P_1}(a,\hat{t}_1^a)$, that is, $V_1(\hat{A}_1;(a,\hat{t}_1^a))-\hat{t}_1^a>0$. Thus,

$$\begin{aligned} \underline{t}_1=\max _{A_1\in \mathcal {M}_a}\{V_1(A_1;(a,\hat{t}_1^a))-\hat{t}_1^a\}\ge V_1(\hat{A}_1;(a,\hat{t}_1^a))-\hat{t}_1^a>0. \end{aligned}$$

$\square $

By Claim 1, there is $d_*\in \mathbb {R}_{++}$ such that $5(m-1)d_*<\underline{t}_1$ and for each $a\in M$, $(a,3d_*)\mathrel {P_1}\varvec{0}$. Let $a^*\in M$ be such that for each $a\in M{\setminus } \{a^*\}$, $(a^*,3d_*)\mathrel {R_1}(a,3d_*)$. Without loss of generality, assume $a^*=1$.

Since $\mathcal {R}$ is rich, there is $R'_1\in \mathcal {R}\cap \mathcal {R}^U$ such that for each $a\in M$ and each $t_1\in \mathbb {R}$, $V'_1(a;(\emptyset ,t_1))=\frac{d_*}{2}+t_1$. Let

$$\begin{aligned} s^*_1&\equiv \min \left\{ 0, \min _{A_1\in \mathcal {M}{\setminus } \{\emptyset \}}V'_1(A_1;\varvec{0})\right\} ,\text { and}\\ \mathcal {M}(R_1,s^*_1)&\equiv \{A_1\in \mathcal {M}{\setminus } \{\emptyset \}:V_1(A_1;\varvec{0})\ge s^*_1\}. \end{aligned}$$

Note that by first object monotonicity, $\mathcal {M}(R_1,s^*_1)\ne \emptyset $.

Claim 2: There is $\overline{t}_1\in \mathbb {R}$ such that $\overline{t}_1\ge \underline{t}_1$ and

$$\begin{aligned} \overline{t}_1=\max _{A_1\in \mathcal {M}(R_1,s^*_1)}\max _{t_1\in [s^*_1,V_1(A_{1};\varvec{0})]}\{t_1-V_1(\emptyset ;(A_1,t_1))\}. \end{aligned}$$

Proof

For each $A_1\in \mathcal {M}(R_1,s^*_1)$, let $g^{A_1}$ be a function on $\mathbb {R}$ such that for each $t_1\in \mathbb {R}$, $g^{A_1}(t_1)=t_1-V_1(\emptyset ;(A_1,t_1))$. Note that by Lemma 1, for each $A_1\in \mathcal {M}(R_1,s^*_1)$, $g^{A_1}$ is continuous in $\mathbb {R}$. For each $A_1\in \mathcal {M}(R_1,s^*_1)$, since $[s^*_1,V_1(A_1;\varvec{0})]$ is compact, there is $\hat{t}^{A_1}_1\in [s^*_1,V_1(A_1;\varvec{0})]$ such that $g^{A_1}(\hat{t}^{A_1}_1)=\max _{t_1\in [s^*_1,V_1(A_1;\varvec{0})]}g^{A_1}(t_1)$. For each $A_1\in \mathcal {M}(R_1,s^*_1)$, let $\overline{t}^{A_1}=g^{A_1}(\hat{t}^{A_1}_1)$. Since $\mathcal {M}(R_1,s^*_1)$ is finite, $\max \{\overline{t}^{A_1}:A_1\in \mathcal {M}(R_1,s^*_1)\}$ exists. Let $\overline{t}_1\equiv \max \{\overline{t}^{A_1}:A_1\in \mathcal {M}(R_1,s^*_1)\}$. Then,

$$\begin{aligned} \overline{t}_1=\max _{A_1\in \mathcal {M}(R_1,s^*_1)}\max _{t_1\in [s^*_1,V_1(A_{1};\varvec{0})]}\{t_1-V_1(\emptyset ;(A_1,t_1))\}. \end{aligned}$$

Next, we show $\overline{t}_1\ge \underline{t}_1$. Let $a\in M $, $t_1\in [ 0,V_1(a;\varvec{0})]$ and $A_1\in \mathcal {M}_a$ be such that $\underline{t}_1=V_1(A_1;(a,t_1))-t_1$. Let $\hat{t}_1\equiv V_1(A_1;(a,t_1))$. Since $V_1(\emptyset ;(A_1,\hat{t}_1))=V_1(\emptyset ;(a,t_1))$ and since first object monotonicity implies $t_1-V_1(\emptyset ;(a,t_1))> 0$,

$$\begin{aligned} \hat{t}_1-V_1(\emptyset ;(A_1,\hat{t}_1))= & {} V_1(A_1;(a,t_1))-t_1+t_1-V_1(\emptyset ;(a,t_1))\\> & {} V_1(A_1;(a,t_1))-t_1. \end{aligned}$$

By $t_1\le V_1(a;\varvec{0})$, $\hat{t}_1\le V_1(A_1;\varvec{0})$. By $t_1\ge 0$, $\underline{t}_1>0$, and $s^*_1\le 0$, $\hat{t}_1=\underline{t}_1+t_1> 0\ge s^*_1$. Thus, $s^*_1\le \hat{t}_1\le V_1(A_1;\varvec{0})$. This implies $A_1\in \mathcal {M}(R_1,s^*_1)$, and thus,

$$\begin{aligned} \overline{t}_1= & {} \max _{A'_1\in \mathcal {M}(R_{1},s_{1}^{*})}\max _{t'_1\in [ s_{1}^{*},V_1(A'_1;\varvec{0})]}\{t'_1-V_1(\emptyset ;(A'_1,t'_1))\} \\\ge & {} \hat{t}_1-V_1(\emptyset ;(A_1,\hat{t}_1)) \\\ge & {} V_1(A_1;(a,t_1))-t_1=\underline{t}_1. \end{aligned}$$

$\square $

Let $d^*\in \mathbb {R}_{++}$ be such that $d^*>\overline{t}_1$. Note that by Claim 2, $5(m-1)d_*<\underline{t}_1\le \overline{t}_1<d^*$. Since $\mathcal {R}$ is rich, for each $i\in \{2,\dots , m\}$, there is $R_i\in \mathcal {R}\cap \mathcal {R}^U$ satisfying the following conditions:

Since $\mathcal {R}$ is rich, for each $i\in N{\setminus } \{1,\dots , m\}$, there is $R_i\in \mathcal {R}\cap \mathcal {R}^U$ such that for each $a\in M$ and each $t_i\in \mathbb {R}$,

$$\begin{aligned} V_i(a;(\emptyset ,t_i))=3d_*+t_i. \end{aligned}$$

Denote $R\equiv (R_1,\dots , R_n)$. Figure 9 illustrates $R_i$ and $R_j$, where $i\in \{2,\dots , m\}$ and $j\in \{m+1,\dots , n\}$.

Notice that for each $a\in M$ and each $t_1\in \mathbb {R}$,

$$\begin{aligned} V'_1(a;(\emptyset ,t_1))-t_1=\frac{d_*}{2}<\min _{i\in N\setminus \{1\}}V_i(a;\varvec{0}). \end{aligned}$$

Thus, by Lemma 9, $t_1(R)\ge V'_1(A_1(R);\varvec{0})\ge s^*_1$. $\blacksquare $

Step 2: For each $i\in \{2,\dots ,m\}$, $V_i(\emptyset ;f_i(R))\ge -d_*$.

Let $i\in \{2,\dots ,m\}$. If $A_i(R)=\emptyset $, then by Lemma 5, $V_i(\emptyset ;f_i(R))=t_i(R)=0>-d_*$. Suppose $A_i(R)\ne \emptyset $. By $R_i\in \mathcal {R}^U$ and Lemma 4, there is $a\in M$ such that $A_i(R)=a$. Thus, Lemma 9 implies $t_i(R)\ge 0$.

If $a=i$, then by money monotonicity, $(i,0)\mathrel {R_i}f_i(R)$, and thus, by ib, $V_i(\emptyset ;f_i(R))\ge V_i(\emptyset ;(i,0))=-d_*$. If $a\ne i$, then by ic,

$$\begin{aligned} V_i(a;(i,0))<V_i(a;(i,3d_*))<0\le t_i(R), \end{aligned}$$

which implies $(i,0)\mathrel {P_i}f_i(R)$, and thus, by ib $V_i(\emptyset ;f_i(R))> V_i(\emptyset ;(i,0))=-d_*$. $\blacksquare $

Step 3: For each $i\in \{2,\dots ,m\}$, $A_i(R)\ne \emptyset $.

Suppose by contradiction that there is an agent $i\in \{2,\dots , m\}$ such that $A_i(R)=\emptyset $. By Lemma 5, $t_i(R)=0$. By Lemma 7, there is an agent $j\in N{\setminus } \{i\}$ such that $i-1\in A_j(R)$. We show the following claim.

Claim 1: $t_j(R)-V_j(\emptyset ;f_j(R))<d^*$.

Proof

We have three cases.

Case 1: $j=1$. By Lemma 6 and Lemma 9, $s^*_1\le t_1(R)\le V_1(A_1(R);\varvec{0})$, implying $A_1(R)\in \mathcal {M}(R_1,s^*_1)$. Thus, by the def. of $\overline{t}_1$,

$$\begin{aligned} t_1(R)-V_1(\emptyset ;f_1(R))\le \overline{t}_1<d^*. \end{aligned}$$

Case 2: $j\in \{2,\dots , m\}$. By $R_j\in \mathcal {R}^U$ and Lemma 4, $A_j(R)=i-1$. By Lemma 6, $t_j(R)\le V_j(i-1;\varvec{0})$. Since $j-1\ne i-1$, $V_j(i-1;\varvec{0})=4d_*$ or $d_*$. Thus, $V_j(i-1;\varvec{0})\le 4d_*$. Moreover, by Step 2, $V_j(\emptyset ;f_j(R))\ge -d_* $. Therefore, by $5d_*<5(m-1)d_*<d^*$,

$$\begin{aligned} t_j(R)-V_j(\emptyset ;f_j(R))\le V_j(i-1;\varvec{0})+d_*\le 5d_*<d^*. \end{aligned}$$

Case 3: $j\in \{m+1,\dots , n\}$. By $R_j\in \mathcal {R}^U$ and Lemma 4, $A_j(R)=i-1$. Let $t^*_j\equiv V_j(\emptyset ;f_j(R))$. By the def. of $R_j$ and $3d_*<5(m-1)d_*<d^*$,

$$\begin{aligned} t_j(R)-V_j(\emptyset ;f_j(R))=V_j(i-1;(\emptyset ,t^*_j))-t^*_j=3d_*<d^*. \quad \end{aligned}$$

$\square $

By $f_i(R)=\varvec{0}$, $V_i(i-1;f_i(R))=V_i(i-1;\varvec{0})=d^*$. Thus, by Claim 1,

$$\begin{aligned} V_i(i-1;f_i(R))+V_j(\emptyset ;f_j(R))>d^*+t_j(R)-d^*=t_i(R)+t_j(R). \end{aligned}$$

This contradicts Lemma 8. $\blacksquare $

Step 4: $A_1(R)=1$.

First we show the following claim.

Claim 1: For each $a\in M$, there is $t(a)\in \mathbb {R}$ such that $(a,t(a))\in o_1(R_{-1})$ and

$$\begin{aligned} t(a) {\left\{ \begin{array}{ll} {\le } 3d_*&{}\text {if }a=1,\\ {>}3d_*&{}\text {otherwise}. \end{array}\right. } \end{aligned}$$

Proof

Let $a\in M$. Since $\mathcal {R}$ is rich, there is $R''_1\in \mathcal {R}\cap \mathcal {R}^U$ such that

Figure 10 illustrates $R''_1$.

By $(R''_1,R_{-1})\in (\mathcal {R}^U)^n$ and Lemma 10, $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$. Let $p\equiv p_{\min }(R''_1,R_{-1})$. By $(R''_1,R_{-1})\in (\mathcal {R}^U)^n$ and Lemma 4, for each $i\in N$, $|A_i(R''_1,R_{-1})|\le 1$. In the following three paragraphs, we show $(a,p^a)\in o_1(R_{-1})$.

First, suppose $A_1(R''_1,R_{-1})=\emptyset $. By Lemma 5, $f_1(R''_1,R_{-1})=\varvec{0}$. By $A_1(R''_1,R_{-1})=\emptyset $ and Lemma 7, there is an agent $i\in N{\setminus } \{1\}$ such that $A_i(R''_1,R_{-1})=a$. Since $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$, $t_i(R''_1,R_{-1})=p^a$. By Lemma 6, $p^a=t_i(R''_i,R_{-i})\le V_i(a;\varvec{0})$. Since $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$, $f_1(R''_1,R_{-1})=\varvec{0}\in D(R''_1,p)$, and thus, $\varvec{0}\mathrel {R''_1}(a,p^a)$. Therefore,

$$\begin{aligned} V''_1(a;\varvec{0})\le p^a\le V_i(a;\varvec{0}). \end{aligned}$$

This contradicts $1a''$. Hence, $A_1(R''_1,R_{-1})\ne \emptyset $.

Next, suppose that for some $b\in M{\setminus } \{a\}$, $A_1(R''_1,R_{-1})=b$. Since $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$, $t_1(R''_1,R_{-1})=p^b$. By Lemma 6, $p^b=t_1(R''_1,R_{-1})\le V''_1(b;\varvec{0})$. By $A_1(R''_1,R_{-1})\ne \emptyset $ and $n>m$, there is an agent $i\in N{\setminus } \{1\}$ such that $A_i(R''_1,R_{-1})=\emptyset $. By Lemma 5, $f_i(R''_1,R_{-1})=\varvec{0}$. Since $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$, $f_i(R''_1,R_{-1})=\varvec{0}\in D(R_i,p)$, and thus, $\varvec{0}\mathrel {R_i}(b,p^b)$. Therefore,

$$\begin{aligned} V_i(b;\varvec{0})\le p^b\le V''_1(b;\varvec{0}). \end{aligned}$$

This contradicts $1b''$. Thus for each $b\in M{\setminus } \{a\}$, $A_1(R''_1,R_{-1})\ne b$.

By $A_1(R''_1,R_{-1})\ne \emptyset $, $A_1(R''_1,R_{-1})\ne b$ for each $b\in M{\setminus }\{a\}$, and $|A_1(R''_1,R_{-1})|\le 1$, we conclude that $A_1(R''_1,R_{-1})=a$. Since $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$, $t_1(R''_1,R_{-1})=p^a$. Hence, $(a,p^a)\in o_1(R_{-1})$.

Next, we show that $p^a\le 3d_*$ if $a=1$, and $p^a> 3d_*$ otherwise.

Case 1: $a=1$. Let $z\in Z$ be such that for each $i\in N$,

$$\begin{aligned} z_i= {\left\{ \begin{array}{ll} (i,3d_*)&{}\text {if }i\in \{1,\dots , m\},\\ \varvec{0}&{}\text {otherwise}. \end{array}\right. } \end{aligned}$$

Let $\hat{p}\in \mathbb {R}^m_+$ be such that for each $b\in M$, $\hat{p}^b=3d_*$. We show that $z_1\in D(R''_1,\hat{p})$, and for each $i\in N{\setminus } \{1\}$, $z_i\in D(R_i,\hat{p})$. This implies that $(z,\hat{p})\in W(R''_1,R_{-1})$, and thus, by $p=p_{\min }(R''_1,R_{-1})$, we conclude that $p^1\le \hat{p}^1=3d_*$.

Note that by $\hat{p}\in \mathbb {R}^m_{++}$ and (i) of Lemma 2, for each $(A_1,t_1)\in D(R''_1,\hat{p})$, $|A_1|\le 1$, and for each $i\in N{\setminus } \{1\}$ and each $(A_i,t_i)\in D(R_i,\hat{p})$, $|A_i| \le 1$.

Let $i\in N$. We have three subcases.

Subcase 1-1: $i=1$. By $1c''$ and $\hat{p}\in \mathbb {R}^m_{++}$, for each $b\in M{\setminus }\{1\}$,

$$\begin{aligned} V''_1(b; (1,\hat{p}^1))=V''_1(b;(1,3d_*))<0< \hat{p}^b. \end{aligned}$$

Thus for each $b\in M{\setminus } \{1\}$, $(1,\hat{p}^1)\mathrel {P'_1}(b,\hat{p}^b)$. Also by $1c''$ and first object monotonicity, $V''_1(\emptyset ;(1;\hat{p}^1))=V''_1(\emptyset ;(1,3d_*))<0$, which implies $(1,\hat{p}^1)\mathrel {P'_1}\varvec{0}$. Thus, $z_1=(1,\hat{p}^1)\in D(R''_1,\hat{p})$.

Subcase 1-2: $i\in \{2,\dots ,m\}$. By ic and $\hat{p}\in \mathbb {R}^m_{++}$, for each $b\in M{\setminus } \{i\}$,

$$\begin{aligned} V_i(b;(i,p^i))=V_i(b;(i,3d_*))<0< p^b. \end{aligned}$$

Thus, for each $b\in M{\setminus } \{i\}$, $(i,\hat{p}^i)\mathrel {P_i}(b,\hat{p}^b)$. Also by ic and first object monotonicity, $V_i(\emptyset ;(i,\hat{p}^i))=V_i(\emptyset ;(i,3d_*))<0$, which implies $(i,\hat{p}^i)\mathrel {P_i}\varvec{0}$. Thus, $z_i=(i,\hat{p}^i)\in D(R_i,\hat{p})$.

Subcase 1-3: $i\in \{m+1,\dots ,n\}$. For each $b\in M$, $V_i(b;\varvec{0})=3d_*=\hat{p}^b$. This implies $\varvec{0}\mathrel {R_i}(b,\hat{p}^b)$. Thus, $z_i=\varvec{0}\in D(R_i,\hat{p})$.

Case 2: $a\in \{2\dots ,m\}$. Let $i=a$. Suppose by contradiction that $p^a\le 3d_*$. Note that by $n<m$ and (i) of Lemma 3, $p\in \mathbb {R}_{++}^m$. Thus by (i) of Lemma 2, for each $(A_i,t_i)\in D(R_i,p)$, $|A_i|\le 1$. By $p^a\le 3d_*$, $i=a$, ic, and $p\in \mathbb {R}^m_{++}$, for each $b\in M{\setminus } \{a\}$,

$$\begin{aligned} V_i(b;(a,p^a))\le V_i(b;(i,3d_*))<0< p^b. \end{aligned}$$

Thus for each $b\in M{\setminus } \{a\}$, $(a,p^a)\mathrel {P_i}(b,p^b)$. Also by $i=a$, $p^a\le 3d_*$, ic, and first object monotonicity, $V_i(\emptyset ;(a,p^a))\le V_i(\emptyset ;(i,3d_*))<0$, which implies $(a,p^a)\mathrel {P_i}\varvec{0}$. Therefore, $D(R_i,p)=\{(a,p^a)\}$. Since $f(R''_1,R_{-1})\in Z_{\min }^W(R''_1,R_{-1})$, $A_i(R''_1,R_{-1})=a$. This contradicts $A_1(R''_1,R_{-1})=a$. $\square $

Recall that $(1,3d_*)\mathrel {P_1}\varvec{0}$ and for each $a\in M{\setminus } \{1\}$, $(1,3d_*)\mathrel {R_1}(a,3d_*)$. By Claim 1, $t(1)\le 3d_*$ and for each $a\in M{\setminus } \{1\}$, $t(a)>3d_*$. Thus,

$$\begin{aligned}&(1,t(1))\mathrel {R_1}(1,3d_*)\mathrel {P_1}\varvec{0}, \end{aligned}$$

and for each $a\in M{\setminus }\{1\}$,

$$\begin{aligned} (1,t(1))\mathrel {R_1}(1,3d_*)\mathrel {R_1}(a,3d_*)\mathrel {P_1}(a,t(a)). \end{aligned}$$

Therefore, (ii) of Lemma 11 implies $A_1(R)\ne \emptyset $ and for each $a\in M{\setminus } \{1\}$, $A_1(R)\ne a$. By Step 3, $|A_1(R)|\le 1$, because otherwise there exists an agent $i\in \{2,\dots , m\}$ such that $A_i(R)=\emptyset $, which contradicts Step 3. Hence, $A_1(R)=1$. $\blacksquare $

Step 5: For each $i\in \{2,\dots , m\}$, $A_i(R)=i$.

We show that for each $i\in \{2,\dots , m\}$, $A_i(R)\subseteq \{i,i-1\}$. Then, since $A_1(R)=1$ by Steps 3 and 4, we conclude that for each $i\in \{2,\dots , m\}$, $A_i(R)=i$.

Suppose by contradiction that there is $i\in \{2,\dots , m\}$ such that $A_i(R)\not \subseteq \{i-1, i\}$. By Lemma 4, there is $a\in M{\setminus } \{i-1, i\}$ such that $A_i(R)=a$. By $a\in M{\setminus } \{i-1,i\}$ and ia, $V_i(a;\varvec{0})=d_*$. Thus, by Step 2 and Lemma 6,

$$\begin{aligned} V_i(\emptyset ; f_i(R))\ge -d_* =V_i(a;\varvec{0})-2d_*\ge t_i(R)-2d_*. \end{aligned}$$

(1)

Let $j\in \{m+1,\dots , n\}$. By Step 3 and Step 4, $A_j(R)=\emptyset $, and thus, by Lemma 5, $f_j(R)=\varvec{0}$. Thus, by the def. of $R_j$,

$$\begin{aligned} V_j(a;f_j(R))=V_j(a;\varvec{0})=3d_*. \end{aligned}$$

(2)

Therefore, by (1), (2), and $t_j(R)=0$,

$$\begin{aligned} V_i(\emptyset ; f_i(R))+V_j(a;f_j(R))\ge t_i(R)-2d_*+3d_*>t_i(R)=t_i(R)+t_j(R). \end{aligned}$$

This contradicts Lemma 8. $\blacksquare $

Step 6: Completing the proof.

For each $i\in \{2,\dots , m\}$, by Step 2, $V_i(\emptyset ;f_i(R))\ge -d_*$, by ia, $V_i(i;\varvec{0})=4d_*$, and by Lemma 6 and Step 5, $t_i(R)\le V_i(A_i(R);\varvec{0})=V_i(i;\varvec{0})$. Thus, for each $i\in \{2,\dots , m\}$,

$$\begin{aligned} V_i(\emptyset ;f_i(R))&\ge -d_*= V_i(i;\varvec{0})-5d_*\ge t_i(R)-5d^*. \end{aligned}$$

(3)

By $A_1(R)=1$, there is $A_1\in \mathcal {M}$ such that $1\in A_1$ and

$$\begin{aligned} V_1(A_1;f_1(R))-t_1(R)=\max _{A'_1\in \mathcal {M}_1}\{V_1(A'_1;f_1(R))-t_1(R)\}. \end{aligned}$$

By $A_1(R)=1$, Lemma 6, and Lemma 9, $t_1(R)\in [0,V_1(1;\varvec{0})]$. Thus, by the def. of $\underline{t}_1$,

$$\begin{aligned} V_1(A_1;f_1(R))-t_1(R)\ge \underline{t}_1. \end{aligned}$$

(4)

Let $N'\equiv \{i\in \{2,\dots ,m\}: A_i(R)\subseteq A_1\}$. Let $z'\equiv ((A'_i,t'_i))_{i\in N}\in Z$ be such that

$$\begin{aligned}&z'_1=(A_1,V_1(A_1;f_1(R))),\\&z'_i=(\emptyset , V_i(\emptyset ;f_i(R)))\text { for each }i\in N',\text { and}\\&z'_i=f_i(R)\text { for each }i\in N{\setminus } (N'\cup \{1\}). \end{aligned}$$

Figure 11 is an illustration of $z'$ when $A_1=\{1,2,3\}$.

Clearly, for each $i\in N$, $z'_i\mathrel {I_i}f_i(R)$. By Step 5 and $1\in A_1$, $|N'|=|A_1|-1\le m-1$. Thus, $5|N'|d_*\le 5(m-1)d_*<\underline{t}_1$, Therefore, by (3), (4), and $5|N'|d_*<\underline{t}_1$,

$$\begin{aligned} \sum _{i\in N}t'_i&=V_1(A_1;f_1(R))+\sum _{i\in N'}V_i(\emptyset ;f_i(R))+\sum _{i\in N\setminus (N'\cup \{1\})}t_i(R)&\\&\ge t_1(R)+\underline{t}_1+\sum _{i\in N'} (t_i(R)-5d_*)+\sum _{i\in N\setminus (N'\cup \{1\})}t_i(R)&(\hbox {by (3) and (4)})\\&= \underline{t}_1-5|N'|d_*+\sum _{i\in N} t_i(R)&\\&>\sum _{i\in N}t_i(R).&(\hbox {by }5|N'|d_*<\underline{t}_1) \end{aligned}$$

This contradicts efficiency. $\blacksquare $

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and permissions

About this article

Cite this article

Kazumura, T., Serizawa, S. Efficiency and strategy-proofness in object assignment problems with multi-demand preferences. Soc Choice Welf 47, 633–663 (2016). https://doi.org/10.1007/s00355-016-0986-8

Download citation

Received: 17 August 2015
Accepted: 30 July 2016
Published: 21 September 2016
Issue Date: October 2016
DOI: https://doi.org/10.1007/s00355-016-0986-8

Efficiency and strategy-proofness in object assignment problems with multi-demand preferences

Abstract

Similar content being viewed by others

Strategy-proof mechanism design with non-quasi-linear preferences: ex-post revenue maximization for an arbitrary number of objects

Overlapping multiple object assignments

Optimal multi-unit allocation with costly verification

1 Introduction

2 The model and definitions

Definition 1

Lemma 1

Definition 2

Remark 1

Definition 3

Definition 4

Example 1:

Example 2:

Example 3:

Remark 2

3 Unit-demand model and rich domains

Definition 5

Definition 6

Definition 7

Remark 3

Definition 8

4 Minimum price Walrasian rules

Lemma 2

Definition 9

Lemma 3

Fact 1

Fact 2

Definition 10

Lemma 4

Fact 3

5 Main result

5.1 Impossibility result

Theorem

Corollary 1

Remark 4

Corollary 2

Corollary 3

Remark 5

5.2 Sketch of the proof

5.2.1 Preliminary results

Lemma 5

Lemma 6

Lemma 7

Lemma 8

Lemma 9

Lemma 10

Lemma 11

5.2.2 Three-agent and two-object example

6 Concluding remarks

Notes

References

Acknowledgments

Author information

Authors and Affiliations

Corresponding author

Appendix: Proofs

Appendix: Proofs

1.1 A Proofs of Lemmas

Proof of Lemma 1:

Proof of (i) of Lemma 2:

Proof of (ii) of Lemma 2:

Proof of (i) of Lemma 3:

Proof of (ii) of Lemma 3:

Proof of Lemma 4:

Proof of Lemma 8:

Proof of Lemma 9:

1.2 B Proof of Theorem

Proof

Proof

Proof

Proof

Rights and permissions

About this article

Cite this article

Share this article

Keywords

Search