Skip to main content
Top
Published in:

Open Access 04-06-2021 | Original Paper

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

Authors: Ryosuke Sakai, Shigehiro Serizawa

Published in: Social Choice and Welfare | Issue 1-2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the multi-object allocation problem with monetary transfers where each agent obtains at most one object (unit-demand). We focus on allocation mechanisms satisfying individual rationality, non-wastefulness, equal treatment of equals, and strategy-proofness. Extending the result of Kazumura et al. (J Econ Theory 188:105036, 2020b), we show that for an arbitrary number of agents and objects, the minimum price Walrasian is the unique ex-post revenue maximizing mechanism among the mechanisms satisfying no subsidy in addition to the four properties, and that no subsidy in this result can be replaced by no bankruptcy on the positive income effect domain.
Notes
We are grateful to two anonymous referees for their constructive comments. We also would like to thank Tomoya Kazumura, Debasis Mishra, Hiroki Shinozaki, Yu Zhou, and the participants of the 2nd ISI-ISER Young Economists Workshop and Nanjing-Osaka Economic Theory Workshop. We gratefully acknowledge financial support from the Joint Usage/Research Center at ISER, Osaka University, Osaka University’s International Joint Research Promotion Program (Type A), and the Japan Society for the Promotion of Science (15H05728, 19J10221, 20H05631, 20KK0027).

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

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.
(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.

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:
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) \).
 
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
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 define
$$\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}$$
and
$$\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
(Demange and Gale 1985) For each \(R \in {\mathcal {R}}^{n}\), there is \(p \in \mathbb {R}^{m}_{+}\) such that for each \(p^{\prime }\in P(R)\), \(p \le p^{\prime }\).3
Given \(R \in {\mathcal {R}}^{n}\), we denote the minimum Walrasian price for R by \(p^{min}(R)\) and define
$$\begin{aligned} Z^{min}(R) \equiv \{ z \in A \times \mathbb {R}^{n}: (z,p^{min}(R)) \in W(R) \}. \end{aligned}$$
We 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)\).
Fact 3
(Demange and Gale 1985) The minimum price Walrasian mechanism f on \({\mathcal {R}}^n\) is strategy-proof.4
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
Let
$$\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}$$
Then \(\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}\).
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\),
$$\begin{aligned} (b,t^{\prime }-\delta )\,P_{i}\,(a,t-\delta ). \end{aligned}$$
Let \({\mathcal {R}}^{++}\) be the set of positive income effect preferences.
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\).
By the same logic of Corollary 1, we have the following corollary, which implies Fact 7.
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 (bt) 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 (at)-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 (at)-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 (at) -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}\).
 
\(\square \)
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,
$$\begin{aligned} (x_{i},0)\,\underset{\text {by }0\le t_{i}}{R_{i}}\,z_{i}\,P_{i}\,f_{i}(R), \end{aligned}$$
which contradicts non-wastefulness.
 
(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}\).
 
\(\square \)
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)\). Let
$$\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}$$
Suppose that there is \(i \in N\) such that \(z_{i} \, P_{i} \, f_{i}(R)\). Without loss of generality, let \(i \equiv 1\).
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\).
(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)
By (i-a), (ii-a) and Lemma 1 (ii), \(x_{1}(R^{(1)})\ne x_{1}\). Thus since \(R_{1}^{\prime }\) is \(z_{1}^{\varepsilon _{1}}\)-favoring, by Remark 7, \(z_{1}\,P_{1}^{\prime }\,f_{1}(R^{(1)})\).
 
(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}$$
 
Thus, \(z_{2}\,P_{2}\,f_{2}(R^{(1)})\).
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.
(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).
 
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.
(iii)
By (i-a), (ii-a) and Lemma 1 (ii), \(x_{k+1}(R^{(k+1)})\ne x_{k+1}\). Thus since \(R_{k+1}^{\prime }\) is \(z_{k+1}\)-favoring, by Remark 7, \( z_{k+1}\,P_{k+1}^{\prime }\,f_{k+1}(R^{(k+1)})\).
(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,
$$\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}$$
Hence \(z_{j}\,P_{j}\,f_{j}(R^{(k+1)})\). The proof of Claim is completed.
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
By Proposition 1 and Fact 9, a minimum price Walrasian mechanism is ex-post revenue optimal in the class of desirable mechanisms satisfying no subsidy. The uniqueness of the ex-post revenue optimal mechanism directly follows from the proof of Theorem 1 in Kazumura et al. (2020b). \(\square \)

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 (at)-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 (at)-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,
$$\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}$$
which contradicts no bankruptcy. \(\square \)
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))\)
 
(ii)
Directly follows from the proof of Lemma 1 (ii).
 
\(\square \)
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,
$$\begin{aligned} (x_{i},0)\,\underset{\text {by }0\le t_{i}}{R_{i}}\,z_{i}\,{P_{i}}\,f_{i}(R) \text {,} \end{aligned}$$
which contradicts non-wastefulness.
 
(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}\).
 
\(\square \)
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)\). Let
$$\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}$$
Suppose that there is \(i \in N\) such that \(z_{i} \, P_{i} \, f_{i}(R)\). Without loss of generality, let \(i \equiv 1\).
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.
Footnotes
1
See Sect. 3.1 for the formal definition of richness.
 
2
Kazumura et al. (2020b) assume that \({\mathcal {R}} \subseteq {\mathcal {R}}^C\). We discuss the difference of the domains and the relation of results in Sect. 3.
 
3
\(p \le p^{\prime }\) means that \(p_{a} \le p^{\prime }_{a}\) for each \(a \in M\).
 
4
Precisely, they show that the minimum price Walrasian mechanism is group strategy-proof; we say a mechanism f is group strategy-proof if for each \(R \in {\mathcal {R}}^{n}\) and each \(N^{\prime }\subseteq N\), there is no \(R^{\prime }_{N^{\prime }} \in {\mathcal {R}}^{|N^{\prime }|}\) such that for each \(i \in N\), \(f_{i}(R^{\prime }_{N^{\prime }},R_{-N^{\prime }})\,P_{i}\,f_{i}(R).\)
 
5
\(p^{\prime }>p \) means that \(p_{a}^{\prime }>p_{a}\) for each \(a\in M\).
 
Literature
go back to reference Alkan A, Gale D (1990) The core of the matching game. Games Econ Behav 2:203–212CrossRef Alkan A, Gale D (1990) The core of the matching game. Games Econ Behav 2:203–212CrossRef
go back to reference Baisa B (2020) Efficient multi-unit auctions for normal goods. Theor Econ 15:361–423CrossRef Baisa B (2020) Efficient multi-unit auctions for normal goods. Theor Econ 15:361–423CrossRef
go back to reference Demange G, Gale D (1985) The strategy structure of two-sided matching markets. Econometrica 53:873–888CrossRef Demange G, Gale D (1985) The strategy structure of two-sided matching markets. Econometrica 53:873–888CrossRef
go back to reference Kazumura T, Mishra D, Serizawa S (2020a) Mechanism design without quasilinearity. Theor Econ 15:511–544CrossRef Kazumura T, Mishra D, Serizawa S (2020a) Mechanism design without quasilinearity. Theor Econ 15:511–544CrossRef
go back to reference Kazumura T, Mishra D, Serizawa S (2020b) Strategy-proof multi-object mechanism design: ex-post revenue maximization with non-quasilinear preferences. J Econ Theory 188:105036CrossRef Kazumura T, Mishra D, Serizawa S (2020b) Strategy-proof multi-object mechanism design: ex-post revenue maximization with non-quasilinear preferences. J Econ Theory 188:105036CrossRef
go back to reference Kazumura T, Serizawa S (2016) Efficiency and strategy-proofness in object assignment problems with multi-demand preferences. Soc Choice Welf 47:633–663CrossRef Kazumura T, Serizawa S (2016) Efficiency and strategy-proofness in object assignment problems with multi-demand preferences. Soc Choice Welf 47:633–663CrossRef
go back to reference Malik M, Mishra D (2021) Pareto efficient combinatorial auctions: dichotomous preferences without quasilineality. J Econ Theory 191:105128CrossRef Malik M, Mishra D (2021) Pareto efficient combinatorial auctions: dichotomous preferences without quasilineality. J Econ Theory 191:105128CrossRef
go back to reference Morimoto S, Serizawa S (2015) Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule. Theor Econ 10:445–487CrossRef Morimoto S, Serizawa S (2015) Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule. Theor Econ 10:445–487CrossRef
go back to reference Saitoh H, Serizawa S (2008) Vickrey allocation rule with income effect. Econ Theory 35:391–401CrossRef Saitoh H, Serizawa S (2008) Vickrey allocation rule with income effect. Econ Theory 35:391–401CrossRef
go back to reference Sakai T (2008) Second price auctions on general preference domains: two characterization. Econ Theory 37:347–356CrossRef Sakai T (2008) Second price auctions on general preference domains: two characterization. Econ Theory 37:347–356CrossRef
go back to reference Shinozaki H, Kazumura T, Serizawa S (2020) Efficient and strategy-proof multi-unit object allocation with money: (Non)decreasing marginal valuations without quasi-linearity. ISER Discussion Paper, No. 1097 Shinozaki H, Kazumura T, Serizawa S (2020) Efficient and strategy-proof multi-unit object allocation with money: (Non)decreasing marginal valuations without quasi-linearity. ISER Discussion Paper, No. 1097
go back to reference Zhou Y, Serizawa S (2018) Strategy-proofness and efficiency for non-quasi- linear and common-tiered-object preferences: characterization of minimum price rule. Game Econ Behav 109:327–363CrossRef Zhou Y, Serizawa S (2018) Strategy-proofness and efficiency for non-quasi- linear and common-tiered-object preferences: characterization of minimum price rule. Game Econ Behav 109:327–363CrossRef
Metadata
Title
Strategy-proof mechanism design with non-quasi-linear preferences: ex-post revenue maximization for an arbitrary number of objects
Authors
Ryosuke Sakai
Shigehiro Serizawa
Publication date
04-06-2021
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 1-2/2023
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-021-01333-y

Other articles of this Issue 1-2/2023

Social Choice and Welfare 1-2/2023 Go to the issue

Premium Partner