Bribe-proof reallocation with single-peaked preferences

Abstract

We study reallocation rules in the context of a one-good economy consisting of agents with single-peaked preferences and individual endowments. A rule is bribe-proof if no group of agents can compensate one of its subgroups to misrepresent their characteristics (preferences or endowments) in order that each agent is better off after an appropriate redistribution of what the rule reallocates to the group, adjusted by the resource surplus or deficit they all engage in by misreporting endowments. First, we characterize all bribe-proof rules as the class of efficient, (preference and endowment) strategy-proof and weakly replacement monotonic rules, extending the result due to Massó and Neme (Games Econ Behav 61: 331–343, 2007) to our broader framework. Second, we present a full description of the family of bribe-proof rules that in addition are individually rational and peak-only. Finally, we provide two further characterizations of the uniform reallocation rule involving bribe-proofness.

1 Introduction

In this paper we study the problem of reallocating a perfectly divisible good among a group of agents with individual endowments. We restrain our analysis to the case where agents’ preferences are single-peaked: up to some critical level, called the peak amount, an increase in an agent’s consumption raises her welfare; beyond that level, the opposite holds. To illustrate this type of problem, consider the distribution of a task among the members of a group. If agents’ disutility of labor is concave, their induced preferences are single-peaked: each individual has an ideal amount of time to work, and having to work more or less decreases her utility. Since external factors might affect the preferences of the agents from one period to the other, a reallocation of the time assigned to each agent in the first period (considered as a reference point for the second period) could be performed to benefit everyone.

Our analysis will be conducted over reallocation rules, i.e., systematic ways of selecting reallocations for each possible configuration of agents’ preferences and endowments. These rules are assumed to fulfill the fundamental property of efficiency: there should not be an allocation different from the one chosen by the rule that all agents find at least as desirable and at least one agent prefers.

We will focus on the strategic aspect of the reallocation problem by considering manipulability issues. Specifically, and given that in our context agents’ characteristics consist of preferences and endowments which are supposed to be private information, we will discuss whether there are incentives for the agents to misreport preferences, endowments, or both.

Reallocation rules can often be manipulated by agents misrepresenting their preferences. A rule is preference strategy-proof if it does not allow for such behavior. For general social choice problems this has proven to be quite a demanding property: only dictatorial rules are immune to strategic manipulation of preferences. It is well-known since Hurwicz (1972) that there is a trade-off between this property and efficiency in the domain of classical preferences, once some mild notion of fairness is involved as well. However, when there is a one-good social endowment to be allocated and preferences are single-peaked, the class of efficient rules that are preference strategy-proof is very large, as shown by Barberà et al. (1997). They characterize the family of sequential allotment rules as the only rules that satisfy efficiency, preference strategy-proofness, and a property they call replacement monotonicity. This last property can be seen as a strong solidarity notion. It requires that when the preferences of an agent change, in a way that does not turn the economy from one in which there is too much to one in which there is too little (or vice versa), the welfares of all other agents should be affected in the same direction. By a weakening of the replacement monotonicity property, Massó and Neme (2007) achieve the characterization of the family of rules in which no group of agents can compensate one of its subgroups to misrepresent their preferences so that, after an appropriate redistribution of their shares, each obtain a preferred share.

The reallocation problem differs from an allocation problem because individual endowments matter, since an agent who is made worse off than at her individual endowment might refuse to participate. The property of individual rationality does not permit such treatment, and is one of the key aspects of our study. An agent can also benefit by manipulating her endowment. The manipulation through endowments may be performed in two ways. In one of them, an agent could, by withholding some of her endowment prior to the operation of the rule, and after adding the resources she withheld to the consumption that the rule assigns to her, end up better off than if she had not withheld. In the other, suppose that prior to the operation of the chosen rule, an agent borrows resources (from the outside world) to enlarge her endowment. The rule is then applied, the agent receives her assigned consumption, and returns what she had borrowed. The end result may be an outcome that she prefers to the one that she would have been assigned had she not borrowed.

Manipulation through withholding of endowments was first analyzed in the context of classical exchange economies by Postlewaite (1979), where he shows that efficient and individually rational rules are manipulable in this way (he calls the lack of such manipulability withholding-proofness). In one-good economies with single-peaked preferences and individual endowments, a similar study has been carried out by Klaus et al. (1997), where this non-manipulability property is used to obtain characterizations of the uniform reallocation rule.

Concerning the lack of manipulation via augmentation of endowments, a property known as borrowing-proofness, Thomson (2008) shows that in the classical exchange model the walrasian rule fails to meet borrowing-proofness both in the homothetic and the quasi-linear domains of classical preferences. A recent paper where immunity to manipulation via endowments is analyzed is Atlamaz and Klaus (2007). Their setting, however, considers exchange markets with heterogenous and indivisible objects. They also show that efficient and individually rational rules are in general manipulable and identify some subclasses of exchange markets where these incompatibilities do not apply.

Our aim is to develop a strong non-manipulability property in our broader framework that takes into account preferences and individual endowments at the same time. To do this, consider the following manipulation, or bribe. A group of agents can compensate one of its subgroups to misrepresent their preferences or endowments in order that, after an appropriate redistribution of what the rule reallocates to the group adjusted by the resource surplus or deficit they all engage in by misreporting, (i) agents in the misrepresenting subgroup obtain a preferred amount and (ii) the rest of the agents in the group are not made worse-off. The property of bribe-proofness we propose rules out this sort of strategic behavior, and also all the aforementioned types of manipulation as well, as particular cases. It can be seen as a stronger version of the property presented, with the same name, by Massó and Neme (2007) in the model with a social endowment. Our version is stronger because allows manipulation not only by preferences but also by individual endowments in the definition of a bribe. The concept of bribe-proofness first appeared in Schummer (2000), where it is studied in the setting of quasi-linear economies.

The main result of the paper consists of a characterization of the family of bribe-proof rules as the class of rules fulfilling efficiency, strategy-proofness (meaning by this the combination of preference strategy-proofness, borrowing-proofness and withholding-proofness) and a generalization of the solidarity axiom previously discussed, that considers changes in endowments as well, which we call weak replacement monotonicity. Since individual rationality is a natural property to be asked in this context, we also give a full description of the family of bribe-proof rules that also meet this participation requirement together with the informational restriction of being peak-only, i.e., the rule determines the reallocation only using the peaks of the preferences. We call this family the class of weakly sequential rules, since they build upon the previously mentioned family of sequential rules of Barberà et al. (1997) and extend the weakly sequential rules presented by Massó and Neme (2003).

Furthermore, the property of bribe-proofness allow us to obtain two new characterizations of the uniform reallocation rule, a rule that satisfies many appealing properties and has been extensively studied, among others, by Klaus (1997) and Klaus et al. (1997, 1998). The first characterization, in the spirit of Ching (1992), states that this rule is the only bribe-proof rule fulfilling the property of no-envy (in net trades): no agent prefers another agent’s allotment change to his own allotment change. The second characterization says that the uniform reallocation rule is the only bribe-proof rule that satisfies the properties of equal treatment of equals (by which a rule cannot distinguish between agents with equal net demands, i.e., the difference between peaks and endowments) and reversibility (which requires a sort of symmetry between excess demand and excess supply problems).

The rest of the paper is organized as follows. In Sect. 2 we present the model and some preliminary results about efficiency, strategy-proofness and individual rationality. Section 3 is concerned with bribe-proof rules and its characterization, whereas Sect. 4 describes the weakly sequential rules. The uniform reallocation rule is analyzed in Sect. 5 and finally, in Sect. 6, we present some concluding comments.

2 The model and preliminary results

Let $\varvec{N}=\{1, \ldots , n\}$ be the set of agents. Each $i \in N$ is characterized by an endowment $\varvec{\omega _i} \in \mathbb {R}_+$ of the good and a continuous preference relation $\varvec{R_i}$ defined over $\mathbb {R}_+$. Call $\varvec{P_i}$ and $\varvec{I_i}$ to the strict preference and indifference relations associated with $R_i,$ respectively. We suppose that agents’ preferences are single-peaked, i.e., each $R_i$ has a unique maximum $\varvec{p(R_i)} \in \mathbb {R}_+$ such that, for each pair $x_i, x_i' \in \mathbb {R}$, we have $x_iP_ix_i^{\prime }$ as long as either $x_i^{\prime }<x_i\le p(R_i)$ or $p(R_i) \le x_i<x_i^{\prime }$ holds. Denote by $\varvec{\mathcal {R}}$ the domain of single-peaked preferences defined on $\mathbb {R}$. Given the profile of preferences $\varvec{R}:=(R_i)_{i \in N} \in \mathcal {R}^N,$ we often write the profile of peaks of $R$ by $\varvec{p(R)}.$ An economy consists of a profile of preferences $R \in \mathcal {R}^N$ and an individual endowments vector $\varvec{\omega } := (\omega _i)_{i \in N}\in \mathbb {R}^N_+$ and is denoted by $\varvec{e=(R,\omega )}$. If $S \subset N$ and $R \in \mathcal {R}^N,$ let $\varvec{R_S}:=(R_j)_{j \in S}$ denote the restriction of $R$ to $S.$ We often write $N{\setminus } S$ by $\varvec{-S}$. With this notation, $e^{\prime }=(R_S',R_{-S}, \omega _S^{\prime },\omega _{-S})$ stands for the economy where the preference and endowment of agent $i \in S$ are $R_i^{\prime }$ and $\omega _i^{\prime },$ and those of agent $i \notin S$ are $R_i$ and $\omega _i.$ Let $\varvec{\mathcal {E}^N}$ be the domain of economies with agents in $N$. A (feasible) reallocation for $e=(R, \omega ) \in \mathcal {E}^N$ is a vector $x=(x_1, \ldots , x_n) \in \mathbb {R}_+^N$ such that $\sum _{j \in N}x_j=\sum _{j \in N}\omega _j$. Denote by $\varvec{X(e)}$ the set of reallocations for economy $e \in \mathcal {E}^N$. A (reallocation) rule $\varvec{f}$ is a mapping $f:\mathcal {E}^N \rightarrow \mathbb {R}_+^N,$ such that for each $e \in \mathcal {E}^N,$ $f(e) \in X(e).$ Given $e=(R,\omega ) \in \mathcal {E}^N,$ let $\varvec{\Delta f_i(e)}:=f_i(e)-\omega _i$ denote agent i’s net trade for each $i\in N$ and let $\varvec{z(e)}:=\sum _{j \in N}p(R_j)-\sum _{j \in N}\omega _j.$ If $z(e) \ge 0$ we say that economy $e$ has excess demand whereas if $z(e)<0$ we say that economy $e$ has excess supply.

We now define formally some properties reallocation rules should satisfy and discuss some examples and preliminary results.

Efficiency: For each $e=(R,\omega )\in \mathcal {E}^N,$ if $f(e)=x$ then there is no other feasible allocation $y \in X(e)$ such that $y_i R_i x_i$ for each $i \in N$ and $y_j P_j x_j$ for some $j \in N.$

This is the usual Pareto optimality criterium. With single-peaked preferences, efficiency is equivalent to the following same-sidedness condition: given a rule $f$, for each $e=(R,\omega ) \in \mathcal {E}^N,$ (i) if $z(e)\ge 0$ then $f_j(e)\le p(R_j)$ for each $j \in N,$ and (ii) if $z(e)\le 0$ then $f_j(e)\ge p(R_j)$ for each $j \in N.$

The next property rules out the possibility that an agent can, by misrepresenting her preference or endowment, obtain an amount she prefers over the one assigned to her by the rule, adjusted to take into account the resources she withheld or borrowed.

Strategy-proofness: For each $e=(R,\omega ) \in \mathcal {E}^N,$ $i \in N$ and $(R_i^{\prime },\omega _i^{\prime }) \in \mathcal {R}\times \mathbb {R}_+,$ if $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime }, \omega _{-i})$ then it is not the case that $\left( f_i(e^{\prime })+(\omega _i-\omega _i^{\prime })\right) P_if_i(e).$

Notice that we need to state the property in this negative way since in a borrowing situation, i.e., when $\omega _i^{\prime }>\omega _i,$ the non-negativity of the amount $\left( f_i(e^{\prime })+(\omega _i-\omega _i^{\prime })\right)$ cannot be assured. Not every rule immune to manipulation via preferences is strategy-proof in our sense, as the following example shows.

Example 1

Consider the following queuing rule, $\varvec{f^q}.$ For each $e=(R,\omega ) \in \mathcal {E}^N,$ if $i<n,$ then $f^q_i(e):=\min \{p(R_i), \sum _{j \in N} \omega _j- \sum _{j<i}f_j^q(e)\},$ and $f_n:=\sum _{j \in N} \omega _j$ $- \sum _{j<n}f_j^q(e).$ This rule is easily seen to be preference strategy-proof, but is not withholding-proof. To check this, let $e=(R, \omega ) \in \mathcal {E}^{\{1,2\}}$ be such that $p(R)=(1,1),$ and $\omega =(0,1).$ Then, if agent 2 declares $\omega _2^{\prime }=0$ and $e^{\prime }=(R,\omega _1, \omega _2^{\prime }),$ we have $1=(f_2(e^{\prime })+(\omega _2-\omega _2^{\prime }))P_2f_2(e)=0.$

In our next definition, we ask for the reallocation rule to leave no one worse-off than at her individual endowment.

Individual rationality: For each $e=(R, \omega ) \in \mathcal {E}^N$ and $i \in N$, $f_i(e)R_i\omega _i.$ In a reallocation model, this property should be, at least, a desirable one.

It can be interpreted as a participation requirement, since the offering to an agent of an amount less preferred than her endowment would make her reluctant to participate in the reallocation process.¹ Not all efficient and strategy-proof rules are individually rational, as can be seen in the following example.

Example 2

The hierarchical rule $\varvec{f^h},$ in case of excess demand (supply), satiates all suppliers (demanders) and the demanders (suppliers) according to their number. Formally, it is defined in the following way: given $e=(R,\omega ) \in \mathcal {E}^N,$ let $\mathcal {S}(e):=\{j \in N : \omega _j \ge p(R_j)\}$ and $s(e):=\sum _{j \in \mathcal {S}(e)}(\omega _j-p(R_j))$. If $z(e)\ge 0$ then

$$\begin{aligned} f_i^h(e):=\left\{ \begin{array}{l} p(R_i) \ \ \ \ \ \mathrm {if} \ i \in \mathcal {S}(e) \\ \min \{ p(R_i), \omega _i+ s(e)-\sum _{j \notin \mathcal {S}(e),j<i}\Delta f_j^h(e)\} \quad \mathrm {otherwise.}\end{array} \right. \end{aligned}$$

When $z(e) \le 0$ the rule is defined similarly. Now consider the following rule:

$$\begin{aligned} \varvec{f^*(e)}:=\left\{ \begin{array}{l} f^h(e) \ \ \ \ \mathrm {if} \ z(e) \ge 0 \\ f^q(e)\ \ \ \ \mathrm {if} \ z(e) < 0. \end{array} \right. \end{aligned}$$

where $f^q$ is the queueing rule presented in Example 1. The rule $f^*$ is efficient and strategy-proof, but not individually rational. To verify this, consider $e=(R,\omega ) \in \mathcal {E}^{\{1,2\}}$ such that $p(R_1) < \omega _1$ and $p(R_2)=\omega _2=0.$ Then $f^*(e)=(p(R_1),\omega _1$ $-p(R_1))$ and $\omega _2 P_2 f_2^*(e).$

Next, we present two lemmata. For the first one we need the following definition.

Own peak-only: For each $e=(R,\omega ) \in \mathcal {E}^N,$ $i \in N$ and $R_i^{\prime } \in \mathcal {R}$ such that $p(R_i^{\prime })=p(R_i),$ if $e^{\prime }=(R_i',R_{-i},\omega )$ then $f_i(e^{\prime })=f_i(e).$

This property means that unilateral preference changes with the same peak performed by an agent do not change her allotment. It is well-known that any efficient and preference strategy-proof rule is own peak-only (for example, this is a straightforward consequence of Lemma 3 in Klaus et al. (1998)). For later reference, we present this observation as a lemma.

Lemma 1

Any efficient and strategy-proof rule is own peak-only.

The second lemma restraints the behavior of efficient and strategy-proof rules with respect to the direction of change of the net trades.

Lemma 2

For each $e=(R,\omega ) \in \mathcal {E}^N,\,i \in N$ and $(R_i^{\prime },\omega _i^{\prime }) \in \mathcal {R}\times \mathbb {R}_+,$ if $f$ is an efficient and strategy-proof rule, $f_i(e) \ne p(R_i)$ and $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime }, \omega {_i}),$ then: (i) $z(e) \ge 0$ implies $\Delta f_i(e) \ge \Delta f_i(e^{\prime }),$ and (ii) $z(e) \le 0$ implies $\Delta f_i(e) \le \Delta f_i(e^{\prime }).$

Proof

Let us only see (i), since (ii) is symmetric. Assume $z(e)\ge 0$ and $\Delta f_i(e) < \Delta f_i(e^{\prime })$ or, equivalently, $f_i(e)<f_i(e^{\prime })+(\omega _i-\omega _i^{\prime }).$ By efficiency and the fact that $f_i(e) \ne p(R_i),$ we have $f_i(e)<p(R_i).$ Single-peakness of preferences and strategy-proofness imply that $f_i(e^{\prime })+(\omega _i-\omega _i^{\prime })>p(R_i).$ Now consider a preference $\tilde{R}_i \in \mathcal {R}$ such that $p(\tilde{R}_i)=p(R_i)$ and $(f_i(e^{\prime })+(\omega _i-\omega _i^{\prime }))\tilde{P}_if_i(e).$ By Lemma 1, $f$ is an own peak-only rule. Therefore, if $\tilde{e}=(\tilde{R}_i, R_{-i}, \omega ),$ then $f_i(\tilde{e})=f_i(e)$ and $(f_i(e^{\prime })+(\omega _i$ $-\omega _i^{\prime }))\tilde{P}_if_i(\tilde{e}),$ contradicting the strategy-proofness of $f.$ $\square$

The next property is a weakening of the dummy property presented in Klaus et al. (1997).²

Weak dummy: For each $e=(R,\omega ) \in \mathcal {E}^N,$ whenever $i \in N$ is such that $p(R_i)=\omega _i=0,$ we have $f_i(e)=0.$

Lemma 3

For each $e=(R, \omega ) \in \mathcal {E}^N,$ if $f$ is an efficient and strategy-proof rule satisfying the weak dummy property then: (i) $z(e)\ge 0$ implies $\omega _i \le f_i(e) \le p(R_i)$ if $\omega _i<p(R_i)$ and $f_i(e)=p(R_i)$ if $\omega _i \ge p(R_i),$ and (ii) $z(e) \le 0$ implies $p(R_i) \le f_i(e) \le \omega _i$ if $\omega _i>p(R_i)$ and $f_i(e)=p(R_i)$ if $\omega _i \le p(R_i).$

Proof

Let $e=(R, \omega ) \in \mathcal {E}^N$ and $i \in N.$ If $z(e)\ge 0,$ by efficiency $f_i(e) \le p(R_i).$ Suppose $f_i(e) < p(R_i).$ Let $\omega _i^{\prime }=0$ and consider $e^{\prime }=(R, \omega _i^{\prime }, \omega _{-i}).$ By Lemma 2, $\Delta f_i(e) \ge \Delta f_i(e^{\prime })=f_i(e^{\prime })-0 \ge 0,$ and then $f_i(e) \ge \omega _i.$ Furthermore, $i$ is such that $\omega _i < p(R_i).$

If $z(e) < 0,$ efficiency implies $f_i(e) \ge p(R_i).$ Suppose $f_i(e) > p(R_i).$ Next, let us consider $(R_i^{\prime },\omega _i^{\prime })\in \mathcal {R}\times \mathbb {R}_+$ such that $p(R_i^{\prime })=\omega _i^{\prime }=0$ and define the economy $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime },\omega _{-i}).$ Using Lemma 2 and the weak dummy property, we obtain $\Delta f_i(e)\le \Delta f_i(e^{\prime })=f_i(e^{\prime })-\omega _i^{\prime }=0,$ so $f_i(e)\le \omega _i$ follows. Furthermore, $i$ is such that $\omega _i > p(R_i).$ $\square$

Remark 1

The previous Lemma 3 extends, as far as possible, Corollary 6.2 in Klaus et al. (1997) to the case of excess supply. Example 2 shows that the weak dummy property is necessary when $z(e)<0.$

For efficient and strategy-proof rules the weak dummy property is equivalent to individual rationality.

Lemma 4

Any efficient and strategy-proof rule satisfies the weak dummy property if and only if it is individually rational.

Proof

Let $f$ be an efficient and strategy-proof rule. If $f$ is individually rational then it trivially fulfills the weak dummy property. Suppose $f$ also satisfies the weak dummy property. By Lemma 3, $f$ assigns to each agent either her peak or something in between her endowment and her peak, and since preferences are single-peaked $f$ is individually rational. $\square$

3 A characterization of bribe-proof reallocation rules

In addition to efficiency, strategy-proofness and individual rationality, we are interested in rules that preclude the possibility that a group of agents gain by an internal redistribution of the allotments they obtain after some of its members misrepresent their characteristics, adjusted by the surplus (deficit) they engage in when they withhold (borrow) resources.

Bribe-proofness: For each $e=(R,\omega ) \in \mathcal {E}^N$ and $V \subseteq S \subseteq N$, there are no $(R_i^{\prime },\omega _i^{\prime })_{i \in V} \in \mathcal {R}^V \times \mathbb {R}_+^V$ and $(\ell _j)_{j \in S} \in \mathbb {R}^S$ such that, if $e^{\prime }=(R_V', R_{-V},\omega _V^{\prime }, \omega _{-V}),$ then:

• 1. $\sum _{j \in S}\ell _j=\sum _{j \in S}f_j(e^{\prime })+\sum _{i \in V}(\omega _i-\omega _i^{\prime }),$

• 2. $\ell _j R_j f_j(e)$ for each $j \in S,$ and

• 3. $\ell _i P_i f_i(e)$ for each $i \in V$.

Remark 2

The property of bribe-proofness implies both efficiency and strategy-proofness.³ To see efficiency, assume $f$ is not same-sided. Without loss of generality take $e \in \mathcal {E}^N$ such that $z(e) \ge 0.$ Then there is $i \in N$ such that $f_i(e)>p(R_i).$ Feasibility implies the existence of $j \in N$ such that $f_j(e)<p(R_j).$ Let $\varepsilon >0$ be sufficiently small such that $f_i(e)-\varepsilon > p(R_i)$ and $f_j(e)+\varepsilon <p(R_j).$ Define $S=\{i,j\},$ $V=\{i\},$ $(R_i',\omega _i^{\prime })=(R_i,\omega _i),$ $\ell _i=f_i(e)-\varepsilon$ and $\ell _j=f_j(e)+\varepsilon .$ Hence $f$ is not bribe-proof. To see strategy-proofness, consider $S=V=\{i\}$ in the definition of bribe-proofness.

Remark 3

Bribe-proofness does not imply individual rationality. Consider rule $f^*$ defined in Example 2. This rule is not individually rational, and it is not hard to prove that it is bribe-proof.

Remark 4

The requirement that only bribed agents (i. e., agents in coalition $V$) are made strictly better off after the misrepresentation of preferences or endowments is inessential: all of our results still hold if we ask that all the agents involved in the bribe get strictly better off (i.e., if we ask “$\ell _j P_j f_j(e)$ for each $j \in S$” instead of points (2) and (3) in the definition of bribe-proofness). If, however, bribed agents are allowed to remain indifferent (i.e., if point (3) in the definition is removed), then bribe-proofness is very hard to get and not even the uniform reallocation rule (see Sect. 5) would satisfy the property.

The concept of manipulation through bribes was introduced by Schummer (2000) for general economies with quasi-linear preferences. In his paper, bribe-proofness requires that there is no pair of agents who are jointly better off if one of them transfers some money to the other to misrepresent her type. An alternate notion of bribe-proofness is analyzed by Massó and Neme (2007) in the context of one-good economies with single-peaked preferences and a social endowment. Their definition requires that no group of agents can be better off by misreporting preferences and reallocating the outcome within the group. Our definition of bribe-proofness is stronger than Massó and Neme’s version since our bribes allow manipulation through endowments as well, in a more general model.⁴ Not all bribe-proof rules in Massó and Neme’s sense are bribe-proof in ours. In fact, the queuing rule presented in Example 1 is bribe-proof in their sense but manipulable via (withholding of) endowments and, consequently, not bribe-proof in our broader sense. An example of a rule that satisfies our requirement is the uniform reallocation rule analyzed in Sect. 5.

The next property we introduce is a strong solidarity notion. It requires that when the characteristics of an agent change and the agent’s net allotment increases then, unless the agent gets her true peak before or her false peak after, none of the remaining agents’ allotments can increase. Formally,

Weak replacement monotonicity: For each $e=(R, \omega ) \in \mathcal {E}^N$, $i \in N$ and $(R_i^{\prime },\omega _i^{\prime }) \in \mathcal {R}\times \mathbb {R}_+^N,$ if $e^{\prime }=(R_i',R_{-i}, \omega _i^{\prime }, \omega _{-i})$ and $\Delta f_i(e^{\prime }) \ge \Delta f_i(e),$ then $f_j(e^{\prime }) \le f_j(e)$ for each $j \ne i$ whenever $f_i(e)\ne p(R_i)$ or $f_i(e^{\prime })\ne p(R_i^{\prime }).$

We say that this is a strong solidarity notion because, under efficiency, this property is equivalent to the application of a one-sided replacement principle (see Thomson (1997)): when data entering the description of the problem to be solved changes (in our case one agent’s preference and endowment) and the change is not so disruptive that it turns the economy from one in which there is “too little” of the commodity (i.e., the economy has excess demand), to one in which there is “too much” (i.e., the economy has excess supply), all the (remaining) agents’ welfare should be affected in the same direction. By same-sidedness, this is precisely what weak replacement monotonicity asks for in its definition, adding the proviso of not requiring anything whenever the agent whose characteristics are replaced receives her peak amount.

We now proceed to proof the main result of the paper, a characterization of all bribe-proof rules. To do this, we follow closely the proof presented in Massó and Neme (2007) for the problem of allocating a social endowment, although we cannot make use of their Lemma 2, which consists of a fundamental result about rules that are preference strategy-proof and is extensively used throughout their paper. Instead of working with the property of bribe-proofness we will deal with bribes in which the set of bribed agents is a singleton.

Individual bribe-proofness: For each $e=(R,\omega ) \in \mathcal {E}^N,$ $i \in N,$ and $(R_i^{\prime },\omega _i^{\prime }) \in \mathcal {R} \times \mathbb {R}_+,$ there are no $S \subseteq N$ and $(\ell _j)_{j \in S} \in \mathbb {R}^S$ such that $i \in S$ and, if $e^{\prime }=(R_i', R_{-i},\omega _i^{\prime }, \omega _{-i}),$ then

• 1. $\sum _{j \in S}\ell _j=\sum _{j \in S}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime }),$

• 2. $\ell _j R_j f_j(e)$ for each $j \in S$ and

• 3. $\ell _i P_i f_i(e).$

Of course, every bribe-proof rule is individually bribe-proof. Our main result is the following:

Theorem 1

A rule is bribe-proof if and only if it is efficient, strategy-proof and weakly replacement monotonic.

The proof of the theorem makes use of the following three lemmata. Lemma 5 states that any efficient, strategy-proof and weakly replacement monotonic rule is individually bribe-proof, whereas Lemma 6 says that any individually bribe-proof rule is efficient, strategy-proof and weakly replacement monotonic. Finally, in Lemma 7, it is shown that individual bribe-proofness is actually equivalent to bribe-proofness.

Lemma 5

Any efficient, strategy-proof and weakly replacement monotonic rule is individually bribe-proof.

Proof

Let $f$ be an efficient, strategy-proof and weakly replacement monotonic rule. Assume $f$ is not individually bribe-proof. Then there are $\{i\} \subset S\subset N,$ $e=(R,\omega ) \in \mathcal {E}^N,$ $(R_i^{\prime },\omega _i^{\prime }) \in \mathcal {R}\times \mathbb {R}_+$ and $(\ell _j)_{j \in S} \in \mathbb {R}^S$ such that, if $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime },\omega _{-i})$:

$$\begin{aligned} \sum _{j \in S}\ell _j=\sum _{j \in S}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime }), \end{aligned}$$

(1)

$$\begin{aligned} \ell _jR_jf_j(e) \quad \mathrm for \ \mathrm each \ j \in S, \end{aligned}$$

(2)

and

$$\begin{aligned} \ell _iP_if_i(e). \end{aligned}$$

(3)

Without loss of generality, let us assume $z(e)\ge 0.$ By efficiency, $f_j(e) \le p(R_j)$ for each $j \in N$. Consequently, by conditions (2) and (3),

$$\begin{aligned} f_j(e) \le \ell _j \quad \mathrm for \ \mathrm each \ j \in S, \end{aligned}$$

(4)

and

$$\begin{aligned} f_i(e)<\ell _i. \end{aligned}$$

(5)

By (1), (4) and (5),

$$\begin{aligned} \sum _{j\in S}f_j(e)<\sum _{j \in S} \ell _j=\sum _{j \in S}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime }). \end{aligned}$$

(6)

By Lemma 2, efficiency and strategy-proofness of $f$ and Eq. (3) imply $\Delta f_i(e) \ge \Delta f_i(e^{\prime }).$ Weak replacement monotonicity implies $f_j(e^{\prime }) \ge f_j(e^{\prime })$ for each $j \ne i.$ Hence,

$$\begin{aligned} \sum _{j \notin S}f_j(e^{\prime }) \ge \sum _{j \notin S}f_j(e). \end{aligned}$$

(7)

Because of feasibility,

$$\begin{aligned} \sum _{j \in N}f_j(e)=\sum _{j \in N}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime }) \end{aligned}$$

(8)

Using (7) and (8), we get $\sum _{j \in N}f_j(e)\ge \sum _{j \notin S}f_j(e)+\sum _{j \in S}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime })$ or

$$\begin{aligned} \sum _{j \in S}f_j(e)\ge \sum _{j \in S}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime }), \end{aligned}$$

contradicting (6). $\square$

Lemma 6

Any individually bribe-proof rule is efficient, strategy-proof and weakly replacement monotonic.

Proof

The properties of efficiency and strategy-proofness follow from Remark 2. Suppose $f$ is not weakly replacement monotonic. Then, we can assume, w.l.og., there are $e=(R, \omega ) \in \mathcal {E}^N,$ $i \in N$ and $(R_i^{\prime },\omega _i^{\prime }) \in \mathcal {R}\times \mathbb {R}_+$ such that, if $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime },\omega _{-i}),$ $f_i(e^{\prime }) \ne p(R_i^{\prime }),$ and either:

• 1. $\Delta f_i(e)< \Delta f_i(e^{\prime })$ and there is $k \ne i$ such that $f_k(e)<f_k(e^{\prime }),$ or

• 2. $\Delta f_i(e)=\Delta f_i(e^{\prime })$ and there is $k, k^{\prime } \in N {\setminus } \{i\}$ such that $f_k(e)<f_k(e^{\prime })$ and $f_{k^{\prime }}(e)>f_{k^{\prime }}(e').$

We will analyze each possibility separately.

Case 1 Assume $\varvec{\Delta f_i(e)< \Delta f_i(e^{\prime })}$ and $\varvec{f_k(e)<f_k(e^{\prime })}$ for some $\varvec{k \ne i.}$ The subcase $z(e^{\prime }) < 0$ is ruled out by Lemma 2, so we only need to consider $z(e^{\prime }) \ge 0.$ Let $S:=\{j \in N : f_j(e^{\prime }) < f_j(e)\} \cup \{i\}.$ Note that $S \ne \{i\},$ since otherwise we would contradict the hypothesis $\Delta f_i(e)< \Delta f_i(e^{\prime }).$ We will show that in economy $e^{\prime }$ coalition $S$ can bribe agent $i$ to misrepresent her characteristics by reporting $(R_i,w_i)$ so all of them get better off. By efficiency, $f_j(e^{\prime }) \le p(R_j)$ for each $j \in N.$ As $f_k(e)<f_k(e^{\prime }) \le p(R_k),$ using efficiency once again we get

$$\begin{aligned} f_j(e) \le p(R_j) \ \mathrm for \ \mathrm each \ j \in N.\end{aligned}$$

(9)

and, as $f_i(e^{\prime }) \ne p(R_i^{\prime }),$ we also get

$$\begin{aligned} f_i(e^{\prime }) < p(R_i^{\prime }). \end{aligned}$$

(10)

Since $k \notin S,\,\sum _{j \in N {\setminus } S}f_j(e^{\prime }) > \sum _{j \in N {\setminus } S}f_j(e).$ This fact and feasibility imply

$$\begin{aligned} \sum _{j \in S}f_j(e)>\sum _{j \in S}f_j(e^{\prime })+(\omega _i-\omega _i^{\prime }). \end{aligned}$$

(11)

Hence, by (10) and (11) we can choose $\varepsilon >0$ such that

$$\begin{aligned} \varepsilon < \sum _{j \in S}(f_j(e)-f_j(e^{\prime }))+(\omega _i^{\prime }-\omega _i) \end{aligned}$$

(12)

and $\varepsilon < p(R_i^{\prime })-f_i(e^{\prime }).$ Equation (12) can be rewritten as

$$\begin{aligned} \Delta f_i(e^{\prime })-\Delta f_i(e)+\varepsilon < \sum _{S {\setminus } \{i\}}(f_j(e)-f_j(e^{\prime })). \end{aligned}$$

By (9) and the definition of $S,\,f_j(e^{\prime })<f_j(e)\le p(R_j)$ for each $j \in S {\setminus } \{i\},$ so there is $\alpha _j>0$ for each $j \in S {\setminus } \{i\}$ such that $\alpha _j<f_j(e)-f_j(e^{\prime })$ and

$$\begin{aligned} \sum _{j \in S{\setminus } \{i\}}\alpha _j=\Delta f_i(e^{\prime })-\Delta f_i(e)+\varepsilon . \end{aligned}$$

(13)

Now, define $\ell _i:=f_i(e^{\prime })+\varepsilon$ and $\ell _j:=f_j(e)-\alpha _j$ for $j \in S {\setminus } \{i\}.$ Note that $\ell _j P_j f_j(e^{\prime })$ for each $j \in S$ and that

$$\begin{aligned} \sum _{j \in S}\ell _j&= f_i(e^{\prime })+\varepsilon +\sum _{S {\setminus } \{i\}}f_j(e)-\sum _{S {\setminus } \{i\}}\alpha _j\\&= f_i(e^{\prime })+\varepsilon +\sum _{S {\setminus } \{i\}}f_j(e)-\Delta f_i(e^{\prime })+\Delta f_i(e)-\varepsilon \\&= \sum _{j \in S}f_j(e)+(\omega _i^{\prime }-\omega _i), \end{aligned}$$

so $f$ is not individually bribe-proof.

Case 2 Assume $\varvec{\Delta } {\varvec{f}}_{\varvec{i}}({\varvec{e}})=\varvec{\Delta } {\varvec{f}}_{\varvec{i}}(\varvec{e}^{\prime })$ and there are $\varvec{k}, \varvec{k}^{\prime } \in \varvec{N} {\setminus } \{\varvec{i}\}$ such that $\varvec{f}_{\varvec{k}}(\varvec{e})<\varvec{f}_{\varvec{k}}(\varvec{e}^{\prime })$ and $\varvec{f}_{\varvec{{k}}^{\prime }}(\varvec{e})>\varvec{f}_{\varvec{k}^{\prime }}(\varvec{e}^{\prime }).$

Subcase 2.1

$\varvec{z}(\varvec{e}^{\prime }) \ge \mathbf{0}.$ By hypothesis, $f_i(e^{\prime }) \ne p(R_i^{\prime }),$ so

$$\begin{aligned} f_i(e)+(\omega _i^{\prime }-\omega )=f_i(e^{\prime })<p(R_i^{\prime }). \end{aligned}$$

(14)

By efficiency,

$$\begin{aligned} f_k(e^{\prime })<f_k(e) \le p(R_k). \end{aligned}$$

(15)

Considering Eqs. (14) and (15) we can choose an $\varepsilon >0$ such that $f_i(e^{\prime })<f_i(e)+(\omega _i^{\prime }-\omega _i)+\varepsilon <p(R_i^{\prime })$ and $f_k(e^{\prime })<f_k(e)-\varepsilon <f_k(e)\le p(R_k).$ Now set $S:{=}\{i,k\},\,\ell _i:=f_i(e)+(\omega _i^{\prime }-\omega _i)+\varepsilon$ and $\ell _k:=f_k(e)-\varepsilon .$ As $\sum _{j \in S}\ell _j=f_k(e)+f_i(e)+(\omega _i^{\prime }-\omega _i),$ $\ell _iP_i^{\prime }f_i(e')$ and $\ell _kP_k^{\prime }f_k(e'),$ in economy $e^{\prime }$ coalition $S$ makes a bribe through agent $i$ reporting $(R_i, \omega _i)$ and $f$ is not individually bribe-proof.

Subcase 2.2

$\varvec{z}(\varvec{e}^{\prime }) < \mathbf{0}.$ Efficiency implies $p(R_j)\le f_j(e^{\prime })$ for each $j \ne i$ and

$$\begin{aligned} p(R_i^{\prime })<f_i(e^{\prime })=f_i(e)+(\omega _i^{\prime }-\omega _i), \end{aligned}$$

(16)

since, by hypothesis, $f_i(e^{\prime })\ne p(R_i^{\prime }).$ As $p(R_{k^{\prime }})\le f_{k^{\prime }}(e')<f_{k^{\prime }}(e),$ by efficiency $z(e)\le 0$ and

$$\begin{aligned} p(R_k)\le f_k(e)<f_k(e^{\prime }). \end{aligned}$$

(17)

By (16) and (17) there is $\varepsilon >0$ such that $p(R_i^{\prime })<f_i(e)+(\omega _i^{\prime }-\omega _i)-\varepsilon <f_i(e^{\prime })$ and $p(R_k)<f_k(e)+\varepsilon <f_k(e^{\prime }).$ Define $S:=\{i,k\},$ $\ell _i:=f_i(e)+(\omega _i^{\prime }-\omega _i)-\varepsilon$ and $\ell _k:=f_k(e)+\varepsilon .$ As $\ell _i P_i^{\prime } f_i(e'),$ $\ell _k P_k f_k(e^{\prime })$ and $\sum _{j \in S}\ell _j=f_k(e)+f_i(e)+(\omega _i^{\prime }-\omega _i),$ the rule $f$ is not individually bribe-proof. $\square$

Lemma 7

A rule is individually bribe-proof if and only if it is bribe-proof.

Proof

Let $f$ be an individually bribe-proof rule and assume that it is not bribe-proof. This means that there are $e=(R,\omega ) \in \mathcal {E}^N,\,V \subseteq S \subseteq N$ with $|V|\ge 2,\,(R_i^{\prime },\omega _i^{\prime })_{i \in V} \in \mathcal {R}^V\times \mathbb {R}_+^V$ and $(\ell _j)_{j \in S} \in \mathbb {R}^S$ such that, taking $e^{\prime }=(R_V', R_{-V},\omega _V^{\prime }, \omega _{-V}),$ we have

$$\begin{aligned}&\sum _{j \in S}\ell _j=\sum _{j \in S}f_j(e^{\prime })+\sum _{i \in V}(\omega _i-\omega _i^{\prime }), \end{aligned}$$

(18)

$$\begin{aligned}&\ell _j R_j f_j(e) \ \mathrm {for} \ \mathrm {each} \ j \in S \ \mathrm {and} \ \ell _i P_i f_i(e) \ \mathrm {for} \ \mathrm {each} \ i \in V. \end{aligned}$$

(19)

Without loss of generality, assume $V$ to be minimal in the following way: for each $i \in V$ there are no $\bar{S} \supseteq V {\setminus } \{i\},\,(\bar{R}_{V {\setminus } \{i\}}, \bar{\omega }_{V {\setminus } \{i\}}) \in \mathcal {R}^{V {\setminus } \{i\}}\times \mathbb {R}^{V {\setminus } \{i\}},$ and $(\bar{\ell }_j)_{j \in \bar{S}}$ with the property that, if $\bar{e}=(R_{V{\setminus } \{i\}}^{\prime },R_i, R_{-V},\omega _{V{\setminus }\{i\}}^{\prime },\omega _i, \omega _{-V}),$ then $\sum _{j \in \bar{S}}\bar{\ell }_j=\sum _{j \in \bar{S}}f_j(\bar{e})+\sum _{\bar{i} \in V {\setminus } \{i\}}(\omega _{\bar{i}}-\omega ^{\prime }_{\bar{i}}),\,\bar{\ell }_jR_jf_j(e)$ for each $j \in \bar{S},$ and $\bar{\ell }_{\bar{i}}R_{\bar{i}}f_{\bar{i}}(e)$ for each $\bar{i} \in V{\setminus } \{i\}.$ Assume $z(e)\ge 0$ (the other case is symmetrical). By Lemma 6, $f$ is efficient, then (18) and (19) imply

$$\begin{aligned} \sum _{j \in S}f_j(e^{\prime })+\sum _{i \in V}(\omega _i-\omega _i^{\prime })>\sum _{j \in S}f_j(e). \end{aligned}$$

(20)

By the minimality condition placed on $V$, it must be that, for each $i \in V,$

$$\begin{aligned} \sum _{j \in S}f_j(\bar{e})+\sum _{\bar{i} \in V{\setminus }\{i\}}(\omega _{\bar{i}}-\omega _{\bar{i}}^{\prime }) \le \sum _{j \in S}f_j(e). \end{aligned}$$

(21)

To see that (21) holds, assume otherwise. Then there is $i \in V$ such that

$$\begin{aligned} \sum _{j \in S}f_j(e) < \sum _{j \in S}f_j(\bar{e})+\sum _{\bar{i} \in V{\setminus }\{i\}}(\omega _{\bar{i}}-\omega _{\bar{i}}^{\prime }). \end{aligned}$$

(22)

Efficiency, $z(e)\ge 0$ and $\ell _iP_if_i(e)$ for each $i \in V$ imply that $p(R_k)>f_k(e)$ for each $k \in V.$ Take $k \in V{\setminus }\{i\}$ and consider any $\tilde{R}_k \in \mathcal {R}$ such that $p(\tilde{R}_k)=\sum _{j \in N}\omega _j,$ and the associated economy $\tilde{e}=(\tilde{R}_k,R_{-k},\omega ).$ By Lemma 6, $f$ is also strategy-proof, and as $z(e), z(\tilde{e})\ge 0,$ by Lemma 2 we have that $f_k(e)=f_k(\tilde{e}).$ Since $f$ is furthermore weakly replacement monotonic (this is consequence of Lemma 6 again) we obtain $f(e)=f(\tilde{e}).$ Hence, by (22) and $p(\tilde{R}_k)=\sum _{j \in N}\omega _j,$

$$\begin{aligned} \sum _{j \in S}f_j(\tilde{e})=\sum _{j \in S}f_j(e) < \sum _{j \in S}f_j(\bar{e})+\sum _{\bar{i} \in V{\setminus }\{i\}}(\omega _{\bar{i}}-\omega _{\bar{i}}^{\prime }) \le \sum _{j \in S{\setminus }\{k\}}p(R_j)+p(\tilde{R}_k). \end{aligned}$$

We can now assure the existence of $(\bar{\ell }_j)_{j \in S}\in \mathbb {R}^S$ such that $\sum _{j \in S}\bar{\ell }_j=\sum _{j \in S}f_j(\bar{e})$ $+\sum _{\bar{i} \in V {\setminus } \{i\}}(\omega _{\bar{i}}-\omega ^{\prime }_{\bar{i}})$ and $f_j(\tilde{e}) <\bar{\ell }_j\le p(R_j)$ for each $j \in S$. Thus, $\bar{\ell }_jP_jf_j(\tilde{e})$ for each $j \in S,$ and in economy $\tilde{e}$ coalition $S$ can bribe coalition $V{\setminus } \{i\}$ to misrepresent their characteristics by reporting $(R_{V{\setminus } \{i\}}^{\prime }, \omega _{V{\setminus } \{i\}}^{\prime }),$ in contradiction with the minimality of $V.$ Thus (21) holds.

From (20) and (21) it follows that

$$\begin{aligned} \sum _{j \in S}f_j(\bar{e})+\sum _{\bar{i} \in V{\setminus }\{i\}}(\omega _{\bar{i}}-\omega _{\bar{i}}^{\prime })<\sum _{j \in S}f_j(e^{\prime })+\sum _{i \in V}(\omega _i-\omega _i^{\prime }), \end{aligned}$$

and therefore in economy $\bar{e}$ coalition $S$ can bribe agent $i$ to report $(R_i^{\prime },\omega _i^{\prime }).$ But this means that $f$ is not individually bribe-proof. $\square$

Proof of Theorem 1

By Lemmata 5 and 6, a rule $f$ is efficient, strategy-proof and weakly replacement monotonic if and only if it is individually bribe-proof. By Lemma 7, individual bribe-proofness is equivalent to bribe-proofness. $\square$

4 A description of weakly sequential reallocation rules

In the model with a social endowment, Barberà et al. (1997) provide a characterization of the class of efficient, preference strategy-proof and replacement monotonic ⁵ rules by means of a sequential procedure of adjustments which uses certain “guaranteed levels” as starting reference. Such idea is adapted by Massó and Neme (2003) to cope with bribe-proofness (in their weaker sense). Following this approach, in this section we describe a collection of rules which are bribe-proof and individually rational. We also require the rules to be peak-only, this is, to depend only on the profile of peaks instead of on all the profile of preferences.⁶ To begin, we present a way to redistribute the endowments of the agents through sequential improvements that respect the properties we have analyzed so far. Let $\varvec{\mathcal {Q}}:=\{(q,e) \in \mathbb {R}^N \times \mathcal {E}^N \ | \ e=(R,\omega ) \ \mathrm {and} \ q+\omega \ge 0 \ \mathrm {with} \ \sum _{j \in N} q_j=0 \}.$

Given $e=(R,\omega )$ and $e'=(R_i',R_{-i},\omega _i^{\prime },\omega _{-i})$ in $\mathcal {E}^N$, a function $\varvec{g}$ mapping $\mathcal {Q}$ into itself is a weakly sequential reallocator if the following conditions hold for each $t \ge 1,$ each $(q^t,e) \in \mathcal {Q}$ such that $(q^t,e)=g^t(q^0,e)$ and each $(q^{\prime t},e') \in \mathcal {Q}$ such that $(q^{\prime t},e')=g^t(q^0,e^{\prime })$: ⁷

• (i) $q^0=0.$

• (ii) $q_i^t=p(R_i)-\omega _i$ if $z(e)(p(R_i)-\omega _i-q_i^{t-1}) \le 0.$

• (iii) $(q_i^t-q_i^{t-1}) z(e) \ge 0$ if $z(e)(p(R_i)-\omega _i-q_i^{t-1}) > 0.$

• (iv) If $\min \{p(R_i^{\prime })-\omega _i^{\prime }, p(R_i)-\omega _i\} \ge q_i^{t-1}$ when $z(e)\ge 0$ or $\max \{p(R_i^{\prime })$ $-\omega _i^{\prime }, p(R_i)-\omega _i\}\le q_i^{t-1}$ when $z(e)\le 0,$ then $q^{t}=q^{\prime t}.$

• (v) If $p(R_i^{\prime })-\omega _i^{\prime }<q_i^n<p(R_i)-\omega _i$ and $z(e)\ge 0,$ then $q^{\prime n}_j \ge q_j^n$ for each $j \ne i,$ and if $p(R_i^{\prime })-\omega _i^{\prime }>q_i^n>p(R_i)-\omega _i$ and $z(e)\le 0,$ then $q^{\prime n}_j \le q_j^n$ for each $j \ne i.$

Let us put in words the above definition for the case of excess demand (this is, when $z(e)\ge 0$). In the definition of the reallocator $g,$ part (i) simply starts the reallocation vector at zero. Part (ii) says that if at any stage some agents’ peaks are not higher than their endowments plus the reallocation amount offered in the previous stage to them, then they should get their peaks. Part (iii) establishes that for the remaining agents the offers at each stage will be non-decreasing. Part (iv) states that if, at some stage, the change of characteristics of an agent whose peak is above her endowment plus what is offered to her via the reallocator is such that she still wants more than offered, her reallocation will be kept unaffected. Finally, part (v) says that when an agent that is not obtaining her peak changes her characteristics and this makes her new peak feasible, then the reallocator’s offers to the remaining agents cannot decrease.

A reallocation rule $f$ is weakly sequential if there exists a weakly sequential reallocator $g$ such that, for each $e=(R, \omega ) \in \mathcal {E}^N,$ if $q^n$ comes from $(q^n,e)=g^n(q^0,e),$ then $\Delta f(e)=q^n.$

A weakly sequential rule is obtained adjusting the net trades of the agents according to a weakly sequential reallocator. The following theorem, that can be seen as an extension of the Corollary in Barberà et al. (1997) (using as initial “guaranteed levels” the individual endowments), completely describes as weakly sequential any bribe-proof and individually rational rule that in addition is peak-only.⁸

Theorem 2

A reallocation rule is weakly sequential if and only if it is bribe-proof, individually rational and peak-only.

Proof

($\Longleftarrow$) Consider a bribe-proof, individually rational and peak-only rule $f.$ Given economy $e=(R,\omega ) \in \mathcal {E}^N,$ define economy $\bar{e}=(\bar{R},\omega )$ such that $p(\bar{R}_i)=2\sum _{j \in N}\omega _j$ for each $i \in N$ and economy $\underline{e}=(\underline{R},\omega )$ so that $p(\underline{R}_i)=0$ for each $i \in N.$ Next, define a weakly sequential reallocator $g:\mathcal {Q} \longrightarrow \mathcal {Q}$ as follows: for each $(q,e) \in \mathcal {Q},$

$$\begin{aligned} g(q,e)=(\varDelta f(\tilde{e}), e) \end{aligned}$$

where $\tilde{e}=(\tilde{R}, \omega )$ is such that

$$\begin{aligned} p(\tilde{R}_i)=\left\{ \begin{array}{l} p(R_i) \ \ \ \mathrm {if} \ z(e)(p(R_i)-\omega _i-q_i)< 0, \\ p(\overline{R}_i) \ \ \ \mathrm {if} \ z(e)\ge 0 \ \mathrm {and} \ p(R_i)-\omega _i \ge q_i, \ \mathrm {and} \\ p(\underline{R}_i) \ \ \ \mathrm {if} \ z(e) < 0 \ \mathrm {and} \ p(R_i)-\omega _i \le q_i. \end{array} \right. \end{aligned}$$

and set $q^0:=\Delta f(\overline{e})$ if $z(e)\ge 0$ and $q^0:=\Delta f(\underline{e})$ if $z(e)<0.$ We need to show that $g$ fulfills the conditions of a weakly sequential reallocator and that if $q^n$ comes from $(q^n,e)=g^n(q^0,e)$ then $q^n=\Delta f(e).$ In order to do so, consider $e=(R,\omega ) \in \mathcal {E}^N$ with $z(e)\ge 0$ (the case $z(e)<0$ follows similar reasonings). Define, recursively, the sets of agents

$$\begin{aligned} S^t=S^{t-1} \cup \{i \in N{\setminus } S^{t-1} \ | \ p(R_i)-\omega _i \le q_i^{t-1}\}, \ \ t=1, \ldots ,n \end{aligned}$$

with $S^0=\emptyset ,$ and let $q^t=\Delta f(\tilde{e}^t)$ where $\tilde{e}^t=(R_{S^t}, \bar{R}_{-S^t},\omega ).$ Notice that as $q^0=\Delta f(\bar{e})$ we have $q^0=0,$ since by individual rationality $f_i(\bar{e}) \ge \omega _i$ for each $i \in N,$ so feasibility implies $f(\bar{e})=\omega$ and therefore $\Delta f(\bar{e})=0.$ Next, let $S^1:=\{i_1, i_2, \ldots , i_{s^1}\},$ $\tilde{e}^0_1:=(R_{i_1},\bar{R}_{-i_1}, \omega )$ and $q^{0,1}:=\Delta f(\tilde{e}^0_1).$ Being $p(R_{i_1})-\omega _{i_1}\le q^0=0,$ Lemma 3 implies $f_{i_1}(\tilde{e}^0_1)=p(R_{i_1}).$ As $f_{i_1}(\bar{e})\ne p(\bar{R}_{i_1}),$ Lemma 2 implies $\Delta f_{i_1}(\bar{e}) \ge \Delta f_{i_1}(\tilde{e}_1^0)$ and by weak replacement monotonicity $q_j^0=\Delta f_{j}(\bar{e}) \le \Delta f_{j}(\tilde{e}_1^0)=q_j^{0,1}$ for $j \ne i_1.$ Now let $\tilde{e}^0_2=\left( R_{i_1},R_{i_2}, \bar{R}_{-\{i_1,i_2\}},\omega \right)$ and $q^{0,2}=\Delta f(\tilde{e}^0_2).$ As $p(\bar{R}_{i_2})-\omega _{i_2}>\Delta f_{i_2}(\tilde{e}^0_1) \ge \Delta f_{i_2}(\bar{e}) \ge p(R_{i_2})-\omega _{i_2},$ by Lemma 2 $f_{i_2}(\tilde{e}^0_2)=p(R_{i_2})$ (otherwise $f_{i_2}(\tilde{e}^0_2)<p(R_{i_2}),\,\Delta f_{i_2}(\tilde{e}^0_2)\ge \Delta f_{i_2}(\tilde{e}^0_1) \ge p(R_{i_2})-\omega _{i_2},$ and it follows that $f_{i_2}(\tilde{e}^0_2)\ge p(R_{i_2}),$ which is absurd). Also, by weak replacement monotonicity and since $f_{i_2}(\tilde{e}^0_1)\ne p(\bar{R}_{i_2}),$ we have $f_{j}(\tilde{e}^0_1)\le \Delta f_{j}(\tilde{e}^0_2)$ for each $j \ne i_2.$ In particular, for $j=i_1,$ efficiency implies $f_{i_1}(\tilde{e}_0^2)=p(R_{i_1}).$ Notice that, for $j \notin \{i_1,i_2\},$ it is true that $q_j^{0,2}\ge q_j^{0,1}.$ Continuing in the same fashion we obtain a sequence $q^{0,1}, \ldots , q^{0,s^1}$ such that $f_{i_j}(\tilde{e}_k^0)=p(R_{i_j})$ for each $j \le k$ and $q_j^{0,k}\ge q_j^{0,k^{\prime }}$ for each $k^{\prime }<k$ and $j \notin \{i_1, \ldots , i_k\}.$ Notice that $q^{0,i_{s^1}}=q^1.$ Repeating this process for the sets $S^2, \ldots , S^n$ we obtain sequentially $q^2, \ldots ,q^n.$

Now we show that conditions (i)–(v) in the definition of weakly sequential reallocator are satisfied by function $g$. Conditions (i) through (iii) are clear from the previous construction of the sequence $q^t,\,1 \le t \le n$. To see condition (iv), consider $e^{\prime }=(R_i',R_{-i}, \omega _i^{\prime },\omega _{-i}) \in \mathcal {E}^N$ and suppose $p(R_i^{\prime })-\omega _i^{\prime } > q_i^{t-1}$ and $p(R_i)-\omega _i > q_i^{t-1}.$ As $\tilde{e}^{t-1}=\tilde{e}^{\prime {t-1}}$ we have $q^{t-1}=q^{\prime {t-1}},$ where $q^{\prime {t-1}}$ comes from $(q^{\prime {t-1}},e^{\prime })=g^{t-1}(q^{0},e^{\prime }).$ But then, we also have $\tilde{e}^{t}=\tilde{e}^{\prime t}$ and thus $q^{t}=q^{\prime t}.$ To check (v), let $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime },\omega _{-i}) \in \mathcal {E}^N$ be such that $p(R_i^{\prime })-\omega _i^{\prime }<q_i^n<p(R_i)-\omega _i.$ Then by construction $q_i^{\prime n} \le q_i^n$ or, equivalently, $\Delta f_{i}(\tilde{e}^{\prime n})\le \Delta f_{i}(\tilde{e}^n).$ As $q_i^n<p(R_i)-\omega _i,$ it follows that $f_{i}(\tilde{e}^n)\ne p(R_i).$ By weak replacement monotonicity $f_{j}(\tilde{e}^{\prime n})\ge f_{j}(\tilde{e}^n)$ for each $j \ne i$ and then $q^{\prime n_j} \ge q_j^n$ for each $j \ne i.$

It remains to be shown that if $q^n$ comes from $(q^n,e)=g^n(q^0,e)$ then $q^n=\Delta f(e).$ It is sufficient to see that $\Delta f(\tilde{e}^n)= \Delta f(e).$ To do this, let $i \in N {\setminus } S^n$ and consider economy $\hat{e}=\left( R_i,R_{S^n},\bar{R}_{S^n \cup \{i\}}\right) .$ Since $f_i(\tilde{e}^n)\ne p(\bar{R}_i),$ applying Lemma 2 we obtain $\Delta f_i(\tilde{e}^n)=\Delta f_i(\hat{e}).$ Weak replacement monotonicity implies then that $\Delta f_j(\tilde{e}^n)=\Delta f_j(\hat{e})$ for each $j \ne i.$ Thus $\Delta f(\tilde{e}^n)=\Delta f(\hat{e}).$ Repeating this argument for all members of $N {\setminus } S^n$ we get the result.

($\Longrightarrow$) Suppose $f$ is a weakly sequential rule. Then there exists a weakly sequential reallocator $g$ such that, for each $e=(R,\omega ) \in \mathcal {E}^N,$ if $(q^n,e)=g^n(q^0,e)$ then $\Delta f(e)=q^n.$ We will consider only the case $z(e)\ge 0,$ since an analogous argument can be used in the other case. Next we prove that $f$ is efficient, strategy-proof, fulfills the weak dummy property and is weakly replacement monotonic.

Efficiency We need to show that $f_i(e)\le p(R_i)$ for each $i \in N.$ Suppose $f_i(e)\ne p(R_i).$ Then $\omega _i+q_i^n \ne p(R_i)$ and (i) implies $q_i^t <p(R_i)- \omega _i$ for each $t<n.$ Hence, by (ii), $q_i^n<p(R_i)-\omega _i$ and the result follows.

Strategy-proofness Notice that if $f_i(e)=p(R_i)$ agent $i$ has no incentive to manipulate. By efficiency, if $f_i(e) \ne p(R_i)$ it must be $f_i(e)<p(R_i),$ so $q^n < p(R_i)- \omega _i.$ Conditions (i) and (ii) imply $q_i^{t-1}\le q_i^{t}<p(R_i)-\omega _i$ for each $1 \le t \le n.$ By (iii), any manipulation via $(R_i^{\prime },\omega _i^{\prime })$ should be such that $q_i^t>p(R_i^{\prime })-\omega _i^{\prime },$ but then using (i), we would have $p(R_i^{\prime })-\omega _i^{\prime }=q^{t+1}\le q_i^n$ and, in consequence, $f_i(e^{\prime })=p(R_i^{\prime })$ and $\Delta f_i(e^{\prime })= \Delta f_i(e).$

Weak dummy Simply note that, if $i \in N$ is such that $p(R_i)=\omega _i=0,$ by (i) it follows that $q_i^n=p(R_i)-\omega _i,$ so $f_i(e)=p(R_i)=0.$

Weak replacement monotonicity Let be $q^n$ and $\tilde{q}^n$ such that $(q^n,e)=g^n(q^0,e)$ and $(\tilde{q}^n,e^{\prime })=g^n(q^0,e^{\prime }).$ Thus $f(e)=\omega +q^n$ and $f(e^{\prime })=\omega ^{\prime }+\tilde{q}^n.$ Assume, without lost of generality, that $f_i(e)\ne p(R_i)$ (efficiency implies $f_i(e)<p(R_i)$). By Lemma 2, $\Delta f_i(e) \ge \Delta f_i(e^{\prime }).$ We need to show that $f_j(e) \le f_j(e^{\prime })$ for each $j \ne i.$ There are two cases to consider:

Case 1 :

$\varvec{p(R_i^{\prime })-\omega _i^{\prime } \ge q_i^n.}$ As $f_i(e)<p(R_i)$ implies $q_i^n<p(R_i)-\omega _i,$ by (iv) it follows $q^n=\tilde{q}^n$ and hence $f_j(e)=f_j(e^{\prime })$ for each $j \ne i.$

Case 2 :

$\varvec{p(R_i^{\prime })-\omega _i^{\prime } < q_i^n.}$ As $f_i(e)<p(R_i)$ implies $q_i^n<p(R_i)-\omega _i,$ by (v) it follows that $q_j^n \le \tilde{q}_j^n$ for each $j \ne i.$ In consequence, $f_j(e) \le f_j(e^{\prime })$ for each $j \ne i.$

To complete the proof, notice that $f$ satisfies the peak-only property clearly because $g$ does, and that as it also fulfills efficiency, strategy-proofness, weak replacement monotonicity and the weak dummy property, individual rationality comes from Lemma 4 and bribe-proofness is guaranteed by Theorem 1. $\square$

5 The uniform reallocation rule: two further characterizations

Given economy $e=(R,\omega ) \in \mathcal {E}^N$, define the uniform reallocation rule as

$$\begin{aligned} \varvec{u_i(e)}:=\left\{ \begin{array}{l} \min \{p(R_i), \omega _i+\lambda (e)\} \ \ \ \mathrm {if} \ \ z(e) \ge 0 \\ \max \{p(R_i), \omega _i-\lambda (e)\} \ \ \ \mathrm {if} \ \ z(e)\le 0 \end{array} \right. \end{aligned}$$

where $\lambda (e) \ge 0$ and solves $\sum _{j \in N}u_j(e)= \sum _{j \in N}\omega _j$. The uniform reallocation rule is same-sided by definition and in consequence efficient. It works as follows. When $z(e)=0$ each agent receives her peak; if $z(e)>0$ each agent $i \in N$ such that $p(R_i) \le \omega _i$ gets her peak, whereas the other agents either receive their peaks or get an equal (and maximal) net trade. Symmetrically when $z(e)<0.$ Hence, agents are either satiated or receive the same (maximal or minimal) net trade. Actually, we can see the uniform reallocation rule as a weakly sequential rule. Its associated weakly sequential reallocator treats agents symmetrically while they are not able to achieve their peaks, and can be specified adding to condition (ii) in the definition of weakly sequential reallocator the following: “whenever $j, k \in N$ are such that $z(e)(p(R_j)-\omega _j-q_j^{t-1}) > 0$ and $z(e)(p(R_k)-\omega _k-q_k^{t-1}) > 0,$ we have $q_j^t=q_k^{t}.$”

Next, we prove that the uniform reallocation rule is bribe-proof. To do this, we first show that it is a strategy-proof and weakly replacement monotonic rule.

Lemma 8

The uniform reallocation rule is strategy-proof.

Proof

The preference strategy-proofness of this rule is established by Proposition 1 in Klaus et al. (1998). Let us see first that misreporting of endowments is not profitable either. Consider first the case in which $\omega _i^{\prime } \le \omega _i.$ By feasibility and the definition of the rule, if $e^{\prime }=(R,\omega _i^{\prime },\omega _{-i}),$ then $u_j(e^{\prime })\le u_j(e)$ for each $j \in N.$ Feasibility also imposes $\omega _i-\omega _i^{\prime }=\sum _{j \ne i}(u_j(e)-u_j(e^{\prime }))+(u_i(e)-u_i(e^{\prime })).$ Therefore, as $\sum _{j \ne i}(u_j(e)-u_j(e^{\prime }))\ge 0,$ it follows that

$$\begin{aligned} u_i(e)\le u_i(e^{\prime }) + (\omega _i-\omega _i^{\prime }). \end{aligned}$$

(23)

Case 1 :

$\varvec{z(e) \le 0.}$ As $u$ satisfies efficiency, $p(R_i) \le u_i(e).$ Hence, (23) implies $u_i(e)R_i(u_i(e^{\prime })+(\omega _i-\omega _i^{\prime }))$.

Case 2 :

$\varvec{z(e) \ge 0.}$ Assume $u$ is not withholding-proof. Then $(u_i(e^{\prime })+(\omega _i-\omega _i^{\prime }))P_iu_i(e)$ or, using same-sidedness, $u_i(e)-u_i(e^{\prime })<\omega _i-\omega _i^{\prime }$ with $\omega _i^{\prime }<\omega _i.$ It follows, considering the fact that $\omega _i-\omega _i^{\prime }=\sum _{j \in N}(u_j(e)-u_j(e^{\prime })),$ that $\sum _{j \ne i}u_j(e)>\sum _{j \ne i}u_j(e^{\prime }).$ This fact and efficiency imply the existence of an agent $k \in N{\setminus }\{i\}$ such that $u_k(e^{\prime })<u_k(e) \le p(R_k).$ Let $\lambda (e)$ and $\lambda (e^{\prime })$ be the feasibility scalars associated to the definitions of $u(e)$ and $u(e^{\prime }),$ respectively. Then $\omega _k+\lambda (e^{\prime })=u_k(e^{\prime })<u_k(e) \le \omega _k+\lambda (e)$ and consequently $\lambda (e^{\prime })<\lambda (e).$ On the other hand, as $u_i(e^{\prime }) \le u_i(e)<p(R_i),$ using (23) we have $\lambda (e^{\prime }) \ge \lambda (e),$ which is a contradiction.

The proof when $\omega _i^{\prime } \ge \omega _i$ is analogous to the previous one, so we only sketch it. Definition of the rule and feasibility imply

$$\begin{aligned} u_i(e)\ge u_i(e^{\prime }) - (\omega _i^{\prime }-\omega _i). \end{aligned}$$

(24)

When $z(e) \ge 0,$ the result follows from efficiency and (24), whereas in the case $z(e) \le 0$ assuming that the rule is manipulable through borrowing and same-sidedness lead us to $u_i(e^{\prime })-(\omega _i^{\prime }-\omega _i)<u_i(e).$ This implies the existence of an agent $k \in N{\setminus }\{i\}$ such that $u_k(e^{\prime })>u_k(e) \ge p(R_k).$ Thus, we obtain $\lambda (e^{\prime })>\lambda (e)$ which is in contradiction to Eq. (24).

Finally, for each $e=(R,\omega ) \in \mathcal {E}^N,$ $i \in N$ and $(R_i^{\prime }, \omega _i^{\prime }) \in \mathcal {R} \times \mathbb {R}_+,$ if $\overline{e}=(R_i^{\prime },R_{-i},\omega )$ and $e^{\prime }=(R_i',R_{-i},\omega _i^{\prime },\omega _{-i})$ we have, since $u$ is preference strategy-proof, that $u_i(e)R_iu_i(\overline{e}),$ and since $u$ is not manipulable via endowments, that $u_i(\overline{e})R_i(u_i(e^{\prime })+(\omega _i^{\prime }-\omega _i)).$ Therefore, $u_i(e)R_i(u_i(e^{\prime })+(\omega _i^{\prime }-\omega _i))$, and $u$ is strategy-proof. $\square$

Lemma 9

The uniform reallocation rule is weakly replacement monotonic.

Proof

Let $e=(R, \omega ) \in \mathcal {E}^N,\,i \in N,\,(R_i^{\prime }, \omega _i) \in \mathcal {R}\times \mathbb {R}_+$ and $e=(R_i^{\prime },R_{-i},\omega _i^{\prime },\omega _{-i})$ such that $\Delta u_i(e) \le \Delta u_i(e^{\prime }).$ We only consider the case where $z(e)\ge 0,$ since a similar argument holds when $z(e)<0.$ We can distinguish two cases. When $z(e^{\prime })<0,$ by definition of the rule we have, for $j \ne i,$ that $u_j(e)=\min \{p(R_j), \omega _j+\lambda (e)\}\le p(R_j) \le \max \{p(R_j),\omega _j-\lambda (e^{\prime })\}=u_j(e^{\prime }).$ Hence, $u_j(e) \le u_j(e^{\prime })$ for each $j \ne i.$ Suppose there is $k \in N {\setminus } \{i\}$ such that $u_k(e)<u_k(e^{\prime }).$ Then $0=\sum _{j \in N} \Delta u_j(e)<\sum _{j \in N} \Delta u_j(e^{\prime })=0,$ and thus $u_j(e) = u_j(e^{\prime })$ for each $j \ne i.$ On the other hand, if $z(e^{\prime })\ge 0,$ suppose there is $k \in N {\setminus } \{i\}$ such that $u_k(e)<u_k(e^{\prime }).$ Then, if we call $\lambda (e)$ and $\lambda (e^{\prime })$ to the feasibility scalars of the uniform reallocation rule associated with economies $e$ and $e^{\prime },$ respectively, we have $\omega _j+ \lambda (e)=\min \{p(R_j), \omega _j+ \lambda (e)\} < \min \{p(R_j), \omega _j+ \lambda (e^{\prime })\}=\omega _j+ \lambda (e^{\prime })$ and consequently $\lambda (e)<\lambda (e^{\prime }).$ This, in turn, implies that $u_j(e)\le u_j(e^{\prime })$ for each $j\ne i.$ Therefore, $0=\sum _{j \in N}\Delta u_j(e)<\sum _{j \in N}\Delta u_j(e^{\prime })=0,$ an absurd.⁹ $\square$

Theorem 3

The uniform reallocation rule is bribe-proof.

Proof

As the rule satisfies efficiency by definition, is strategy-proof by Lemma 8 and is weakly replacement monotonic by Lemma 9, the result follows after considering Theorem 1. $\square$

Several characterizations of this rule have been presented by Klaus (1997), and Klaus et al. (1997, 1998). Here we present two further characterizations involving the bribe-proof property. For the first characterization, we introduce a notion of fairness in terms of net trades.

No-envy: For each $e=(R, \omega ) \in \mathcal {E}^N$ and $i,j \in N$, $f_i(e)R_i\max \left\{ 0,\left( \omega _i+\Delta f_j(e)\right) \right\} .$

If a rule fulfills no-envy in terms of net trades, no agent strictly prefers the (feasible part of the) net trade of another agent to his own net trade. The properties of bribe-proofness and no-envy characterize the uniform reallocation rule.

Theorem 4

The uniform reallocation rule is the only bribe-proof and no-envy rule.

Proof

The rule is bribe-proof by Theorem 3, whereas no-envy is easy to check. Conversely, let $f$ be a rule satisfying bribe-proofness and no-envy, and assume $f\ne u.$ This implies the existence of an agent $i \in N$ such that $f_i(e)<u_i(e).$ Let $R_i^{\prime } \in \mathcal {R}$ be such that $p(R_i^{\prime })=p(R_i)$ and, if $p(R_i^{\prime })< 2\sum _{j \in N}\omega _j,$ then $(2\sum _{j \in N}\omega _j) P_i^{\prime }f_i(e).$ As bribe-proofness implies efficiency and strategy-proofness, by Lemma 1 $f$ is own peak-only, so if we let $e'=(R_i',R_{-i},\omega )$ we obtain $f_i(e^{\prime })=f_i(e).$ By efficiency and feasibility there is $k \in N$ such that $u_k(e)<f_k(e^{\prime })\le p(R_k).$ As $u_k(e)<p(R_k),$ by the definition of the uniform reallocation rule $\Delta u_k(e) \ge \Delta u_j(e)$ for each $j \in N.$ In consequence, $\Delta f_i(e^{\prime })< \Delta u_i(e) \le \Delta u_k(e) < \Delta f_k(e^{\prime })$ and then $f_i(e^{\prime }) < \omega _i+ \Delta f_k(e^{\prime }).$ Thus $(\omega _i+ \Delta f_k(e^{\prime }))P_i'f_i(e^{\prime }),$ contradicting no-envy. $\square$

For the second characterization we introduce two properties. The first one, states that whenever all agents demand (supply) at economy $e$ as much as they supply (demand) at economy $e',$ then their net trade at $e^{\prime }$ is the reversal of that at $e.$

Reversibility: For each pair of economies $e=(R, \omega )$ and $e^{\prime }=(R',\omega ^{\prime }) \in \mathcal {E}^N$ such that $\omega _i-p(R_i)=-(\omega _i^{\prime }-p(R_i'))$ for each $i \in N,$ we have $\Delta f_i(e)=-\Delta f_i(e^{\prime })$ for each $i \in N.$

The second property requires that, if the difference between the individual endowment and the peak of any two agents are the same, then each one of them should receive the same net trade.

Equal-treatment: For each $e=(R, \omega ) \in \mathcal {E}^N$ and $i,j \in N$ such that $\omega _i-p(R_i)=\omega _j-p(R_j),$ we have $\Delta f_i(e)= \Delta f_j(e).$

Both of this properties are presented in Klaus et al. (1997) and are used to obtain characterizations of the uniform reallocation rule. Our second characterization of this rule states that it is the only bribe-proof rule that in addition is reversible and equally-treating.

Theorem 5

The uniform reallocation rule is the only rule that satisfies bribe-proofness, reversibility and equal-treatment.

Proof

This is a straightforward consequence of Theorem 6.4 in Klaus et al. (1997) which states, in our terminology, that the uniform reallocation rule is the only rule fulfilling efficiency, withholding-proofness, reversibility and equal-treatment. In fact, Theorem 6.4 in Klaus et al. (1997) implies that the uniform reallocation rule satisfies reversibility and equal-treatment, and bribe-proofness of the rule follows from Theorem 3. Conversely, let $f$ satisfy bribe-proofness, reversibility and equal-treatment. By Remark 2, $f$ fulfills efficiency and strategy-proofness, and hence withholding-proofness as well. Applying Theorem 6.4 in Klaus et al. (1997) we obtain the desired result. $\square$

In order to analyze the independence of properties in Theorems 4 and 5, consider the following examples:

Example 3

For each $e=(R,\omega ) \in \mathcal {E}^N,$ define the endowment rule by $\varvec{f^\omega _i(e)}:=\omega _i$ for each $i \in N.$ This rule is easily seen to satisfy no-envy, reversibility and equal-treatment, yet it is not bribe-proof. To see this, let $e=(R,\omega ) \in \mathcal {E}^N$ with agents $i,k \in N$ such that $p(R_i)=0$ and $p(R_k)=\sum _{j \in N}\omega _j.$ Let $S=\{i,j\},$ $V=\{i\},$ $(R_i^{\prime },\omega _i^{\prime })=(R_i,\omega _i),$ $\ell _i=0$ and $\ell _j=\omega _i+\omega _j.$ Then $f^\omega$ is not bribe-proof.

Example 4

The hierarchical rule $f^h$ introduced in Example 2 is bribe-proof and reversible, but it satisfies neither no-envy nor equal-treatment. To verify this, consider $e=(R, \omega ) \in \mathcal {E}^{\{1,2,3\}}$ such that $p(R)=(0,4,4)$ and $\omega =(2,1,1).$ It follows that $f^h(e)=(0,3,1)$ and, in consequence, agent 3 envies agent 2, and both are treated unequally.

Example 5

The modified maximally satiating rule $\varvec{f^m},$ in case of excess demand, satiates as many agents as possible; and in case of excess supply equals the uniform reallocation rule. Given $e=(R,\omega ) \in \mathcal {E}^N,$ let $\mathcal {D}(e):=\{j \in N : \omega _j < p(R_j)\}$ and $s(e):=\sum _{j \notin \mathcal {D}(e)}(\omega _j-p(R_j))$. Without loss of generality, assume $\mathcal {D}(e)=\{1,\ldots ,k\}$ is such that $p(R_1)-\omega _1=\ldots =p(R_{t_1})-\omega _{t_1}<p(R_{t_1+1})-\omega _{t_1+1}=\ldots =$ $p(R_{t_2})-\omega _{t_{2}}<\ldots <p(R_{t_r})-\omega _{t_r}=\ldots =p(R_k)-\omega _k.$ If $z(e)\ge 0$ then

$$\begin{aligned} f_i^m(e):=\left\{ \begin{array}{l} p(R_i) \ \ \ \ \ \mathrm {if} \ i \in \mathcal {S}(e) \\ \min \{ p(R_i), \omega _i+ \frac{1}{t_s-t_{s-1}}(s(e)-\sum _{j \in \mathcal {D}(e),j\le t_{s}-1}\varDelta f_j^m(e))\} \quad \mathrm {otherwise,}\end{array} \right. \end{aligned}$$

for $t_{s-1}<i\le t_s,$ and if $z(e)< 0,$ then $f^m(e)=u(e).$ This rule is bribe-proof and satisfies equal-treatment but not reversibility. To check this, consider $e=(R,\omega )$ and $e^{\prime }=(R',\omega ^{\prime }) \in \mathcal {E}^{\{1,2,3,4\}}$ such that $p(R)=\omega ^{\prime }=(0,5,6,10)$ and $p(R^{\prime })=\omega =(9,1,2,3).$ It follows that $f^m(e)=(0,5,6,4),$ $f^m(e^{\prime })=(9,2,3,7)$ and thus $\Delta f^m(e)=(-9,4,4,1)$ and $\Delta f^m(e^{\prime })=(9,-3,-3,-3).$

6 Concluding comments

Before finishing the paper some final comments are in order. To begin with, we could try to change our definition of bribe-proofness to one closer to Schummer’s definition, in which only two-agent coalitions (one briber and one bribed agent) are involved in a bribe. If we do so, then the family of bribe-proof rules would considerably increase allowing for rules lacking the weak replacement monotonicity property. To see this point, consider the following example:¹⁰

Example 6

Let $e=(R, \omega ) \in \mathcal {E}^{\{1,2,3,4\}}$ and let $f$ be a rule such that $f_1(e)<p(R_1).$ Let also $(R_1', \omega _1^{\prime }) \in \mathcal {R} \times \mathbb {R}_+$ be such that $p(R_1^{\prime })-\omega _1^{\prime }=\Delta f_1(e)-\varepsilon$ for $\varepsilon <p(R_1)-f_1(e),$ and consider economy $e^{\prime }=(R_1',R_{-1}, \omega _1^{\prime }, \omega _ {-1}).$ Assume $f_1(e^{\prime })=p(R_1')$ and $f_i(e^{\prime })=f_i(e)+\frac{3}{4 }\varepsilon <p(R_i)$ for $i=2,3.$ As $f_4(e^{\prime })=f_4(e)-\frac{1}{2}\varepsilon ,$ $f$ is not weakly replacement monotonic. It is not bribe-proof either, because a bribe can be constructed by taking $S=\{1,2,3\},$ $V=\{1\}$ and $\ell _i=f_i(e)+\frac{1}{6}\varepsilon$ for $i \in S.$ Nevertheless, $f$ is bribe-proof in Schummer’s sense, since no agent alone can compensate agent 1 loss of $\varepsilon .$

Second, we could specify an economy not only with agents’ preferences and endowments but considering also an amount that represents net trades with the outside world. Formally, given the set of agents $N,$ a mixed ownership economy ¹¹ consists of a profile of preferences $R \in \mathcal {R}^N$, an initial endowment vector $\omega \in \mathbb {R}^N_+$ and an (outside) obligation $T \in \mathbb {R}$ with $\sum _{j \in N}\omega _j+T \ge 0,$ and is denoted by $e=(R,\omega ,T)$. Let $\mathcal {ME}^N$ be the domain of mixed ownership economies with agents in $N$. In this context, a rule associates to each $e=(R,\omega ,T) \in \mathcal {ME}^N$ an element of $X(e):=\{x=(x_1,\ldots , x_n) \in \mathbb {R}^N_+ : \sum _{j\in N}x_j=\sum _{j \in N}\omega _j+T\}$. These economies have been studied, among others, by Thomson (1995) and Herrero (2002) and provide a good framework, for example, to extend the property of consistency ¹² to models with individual endowments (see Thomson (2010, 2011), section 5.2). However, manipulation via endowments in this extended environment seems pervasive: not even the natural generalization of the uniform reallocation rule is immune to such strategic behavior (although it continues to be preference strategy-proof, see Thomson (1995)), and therefore it no longer fulfills bribe-proofness either. We show a manipulation through the following example:

Example 7

Consider $e=(R,\omega ,T) \in \mathcal {ME}^{\{1,2\}}$ with $p(R)=(2,3),$ $\omega =(1,2),$ and $T=-1.$ Then $u(e)=(0.5,1.5).$ Now take $\omega ^{\prime }_1=0$, and let $e^{\prime }=(R,\omega _1^{\prime },\omega _2,T)$ $\in \mathcal {ME}^{\{1,2\}}$. It follows that $u(e^{\prime })=(0,1)$ and $1=(u_1(e^{\prime })+(\omega _1-\omega _1^{\prime }))P_1u_1(e)=0.5,$ so $u$ is not withholding-proof.

In the third place, in Postlewaite (1979) the following sort of manipulation through resources is also considered: it could be possible that a group of agents, by trading their endowments “outside the market structure” before the rule is applied, end up in a better situation after the rule performs its reallocation. Formally, given $e=(R,\omega ) \in \mathcal {E}^N,$ there are $S \subset N$ and $\omega ^{\prime }_S \in \mathbb {R}_+^S$ such that $\sum _{j \in S}\omega _j^{\prime } =\sum _{j \in S}\omega _j$ and, if $e^{\prime }=(R,\omega _S^{\prime }, \omega _{-S}),\,\,f_j(e^{\prime })P_jf_j(e)$ for each $j \in S.$ It is easy to see that if a rule is bribe-proof this kind of manipulation is forbidden as well. Another type of manipulation also introduced by Postlewaite (1979) might arise when an agent destroys (part of) her endowment in order to improve her situation. Formally, for each $e=(R,\omega ) \in \mathcal {E}^N,\,i \in N$ and $\omega _i^{\prime } \in \mathbb {R}_+$ such that $\omega _i^{\prime } \le \omega _i,$ if $e^{\prime }=(R,\omega _i^{\prime }, \omega _{-i})$ then $f_i(e^{\prime })P_if_i(e).$ It is easy to prove that any individually rational rule can be manipulated in such a fashion. In fact, any agent with an endowment bigger than her peak could always get her peak by first destroying the excess and then invoking individual rationality.

Finally, an important feature of the uniform reallocation rule is that admits a walrasian interpretation. Indeed, it is a special case of a solution concept introduced, among others, by Mas-Colell (1992) to deal with possibly satiated preferences in the general equilibrium model. Given $e=(R,\omega ) \in \mathcal {E}^N,$ a walrasian equilibrium with slack is a triplet $(x, q, \mu ) \in X(e) \times \{-1, 0, 1\} \times \mathbb {R}_+$ such that, for each $i \in N$, allocation $x_i$ maximizes $R_i$ in the budget set $\{y_i \in \mathbb {R}_+ : q y_i \le q \omega _i+ \mu \}.$ It is straightforward to see that the allocation associated with the walrasian equilibrium with slack of an economy in our model is no other than the uniform reallocation of that economy. Therefore, by Theorem 3 we obtained a (rather restricted) domain of preferences where a walrasian-like mechanism satisfies several interesting properties of immunity to manipulation via both preferences and endowments. Identifying such domain restrictions is pointed out by Thomson (2008) as an interesting avenue of research.