Strategy-proof and fair reallocation with single-peaked preferences

Abstract

We consider the strategy-proof rules for reallocating individual endowments of an infinitely divisible good when agents’ preferences are single-peaked. In social endowment setting, the seminal work established by Sprumont (Econometrica 59:509–519, 1991) proves that the uniform rule is the unique one which satisfies strategy-proofness, efficiency, and envy-freeness. However, the uniform rule is not so appealing in our model since it disregards the differences in individual endowments. In other words, the uniform rule is not individually rational. In this paper, we propose a new rule named the uniform proportion rule. First, we prove that it is the unique rule which satisfies strategy-proofness, efficiency, and envy-freeness on proportion and we show that it is individually rational. Then, we show that our rule is indeed a member of the class of sequential allotment rules characterized by Barberà et al. (Games Econ Behav 18:1–21, 1997).

1 Introduction

Consider the problem of reallocating individual endowments of an infinitely divisible good among agents with single-peaked preferences which mean that every agent has an optimal amount of the good around which his preference is decreasing. Our purpose is to construct desirable reallocation rules based on agents’ preferences.

A potential application could be found in the electricity markets where the agents would be countries or states. Since excess electricity costs more on electricity storage and overload can potentially damage the infrastructures, “more is better” does not hold in this circumstance, whereas the existence of an optimal amount of electricity might be considered more practical. Thus the preferences over agents’ share of electricity could be interpreted as single-peaked. We intend to construct rules to design a reallocation system of electricity in this situation.

We study strategy-proof, efficient, and fair reallocation rules. Strategy-proofness states that no agent can gain by misrepresenting his preference. Efficiency requires that there should be no other reallocation in which some agent is better off and no agent is worse off. On fairness, there is a well-known property of envy-freeness introduced in Foley (1967) which plays an important role in the theory of social choice. It states that no agent prefers someone else’s allocation to his own. These three properties are fairly standard in the theory of social choice. A prominent work established by Sprumont (1991) proves that the uniform rule (Benassy 1982) is the unique rule satisfying strategy-proofness, efficiency, and envy-freeness. Though the uniform rule is believed to be one of the most attractive in the literature, it is not considered to be suitable in our model taking into account the differences in individual endowments. In other words, the uniform rule is not individually rational which requires that no agent should be worse off than his endowment.

Rather than envy-freeness, Barberà et al. (1997) introduce a novel concept, replacement monotonicity. It requires that if an agent claims a different preference which leads to at least as large (respectively, small) an allocation, then all other agents receive no larger (respectively, smaller) allocation than before. In their seminal work, they characterize the class of sequential allotment rules satisfying strategy-proofness, efficiency, and replacement monotonicity. Moreover, they show that if we impose individual rationality on the selections from this class of rules, only the sequential allotment rules with initial guaranteed levels equal to agents’ individual endowments remain acceptable. However, such class of rules is yet so large that it is hard to specify a simple algorithm that could provide us a plausible solution of the reallocation problem. This urges us to search for other fairness properties that can help us to select some specific and desirable ones from this class of rules.

Hashimoto and Wakayama (2021) define a new concept of fairness named envy-freeness for similarities: no envy among demanders or suppliers.¹ They construct a new reallocation rule named the gross uniform reallocation rule and show that it is the unique rule satisfying strategy-proofness, efficiency, individual rationality, and envy-freeness for similarities. Another interesting work established by Klaus et al. (1998) introduces a different concept of fairness named adjusted envy-freeness which states that no agent prefers another agent’s net trade to his own.² They construct a new rule named the uniform reallocation rule³ and show that it is the unique rule satisfying strategy-proofness, efficiency, and adjusted envy-freeness.

In this paper, we propose a new concept of fairness named envy-freeness on proportion which states that no agent prefers another agent’s trading proportion to his own. In the example of electricity reallocation problem, we believe that the relative electricity usage level represented by the ratio of individual endowments between agents should be taken into consideration, and this idea is to some extent captured by our new axiom. Then, we propose a new reallocation rule named the uniform proportion rule and prove that it is the unique rule satisfying strategy-proofness, efficiency, and envy-freeness on proportion. An interesting aspect of our result is that the uniform proportion rule is one special element of the class of rules characterized by Barberà et al. (1997), however, individual rationality is not required in our characterization. In other words, strategy-proofness, efficiency, and envy-freeness on proportion imply individual rationality, which amounts to a partial but important justification of envy-freeness on proportion.

In Sect. 2, we set up the model. In Sect. 3, we prove the theorem and show that our rule is indeed a member of the sequential allotment rules. In Sect. 4, we show that the theorem is tight. In Sect. 5, we discuss an interesting open question.

2 Notation and definitions

The set of agents is $N= \lbrace 1,\ldots , n\rbrace$. Consider economies with one divisible good of which each agent $i \in N$ possesses an individual endowment $e_{i} \in \mathbb {R}_{++}$. Let $e = (e_{1}, \ldots ,e_{n}) \in \mathbb {R}_{++}^{n}$ be the profile of individual endowments, and denote the total endowment by $E = \sum _{i \in N} e_{i}$. Each agent $i \in N$ has a single-peaked preference relation $R_{i}$ on $\mathbb {R}_{+}$: there is a point $p(R_{i}) \in \mathbb {R}_{+}$ such that for all $x_{i} , y_{i} \in \mathbb {R}_{+}$, if either $y_{i} < x_{i} \le p(R_{i})$ or $p(R_{i}) \le x_{i} < y_{i}$, then $x_{i}$ $P_{i}$ $y_{i}$, where $P_{i}$ is the asymmetric part of $R_{i}$. The unique point $p(R_{i})$ is called the peak of $R_{i}$. Denote the set of all single-peaked preferences defined on $\mathbb {R}_{+}$ by $\mathscr {R}$ and let $R = (R_{1}, \ldots , R_{n})$ of $\mathscr {R}^{n}$ be the profile of preferences. Let $p(R) = (p(R_{1}), \ldots , p(R_{n}))$ be the profile of peaks. To distinguish the preferences of some agent and those of the rest, let $R_{-i} = (R_{1}, \ldots , R_{i-1}, R_{i+1}, \ldots , R_n)$, and write $R = (R_{i}, R_{-i})$. The set of feasible allocations is $X = \lbrace (x_{1}, \ldots ,x_{n}) \in \mathbb {R}_{+}^{n}: \sum _{i \in N} x_{i} = E \rbrace$.

A rule is a function $f: \mathscr {R}^{n} \rightarrow X$ assigning to each preference profile $R \in \mathscr {R}^{n}$ a feasible allocation $f(R) = (f_1(R), \ldots , f_n(R)) \in X$, where $f_i(R)$ means agent i’s allocation at R.

For convenience, depending on R, we classify agents into three sets. For all $R \in \mathscr {R}^{n}$, let $N^{d}(R) = \{ i \in N : p(R_{i}) > e_i \}$, $N^{n}(R) = \{ i \in N : p(R_{i}) = e_i \}$ and $N^{s}(R) = \{ i \in N : p(R_{i}) < e_i \}$ be the sets of demanders, non-traders and suppliers, respectively.

Next we introduce several axioms which are standard in the literature.

Definition 1

A rule f is strategy-proof if for all $R \in \mathscr {R}^{n}$, all $i \in N$ and all $R_i^{\prime } \in \mathscr {R}$, $f_i(R)$ $R_i$ $f_i(R^{\prime }_i, R_{-i})$.

Obviously, if a rule f is strategy-proof, then reporting the truth is always a weakly dominant strategy for each agent.

Definition 2

A rule f is efficient if for all $R \in \mathscr {R}^{n}$, there is no $x \in X$ such that for all $i \in N$, $x_{i}$ $R_i$ $f_i(R)$, and for some $j\in N$, $x_{j}$ $P_j$ $f_j(R)$.

Efficiency states that there is no other allocation in which some agent is better off and no agent is worse off.

Now we propose a new concept of fairness which requires that an allocation rule is such that every agent i weakly prefers what he is allocated to what any other agent j is allocated, if the allocation of j would be multiplied by the ratio of the individual endowments between j and i.

Definition 3

A rule f satisfies envy-freeness on proportion, if for all $R \in \mathscr {R}^{n}$, and all $\lbrace i, j \rbrace \subset N$, $f_i(R)$ $R_i$ $\frac{e_i}{e_j} f_j(R)$.

Remark

In our model, it is easy to show that efficiency is equivalent to same-sidedness, that is, for all $R \in \mathscr {R}^{n}$, either $f_i(R) \ge p(R_i)$ for all $i \in N$ or $f_i(R) \le p(R_i)$ for all $i \in N$.

3 Main results

In social endowment setting, the well-known uniform rule is the most studied rule in the literature.⁴ We extend it into individual endowments setting. In this section, we first introduce our reallocation rule which is called the uniform proportion rule, and we show the characterization result. Then we prove that the uniform proportion rule is individually rational. Finally, we show that the uniform proportion rule is a member of the sequential allotment rules.

Definition 4

The uniform proportion rule: For all $R \in \mathscr {R}^{n}$ and all $i \in N$,

$$\begin{aligned} \varphi _{i}(R) = {\left\{ \begin{array}{ll} min \lbrace p(R_i), \lambda e_i \rbrace &{} \text {if} \sum _{j \in N}p(R_j) \ge E, \\ max \lbrace p(R_i), \lambda e_i \rbrace &{} \text {if} \sum _{j \in N}p(R_j) \le E, \end{array}\right. } \end{aligned}$$

where $\lambda \in \mathbb {R}_{+}$ solves $\sum _{j \in N}\varphi _j(R) = E$.

The uniform proportion rule works as follows. In case of excess demand ($\sum _{j \in N}p(R_j) > E$), all suppliers and non-traders receive their peaks. Then distribute the total resulting supply to each demander in a uniform proportion over each demander’s initial endowment. If some demander were distributed more than his peak, then he would receive his peak as the final allocation. Iterate this process until there is no supply left. In the balanced situation ($\sum _{j \in N}p(R_j) = E$), all agents receive their peaks. In case of excess supply ($\sum _{j \in N}p(R_j) < E$), all demanders and non-traders receive their peaks. Then subtract the total resulting demand in a uniform proportion from each supplier’s initial endowment. If some supplier were subtracted less then his peak, then he would receive his peak as the final allocation. Iterate this process until there is no demand left.

We illustrate the algorithm with an example.

Example 1

Let $N = \{1, 2, 3, 4, 5\}$, and $e = (100, 40, 30, 20, 10)$. Let $R \in \mathscr {R}^{5}$ be such that $p(R) = (60, 50, 50, 40, 20)$. Since $\sum _{i \in N}p(R_i) = 220 > 200 = E$, the only supplier agent 1 has $f_1(R) = p(R_1) = 60$ as his final allocation. Then we have $e_1 - p(R_1) = 40$ units to be distributed to other four agents based on the ratio between their individual endowments. Thus we would distribute $\frac{e_2}{e_2 + e_3 + e_4 + e_5} \left[ e_1 - p(R_1)\right] = 16$ units, $\frac{e_3}{e_2 + e_3 + e_4 + e_5} \left[ e_1 - p(R_1)\right] = 12$ units, $\frac{e_4}{e_2 + e_3 + e_4 + e_5} \left[ e_1 - p(R_1)\right] = 8$ units, and $\frac{e_5}{e_2 + e_3 + e_4 + e_5} \left[ e_1 - p(R_1)\right] = 4$ units to each remaining agents respectively. Since $e_2 + \frac{e_2}{e_2 + e_3 + e_4 + e_5} \left[ e_1 - p(R_1)\right] = 40 + 16 = 56 > 50 = p(R_2)$, we have $f_2(R) = p(R_2) = 50$ as the final allocation for agent 2. Now we have $e_1 - p(R_1) - (p(R_2) - e_2)= 30$ units to be distributed to agent 3, 4, and 5 in the same fashion. Thus $f_3(R) = e_3 + \frac{e_3}{e_3 + e_4 + e_5} \left[ e_1 - p(R_1) - (p(R_2) - e_2)\right] = 45$, $f_4(R) = e_4 + \frac{e_4}{e_3 + e_4 + e_5} \left[ e_1 - p(R_1) - (p(R_2) - e_2)\right] = 30$, and $f_5(R) = e_5 + \frac{e_5}{e_3 + e_4 + e_5} \left[ e_1 - p(R_1) - (p(R_2) - e_2)\right] = 15$ are the final allocations for agent 3, 4, and 5 respectively. We conclude that the final allocation is $f(R) = (60, 50, 45, 30, 15)$. It is easy to see that, in this example, $f_i(R)=p(R_i)$ for $i=1$ and 2, and $f_i(R)=\lambda e_i$ for $i=3, 4,$ and 5, where $\lambda =1.5$.

Now we state our characterization.

Theorem

The uniform proportion rule is the only rule that satisfies strategy-proofness, efficiency and envy-freeness on proportion.

Proof

We first prove the necessity part of the theorem. Obviously the uniform proportion rule satisfies efficiency. On strategy-proofness, we refer to the proof proposed by Sprumont (1991). By replacing $\lambda$ defined in his model with $\lambda e_i$ defined in our model, and without any other modification the proof is complete.

Lastly, we check envy-freeness on proportion. Let $R \in \mathscr {R}^{n}$ and $i, j \in N$ be arbitrary. Consider the case of $\sum _{i \in N}p(R_i) \ge E$ (since the other case is similar, we omit the proof).

Case 1

If $\varphi _{i}(R)=p(R_i)$, then it is obvious that $\varphi _{i}(R)$ $R_i$ $\frac{e_i}{e_j} \varphi _{j}(R)$.

Case 2

Let $\varphi _{i}(R)= \lambda e_i$ and $\varphi _{j}(R)= \lambda e_j$. Since $\frac{e_i}{e_j} \varphi _{j}(R) = \frac{e_i }{e_j} \lambda e_j = \lambda e_i$, we have $\varphi _{i}(R)$ $R_i$ $\frac{e_i}{e_j} \varphi _{j}(R)$.

Case 3

Let $\varphi _{i}(R)= \lambda e_i$ and $\varphi _{j}(R) = p(R_j)$. By the definition of the rule, $\varphi _{i}(R)= \lambda e_i \le p(R_i)$ and $\frac{e_i}{e_j} \varphi _{j}(R) = \frac{e_i}{e_j} p(R_j) \le \frac{e_i}{e_j} \lambda e_j = \lambda e_i$. Since $\frac{e_i}{e_j} \varphi _{j}(R) \le \lambda e_i \le p(R_i)$, by the definition of single-peakedness, $\varphi _{i}(R)$ $R_i$ $\frac{e_i}{e_j} \varphi _{j}(R)$.

Now we prove the sufficiency part of the theorem. Let f be a rule satisfying strategy-proofness, efficiency, and envy-freeness on proportion. Let $R \in \mathscr {R}^{n}$ be such that $\sum _{j \in N}p(R_j) \ge E$ (the other case is similar and we omit the proof). By efficiency, $f_i(R) \le p(R_i)$ for all $i \in N$. For convenience, arrange the indexes of agents such that $\frac{f_1(R)}{e_1} \le \frac{f_2(R)}{e_2} \le \cdots \le \frac{f_n(R)}{e_n}$. Notice that we do not rearrange the indexes of agents henceforth, although we argue agents’ allocation on a different profile of preferences. Let $N^{*}(R) = \{ i \in N: \frac{f_i(R)}{e_i} < \frac{f_j(R)}{e_j}$ for some $j \in N\}$. We will now show that all agents who receive their optimal assignment by the allocation rule will be in $N^{*}(R)$, while every agent i outside of $N^{*}(R)$ will receive $\lambda e_i$ for some $\lambda$.

Step 1. For all $i \in N^{*}(R)$, $f_i(R)=p(R_i)$.

Suppose by way of contradiction that there is some $j \in N^{*}(R)$ such that $f_j(R) < p(R_j)$. Let $l = min \{ j \in N^{*}(R): f_j(R) < p(R_j) \}$. By the definition of agent l, we have $f_l(R) < p(R_l)$, and $f_i(R) = p(R_i)$ for all $i < l$. We are now considering a preference order $R_l^\prime$ which is such that l strictly prefers having more than $f_l(R)$ to $f_l(R)$, even if the amount exceeds the peak of l. Formally, this property can be stated as let $R_l^\prime \in \mathscr {R}$ be such that $p(R_l^\prime ) =p(R_l)$ and $x_l$ $P_l ^\prime$ $f_l(R)$ for all $x_l \ge p(R_l^\prime )$. Since $\sum _{i \ne l}p(R_i) + p(R_l^\prime ) = \sum _{i \in N}p(R_i) \ge E$, by efficiency, for $i= 1, \ldots , l$, $f_i(R_l^\prime , R_{-l}) \le p(R_i)$. Since it is already shown that $f_l(R) < p(R_l)$, we can compare $f_l(R_l^\prime , R_{-l})$ with $f_l(R)$. By the definition of $R_l^\prime$ and strategy-proofness, we have $f_l(R)$ $R_l$ $f_l(R_l^\prime , R_{-l})$ which implies that $f_l(R) \ge f_l(R_l^\prime , R_{-l})$, and $f_l(R_l^\prime , R_{-l})$ $R_l^\prime$ $f_l(R)$ which implies that $f_l(R_l^\prime , R_{-l}) \ge f_l(R)$. Thus we must have $f_l(R_l^\prime , R_{-l}) = f_l(R)$. Hence, we have $\sum _{i = 1, \ldots , l}f_i(R) \ge \sum _{i = 1, \ldots , l} f_i(R_l^\prime , R_{-l})$. By feasibility, we have $\sum _{i = l+1, \ldots , n}f_i(R) \le \sum _{i = l+1, \ldots , n} f_i(R_l^\prime , R_{-l})$.

Now we have to consider two cases.

Case 1

For some $j \in \{ l+1, \ldots , n \}$, $f_j(R) < f_j(R_l^\prime , R_{-l})$. Then we have $\frac{f_l(R)}{e_l} \le \frac{f_j(R)}{e_j} < \frac{f_j(R_l^\prime , R_{-l})}{e_j}$. By envy-freeness on proportion, it must hold that $f_l(R_l^\prime , R_{-l})$ $R_l^\prime$ $\frac{e_l}{e_j}f_j(R_l^\prime , R_{-l})$. However, this contradicts the definition of $R_l^\prime$ since $\frac{e_l}{e_j}f_j(R_l^\prime , R_{-l}) > f_l(R) = f_l(R_l^\prime , R_{-l})$ and thus the proof of Case 1 is completed.

Case 2

For all $j \in \{ l+1, \ldots , n \}$, $f_j(R) \ge f_j(R_l^\prime , R_{-l})$. Then we have $\sum _{i = l+1, \ldots , n}f_i(R) \ge \sum _{i = l+1, \ldots , n} f_i(R_l^\prime , R_{-l})$ which implies $\sum _{i = l+1, \ldots , n}f_i(R) = \sum _{i = l+1, \ldots , n} f_i(R_l^\prime , R_{-l})$. Hence, $f_j(R) = f_j(R_l^\prime , R_{-l})$ for all $j \in \{ l+1, \ldots , n \}$. By the definition of $N^{*}(R)$, $\frac{f_l(R)}{e_l} < \frac{f_n(R)}{e_n} = \frac{f_n(R_l^\prime , R_{-l})}{e_n}$. By envy-freeness on proportion, it must hold that $f_l(R_l^\prime , R_{-l})$ $R_l^\prime$ $\frac{e_l}{e_n}f_n(R_l^\prime , R_{-l})$. However, this contradicts the definition of $R_l^\prime$ since $\frac{e_l}{e_n}f_n(R_l^\prime , R_{-l}) > f_l(R) = f_l(R_l^\prime , R_{-l})$ and thus the proof of Case 2 is completed.

Step 2. There is some $\lambda \in \mathbb {R}_{+}$ such that for all $i \in N \backslash N^{*}(R)$, $f_i(R) = \lambda e_i$.

By the definition of $N^{*}(R)$, for all $i \in N^{*}(R)$ and all $j, k \in N \backslash N^{*}(R)$, we have $0 \le \frac{f_i(R)}{e_i} < \frac{f_j(R)}{e_j} = \frac{f_k(R)}{e_k}$. Let $\lambda = \frac{f_j(R)}{e_j}$ for some $j \in N \backslash N^{*}(R)$.⁵ Therefore, we can write $f_j(R) = \lambda e_j$ for all $j \in N \backslash N^{*}(R)$.

As shown in Steps 1 and 2, for all $i \in N^{*}(R)$ and all $j \in N \backslash N^{*}(R)$, we have $p(R_i)=f_i(R) < \frac{f_j(R)}{e_j}e_i = \lambda e_i$, and by efficiency, we have $\lambda e_j = f_j(R) \le p(R_j)$. Therefore, for all $i \in N$, we have $f_i(R)=min \{ p(R_i), \lambda e_i \}$.□

In our model of individual endowments setting, it is fairly natural to consider individual rationality as an important criterion when constructing reallocation rules which states that no agent prefers his individual endowment to his allocation.⁶ We define individual rationality as follows.

Definition 5

A rule f is individually rational if for all $R \in \mathscr {R}^{n}$ and all $i \in N$, $f_i(R)$ $R_i$ $e_i$.

Although individual rationality is not required in our characterization, in fact, the uniform proportion rule is individually rational. We prove it in the following proposition.

Proposition 1

The uniform proportion rule $\varphi$ is individually rational.

Proof

Let $R \in \mathscr {R}^{n}$ be such that $\sum _{j \in N}p(R_j) \ge E$ (the other case is similar and we omit the proof). We show that $\lambda \ge 1$.

Suppose by way of contradiction that $\lambda < 1$. For all $i \in N$, we have $\varphi _{i}(R) = min \lbrace p(R_i), \lambda e_i \rbrace < e_i$. Thus $\sum _{i \in N}\varphi _i(R) < E$ which is contradictory to the feasibility of $\varphi$. Therefore, $\lambda \ge 1$. By the definition of single-peaked preference, it is easy to see that for all $i \in N$, we have $\varphi _{i}(R)$ $R_i$ $e_i$. □

Remark

A seminal work by Barberà et al. (1997) studies strategy-proof and efficient allocation rules where the agents might be treated with different priorities. Moreover, it introduces a novel concept—replacement monotonicity, and characterizes a large class of rules named sequential allotment rules which are the only rules that satisfy strategy-proofness, efficiency, and replacement monotonicity. Indeed, the uniform proportion rule is a member of such class of rules. To show that, we only need to prove that our rule satisfies replacement monotonicity. First, we define replacement monotonicity which requires that if an agent claims a different preference which leads to at least as large (respectively, small) an allocation, then all other agents receive no larger (respectively, smaller) allocation than before. Then we show that the uniform proportion rule is replacement monotonic.

Definition 6

A rule f is replacement monotonic if for all $R \in \mathscr {R}^{n}$, all $i \in N$, and all $R_i^{\prime } \in \mathscr {R}$, $\left[ f_i(R) \le f_i(R^{\prime }_i, R_{-i})\right] \implies \left[ f_j(R) \ge f_j(R^{\prime }_i, R_{-i})\right]$ for all $j \ne i$.

Proposition 2

The uniform proportion rule $\varphi$ is replacement monotonic.

Proof

Suppose by way of contradiction that for some $R \in \mathscr {R}^{n}$, some $i \in N$, and some $R_i^{\prime } \in \mathscr {R}$, $\varphi _i(R) \le \varphi _i(R^{\prime }_i, R_{-i})$, and $\varphi _j(R) < \varphi _j(R^{\prime }_i, R_{-i})$ for some $j \ne i$. Consider the case of $\sum _{i \in N}p(R_i) \ge E$ (since the other case is similar, we omit the proof).

Case 1

$\sum _{k \ne i}p(R_k) + p(R_i^\prime ) \ge E$.

By the definition of $\varphi$, $\varphi _j(R)=min\{ p(R_j), \lambda e_j \}$ and $\varphi _j(R^{\prime }_i, R_{-i})=min\{ p(R_j), \mu e_j\}$ for some $\lambda , \mu \in \mathbb {R}_{+}$.

First, let $\varphi _j(R)=p(R_j)$. Since $\varphi _j(R) < \varphi _j(R^{\prime }_i, R_{-i})$, we have $\varphi _j(R^{\prime }_i, R_{-i})= \mu e_j \le p(R_j)$. It implies $p(R_j) < \mu e_j \le p(R_j)$, which is a contradiction.

Second, let $\varphi _j(R)=\lambda e_j$. Since $\varphi _j(R) < \varphi _j(R^{\prime }_i, R_{-i})$, we have $\lambda e_j < min\{ p(R_j), \mu e_j\}$ which implies $\lambda < \mu$. Thus for all $k \ne i, j$, $\varphi _k(R) = min \lbrace p(R_k), \lambda e_k \rbrace \le min \lbrace p(R_k), \mu e_k \rbrace = \varphi _k(R^{\prime }_i, R_{-i})$. Since $\varphi _i(R) \le \varphi _i(R^{\prime }_i, R_{-i})$ and $\varphi _j(R) < \varphi _j(R^{\prime }_i, R_{-i})$, we have $\sum _{k \in N}\varphi _k(R) < \sum _{k \in N}\varphi _k(R^{\prime }_i, R_{-i})$, which contradicts the feasibility of $\varphi$.

Case 2

$\sum _{k \ne i}p(R_k) + p(R_i^\prime ) < E$.

By the definition of $\varphi$, for all $k \ne i, j$, $\varphi _k(R) = min \lbrace p(R_k), \lambda e_k \rbrace \le p(R_k) \le max \lbrace p(R_k), \mu e_k \rbrace = \varphi _k(R^{\prime }_i, R_{-i})$ for some $\lambda , \mu \in \mathbb {R}_{+}$. Since $\varphi _i(R) \le \varphi _i(R^{\prime }_i, R_{-i})$ and $\varphi _j(R) < \varphi _j(R^{\prime }_i, R_{-i})$, we have $\sum _{k \in N}\varphi _k(R) < \sum _{k \in N}\varphi _k(R^{\prime }_i, R_{-i})$, which contradicts the feasibility of $\varphi$.

Therefore, we conclude that the uniform proportion rule is replacement monotonic.□

4 Independence

We show the independence of the axioms in our theorem.

Example 2

The endowment rule is defined as $f_i^e(R) =e_i$ for all $i \in N$, and all $R \in \mathscr {R}^{n}$. The endowment rule satisfies strategy-proofness and envy-freeness on proportion but not efficiency.

Example 3

The uniform rule is defined as follows. For all $R \in \mathscr {R}^{n}$ and all $i \in N$,

$$\begin{aligned} f_{i}^u(R) = {\left\{ \begin{array}{ll} min \lbrace p(R_i), \lambda \rbrace &{} \text {if} \sum _{j \in N}p(R_j) \ge E, \\ max \lbrace p(R_i), \lambda \rbrace &{} \text {if} \sum _{j \in N}p(R_j) \le E, \end{array}\right. } \end{aligned}$$

where $\lambda \in \mathbb {R}_{+}$ solves $\sum _{j \in N}f_{j}^u(R) = E$.

The uniform rule satisfies strategy-proofness and efficiency but not envy-freeness on proportion.

Example 4

Let $n = 3$ and $e = (1, 1, 2)$. Let $R^{\prime } \in \mathscr {R}^{3}$ be such that 1 $R_1^{\prime }$ 3 and $p(R^{\prime }) = (2, 3, 0)$. Define $\tilde{f}$ as follows: for all $R \in \mathscr {R}^{3}$,

$$\begin{aligned} \tilde{f}(R) = {\left\{ \begin{array}{ll} (1, 3, 0) &{} \text {if} R = R^{\prime }, \\ \varphi (R) &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

Then $\tilde{f}$ satisfies efficiency and envy-freeness on proportion but not strategy-proofness.

5 Discussion

In this paper, we introduce a new concept—envy-freeness on proportion, and show that the uniform proportion rule is the only rule that satisfies strategy-proofness, efficiency, and envy-freeness on proportion. In the same setting as ours, several studies introduce different concepts of envy-freeness. One is adjusted envy-freeness introduced by Klaus et al. (1998) and Moreno (2002).

Definition 7

A rule f is adjusted envy-free, if for all $R \in \mathscr {R}^{n}$ and all $\lbrace i, j \rbrace \subset N$, $f_i(R)$ $R_i$ $max \lbrace e_i + (f_j(R) - e_j), 0 \rbrace$.

Another one is envy-freeness for similarities introduced by Hashimoto and Wakayama (2021).

Definition 8

An allocation $x \in X$ is envy-free for similarities for $R \in \mathscr {R}^{n}$ if for all $\{i, j\} \subset N$, if either $\{i, j\} \subset N^{d}(R)$ and $x_j > e_j$ or $\{i, j\} \subset N^{s}(R)$ and $x_j < e_j$, then $x_i$ $R_i$ $x_j$. A rule f is envy-free for similarities if for all $R\in \mathscr {R}^{n}$, f(R) is envy-free for similarities for R.

These three concepts define envy-freeness in three different ways, one in terms of the proportion of allotment changes, one the net allotment changes, and the other the final allotments, respectively. It triggers us to consider if we can define these concepts in a general form with which we could define a class of concepts of envy-freeness. Let us define it formally.⁷

For all $R \in \mathscr {R}^{n}$, let $\{N^1(R), N^2(R),\ldots , N^l(R)\}$ for $1\le l \le n$ be a partition of the set of agents, and $g : \mathbb {R}_{+}^{4} \rightarrow \mathbb {R}_{+}$ be an auxiliary function used both to define a general envy-free concept.

Definition 9

A rule f satisfies envy-freeness relative to $\{N^k\}_{k=1}^{l}$ and g, if for all $R \in \mathscr {R}^{n}$ , and all $i, j \in N^k(R)$ for $k \in \{1, 2,\ldots , l\}$, $f_i(R)$ $R_i$ $g(e_i, e_j, f_i(R), f_j(R))$.

In Klaus et al. (1998) and Moreno (2002), for all $R \in \mathscr {R}^{n}$, the partition is $N^1(R) = N$ and $N^k(R) = \varnothing$ for all $k \in \{2, \ldots , l\}$, and the auxiliary function is $g = e_i + (f_j(R)-e_j)$ if $e_i + (f_j(R)-e_j) \in \mathbb {R}_{+}$, and $g=0$ otherwise. In our paper, for all $R \in \mathscr {R}^{n}$, the partition is $N^1(R) = N$ and $N^k(R) = \varnothing$ for all $k \in \{2, \ldots , l\}$, and the auxiliary function is $g = \frac{e_i}{e_j}f_j(R)$. In Hashimoto and Wakayama (2021), for all $R \in \mathscr {R}^{n}$, the partition is $N^1(R) = \{ i \in N : p(R_i) > e_i \}$, $N^2(R) = \{ i \in N : p(R_i) = e_i \}$, $N^3(R) = \{ i \in N : p(R_i) < e_i \}$ and $N^k(R) = \varnothing$ for all $k \in \{4, \ldots , l\}$, and the auxiliary function is $g = f_j(R)$ if $f_j(R) \ne e_j$ and $g = f_i(R)$ otherwise.

It might be interesting to consider which envy-free concept is natural and appealing in this general class and characterize the rules which satisfy strategy-proofness, efficiency, and such envy-free concept. We leave it an open question for future research.