1 Introduction
This is to extend (Kazumura et al. 2020b) to a general case of an arbitrary number of agents and objects. They consider the multi-object allocation problem with monetary transfers where each agent obtains at most one object (unit-demand). A (consumption) bundle is a pair of object and payment. Each agent has a continuous preference relation over bundles satisfying the possibility of compensation and money monotonicity. Preferences are called classical if they satisfies object desirability. The classical domain is the class of all classical preferences The extended domain is the class of preferences which satisfies all properties but not object desirability.
An (allocation) mechanism, or simply mechanism chooses, for each preference profile, the object each agent receives and how much each agent pays. We focus on the following four properties of mechanisms. A mechanism is desirable if it satisfies those properties.
Advertisement
(i) Individual rationality requires that each agent’s bundle is at least as good as receiving nothing with no payment. Without this condition, agents does not participate the mechanism voluntarily. (ii) Non-wastefulness means that no agent prefers his own bundle to unassigned object with no payment. This condition is the property of weak efficiency. (iii) Equal treatment of equals requires that if there are two agents with same preferences, then their bundles are indifferent for their preferences. This is a weak condition of fairness. (iv) Strategy-proofness is the incentive compatible condition, which means that no agent has incentive to misreport his preference.
In multi-object allocation problem, for each preference profile, Walrasian equilibrium exists (Alkan and Gale 1990), and Demange and Gale (1985) show that the set of Walrasian prices has a lattice structure; that is, there is the minimum price Walrasian equilibrium for each preference profile. The minimum price Walrasian mechanism is desirable (Demange and Gale 1985), and it satisfies efficiency and no subsidy (no-negative monetary transfer).
A subdomain of the classical domain is rich if for each object, there is a preference in the subdomain which demands only the object for some price and demands no object for some other price.1 Kazumura et al. (2020b) illustrate that various domains including the quasi-linear domain are rich, and show that in the case where the number of agents is greater than the number of objects, the minimum price Walrasian mechanism is the unique ex-post revenue maximizing mechanism among the desirable mechanisms satisfying no subsidy on a classical rich domain; moreover, the mechanism is also the unique ex-post revenue maximizing mechanism among the desirable mechanisms satisfying no bankruptcy on a domain including positive income effect preferences. We extend their results to a general case of an arbitrary number of agents and objects and on the subset of extended domain.
This article is organized as follows. Section 2 introduces the model and basic concepts, and checks the properties of minimum price Walrasian mechanisms. Our results are in Sect. 3. Section 4 provides proofs. Section 5 concludes.
Advertisement
2 The model
Let \(N=\left\{ 1,2,\ldots ,n\right\} \) be the set of agents and \(M=\left\{ 1,2,\ldots ,m\right\} \) be the set of different objects. Not consuming an object in M is called consuming the “null object”. Let \( L\equiv M\cup \left\{ 0\right\} \), where 0 denotes the null object. Each agent consumes at most one object. A typical (consumption) bundle for agent i is a pair \(z_{i}=\left( x_{i},t_{i}\right) \in L\times \mathbb {R}\): agent i receives object \(x_{i}\) and pays \(t_{i}\).
Each agent has a complete and transitive preference relation \(R_{i}\) over \(L \times \mathbb {R}\). Let \(I_{i}\) and \(P_{i}\) be the indifference relation and strict preference relation associated with \(R_{i}\). A typical class of preferences is denoted by \({\mathcal {R}}\). We call \({\mathcal {R}}\) a domain. \(R_i\) is classical if it satisfies the following assumptions: Let \({\mathcal {R}}^{C}\) be the set of classical preferences—the classical domain. Let \({\mathcal {R}}^{E}\) be the set of preferences satisfying the above assumptions except for object desirability. We call \( {\mathcal {R}}^E\) the extended domain. Note that \({\mathcal {R}}^{C} \subsetneq {\mathcal {R}}^{E}\). We assume that \({\mathcal {R}} \subseteq \mathcal {R }^E\).2
1.
Continuity For each \(z_{i}\in L\times \mathbb {R}\), the sets \( \{ z^{\prime }_{i}\in L \times \mathbb {R} :z^{\prime }_{i}\,R_{i}\, z_{i}\} \) and \(\{ z^{\prime }_{i}\in L\times \mathbb {R}: z_{i}\,R_{i}\,z_{i}^{\prime }\} \) are closed.
2.
Possibility of compensation For each pair \(a,b\in L\) and each \( t\in \mathbb {R}\), there exist \(t^{\prime },t^{\prime \prime }\in \mathbb {R}\) such that \(\left( a,t\right) \,R_{i}\,\left( b,t^{\prime }\right) \) and \( \left( b,t^{\prime }\right) \,R_{i}\,\left( a,t^{\prime \prime }\right) \).
3.
Money monotonicity For each \(a\in L\) and each pair \( t,t^{\prime }\in \mathbb {R}\), if \(t<t^{\prime }\), then \(\left( a,t\right) \,P_{i}\,\left( a,t^{\prime }\right) \).
4.
Object desirability For each \(a\in M\) and each \(t \in \mathbb {R }\), \(\left( a,t\right) \,P_{i}\,\left( 0,t\right) \).
A preference profile is a list of preferences \(R\equiv (R_{1},\ldots ,R_{n})\). Given \(i\in N\) and \(N^{\prime }\subseteq N\), let \(R_{-i}\equiv (R_{j})_{j\ne i}\) and \(R_{-N^{\prime }}\equiv (R_{j})_{j\in N{\setminus } N^{\prime }}\).
A (feasible) object allocation is an n-tuple \(x=\left( x_{1},x_{2},\dots ,x_{n}\right) \in L^{n}\) such that for each pair \(i,j\in N\) , if \(x_{i}=x_{j}\), then \(x_{i}=x_{j}=0\). Let A be the set of all object allocations. An allocation is a pair of an object allocation and a vector of payments, \(z=\left( \left( x_{1},x_{2},\dots ,x_{n}\right) ,\left( t_{1},t_{2},\dots ,t_{n}\right) \right) \in A\times \mathbb {R}^{n}\). Given \( z\in A\times \mathbb {R}^{n}\) and \(i\in N\), \(z_{i}=\left( x_{i},t_{i}\right) \in L\times \mathbb {R}\) denotes the bundle of agent i.
An (allocation) mechanism associates an allocation to each preference profile. Formally, a mechanism is a mapping \(f = (x,t) :{\mathcal {R}}^{n}\rightarrow A\times \mathbb {R}^{n}\). Given a mechanism f and a preference profile \(R\in {\mathcal {R}}^{n}\), agent i’s assignment under f at R is denoted by \(f_{i}\left( R\right) \). Moreover, we write \( f_{i}\left( R\right) \equiv (x_{i}(R), t_{i}(R)) \in L\times \mathbb {R}\), where \(x_{i}(R)\) denotes i’s object assignment and \(t_{i}(R)\) denotes his payment. We define \(f\left( R\right) \equiv \left( f_{1}\left( R\right) ,\ldots ,f_{n}\left( R \right) \right) \).
Definition 1
An allocation mechanism \(f = (x,t)\) is desirable if it satisfies the following axioms:
-
Individual rationality For each \(R\in {\mathcal {R}}^{n}\) and each \(i\in N\), \(f_{i}\left( R \right) \,R_{i}\,\left( 0, 0\right) \).
-
Non-wastefulness For each \(R\in {\mathcal {R}}^n\), each \(i\in N\) and each \(a\in M\), if \(x_{i}(R)\ne a\) and \((a,0)\,P_{i}\,f_{i}(R)\), then there is \(j\ne i\) such that \(x_{j}(R)=a\).
-
Equal treatment of equals For each \(R \in {\mathcal {R}}^{n}\) and each \(i,j \in N\) with \(R_{i} = R_{j}\), \(f_{i}(R)\,I_{i}\,f_{j}(R)\).
-
Strategy-proofness For each \(R\in {\mathcal {R}}^{n}\), each \(i\in N\) and each \(R_{i}^{\prime }\in {\mathcal {R}},\) \( f_{i}\left( R\right) \,R_{i}\,f_{i}\left( R_{i}^{\prime },R_{-i}\right) \).
Non-wastefulness means that no agent prefers unassigned object with no payment to his own bundle. This condition is a weak condition of efficiency.
We say the allocation mechanism satisfies no-wastage if for each \(R \in {\mathcal {R}}^{n}\) and each \(a \in M\), there is \(i \in N\) such that \( x_{i}(R) = a\). Note that when \(n < m\), no mechanism satisfies no-wastage. Kazumura et al. (2020b) define desirability by (i) individual rationality, (ii) no-wastage, (iii) equal treatment of equals, and (iv) strategy-proofness, which is different from our definition. However, since they assume that the number of agents is greater than the number of objects, no-wastage implies non-wastefulness. Thus, it is natural to relax no-wastage to non-wastefulness.
Remark 1
(i) If \(n < m\), no mechanism satisfies no-wastage. (ii) If \(n \ge m\) and f satisfies no-wastage, then it is non-wasteful.
Definition 2
An allocation mechanism \(f=(x,t)\) satisfies no subsidy if for each \( R\in {\mathcal {R}}^{n}\) and each \(i\in N\), \(t_{i}(R)\ge 0\).
Let \(p=\left( p_{1},p_{2},\ldots ,p_{m}\right) \in \mathbb {R}_{+}^{m}\) be a price vector. We assume that the price of null object is equal to zero; that is, \(p_{0}=0\). Given \(i\in N\), \(R_{i}\in {\mathcal {R}}\), and \(p\in \mathbb {R} _{+}^{m}\), let \(D(R_{i},p)\equiv \{a\in L:\forall b\in L,\ (a,p_{a})\,R_{i}\,(b,p_{b})\}\) denote the demand set of agent i with \( R_{i} \) at p.
Next, we define the concept of Walrasian equilibrium. It is a pair of a price vector and an allocation such that for each agent it defines the object he demands and its price. Furthermore, the price of an unassigned object is zero.
Definition 3
Given \(R\in {\mathcal {R}}^{n}\), a pair \(\left( \left( x,t\right) ,p\right) \in \left( A\times \mathbb {R}^{n}\right) \times \mathbb {R}_{+}^{m}\) is a Walrasian equilibrium for R if
WE-i: for each \(i\in N\), \(x_{i} \in D( R_{i},p) \) and \(t_{i}=p_{x_{i}} \); and
WE-ii: for each \(a \in M {\setminus } \{x_{j}\}_{j \in N}\), \(p_{a}=0\).
Given \(R\in {\mathcal {R}}^{n}\), let \(W\left( R\right) \) be the set of Walrasian equilibria for R, and defineand
$$\begin{aligned} Z(R) \equiv \{z \in A \times \mathbb {R}^{n}: \exists p \in \mathbb {R} ^{m}_{+} \ \text {s.t.}\ \left( z,p\right) \in W\left( R\right) \} \end{aligned}$$
$$\begin{aligned} P\left( R\right) \equiv \left\{ p\in \mathbb {R}_{+}^{m}:\exists z\in A\times \mathbb {R}^{n}\ \text {s.t.}\ \left( z,p\right) \in W\left( R\right) \right\} . \end{aligned}$$
Fact 1
(Alkan and Gale 1990) For each \(R \in {\mathcal {R}}^{n}\), there is a Walrasian equilibrium; that is, \(W(R) \ne \emptyset \).
Fact 2
Given \(R \in {\mathcal {R}}^{n}\), we denote the minimum Walrasian price for R by \(p^{min}(R)\) and defineWe say an allocation mechanism f is a minimum price Walrasian mechanism if for each \(R \in {\mathcal {R}}^{n}\), \(f(R) \in Z^{min}(R)\).
$$\begin{aligned} Z^{min}(R) \equiv \{ z \in A \times \mathbb {R}^{n}: (z,p^{min}(R)) \in W(R) \}. \end{aligned}$$
Fact 3
By the definition of Walrasian equilibrium, the minimum price Walrasian mechanism satisfies individual rationality, non-wastefulness, and equal treatment for equals, and so it is desirable; moreover, it satisfies no subsidy.
Fact 4
(Demange and Gale 1985) The minimum price Walrasian mechanism f is desirable and satisfies no subsidy.
Remark 2
(i)
If \({\mathcal {R}} \subseteq {\mathcal {R}}^C\) and \(n>m\), the minimum price Walrasian mechanism on \({\mathcal {R}}^n\) satisfies no wastage.
(ii)
Let \(a\in M\) and \(R_{0}\in {\mathcal {R}}^{E}{\setminus } {\mathcal {R}}^{C}\) be such that \((0,0)\,P_{0}\,(a,0)\). If \({\mathcal {R}}^{C}\cup \{R_{0}\}\subseteq {\mathcal {R}}\subseteq {\mathcal {R}}^{E}\), then there is no mechanism that satisfies individual rationality, no subsidy and no wastage.
Remark 3
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^C\) and \(n \ge m\). Let a mechanism \( f=(x,t)\) on \({\mathcal {R}}^n\) satisfy individual rationality and no subsidy. Then f satisfies no-wastage if and only if it is non-wasteful.
Proof
Only if part follows from Remark 1. Thus we show that if part. Assume f satisfies non-wastefulness. Suppose that f does not satisfy no-wastage. Then there are \(R \in {\mathcal {R}}^n\) and \(i \in N\) such that \(x_i(R) = 0\). By individual rationality, \((0,t_i(R))=f_i(R)\,R_i \,(0,0)\), and so \(t_i(R) \le 0\). By no subsidy, \(t_i(R) \ge 0\). Thus \( t_i(R)=0\), and so \(f_i(R)=(0,0)\).
Since \(n\ge m\) and \(x_i(R) = 0\), there is \(a \in M\) such that for each \(j \in N\), \(x_j(R) \ne a\). Since \({\mathcal {R}} \subseteq {\mathcal {R}}^C\), by object desirability, \((a,0)\,P_i\,(0,0)\). Thus by \(f_i(R)=(0,0)\), \( (a,0)\,P_i\,f_i(R)\), which contradicts non-wastefulness. \(\square \)
Remark 4
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^C\) and \(n \ge m\). The class of mechanisms satisfying desirability and no subsidy is equivalent to the class of mechanisms satisfying individual rationality, no-wastage, equal treatment of equals, strategy-proofness and no subsidy.
3 Results
Definition 4
A mechanism \(f=(x^f,t^f)\) revenue dominates \(g = (x^g,t^g)\) if for each \(R \in {\mathcal {R}}^{n}\), \(\sum _{i \in N}t^f_{i}(R) \ge \sum _{i \in N}t^{g}_{i}(R)\).
A mechanism is ex-post revenue optimal among a class of mechanisms if it belongs to the class and revenue dominates each other mechanism in the class. We explore ex-post revenue optimal mechanisms among the class of desirable satisfying no subsidy on rich domains in Sect. 3.1, and among the class of desirable satisfying no bankruptcy on the positive income effect domain in Sect. 3.2.
3.1 The result on rich domains
We define the richness of a domain.
Definition 5
A domain \({\mathcal { R}}\subseteq {{\mathcal {R}}^{E}}\) is rich if for each \(a\in M\) and each \(p\in \mathbb {R}_{+}^{m}\) with \(p_{a}>0\) and \(p_{b}=0\) for each \( b\in M{\setminus } \{a\}\) and for each \(p^{\prime }>p\),5 there is \( R_{i}\in {\mathcal {R}}\) such that
$$\begin{aligned} D(R_{i},p)=\{a\}\text { and }D(R_{i},p^{\prime })=\{0\}. \end{aligned}$$
Since the requirement \({\mathcal { R}}\subseteq {{\mathcal {R}}^{E}}\) is weaker than \({\mathcal { R}}\subseteq {{\mathcal {R}}^{C}}\), the above richness condition is weaker than that of Kazumura et al. (2020b). The example below illustrates this fact.
Example 1
LetThen \(\hat{{\mathcal {R}}}\) satisfies the above richness condition, but not that of Kazumura et al. (2020b) since \(\hat{{\mathcal {R}}}\subseteq {\mathcal {R}} ^{E}{\setminus } {\mathcal {R}}^{C}\).
$$\begin{aligned} \hat{{\mathcal {R}}}\equiv \bigcup _{a\in M}\{R_{i}\in {\mathcal {R}} :(a,0)\,P_{i}\,(0,0)\text { and }(0,0)\,P_{i}\,(b,0)\,\forall b\in M{\setminus } \{a\}\}. \end{aligned}$$
Fact 5
(Theorem 1 in Kazumura et al. (2020b)) Let \({\mathcal {R}} \subseteq {\mathcal {R}}^C\) be rich and \(n>m\). The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no subsidy on \({\mathcal {R}} ^n\).
Fact 6
(Morimoto and Serizawa 2015) Let \({\mathcal {R}} \subseteq {\mathcal {R}}^C\), \(R \in {\mathcal {R}}^{n}\) and \(p =p^{min}(R)\). Then, (i) if \(n > m\), then for each \(a \in M\), \(p_{a} > 0\), and (ii) if \(n \le m\), then there is \(a \in M\) such that \(p_{a}=0\).
In Kazumura et al. (2020b), the proof of Fact 5 depends on Fact 6 (i). However, when the number of agents is less or equal to the number of objects, we cannot use their method directly. Moreover, even when the number of agents is greater than the number of objects, if preferences do not satisfy object desirability, then there is a minimum price Walrasian equilibrium in which some object’s price is zero. Hence, to show the result of Kazumura et al. (2020b) in the general cases, we need to use another proof method.
Theorem 1 shows that for an arbitrary number of agents and objects, the minimum price Walrasian mechanism is revenue optimal among the same class on a rich domain.
Theorem 1
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^E\) be rich. The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no subsidy on \({\mathcal {R}}^n\).
The proof of Theorem 1 only depends on the richness of a domain and so it holds whether preferences in \({\mathcal {R}}\) satisfy object desirability or not. Hence we have the following corollary.
Corollary 1
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^C\) be rich. The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no subsidy on \({\mathcal {R}}^n\).
3.2 The result on the positive income effect domain
We define the positive income effect domain.
Definition 6
A preference \(R_{i}\) satisfies positive income effect if for each \( a,b\in L\) and each \(t,t^{\prime }\in \mathbb {R}\) with \(t<t^{\prime }\) and \( (b,t^{\prime })\,I_{i}\,(a,t)\), for each \(\delta >0\),Let \({\mathcal {R}}^{++}\) be the set of positive income effect preferences.
$$\begin{aligned} (b,t^{\prime }-\delta )\,P_{i}\,(a,t-\delta ). \end{aligned}$$
Definition 7
A mechanism f satisfies no bankruptcy if there is \(l\le 0\) such that for each \(R\in {\mathcal {R}}^{n}\), \(\sum _{i\in N}t_{i}(R)\ge l\).
Remark 5
Let \({\mathcal {R}}\equiv {\mathcal {R}}^{E}\). Then there is no mechanism that satisfies individual rationality, no bankruptcy and no wastage.
Proof
Suppose that there is f that satisfies individual rationality, no bankruptcy and no wastage. Let \(l\le 0\) be the associate lower bound of no bankruptcy and \(R_{0}\in {\mathcal {R}}\) be such that for each \(a\in M\), \((0,0)\,P_{0}\,(a,l)\). Let \(R\in {\mathcal {R}}^{n}\) be such that for each \(i\in N\), \(R_{i}=R_{0}\). Then, by no wastage, there is \( j\in N\) such that \(x_{j}(R)\ne 0\). By individual rationality, for each \( i\in N\), \(t_{i}(R)\le 0\) and \(t_{j}(R)<l\). Thus, \(\sum _{i\in N}t_{i}(R)<l\), which contradicts no bankruptcy. \(\square \)
Remark 6
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^C\) and \(n \ge m\). The class of mechanisms satisfying desirability and no bankruptcy includes the class of mechanisms satisfying individual rationality, no-wastage, equal treatment of equals, strategy-proofness and no bankruptcy.
Fact 7
(Theorem 2 in Kazumura et al. (2020b)) Let \({\mathcal {R}}^{C} \cap {\mathcal {R}}^{++} \subseteq {\mathcal {R}} \subseteq {\mathcal {R}}^{C}\) and \(n>m\). The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of mechanisms satisfying individual rationality, no-wastage, equal treatment of equals, strategy-proofness and no bankruptcy on \({\mathcal {R}}^n\).
Similarly to Fact 7, but on the subset of the extended domain and for an arbitrary number of agents and objects, we have:
Theorem 2
Let \({\mathcal {R}}^{C} \cap {\mathcal {R}}^{++} \subseteq {\mathcal {R}} \subseteq {\mathcal {R}}^{E}\). The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no bankruptcy on \({\mathcal {R}}^n\).
Corollary 2
Let \({\mathcal {R}}^{C} \cap {\mathcal {R}}^{++} \subseteq {\mathcal {R}} \subseteq {\mathcal {R}}^{C}\). The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no bankruptcy on \({\mathcal {R}}^n\).
Since \({\mathcal {R}}^{E}\), \({\mathcal {R}}^{C}\) and \({\mathcal {R}}^{++}\) are supersets of \({\mathcal {R}}^{C} \cap {\mathcal {R}}^{++}\) and subsets of \( {\mathcal {R}}^{E}\), the following is a corollary of Theorem 2.
Corollary 3
Let \({\mathcal {R}} \in \{{\mathcal {R}}^{E},{\mathcal {R}}^{C},{\mathcal {R}}^{++}\}\). The minimum price Walrasian mechanism is the unique ex-post revenue optimal mechanism among the class of desirable mechanisms satisfying no bankruptcy on \({\mathcal {R}}^n\).
3.3 Efficiency
Finally, we discuss the property of efficiency.
Definition 8
A mechanism \(f=(x,t)\) satisfies efficiency if for each \(R\in {\mathcal {R}}^{n}\), there is no allocation \(z\in A\times \mathbb {R}^{n}\) such that (i) for each \(i\in N\), \(z_{i}\,R_{i}\,f_{i}(R)\), (ii) for some \(j \in N\) , \(z_{j}\,P_{j}\,f_{j}(R)\) and (iii) \(\sum _{k \in N}t _{k} \ge \sum _{k \in N}t_{k}(R)\).
Since ex-post revenue optimal mechanism is the minimum price Walrasian mechanism and it is an efficient mechanism (Morimoto and Serizawa 2015), ex-post revenue optimal mechanism is efficient (Kazumura et al. 2020b). By the results of Kazumura et al. (2020b) and ours, we have:
Corollary 4
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^E\) be rich. For each \(n,m\in \mathbb {N }\), if f is ex-post revenue optimal among desirable mechanisms satisfying no subsidy, then f is efficient.
Corollary 5
Let \({\mathcal {R}}^{C}\cap {\mathcal {R}}^{++} \subseteq {\mathcal {R}} \subseteq {\mathcal {R}}^E\). For each \(n,m\in \mathbb {N}\), if f is ex-post revenue optimal among desirable mechanisms satisfying no bankruptcy, then f is efficient.
4 Proofs
Given \(i\in N\), \(R_{i}\in {\mathcal {R}}\), \(a\in L\) and \((b,t)\in L \times \mathbb {R}_{+}\), the compensated valuation \(V^{R_{i}}(a;(b,t))\) of a from (b, t) for \(R_{i}\) is the value such that \((a,V^{R_{i}}(a;(b,t))) \,I_{i}\,(b,t)\).
Fact 8
Let f satisfy individual rationality. Let \(R \in {\mathcal {R}}^{n}\), \(i \in N \) and \(z_i=(x_i,t_i) \in L \times \mathbb {R}_+\). If \(z_{i}\,P_{i}\,f_{i}(R)\) , then \(x_{i} \ne 0\).
Proof
Assume \(z_{i}\,P_{i}\,f_{i}(R)\). Suppose \(x_{i}=0\). By individual rationality, \(f_{i}(R)\,R_{i}\,(0,0)\), and so \( z_{i}\,P_{i}\,(0,0)\). By \(x_{i}=0\), \((0,t_{i})\,P_{i}\,(0,0)\). Thus by money monotonicity, \(t_{i}<0\). Since \(t_{i}\ge 0\), this is a contradiction. \(\square \)
Fact 9
(Lemma 1 in Kazumura et al. (2020b)) Let \(g = (x^{g},t^{g})\) be a minimum price Walrasian mechanism. Then, for each mechanism \(f=(x^f,t^f)\) and each \(R \in {\mathcal {R}}^{n}\),
$$\begin{aligned} {[}\forall i \in N, \ f_{i}(R)\,R_{i}\,g_{i}(R)] \Rightarrow \sum _{i \in N}t^{g}_{i}(R) \ge \sum _{i \in N}t^f_{i}(R). \end{aligned}$$
4.1 Proof of Theorem 1
Throughout this subsection, we assume that \({\mathcal {R}}\) is rich. Our proof employes many results of Kazumura et al. (2020b). We omit the proofs of such results, and write only the proofs of our new results.
We introduce the concept of favoring preferences. Given \(a\in M\), let \( {\mathcal {R}}^{a}\equiv \{R_{i} \in {\mathcal {R}}:\forall b\in L {\setminus } \{a\}\) , \((a,0)\,P_{i}\,(b,0)\}\). By the richness of domains, for each \(a\in M\), \( {\mathcal {R}}^{a} \ne \emptyset \). We say a preference \(R_{i}\in {\mathcal {R}} ^{a}\) is a-favoring.
Definition 9
Given \((a,t)\in M\times \mathbb {R}_{+}\), \(R_{i}^{\prime }\in {\mathcal {R}}^{a}\) is (a, t)-favoring if for each \(b\in L{\setminus } \{a\}\), \( V^{R_{i}^{\prime }}(b;(a,t))<0\).
Remark 7
Let f satisfy no subsidy. Let \(R\in {\mathcal {R}}^{n}\), \(i\in N \), and \( z_i\in M \times \mathbb {R}_+\) be such that \(R_{i}\) is \(z_{i}\)-favoring. If \( x_{i}(R)\ne x_{i}\), then \(z_{i}\,P_{i}\,f_{i}(R)\).
Proof
Let \(x_{i}(R) \ne x_{i}\). Since \(R_{i}\) is \(z_{i}\) -favoring, \(V^{R_i}(x_i(R);z_i)<0\). By no subsidy, \(t_i(R)\ge 0\). Thus \( V^{R_i}(x_i(R);z_i)<t_i(R)\), which means that \(z_{i}\,P_{i}\,f_{i}(R)\). \(\square \)
We say a preference \(R_{i}\) is \((a,t)^{\varepsilon }\)-favoring if at price \(p\in \mathbb {R}_{+}^{m}\) such that \(p_{a}=t\) and \(p_{b}=0\) for each \(b\ne a\), agent i demands only object a, but when all objects’ prices slightly increase, then he demands nothing.
Definition 10
Given \((a,t)\in M\times \mathbb {R}_{+}\) and \(\varepsilon _{i}>0\), \(R_{i}\) is \((a,t)^{\varepsilon _{i}}\)-favoring if \(R_{i}\) is (a, t)-favoring and
$$\begin{aligned} V^{R_{i}}(a;(0,0))<t+\varepsilon _{i}\text { and }V^{R_{i}}(b;(0,0))< \varepsilon _{i}\text { for each }b\in M{\setminus } \{a\}. \end{aligned}$$
Given \(a\in M\) and a preference \(R_{i}\in \) \({\mathcal {R}}^{a}\), let \(t^{*}(R_{i},a)\equiv \min _{b\in L{\setminus } \{a\}}\{V^{R_{i}}(a; (b,0))\}\).
Remark 8
Let \(a\in M\) and \(R_{i}\in {\mathcal {R}}^{a}\). (i) \(R_{i} \) is (a, t) -favoring preference if and only if \(t^{*}(R_{i},a)>t\). (ii) For each \( b\in L{\setminus } \{a\}\) and each \(t\in [0,t^{*}(R_{i},a)) \), \( V^{R_{i}}(b;(a,t))<0\).
Note that even if all object price is zero except object a, agent i with preference \(R_{i}\in {\mathcal {R}}^{a}\) demands only object a if object a’s price is less than \(t^{*}(R_{i},a)\). Given \(a\in M\) and \(R_{i}\in {\mathcal {R}}^{a}\), \(t^{*}(R_{i},a)>0\) and we call \(t^{*}(R_{i},a)\) the supremum a-favoring payment for \(R_{i}\).
Facts 10 and 11 do not depend on the numbers of agents and objects. Moreover these facts hold whether \({\mathcal {R}}\) satisfies object desirability or not.
Fact 10
(Lemma 2 in Kazumura et al. (2020b)) Let \({\mathcal {R}}\) be rich. Then, for each \((a,t)\in M\times \mathbb {R}_{+}\) and each \(\varepsilon >0\), there is \(R_{i}\in {\mathcal {R}}\) such that it is \( (a,t)^{\varepsilon }\)-favoring.
Fact 11
(Lemma 3 in Kazumura et al. (2020b)) Let f be desirable and satisfy no subsidy. For each \(R \in {\mathcal {R}}^{n}\) , each \(i \in N\), and each \(t \ge 0\), if there is \(j \ne i\) such that \(R_{j} \) is \((x_{i}(R),t)\)-favoring, then \(t_{i}(R) > t\).
Lemma 1
Let f satisfy individual rationality and strategy-proofness. Let \(R\in {\mathcal {R}}^{n}\) and \(z_i\in M \times \mathbb {R}_+\). Assume that there is \( i\in N\) such that \(z_{i}\,P_{i}\,f_{i}(R)\). Then, (i) there are \(\varepsilon _{i}\in (0,V^{R_{i}}(x_{i};f_{i}(R))-t_{i})\) and \(z_{i}^{\varepsilon _{i}}\)-favoring preference \(R_{i}^{\prime }\in {\mathcal {R}} \), and (ii) \(x_{i}(R_{i}^{\prime },R_{-i})\ne x_{i}\)
Proof
(i)
By \(z_{i}\,P_{i}\,f_{i}(R)\), \( t_{i}<V^{R_{i}}(x_{i};f_{i}(R))\). Thus, there is \(\varepsilon _{i}\in (0,V^{R_{i}}(x_{i};f_{i}(R))-t_{i})\). Moreover, by \(z_i\in M \times \mathbb {R }_+\) and Fact 10, there is \(z_{i}^{\varepsilon _{i}}\)-favoring preference \( R_{i}^{\prime }\in {\mathcal {R}}\).
(ii)
Suppose \(x_{i}(R_{i}^{\prime },R_{-i})=x_{i}\). Then, by individual rationality, \(t_i(R^{\prime }_i,R_{-i})\le V^{R_{i}^{\prime }}(x_{i};(0,0))\), and by (i), \(V^{R^{\prime }_{i}}(x_{i};(0,0)) < V^{R_{i}}(x_{i};f_{i}(R))\). Thus, \(t_i(R^{\prime }_i,R_{-i})<V^{R_{i}}(x_{i};f_{i}(R))\), and hence \( f_{i}(R_{i}^{\prime },R_{-i})\,P_{i}\,f_{i}(R)\). This contradicts strategy-proofness. Thus, \(x_{i}(R_{i}^{\prime },R_{-i})\ne x_{i}\).
Lemma 2
Let f be desirable and satisfy no subsidy. Let \(R \in {\mathcal {R}}^{n}\), \( N^{\prime }\subseteq N\) and \(z \in A \times \mathbb {R}_+^n \) be such that for each \(i \in N^{\prime }\), \(x_{i} \ne 0\) and \(R_{i}\) is \(z_{i}\)-favoring. Then,
(i)
for each \(i \in N^{\prime }\), there is \(j \in N\) such that \(x_{j}(R) = x_{i}\) and
(ii)
if \(i \ne j\), then \(t_{j}(R) \ge t^{*}(R_{i},x_{i}) > t_{i}\).
Proof
(i)
Let \(i\in N^{\prime }\). Then \(x_{i}\ne 0\). Suppose that for each \(j\in N\), \(x_{j}(R) \ne x_{i}\). Since \(x_{i}(R)\ne x_{i}\) and \(R_{i}\) is \(z_{i}\)-favoring, by Remark 7, which contradicts non-wastefulness.
$$\begin{aligned} (x_{i},0)\,\underset{\text {by }0\le t_{i}}{R_{i}}\,z_{i}\,P_{i}\,f_{i}(R), \end{aligned}$$
(ii)
Let \(i\in N^{\prime }\) and \(j\in N\) be such that \(i\ne j\) and \( x_{j}(R)=x_{i}\). Since \(R_{i}\) is \(z_{i}\)-favoring, by Remark 8 (ii), for each \(t\in [0,t^{*}(R_{i},x_{i}))\), \(R_{i}\) is \((x_{i},t) \) -favoring. Thus by Fact 11, \(t_{j}(R)\ge t^{*}(R_{i},x_{i}) \), and by Remark 6 (i), \(t_{i}<t^{*}(R_{i},x_{i})\). Thus, \(t_{j}(R)\ge t^{*}(R_{i},x_{i})>t_{i}\).
Proposition 1
Let \({\mathcal {R}} \subseteq {\mathcal {R}}^E\) be rich. Let f be desirable and satisfy no subsidy. For each \(R\in {\mathcal {R}}^{n}\), each \(z\in Z^{min}(R)\) and each \(i\in N\), \(f_{i}(R)\,R_{i}\,z_{i}\).
Proof
Let \(R \in {\mathcal {R}}^{n}\), \(p = p^{min}(R)\) and \( z \in Z^{min}(R)\). LetSuppose that there is \(i \in N\) such that \(z_{i} \, P_{i} \, f_{i}(R)\). Without loss of generality, let \(i \equiv 1\).
$$\begin{aligned} \underline{p} \equiv \left\{ \begin{array}{ll} \min \{p_{a} \in \mathbb {R}:a \in M \text { and }p_{a}>0\} &{} \hbox {if }\exists a \in M\hbox { such that }p_{a} > 0 \\ 0 &{} \hbox {otherwise} \end{array} \right. \end{aligned}$$
Claim
For each \(k\ge 0\), there are sets N(k) and \(N(k+1)\) of distinct agents such that \(N(k+1)\supseteq N(k)\), \(\left| N(k)\right| =k\), \( \left| N(k+1)\right| =k+1\), say \(N(k)=\{1,2,\dots ,k\}\), \( N(k+1)=\{1,2,\dots ,k+1\}\), and \((\varepsilon _{j})_{j\in N(k+1)}\in \mathbb { R}_{++}^{k+1}\), \(R^{(k)}\equiv (R_{N(k)}^{\prime },R_{-N(k)})\in {\mathcal {R}} ^{n}\) and \(R^{(k+1)}\equiv (R_{N(k+1)}^{\prime },R_{-N(k+1)})\in {\mathcal {R}} ^{n}\) such that
(i-a)
\(z_{k+1}\,P_{k+1}\,f_{k+1}(R^{(k)})\) and
(i-b)
\(x_{k+1} \ne 0\),
(ii-a)
\(\varepsilon _{1}<\min (\{\underline{p} ,V^{R_{1}}(x_{1};f_{1}(R))-t_{1}\}{\setminus } \{0\})\) and \(R_{1}^{\prime }\) is \(z_{1}^{\varepsilon _{1}}\)-favoring,
(ii-b)
for each \(j\in N(k+1){\setminus } \{1\}\), \(\varepsilon _{j}<\min \{ \varepsilon _{j-1,} t^{*}(R_{j-1}^{\prime },x_{j-1}), V^{R_{j}}(x_{j};f_{j}(R^{(j-1)}))-t_{j}\}\) and \(R_{j}^{\prime }\) is \( z_{j}^{\varepsilon _{j}}\)-favoring,
(iii)
\(x_{k+1}(R^{(k+1)})\ne x_{k+1}\) and \(z_{k+1}\,P_{k+1}^{ \prime }\,f_{k+1}(R^{(k+1)})\),
(iv)
\(x_{k+1}(R^{(k+1)}) \notin \{x_{l}\}_{l \in N(k+1)}\), and
(v)
there is \(j\in N{\setminus } N(k+1)\) such that \(x_{j}\in \{x_{l}\}_{l\in N(k+1)}\) and \(z_{j}\,P_{j}\,f_{j}(R^{(k+1)})\).
We prove Claim by induction on k.
Base Case. Let \(k=0\). Thus, \(z_{2}\,P_{2}\,f_{2}(R^{(1)})\).
(i)
By assumption, \(z_{1}\,P_{1}\,f_{1}(R)\). Thus, (i-a) holds. By (i-a), \( z_i \in L \times \mathbb {R}_+\) and Fact 8, \(x_{1}\ne 0\). Hence, (i-b) holds.
(ii)
By \(z_{1}\,P_{1}\,f_{1}(R)\), \(t_{1}<V^{R_{1}}(x_{1};f_{1}(R)))\). Thus, there is \(\varepsilon _{1}>0\) such that \(\varepsilon _{1}<\min (\{\underline{ p},V^{R_{1}}(x_{1};f_{1}(R))-t_{1}\}{\setminus } \{0\})\). By (i-b), \(x_{1}\ne 0 \). Thus, by Fact 10, there is \(z_{1}^{\varepsilon _{1}}\)-favoring preference \(R_{1}^{\prime }\in {\mathcal {R}}\). Hence, (ii-a) holds. By \(k=0\), (ii-b) holds vacantly.
(iii)
(iv)
By \(k=0\), (iv) directly follows from (iii).
(v)
By \(x_{1}(R^{(1)})\ne x_{1}\) and Lemma 2 (i), there is \(j\in N{\setminus } \{1\}\) such that \(x_{j}(R^{(1)})=x_{1}\). Without loss of generality, let \( j\equiv 2\). We show that \(z_{2}\,P_{2}\,f_{2}(R^{(1)})\). By Lemma 2 (ii) and \((z,p)\in W(R)\), \(t_{2}(R^{(1)})>t_{1}=p_{x_{1}}\). Thus,
$$\begin{aligned} z_{2}\,\underset{\text {by }(z,p)\in W(R)}{R_{2}}\,(x_{1},p_{x_{1}})\, \underset{\text {by }t_{2}(R^{(1)})>p_{x_{1}}}{P_{2}}\,(x_{1},t_{2}(R^{(1)})) \underset{\text {by }x_{2}(R^{(1)})=x_{1}}{=}f_{2}(R^{(1)})\text {.} \end{aligned}$$
Inductive Hypothesis. Let \(k\ge 1\). There are sets \(N(k-1)\) and N(k) of distinct agents such that \(N(k)\supseteq N(k-1)\), \(\left| N(k-1)\right| =k-1\), \( \left| N(k)\right| =k\), say \(N(k-1)=\{1,2,\dots ,k-1\}\), \( N(k)=\{1,2,\dots ,k\}\), and \((\varepsilon _{j})_{j\in N(k)}\in \mathbb {R} _{++}^{k}\), \(R^{(k-1)}\equiv (R_{N(k-1)}^{\prime },R_{-N(k-1)})\in \mathcal {R }^{n}\) and \(R^{(k)}\equiv (R_{N(k)}^{\prime },R_{-N(k)})\in {\mathcal {R}}^{n}\) such that
(i-a-k)
\(z_{k}\,P_{k}\,f_{k}(R^{(k-1)})\) and
(i-b-k)
\(x_{k} \ne 0\),
(ii-a-k)
\(\varepsilon _{1}<\min (\{\underline{p} ,V^{R_{1}}(x_{1};f_{1}(R))-t_{1}\}{\setminus } \{0\})\) and \(R_{1}^{\prime }\) is \(z_{1}^{\varepsilon _{1}}\)-favoring,
(ii-b-k)
for each \(j\in N(k)\), \(\varepsilon _{j}<\min \{ \varepsilon _{j-1}, t^{*}(R_{j-1}^{\prime },x_{j-1}), V^{R_{j}}(x_{j};f_{j}(R^{(j-1)}))-t_{j}\}\) and \(R_{j}^{\prime }\) is \( z_{j}^{\varepsilon _{j}}\)-favoring,
(iii-k)
\(x_{k}(R^{(k)}) \ne x_{k}\) and \(z_{k} \,P^{\prime }_{k} \, f_{k}(R^{(k)})\),
(iv-k)
\(x_{k}(R^{(k)})\notin \{x_{l}\}_{l\in N(k)}\), and
(v-k)
there is \(j \in N {\setminus } N(k)\) such that \(x_{j} \in \{x_{l}\}_{l \in N(k)}\) and \(z_{j} \,P_{j} \,f_{j}(R^{(k)})\).
Inductive Step.Next we show (ii-b). By Inductive Hypothesis, \(\varepsilon _{k}>0\). By (i-a), \(t_{k+1}<V^{R_{k+1}}(x_{k+1};f_{k+1}(R^{(k)})) \). By \(t_{k} \ge 0\), Remark 8 (i) and (ii-b-k), \(t^{*}(R_{k}^{\prime },x_{k})>0\). Thus, there is \( \varepsilon _{k+1}>0\) such that \(\varepsilon _{k+1}<\min \{ \varepsilon _{k}, t^{*}(R_{k}^{\prime },x_{k}),V^{R_{k+1}}(x_{k+1};f_{k+1}(R^{(k)}))-t_{k+1}\}\). By (i-b), \( x_{k+1}\ne 0\). Thus, by Fact 10, there is \(z_{k+1}^{\varepsilon _{k+1}}\) -favoring preference \(R_{k+1}^{\prime }\in {\mathcal {R}}\). Hence by (ii-b-k), (ii-b) holds.
(i)
By (iv-k), there is \(j\in N{\setminus } N(k)\) such that \( z_{j}\,P_{j}\,f_{j}(R^{(k)})\). Without loss of generality, let \(j=k+1\). Then, (i-a) holds. By (i-a), \(z_i \in L \times \mathbb {R}_+\) and Fact 8, \( x_{k+1}\ne 0\). Thus, (i-b) holds.
(ii)
The hypothesis (ii-a-k) is equivalent to (ii-a).
(iii)
(iv)
Suppose that \(x_{k+1}(R^{(k+1)}) \in \{x_{l}\}_{l \in N(k+1)}\). By (iii), since \(x_{k+1}(R^{(k+1)}) \ne x_{k+1}\), there is \(j \in N(k+1) {\setminus }\{k+1\}\) such that \(x_{k+1}(R^{(k+1)}) =x_{j}\). By \( x_{k+1}(R^{(k+1)}) \ne x_{k+1}\) and (ii-b), \(V^{R^{\prime }_{k+1}}(x_{k+1}(R^{(k+1)});(0,0)) < \varepsilon _{k+1}\). By individual rationality, \(t_{k+1}(R^{(k+1)}) \le V^{R^{\prime }_{k+1}}(x_{k+1}(R^{(k+1)});(0,0)),\) and so \(t_{k+1}(R^{(k+1)}) < \varepsilon _{k+1}\). By (ii-b), \(\varepsilon _{k+1} < t^{*}(R^{\prime }_{j},x_{j}), \) and so \(t_{k+1}(R^{(k+1)}) < t^{*}(R^{\prime }_{j},x_{j})\). However, by Lemma 2 (ii), \(t_{k+1}(R^{(k+1)}) \ge t^{*}(R^{\prime }_{j},x_{j}).\) This is a contradiction. Thus, \(x_{k+1}(R^{(k+1)}) \notin \{x_{l}\}_{l \in N(k+1)}\).
(v)
By (ii-a), (ii-b) and Lemma 2 (i), for each \(i\in N(k+1)\), there is \( j\in N\) such that \(x_{j}(R^{(k+1)})=x_{i}\). By (iv), since \( x_{k+1}(R^{(k+1)}) \notin \{x_{l}\}_{l \in N(k+1)}\), there is \(j\in N{\setminus } N(k+1)\) such that \(x_{j}(R^{(k+1)})\in \{x_{l}\}_{l\in N(k+1)}\).
By Lemma 2 (ii) and \((z,p)\in W(R)\), \( t_{j}(R^{(k+1)})>t_{j}=p_{x_{j}(R^{(k+1)})}\). Thus,Hence \(z_{j}\,P_{j}\,f_{j}(R^{(k+1)})\). The proof of Claim is completed.
$$\begin{aligned}&z_{j}\quad R_{j}\quad (x_{j}(R^{(k+1)}),p_{x_{j}(R^{(k+1)})})\, \qquad \qquad \hbox {by }(z,p)\in W(R) \\&\quad P_{j}\quad (x_{j}(R^{(k+1)}),t_{j}(R^{(k+1)})) \quad \, \hbox { by }t_{j}(R^{(k+1)})>p_{x_{j}(R^{(k+1)})} \\&\quad =\,f_{j}(R^{(k+1)}). \end{aligned}$$
By the above Claim, we derive a contradiction. For \(k=n-1\), by (i-b), for each \(i\in N\), \(x_{i}\ne 0\). If \(n>m\), it is impossible. Thus, we assume that \(n\le m\).
By (ii-a), (ii-b) and Lemma 2 (i), for each \(i\in N\), there is \(j\in N\) such that \(x_{j}(R^{(n)})=x_{i}\). However, by Claim (iv), since \( x_{n}(R^{(n)})\notin \{x_{i}\}_{i\in N}\), this is also impossible. \(\square \)
Proof of Theorem 1
4.2 Proof of Theorem 2
Throughout this subsection, we assume that \({\mathcal {R}}\supseteq {\mathcal {R}} ^C \cap {\mathcal {R}}^{++}\) and \(l\le 0\) is the associated lower bound of no bankruptcy.
Given \(a\in M\) and \(\delta >0\), define \({\mathcal {R}}^{a}(\delta )\equiv \{R_{i}\in {\mathcal {R}}:\forall b\in L{\setminus } \{a\},\ (a,0)\,P_{i}\,(b,-\delta )\}\). Note that for each \(a\in M\) and each \(\delta >0\), there is \(R_{i}\in {\mathcal {R}}^C \cap {\mathcal {R}}^{++}\) such that \( R_{i}\in {\mathcal {R}}^{a}(\delta )\). Thus, for each \(a\in M\) and each \(\delta >0\), \({\mathcal {R}}^{a}(\delta )\ne \emptyset \).
Definition 11
Given \((a,t)\in M\times \mathbb {R}_{+}\) and \(\delta > 0\), \(R_{i}^{\prime }\in {\mathcal {R}}^{a}(\delta )\) is (a, t)-favoring with subsidy \( \delta \) if for each \(b\in L{\setminus } \{a\}\), \(V^{R_{i}^{\prime }}(b;(a,t))<-\delta \).
Given \(a\in M\), \(\delta > 0\) and \(R_{i} \in {\mathcal {R}}^{a}(\delta )\), let \( t^{*}(R_{i},a,\delta )\equiv \min _{b\in L{\setminus } \{a\}}\{V^{R_{i}}(a;(b,-\delta ))\}\).
Remark 9
Let \(a\in M\), \(\delta > 0\) and \(R_{i} \in {\mathcal {R}}^{a}(\delta )\). (i) \( R_{i} \) is (a, t)-favoring with subsidy \(\delta \) if and only if \( t^{*}(R_{i},a,\delta )>t\). (ii) For each \(b\in L{\setminus } \{a\}\) and each \( t\in [0,t^{*}(R_{i},a,\delta )) \), \(V^{R_{i}}(b;(a,t))< -\delta \).
For each \(a\in M\), each \(\delta >0\) and each \(R_{i}\in {\mathcal {R}} ^{a}(\delta )\), \(t^{*}(R_{i},a,\delta )>0\).
Given \((a,t)\in M\times \mathbb {R}_{+}\), \(\varepsilon >0\) and \(\delta >0\), let \({\mathcal {R}}((a,t),\varepsilon ,\delta )\) be the set of \( (a,t)^{\varepsilon }\)-favoring preferences in \({\mathcal {R}}^{a}(\delta )\).
Fact 12
For each \((a,t) \in M \times \mathbb {R}_{+}\), each \(\varepsilon > 0\) and each \(\delta > 0\), \({\mathcal {R}}^C \cap {\mathcal {R}}^{++} \cap {\mathcal {R}} ((a,t),\varepsilon ,\delta ) \ne \emptyset \).
Given \((a,t)\in M\times \mathbb {R}_{+}\), \(\varepsilon >0\) and \(\delta >0\),
let \({\mathcal {R}}^{++}_C((a,t),\varepsilon ,\delta ) \equiv {\mathcal {R}}^C \cap {\mathcal {R}}^{++} \cap {\mathcal {R}}((a,t),\varepsilon ,\delta )\).
Given \(R\in {\mathcal {R}}^{n}\) and \(l\le 0\), let \(\delta (R,l)\equiv n(\max _{k\in N}{\max _{b\in L}{V^{R_{k}}(b;(0,0))}})-l\).
Fact 13
(Lemma 4 in Kazumura et al. (2020b)) Let f be desirable and satisfy no bankruptcy. For each \(R \in {\mathcal {R}} ^{n}\), each \(i \in N\), and each \((a,t) \in M \times \mathbb {R}_{+}\) with \( x_i(R)=a\), if there is \(j \ne i\) such that for each \(b \in L {\setminus } \{a\}\) , \(V^{R_{j}}(b;(a,t)) < -\delta (R,l)\), then \(t_{i}(R) > t\).
Lemma 3
Let f satisfy individual rationality and no bankruptcy. For each \(R \in {\mathcal {R}}^{n}\) and \(i \in N\), \(t_{i}(R) \ge -\delta (R,l).\)
Proof
Suppose that there is \(i\in N\) such that \( t_{i}(R)<-\delta (R,l).\) Note that by individual rationality, for each \(j\in N{\setminus } \{i\}\), \(t_{j}(R)\le {\max _{b\in L}{V^{R_{j}}(b;(0,0))}}\). Thus,which contradicts no bankruptcy. \(\square \)
$$\begin{aligned} \sum _{k\in N}t_{k}(R)&<\sum _{j\in N\backslash \{i\}}{\max _{b\in L}{ V^{R_{j}}(b;(0,0))}}-\delta (R,l) \\&\le (n-1)\max _{k\in N}{\max _{b\in L}{V^{R_{k}}(b;(0,0))}}-\delta (R,l) \\&=(n-1)\max _{k\in N}{\max _{b\in L}{V^{R_{k}}(b;(0,0))}}-n(\max _{k\in N}{ \max _{b\in L}{V^{R_{k}}(b;(0,0))}})+l \\&\le l \end{aligned}$$
Remark 10
Let f satisfy individual rationality and no bankruptcy. Let \(R \in {\mathcal {R}}^{n}\), \(i \in N\), and \(z_i \in M \times \mathbb {R}_+\) and \( \varepsilon > 0\) be such that \(R_{i} \in {\mathcal {R}}^{++}_C(z_{i}, \varepsilon ,\delta (R,l))\). If \(x_{i}(R) \ne x_{i}\), then \( z_{i}\,P_{i}\,f_{i}(R).\)
Proof
Since \(R_{i} \in {\mathcal {R}}^{++}_C(z_{i}, \varepsilon ,\delta (R,l))\), \(V^{R_i}(x_i(R);z_i)<-\delta (R,l)\). By no bankruptcy and Lemma 3, \(t_i(R)\ge -\delta (R,l)\). Thus \( V^{R_i}(x_i(R);z_i)<t_i(R)\), which means that \(z_{i}\,P_{i}\,f_{i}(R)\). \(\square \)
Lemma 4
Let f satisfy individual rationality and strategy-proofness. Let \(R\in {\mathcal {R}}^{n}\) and \(z_i \in M \times \mathbb {R}_+\). Assume that there is \( i\in N\) such that \(z_{i}\,P_{i}\,f_{i}(R)\). Then, (i) there are \(\varepsilon _{i} \in (0,V^{R_{i}}(x_{i};f_{i}(R))-t_{i})\) and \(R_{i}^{\prime }\in {\mathcal {R}}^{++}_C(z_{i},\varepsilon _{i},\delta (R,l))\) and (ii) \( x_{i}(R_{i}^{\prime },R_{-i})\ne x_{i}\).
Proof
(i)
By \(z_{i}\,P_{i}\,f_{i}(R)\), \( t_{i}<V^{R_{i}}(x_{i};f_{i}(R))\). Thus, there is \(\varepsilon _{i}\in (0,V^{R_{i}}(x_{i};f_{i}(R))-t_{i}).\) Moreover, by \(z_i \in M \times \mathbb { R}_+\) and Fact 12, there is a preference \(R_{i}^{\prime }\in {\mathcal {R}} ^{++}_C(z_{i},\varepsilon ,\delta (R,l))\)
Lemma 5
Let f be desirable and satisfy no bankruptcy. Let \(R \in {\mathcal {R}}^{n}\), \(N^{\prime }\subseteq N\), \(z \in A \times \mathbb {R}_+^n\) and \( (\varepsilon _i)_{i \in N^{\prime }} \in \mathbb {R}^{|N^{\prime }|}_{++}\) be such that for each \(i \in N^{\prime }\), \(x_{i} \ne 0\) and \(R_{i}\in \mathcal { R}^{++}_C(z_{i},\varepsilon ,\delta (R,l))\). Then,
(i)
for each \(i \in N^{\prime }\), there is \(j \in N\) such that \(x_{j}(R) = x_{i}\) and
(ii)
if \(i \ne j\), then \(t_{j}(R) \ge t^{*}(R_{i},x_{i},\delta (R,l)) > t_{i} \)
Proof
(i)
Let \(i\in N^{\prime }\). Suppose that for each \( j\in N\), \(x_{j}(R)\ne x_{i}\). Since \(x_{i}(R)\ne x_{i}\) and \(R_{i} \in {\mathcal {R}}^{++}_C(z_{i},\varepsilon ,\delta (R,l))\), by Remark 10, which contradicts non-wastefulness.
$$\begin{aligned} (x_{i},0)\,\underset{\text {by }0\le t_{i}}{R_{i}}\,z_{i}\,{P_{i}}\,f_{i}(R) \text {,} \end{aligned}$$
(ii)
Let \(i\in N^{\prime }\) and \(j\in N\) be such that \(i\ne j\) and \( x_{j}(R)=x_{i}\). Since \(R_{i} \in {\mathcal {R}}^{++}_C(z_{i},\varepsilon , \delta (R,l))\), by Remark 9 (ii), for each \(t\in [0,t^{*}(R_{i},x_{i},\delta (R,l)))\), \(V^{R_{i}}(b;(x_i,t)) < -\delta (R,l)\). Thus by Fact 13, \(t_{j}(R)\ge t^{*}(R_{i},x_{i},\delta (R,l))\text {.} \) By Remark 9 (i), \(t_{i}<t^{*}(R_{i},x_{i},\delta (R,l))\text {.} \) Thus, \( t_{j}(R)\ge t^{*}(R_{i},x_{i},\delta (R,l))>t_{i}\).
Proposition 2
Let \({\mathcal {R}}\supseteq {\mathcal {R}}^{++} \cap {\mathcal {R}}^C\). Let f be desirable and satisfy no bankruptcy. For each \(R \in {\mathcal {R}}^{n}\), each \( z \in Z^{min}(R)\) and each \(i \in N \), \(f_{i}(R) \, R_{i}\, z_{i}\).
Proof
Let \(R \in {\mathcal {R}}^{n}\), \(p = p^{min}(R)\) and \( z \in Z^{min}(R)\). LetSuppose that there is \(i \in N\) such that \(z_{i} \, P_{i} \, f_{i}(R)\). Without loss of generality, let \(i \equiv 1\).
$$\begin{aligned} \underline{p} \equiv \left\{ \begin{array}{ll} \min \{p_{a} \in \mathbb {R}:a \in M \text { and }p_{a}>0\} &{} \hbox {if }\exists a \in M\hbox { such that } p_{a} > 0 \\ 0 &{} \hbox {otherwise} \end{array} \right. \end{aligned}$$
Claim
For each \(k\ge 0\), there are sets N(k) and \(N(k+1)\) of distinct agents such that \(N(k+1)\supseteq N(k)\), \(\left| N(k)\right| =k\), \( \left| N(k+1)\right| =k+1\), say \(N(k)=\{1,2,\dots ,k\}\), \( N(k+1)=\{1,2,\dots ,k+1\}\), and \((\varepsilon _{j})_{j\in N(k+1)}\in \mathbb { R}_{++}^{k+1}\), \(R^{(k)}\equiv (R_{N(k)}^{\prime },R_{-N(k)})\in {\mathcal {R}} ^{n}\) and \(R^{(k+1)}\equiv (R_{N(k+1)}^{\prime },R_{-N(k+1)})\in {\mathcal {R}} ^{n}\) such that
(i-a)
\(z_{k+1} \, P_{k+1} \, f_{k+1}(R^{(k)})\) and
(i-b)
\(x_{k+1} \ne 0\),
(ii-a)
\(\varepsilon _{1}<\min (\{\underline{p},t^{*}(R_{1}^{\prime },x_{1},\delta (R,l))-t_{1}\}{\setminus } \{0\})\) and \(\ R_{1}^{\prime }\in {\mathcal {R}}^{++}_C(z_{1},\varepsilon _{1},\delta (R,l))\),
(ii-b)
for each \(j\in N(k+1){\setminus } \{1\}\), \(\varepsilon _{j}<\min \{ \varepsilon _{j-1}, t^{*}(R_{j-1}^{\prime },\,x_{j-1},\delta (R,l)),\,V^{R_{j}}(x_{j};f_{j}(R^{(j-1)}))-t_{j}\}\) and \(\ R_{j}^{\prime }\in {\mathcal {R}}^{++}_C(z_{j},\varepsilon _{j},\delta (R,l))\),
(iii)
\(x_{k+1}(R^{(k+1)}) \ne x_{k+1}\) and \(z_{k+1} \,P^{\prime }_{k+1} \, f_{k+1}(R^{(k+1)})\),
(iv)
\(x_{k+1}(R^{(k+1)})\notin \{x_{l}\}_{l\in N(k+1)}\), and
(v)
there is \(j\in N{\setminus } N(k+1)\) such that \(x_{j}\in \{x_{l}\}_{l\in N(k+1)}\) and \(z_{j}\,P_{j}\,f_{j}(R^{(k+1)})\)
To replace Lemma 1 with Lemma 4, Lemma 2 with Lemma 5, Remark 7 with Remark 10, Remark 8 with Remark 9, and Fact 10 with Fact 12, by the same logic in Proposition 1, we can prove the above claim. \(\square \)
Proof of Theorem 2
The same logic in Theorem 1. \(\square \)
5 Concluding remarks
By extending the results of Kazumura et al. (2020b), we showed that for an arbitrary numbers of agents and objects, the minimum price Walrasian mechanism is the unique ex-post revenue maximizing mechanism on rich domains among desirable mechanisms, and that no subsidy in this result can be replaced by no bankruptcy on the positive income effect domain.
There is the literature on auction with non-quasi-linear preferences. We conclude the paper by referring to some existing literature on auction with non-quasi-linear preferences and mentioning some lines for future research.
Most of the literature on auction with non-quasi-linear preferences focus on efficiency rather than on revenue maximization. Saitoh and Serizawa (2008) and Sakai (2008) show that in the cases of homogeneous objects and unit-demand preferences, the generalized Vickrey mechanism is the only mechanism satisfying strategy-proofness, efficiency, individual rationality, and no subsidy. Morimoto and Serizawa (2015) extend these results to the case of heterogeneous objects by maintaining unit-demand preferences, and show that the minimum price Walrasian mechanism is the only mechanism satisfying the same four properties on classical domain. These works assume that the number of agents is greater than objects. Thus, it is an open question whether these results hold for an arbitrary numbers of agents and objects.
Zhou and Serizawa (2018) also maintain unit-demand preferences, but study the special class of preferences, the common-tiered domains. It says that objects are partitioned into several tiers, and if objects are equally priced, agents prefer an object in the higher tier to one in the lower. They show that for each number of agents and objects, the minimum price Walrasian mechanism is the only mechanism satisfying same four properties on the common-tiered domains. Moreover, when the number of agents is less than the number of objects including null object, the minimum price Walrasian mechanism is also the only mechanism satisfying same four properties on the positive income effect domain. It is an open question whether their results also hold on the common-tiered domains exhibiting positive income effects for an arbitrary number of agents and objects.
There is also the literature on auction with non-quasi-linear preferences admitting multi-demand in various settings. Kazumura and Serizawa (2016) study classes of preferences that include unit-demand preferences and additionally includes at least one multi-demand preference, and show that when the number of agents is greater than the number of objects, no mechanism satisfies the four properties on such a domain. Malik and Mishra (2021) study the special classes of preferences, “dichotomous” domains. A preference is dichotomous if there is a set of objects such that the valuations of its supersets are constant and the valuations of other sets are zero. A dichotomous domain includes all such dichotomous preferences for a given set of objects. They show that when there are at least three agents and two objects, no mechanism satisfies the four properties on a dichotomous domain, but that for each number of agents and objects, the generalized Vickrey mechanism is the only mechanism satisfying the four properties on a class of dichotomous preferences exhibiting positive income effects.
Baisa (2020) assumes that objects are homogeneous and shows that on the class of preferences exhibiting decreasing marginal valuations, positive income effect, and single-crossing property, if the preferences are parametrized by one dimensional types, there is a mechanism satisfying the above four properties, but that if types are multi-dimensional, no mechanism satisfies these properties. Shinozaki et al. (2020) also assume the homogeneity of objects, and show that on the class of preferences including sufficiently various preferences exhibiting non-decreasing marginal valuations (minimal richness), the generalized Vickrey mechanism is the only mechanism satisfying the four properties, but that no mechanism satisfies these properties on the class of preferences that additionally includes at least one preference exhibiting decreasing marginal valuations.
These different results in various settings of multi-demand suggest that analyzing revenue maximization mechanisms in multi-demand settings would be technically challenging. However, such research is important in practical applications. Recently, Kazumura et al. (2020a) develop methods to analyze strategy-proof mechanisms in general settings including multi-demand cases. Their method does not depend on the number of agents and objects. We believe that such methods would be useful to analyze revenue maximization mechanisms in multi-demand settings.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.