Optimality of the uniform rule under single-peaked preferences

Abstract

Consider the problem of distributing a fixed amount of a divisible resource among agents whose preferences are single-peaked. The uniform rule has been widely characterized under an ordinal utility approach. Instead, in a cardinal utility approach, we show that the uniform rule is the only consistent rule that maximizes the worst-case surplus among strategy-proof and ordinally efficient mechanisms.

1 Introduction

Consider the problem of allocating a divisible resource among agents with single-peaked preferences. Single-peaked preferences have been extensively studied in the social choice literature, with much concern about ordinal information in the resource allocation problem. A solution to the problem that has garnered much attention is the uniform rule (Benassy 1982), which entitles agents to obtain a share at least as good as an equal division of the resource. This solution has been widely characterized by ordinal efficiency and various properties including strategy-proofness (Sprumont 1991; Ching 1994), consistency (Thomson 1994b; Dagan 1996), monotonicity (Thomson 1994a, 1995, 1997; Sönmez 1994) and no-envy (Ching 1992; Chun 2000).

Our work differs from the literature by quantifying the quality of an outcome in the allocation problem. We focus on the case where agents report their cardinal intensities over their share, therefore incentive compatibility of the mechanism is desirable. Our incentive compatibility requirement is truth-telling in dominant strategy, that is, strategy-proofness. The traditional impossibility result of finding strategy-proof mechanisms that maximize economic surplus still holds in the limited domain of concave single-peaked preferences that we study in this paper (Hurwicz 1972; Holmström 1979). To overcome this impossibility, our paper refines the optimality criteria and provides a novel characterization of the uniform rule in this setting.

When cardinal utilities matter, an optimality criterion used to rank allocation rules in the recent literature is the worst relative surplus (WS). The worst relative surplus of an allocation rule is the smallest ratio of economic surplus to maximal surplus over all utility profiles. An optimal mechanism will generate the greatest worst relative surplus within a group of strategy-proof mechanisms. With this robustness metric, the social planner does not need to know specific utility functions of agents or to have a prior belief about their distributions. Thus, the index WS appeals to an extremely conservative planner who aims to select a mechanism for the best performance in the worst-case. In the domain of single-peaked preferences, Procaccia and Tennenholtz (2013) and Alon et al. (2010) explore worst-case strategy-proof rules for the problem of locating a public good on a line and on general networks, respectively.¹ The worst-case analysis is also adopted in Aggarwal et al. (2005), Goldberg et al. (2001, 2006), Hartline and McGrew (2005), Johari and Tsitsiklis (2004), Cavallo (2006), Moulin (2009), Moulin and Shenker (2001), Guo and Conitzer (2009, 2010), You (2015), Juarez and Kumar (2013), and Fischer and Klimm (2015).²

Here, our optimality criterion strengthens the worst relative surplus as it requires optimal mechanisms to satisfy consistency in the worst-case. Once an optimal mechanism decides the allocation to each agent in a group N, for any subgroup $S\subseteq N$, there should not be a redistribution of the resource that makes every agent in S better off in the worst-case scenario. Thus, our optimal mechanism guarantees the greatest worst relative surplus not only for a group N but also for any subgroup of N. Strengthening the criterion with consistency, we show that the uniform rule is uniquely optimal among strategy-proof and ordinally efficient rules. It guarantees the greatest surplus at any coalition of agents when the good is either overdemanded or underdemanded (Theorem 1). Furthermore, our characterization is tight, as removing either of the main assumptions in the Theorem provides a fairly large class of efficient rules (Remarks 1–4).

2 Model

Consider a group of agents $N=\{1,\dots , n\}$ for $n\ge 2$. For any $C>0$, a utility function $u_i\in \mathcal {U}(C)$ is a function $u_i:[0,C]\rightarrow \mathbb R_{+}$ that is continuous, concave, and single-peaked: there exists a peak, $x^*_i(u_i) \in [0,C]$, such that for all $y_i, z_i \in [0,C]$, if either $x^*_i(u_i)< y_i < z_i$ or $z_i< y_i< x^*_i(u_i)$, then $u_i(x^*_i)> u_i(y_i) > u_i(z_i)$. We denote by ${\mathcal {U}} (S,C)=\mathcal {U}(C)^S$ the set of utility functions in $\mathcal {U}(C)$ for the agents in S. For the profile $u\in {\mathcal {U}}(S,C)$, let $x^*_S(u) = \sum _{i \in S }x^*_i(u_i)$ be the sum of the peaks of u. If $x^*_S(u) > C$ or $x^*_S(u) < C$, then a resource is overdemanded or underdemanded, respectively. Let $\bar{\mathcal {U}}(S,C)$ and $\underline{\mathcal {U}}(S,C)$ be the set of utility profiles in ${\mathcal {U}} (S,C)$ that are overdemanded and underdemanded for the agents in S and the amount of resource C, respectively.

Definition 1

A problem$(S, C, u_S)$ consists of

• a group of participants $S\subseteq N$,

• an amount to divide $C>0$, and

• a profile of utility functions $u_S\in {\mathcal {U}} (S,C)$.

We denote by $\mathcal {P}$ the set of problems. For any $C>0$ and $S\subseteq N$, the set of feasible allocations $Y(S,C)=\{y \in [0,C]^S | \sum _{i \in S } y_i = C \}$ is the set of vectors that distribute C among the agents in S.

Definition 2

A mechanismF is a function that associates to each problem $(S, C, u_S)\in \mathcal {P}$ a feasible allocation $F(S, C, u_S)\in Y(S,C)$.

The uniform rule$F^U$ is a well-known mechanism that associates the following feasible allocation to problem $(S, C, u_S):$ for all $i \in S$, if $x^*_S(u_S) \ge C$, then $F^U_i(S, C, u_S) =\min \{x^*_i(u_i),\mu \}$ where $\mu$ solves the equation $\sum _{i \in S} \min \{ x^*_i(u_i), \mu \}=C$. If $x^*_S(u_S) \le C$, then $F^U_i(S, C, u_S) = \max \{x^*_i(u_i),\nu \}$ where $\nu$ solves $\sum _{i \in S} \max \{ x^*_i(u_i), \nu \}=C$.

Definition 3

• A mechanism F is strategy-proof if for any problem $(S,C,u_S)$, $i \in S$, and $u'_i \in {\mathcal {U}(C)}$,

  $$\begin{aligned} u_i(F(S,C,[u_i,u_{S\setminus \{i\}}])) \ge u_i(F(S,C,[u'_i,u_{S\setminus \{i\}}])). \end{aligned}$$

• A mechanism F is same-sided if for any problem $(S,C,u_S)$, whenever $x^*_S(u_S) \le C$, $x^*_i (u_i)\le F_i(S,C,u_S)$ holds for all $i\in S$, and whenever $x^*_S(u_S) \ge C$, $x^*_i (u_i)\ge F_i(S,C,u_S)$ holds for all $i\in S$.

• A mechanism F is consistent if for all $C>0$, all $u\in {\mathcal {U}}(N,C)$ and all $S\subseteq N$, $F_i(N,C, u)=F_i(S,\sum _{i\in S}F_i(N,C, u), u_S)$ for all $i\in S$.

A mechanism is strategy-proof if agents do not gain by reporting any utility function different than their true preferences. A mechanism is same-sided if no agent is allocated more than their peak when the good is overdemanded, and no less than their peak when the good is underdemanded. Same-sidedness is equivalent to ordinal efficiency for strategy-proof mechanisms. A mechanism is consistent if after any subgroup of agents have been allocated their share of the resource, the allocations for the remaining agents do not change upon reassessing their allocation with the remaining resource. These three properties have been well studied in the literature of resource allocation.

Given a problem $(S, C, u_S)$, each allocation $y\in Y(S,C)$ generates economic surplus of $\sum _{i \in S}u_i(y_i)$. If $y\in Y(S,C)$ satisfies $y \in$$\arg \max _{z \in Y(S,C)}$$\sum _{i \in S} u_i(z_i)$, the allocation y is efficient. When y is efficient, the economic surplus is said to be the efficient surplus. We denote by Eff(u, S, C) the efficient surplus given the utility profile u, the coalition S and the amount of resource C.

We measure the performance of a mechanism by computing the worst relative surplus at every coalition and resource. Given a utility profile $u\in {\mathcal {U}}(S,C)$, the relative surplus at an allocation is the ratio of the economic surplus to efficient surplus.

The worst relative surplus of the mechanism F at a coalition $S \subseteq N$ and resource C for the overdemanded case is

$$\begin{aligned} \overline{WS}(F,S,C)=\inf _{u\in \bar{\mathcal {U}}(S,C) } \frac{\sum _{i\in S} u_i(F_i(S,C, u))}{Eff(u,S,C)} \end{aligned}$$

The worst relative surplus of the mechanism G at a coalition $S \subseteq N$ and resource C for the underdemanded case is

$$\begin{aligned} \underline{WS}(G,S,C)=\inf _{u\in \underline{\mathcal {U}}(S,C)} \frac{\sum _{i\in S} u_i(G_i(S, C, u))}{Eff(u,S, C)} \end{aligned}$$

Definition 4

(Optimality of a mechanism)

• A strategy-proof and same-sided mechanism $F^*$ is optimal for the overdemanded case if for any other strategy-proof and same-sided mechanism F, any group $S\subseteq N$ and any amount of resource $C>0$ we have that $\overline{WS}(F,S,C)\le \overline{WS}(F^*,S,C).$

• A strategy-proof and same-sided mechanism $G^*$ is optimal for the underdemanded case if for any other strategy-proof and same-sided mechanism G, any group $S\subseteq N$ and any amount of resource $C>0$ we have that $\underline{WS}(G,S,C)\le \underline{WS}(G^*,S,C)$.

Theorem 1

• (i) The uniform rule $F^U$ is the unique optimal and consistent mechanism for the overdemanded case. Moreover, $\overline{WS}(F^U, S, C)=\frac{1}{|S|}$ for any $S\subseteq N$ and any $C>0$.

• (ii) The uniform rule $F^U$ is the unique optimal and consistent mechanism for the underdemanded case. Moreover, $\underline{WS}(F^U, S, C)=\frac{|S|-1}{|S|}$ for any $S\subseteq N$ such that $|S|>1$, and any $C>0$.

Proof

A critical characterization of strategy-proof and same-sided mechanisms due to Barberà et al. (1997) is introduced below. The class of strategy-proof and same-sided mechanisms includes an enormous number of quite varied mechanisms. $\square$

Lemma 1

A mechanism F is strategy-proof and same-sided if and only if for each $i\in N$ there exists $a_i:{\mathcal {U}}(N\setminus i,C) \rightarrow [0,C]$ and $b_i: {\mathcal {U}}(N\setminus i,C) \rightarrow [0,C]$, such that $a_i(u_{-i})\le b_i(u_{-i})$ and $\sum _{i \in N}\min [x^*_i(u_{i}),b_i(u_{-i})]=C \ {{for \ all }}\ u \ such\ that\ x^*_N(u) > C,$$\sum _{i \in N}\max [x^*_i(u_{i}),a_i(u_{-i})]=C \ { for\ all} \ u \ { such\ that}\ x^*_N(u)\le C,$ and $F_i(N, C, u)= \min [x^*_i(u_i),b_i(u_{-i})]$ if $x^*_N(u) > C$, $F_i(N, C, u) = \max [x^*_i(u_i),a_i(u_{-i})]\ {{if}}\ x^*_N(u) \le C$.

Lemma 1 states that each agent will receive his or her most preferred share or personalized cap (floor) for the case of overdemanded (underdemanded, respectively) resource if and only if the mechanism is strategy-proof and same-sided. We use this lemma to prove our main theorem. We split this proof into the overdemanded and underdemanded cases.

Proof for the underdemanded case

Step A1$\overline{WS}(F^U,S,C)= \frac{1}{|S|}$ for any coalition $S\subseteq N$ and any $C>0$. First, we show that $\overline{WS}(F^U,S,C)\ge \frac{1}{|S|}$ for all $S\subseteq N$ and all $C>0$. Consider $v_S\in \bar{\mathcal {U}}(S,C)$ and suppose that $E_i$ is the peak of $v_i$ on [0, C] for each $i\in S$. Since $v_i$ is non-decreasing and concave in the interval $[0,E_i]$, we have $v_i(\min \{\frac{C}{|S|}, E_i\})\ge \frac{v_i(\min \{C, E_i\})}{|S|}$. This implies

$$\begin{aligned} \frac{\sum _{i\in S} v_i(\min \{\frac{C}{|S|}, E_i\})}{\sum _{i\in S} v_i(\min \{C, E_i\})} \ge \frac{1}{|S|} \end{aligned}$$

Furthermore, since $F^U_i(S, C, v_S)\ge \min \{\frac{C}{|S|}, E_i\}$ for each $i\in S$, we have

$$\begin{aligned} \frac{\sum _{i\in S} v_i(F^U_i(S, C, v_S))}{\sum _{i\in S} v_i(\min \{C, E_i\})} \ge \frac{\sum _{i\in S} v_i(\min \{\frac{C}{|S|}, E_i\})}{\sum _{i\in S} v_i(\min \{C, E_i\})} \ge \frac{1}{|S|} \end{aligned}$$

Finally, from $Eff(v_{S},S,C)\le \sum _{i\in S} v_i(\min \{C, E_i\})$, we have

$$\begin{aligned} \frac{\sum _{i\in S} v_i(F^U_i(S, C, v_S))}{Eff(v_{S},S, C)}\ge \frac{\sum _{i\in S} v_i(F^U_i(S, C, v_S))}{\sum _{i\in S} v_i(\min \{C, E_i\})} \ge \frac{1}{|S|} \end{aligned}$$

Hence, $\overline{WS}(F^U,S,C)\ge \frac{1}{|S|}$ for all $S\subseteq N$ and all $C>0$.

Next, we show that $\overline{WS}(F^U,S,C)\le \frac{1}{|S|}$ for all $S\subseteq N$ and all $C>0$. In order to do so, for $S\subseteq N$ and $C>0$, we construct a set of overdemanded utility profiles $u^\delta _S\in \bar{\mathcal {U}}(S,C)$ for each $\delta >0$ such that $\lim _{\delta \rightarrow 0}\frac{\sum _{i\in S} u_i^\delta (F_i^U(S,C,u^\delta _S))}{Eff(u^\delta _S,S,C)}=\frac{1}{|S|}$.

Indeed, let $S=\{i_1,i_2,\dots , i_s\}$ where $i_1<i_2<\dots < i_s$. For each $\delta >0$ and $i_k\in S$, define the linear utility function $u_{i_k}^{\delta }(x)=\delta ^{k-1} x$ for all $x\in [0,C]$. Since the peak of $u_{i_k}^\delta$ equals to C for all $i_k\in S$, then $u^\delta _S\in \bar{\mathcal {U}}(S,C)$ and the uniform rule makes an allocation $F^U_{i_k}(N,C,u^\delta _S)=\frac{C}{s}$ to each ${i_k}\in S$ where $s=|S|$. Thus, the uniform rule $F^U(S,C,u_S^\delta )$ generates a surplus equal to $\sum _{k=1}^s \delta ^{k-1} (\frac{C}{s})$. For each $\delta <1$, efficiency in the problem $(S,C,u_S^\delta )$ gives agent $i_1$ the total resource C: $Eff(u_S, S, C)=C$. Thus, we have

$$\begin{aligned} \overline{WS}(F^U, S,C)\le \lim _{\delta \rightarrow 0}\frac{\sum _{k=1}^s \delta ^{k-1} (\frac{C}{s}) }{C}=\frac{1}{s} \end{aligned}$$

Hence, $\overline{WS}(F^U,S,C)= \frac{1}{|S|}$ for any coalition $S\subseteq N$ and any $C>0$.

Step A2 Suppose that a strategy-proof and same-sided mechanism F is optimal for the agents in N and resource $C>0$. Then for every utility profile u, we have that $b_i(u_{-i})\ge \frac{C}{n}$ for any $i\in N$.

We prove step A2 by contradiction. Suppose there exists an overdemanded utility profile u and agent i such that $b_i(u_{-i})< \frac{C}{n}$. Let agent i’s utility function be $u_i^\alpha (x)=\alpha x$ for $0\le x\le C$ and $\alpha >0$. Since the peak of u is overdemanded and the peak of $u_i^\alpha$ is at C, then the profile $(u_i^\alpha , u_{-i})$ is also overdemanded. For a large enough $\alpha$, the efficient allocation is giving C to agent i. Thus, $Eff((u_i^\alpha ,u_{-i}),N,C)= \alpha C$ for large $\alpha$. On the other hand, the surplus at $F(N,C,(u_i^\alpha , u_{-i}))$ satisfies,

$$\begin{aligned} \alpha b_i(u_{-i})+ \sum _{k\in N\setminus i} u_k(F_k(N,C,(u_i^\alpha , u_{-i})))\le \alpha b_i(u_{-i})+ \sum _{k\in N\setminus i} u_k(x^*_k(u_k)). \end{aligned}$$

Thus,

$$\begin{aligned} \overline{WS}(F,N,C)\le & {} \lim _{\alpha \rightarrow \infty } \frac{\alpha b_i(u_{-i})+ \sum _{k\in N\setminus i} u_k(x^*_k(u_k)) }{\alpha C}=\frac{b_i(u_{-i})}{C}<\frac{1}{n}\\= & {} \overline{WS}(F^U, N,C), \end{aligned}$$

where the last equality comes by step A1. This contradicts that F is optimal.

In particular, Lemma 1 and Step A2 imply the following two conditions for an optimal, strategy-proof and same sided-mechanism F: (a) if $x^*_i(u_i)\le \frac{C}{n}$, then $F_i(N,C, u)=x^*_i(u_i)$; (b) if $F_i(N,C,u)<x^*_i(u_i)$, then $F_i(N,C,u)\ge \frac{C}{n}$.

For the next two steps, we fix a strategy-proof and same-sided mechanism F that is optimal for any coalition $S\subseteq N$ and resource $C>0$.

Step A3 For any profile $u\in \bar{\mathcal {U}}(N,C)$, the mechanism F either assigns the agents their peak or a constant amount.

Consider the set $S^*=\{i\in N | F_i(N,C,u)<x^*_i(u_i)\}$ composed of the agents who receive allocations different from their peaks. Consistency implies $F_i(S^*,D, u_{S^*})=F_i(N,C, u)$ for any $i\in S^*$ where $D=\sum _{i\in S^*}F_{i}(N,C,u)$. Since F is optimal at coalition $S^*$ and condition (b) in step A2 holds for coalition $S^*$, we have $F_i(S^*,D,u_{S^*})\ge \frac{\sum _{i\in S^*}F_{i}(S^*,D,u_{S^*})}{|S^*|}$ for any $i\in S^*$. Hence, by feasibility, $F_i(N,C,u)=F_i(S^*,D,u_{S^*})= \frac{\sum _{i\in S^*}F_{i}(S^*,D,u_{S^*})}{|S^*|}$ for any $i\in S^*.$

Step A4 For any utility profile u, assume, without loss of generality, that $x^*_1(u_1)\le x^*_2(u_2)\le \dots \le x^*_n(u_n)$. There exists $k\le n$ such that $S^*=\{k,k+1,\dots , n\}$. That is, the set of agents who do not receive their peaks is a set of consecutive agents with the highest peaks.

Suppose for the sake of contradiction that there exists $i<j$ such that $F_i(N,C,u)<x^*_i(u_i)$ and $F_j(N,C,u)=x^*_j(u_j)$. Let $D=F_i(N,C,u)+ F_j(N,C,u)$. By consistency, optimality on the set $\{i,j\}$ and condition (b) in step A2, we have $F_i(N,C,u)=F_i(\{i,j\},D,u_{\{i,j\}})\ge \frac{F_i(\{i,j\},D,u_{\{i,j\}})+ F_j(\{i,j\},D,u_{\{i,j\}})}{2}$$= \frac{F_i(N,C,u)+ F_j(N,C,u)}{2}.$ This contradicts to $F_j(N,C,u)=x^*_j(u_j)\ge x^*_i(u_i)>F_i(N,C,u)$.

Finally, there is a unique rule that satisfies steps A3 and A4. This rule is the uniform rule.$\square$

Proof for the underdemanded case

The following steps parallel Steps A1-A4 above.

Step B1$\underline{WS}(F^U, S, C)=\frac{|S|-1}{|S|}$ for any coalition $S\subseteq N$ with $|S|>1$ and any $C>0$.

First, we show that $\underline{WS}(F^U,S,C)\ge \frac{|S|-1}{|S|}$ for $C>0$ and $|S|>1$. Consider $v_S\in \underline{\mathcal {U}}(S,C)$ and suppose that $E_i$ is the peak of $v_i$ on [0, C] for each $i\in S$. Since $v_i$ is non-increasing, non-negative and concave in the interval $[E_i,C]$, we have $v_i(\max \{\frac{C}{|S|}, E_i\})\ge \frac{v_i(E_i)(|S|-1)}{|S|}$. This implies

$$\begin{aligned} \frac{\sum _{i\in S} v_i(\max \{\frac{C}{|S|}, E_i\})}{\sum _{i\in S} v_i(E_i)} \ge \frac{|S|-1}{|S|} \end{aligned}$$

Furthermore, since $E_i\le F^U_i(S, C, v_S)\le \max \{\frac{C}{|S|}, E_i\}$ for each $i\in S$, we have

$$\begin{aligned} \frac{\sum _{i\in S} v_i(F^U_i(S, C, v_S))}{\sum _{i\in S} v_i(E_i)} \ge \frac{\sum _{i\in S} v_i(\max \{\frac{C}{|S|}, E_i\})}{\sum _{i\in S} v_i(E_i)} \ge \frac{|S|-1}{|S|} \end{aligned}$$

Finally, from $Eff(v_{S},S,C)\le \sum _{i\in S} v_i(E_i)$, we have

$$\begin{aligned} \frac{\sum _{i\in S} v_i(F^U_i(S, C, v_S))}{\sum _{i\in S} Eff(v_{S},S,C)} \ge \frac{\sum _{i\in S} v_i(F^U_i(S, C, v_S))}{\sum _{i\in S} v_i(E_i)} \ge \frac{|S|-1}{|S|} \end{aligned}$$

Hence, $\underline{WS}(F^U, S, C)\ge \frac{|S|-1}{|S|}$ for all $C>0$ and $S\subseteq N$.

Next, we show that $\underline{WS}(F^U,S,C)\le \frac{|S|-1}{|S|}$ for all $C>0$, and $S\subseteq N$ such that $|S|>1$. We do so by constructing a set of underdemanded utility profiles $v^\delta _S\in \underline{\mathcal {U}}(S,C)$ for each $\delta >0$ such that $\lim _{\delta \rightarrow 0}\frac{\sum _{i\in S} v_i^\delta (F_i^U(S,C,v^\delta _S))}{Eff(v^\delta _S,S,C)}=\frac{|S|-1}{|S|}$.

Indeed, let $S=\{i_1,i_2,\dots , i_s\}$, for $s>1$, where $i_1<i_2<\dots < i_s$. For each $\delta >0$ we define $v^\delta _{i_s}(x)=\delta (C-x)$ and $v^\delta _{i_1}(x)=v^\delta _{i_2}(x)\dots =v^\delta _{i_{s-1}}(x)=(C-x)$ for $0\le x\le C$. The peak of each agent at the utility profile $v^\delta _S=(v^\delta _{i_1},\dots , v^\delta _{i_s})$ is at zero, thus $v^\delta _S\in \underline{\mathcal {U}}(S,C)$. Furthermore, since all agents have the same peak, the uniform allocation $F^U$ allocates $\frac{C}{s}$ to each agent. Thus, $F^U(S, C,v_S^\delta )$ generates a surplus equal to $(s-1)(C-\frac{C}{s})+\delta (C-\frac{C}{s})=\frac{(s-1)C(s-1+\delta )}{s}$.

On the other hand, for $\delta <1$, the efficient allocation at $v^\delta _S$ allocates the full amount C to agent $i_s$. It generates an efficient surplus $Eff(v^\delta _S,S, C)=(s-1)C$.

Thus,

$$\begin{aligned} \underline{WS}(F^U, S, C)\le \lim _{\delta \rightarrow 0} \frac{(s-1)C(s-1+\delta )/s}{(s-1)C}=\frac{s-1}{s} \end{aligned}$$

Hence, $\underline{WS}(F^U, S, C)= \frac{|S|-1}{|S|}$ for all $C>0$ and $S\subseteq N$ such that $|S|>1$.

Step B2 Suppose that the strategy-proof and same-sided mechanism F is optimal for the agents in N and resource $C>0$. Then for every utility profile u, we have that $a_i(u_{-i})\le \frac{C}{n}$ for any i.

We prove step 2 by contradiction. Suppose there exists an underdemanded utility profile u and agent i such that $a_i(u_{-i})> \frac{C}{n}$. Let agent i’s utility function be $u_i^\alpha (x)=\alpha -\frac{\alpha }{C}x$ for $0\le x\le C$ and $\alpha >0$. Since the peak of $u_i^\alpha$ is at 0, then the profile $(u_i^\alpha , u_{-i})$ is also underdemanded. Furthermore, for a large enough $\alpha$, the efficient allocation requires agent i to receive nothing and the other agents to split the resource C. Thus, $Eff((u_i^\alpha , u_{-i}),N,C)= \alpha +\sum _{j\not = i} u^j(E^j) \ge \alpha$ for large $\alpha$, where $E^j$ is the efficient allocation of the resource to agent $j\not = i$. On the other hand, by Lemma 1 and $a_i(u_{-i})> \frac{C}{n}$, the surplus under F at the profile $(u_i^\alpha , u_{-i})$ satisfies

$$\begin{aligned}&u_i^\alpha (F_i(N, C, (u_i^\alpha , u_{-i})))+\sum _{k\not =i} u_k(F_k(N, C, (u_i^\alpha , u_{-i})))\\&\quad \le \alpha -\frac{\alpha }{C}a_i(u_{-i})+\sum _{k\not = i} u_k(x^*_k(u_{k})) \end{aligned}$$

from Lemma 1. Thus, we have

$$\begin{aligned} \underline{WS}(F,N,C)\le \lim _{\alpha \rightarrow \infty } \frac{\alpha -\frac{\alpha }{C}a_i(u_{-i})+\sum _{k\not = i} u_k(x^*_k(u_{k}))}{\alpha }=1-\frac{a_i(u_{-i})}{C} < \frac{n-1}{n} \end{aligned}$$

Therefore, this inequality and step B1 imply that F is not optimal, which is a contradiction.

In particular, Lemma 1 and Step B2 imply the following conditions for an optimal, strategy-proof and same-sided mechanism F: (a) if $x^*_i(u_i)\ge \frac{C}{n}$, then $F_i(N,C,u)=x^*_i(u_i)$; (b) if $F_i(N,C,u)>x^*_i(u_i)$, then $F_i(N,C,u)\le \frac{C}{n}$.

For the next two steps, we fix a strategy-proof and same-sided mechanism F that is optimal for any coalition $S\subseteq N$ and resource $C>0$.

Step B3 For any profile $u\in \underline{\mathcal {U}}(N,C)$, the mechanism F either assigns the agents their peak or a constant amount.

Consider the set $S^*=\{i\in N | F_i(N,C,u)>x^*_i(u_i)\}$ composed of the agents who receive an allocation different from their peak. Let $D=\sum _{i\in S^*} F_i(N,C,u)$. By applying optimality on $S^*$, consistency and condition (b) in step B2, we have $F_i(N,C,u)=F_i(S^*, D, u_{S^*})\le \frac{\sum _{i\in S^*}F_{i}(S^*,D,u_{S^*})}{|S^*|}$ for any $i\in S^*$. Hence, by feasibility, $F_i(N,C,u)= \frac{\sum _{i\in S^*}F_{i}(N,C,u)}{|S^*|}$ for any $i\in S^*.$

Step B4 For any utility profile u, assume, without loss of generality, that $x^*_1(u_1)\le x^*_2(u_2)\le \dots \le x^*_n(u_n)$. There exists $k\le n$ such that $S^*=\{1,\dots , k\}$. That is, the set of agents who do not receive their peak is a set of consecutive agents with the lowest peaks.

Suppose that there exists $i>j$ such that $F_i(N,C,u)>x^*_i(u_i)$ and $F_j(N,C,u)=x^*_j(u_j)$. Let $D=F_i(N,C,u)+ F_j(N,C,u)$. By consistency, optimality on the set $\{i,j\}$ and condition (b) in step B2, we have $F_i(N,C,u)=F_i(\{i,j\},D,u_{\{i,j\}})\le \frac{F_i(\{i,j\},D,u_{\{i,j\}})+ F_j(\{i,j\},D,u_{\{i,j\}})}{2}=\frac{F_i(N,C,u)+ F_j(N,C,u)}{2}$. This contradicts to $F_j(N,C,u)=x^*_j(u_j)\le x^*_i(u_i)<F_i(N,C,u)$. Finally, there is a unique rule that satisfies steps B3 and B4. This rule is the uniform rule. $\square$

(This characterization is tight, as shown in the next remarks.)

Remark 1

(Without same-sideness) The assumption of same-sideness is necessary to derive the result. Without same-sidedness, the equal division rule $F(S,C,u)=\frac{C}{|S|}$ is another optimal mechanism for both the overdemanded and underdemanded cases. It guarantees the same WS as $F^U$ for any group of agents.

Remark 2

(Without strategy-proofness) For each problem (S, C, u), consider the mechanism that picks the allocation $y\in Y(S,C)$ that is efficient. If there are multiple efficient allocations, break ties lexicographically, by choosing the efficient allocation that gives the largest share to agent 1, following by agent 2, etc. This mechanism guarantees an economic surplus equal to the efficient surplus, thus $\overline{WS}(F^U, S, C)=\underline{WS}(F^U, S, C)=1$. Same-sidedness is implied by efficiency. It is also consistent, as the subset of an efficient allocation is also efficient for the subset of agents (and ties are broken lexicographically in case of multiplicity of efficient allocations). This mechanism is not strategy-proof, as agent who are getting an allocation under (above) their peak, have the incentive to arbitrarily inflate (deflate) their utility.

Remark 3

(Without consistency) Conditions $b_i(u_{-i})\ge \frac{C}{n}$ and $a_i(u_{-i})\le \frac{C}{n}$ found in steps A2 and B2, respectively, are sufficient to guarantee the optimality of the mechanism. By Lemma 1, there is clearly a large class of mechanisms that satisfy these conditions along with strategy-proofness and same-sideness, each of them is optimal.

Remark 4

(Without concavity) The assumption of concavity of the utility function is necessary in order to achieve a non-zero WS. To show this for the overdemanded case, consider a strategy-proof and same-sided mechanism and a utility profile u where some agent i is allocated an amount $y_i$ strictly less than his peak $x^*_i(u_i)$. Consider the utility function $v_i^\alpha (x)=u_i(x)$ for $x\le y_i$, $v_i^\alpha (x)=\alpha ^{x-y_i}u_i(x)$ for $x^*_i(u_i) \ge x\ge y_i$, and $v_i^\alpha (x)=\alpha ^{2 x^*_i(u_i)-y_i-x}u_i(x)$ for $x\ge x^*_i(u_i)$. Note that $v_i^\alpha$ has the same peak as $u_i$ for $\alpha \ge 1$, but the cardinal value at the peak tends to infinity as $\alpha$ tends to infinity. By strategy-proofness and same-sidedness, the allocation of agent i at $(v_i^\alpha , u_{-i})$ is equal to $y_i$ for any $\alpha \ge 1$. Thus, the mechanism generates zero WS as $\alpha$ goes to infinity. A similar argument can be done for the underdemanded case.