Linking the Kar and folk solutions through a problem separation property

Minimum cost spanning tree problems connect agents efficiently to a source with the cost of using an edge fixed. We revisit the dispute between the Kar and folk solutions, two solution concepts to divide the common cost of connection based on the Shapley value. We introduce a property called Weak Problem Separation that allows, under conditions, to divide the problem in two: connecting an agent to the source and connecting agents to each other. It allows us to characterize the set of all affine combinations of the Kar and folk solutions.

1. It would be possible to divide a problem \((N,c)\) in its source connection problem and in a minimum cost spanning tree problem without a source, where we need to connect all players together. While this would eliminate the need to define \(\dot{c},\) the current format has the advantage that \(c,\;\hat{c} , \;\tilde{c}\) and \(\dot{c}\) are all MCST problems with a source as defined in Sect. 2.

2. If \(y\) satisfies Anonymity, then \(y_{i}(N,\dot{c})=\frac{1}{\left| N\right| }\max _{e\in N_{0}^{P}}c_{e}\) for all \(i\in N.\) The extra cost we added in the agent connection problem is split evenly among agents.

3. In their study of Monotonicity and Ranking properties, Bogomolnaia and Moulin (2010) use a stronger but similar restriction. They apply their properties to the set of cost matrices such that for all \(i,j\in N,\; c_{ij}\le \min _{k\in N}c_{0k}.\) That is, they suppose that all connection costs between agents are smaller than all connection costs to the source.

4. Weak Problem Separation is implied by Restricted Addivity, a property used in Bergantinos and Vidal-Puga (2009), among others. See Lemma 2 for details. Thanks to an anonymous referee for pointing this out.

5. If \(i\in R(c),\) the incremental cost of agent \(i\) is \(1\) when he joins the empty set, and \(0\) otherwise. Therefore, \(y_{i}^{k}=\frac{1}{\left| N\right| }.\) If \(i\notin R(c),\) his incremental cost is \(-1\) if he joins a group of players that are all in \(R(c)\) and \(0\) otherwise. If \(R(c)\ne N,\) then the irreducible matrix is such that \(c_{e}^{*}=0\) for all \(e\) and thus \(y_{i}^{f}=0\). If \(R(c)=N,\) then \(c^{*}=c\) and \(y_{i}^{f}=\frac{1}{ \left| N\right| }.\)

6. Agent \(i\) has a marginal contribution of \(1\) if he joins a coalition that does not include any member of \(Z^{i}.\) The probability of such an event is \( \frac{1}{\left| Z^{i}\right| +1}.\) His marginal contribution is \( -(k-1)\) when he joins a coalition that contains \(k\) agents in \(Z^{i}\) (as these agents cannot have a free link between them, as we have no cycles). Thus, \(y_{i}^{k}=\frac{1}{\left| Z^{i}\right| +1}-\sum _{k=2}^{\left| Z^{i}\right| }\frac{\left| Z^{i}\right| (k-1)}{(\left| Z^{i}\right| -k)!k!}\left( \sum _{l=0}^{\left| N\right| -\left| Z^{i}\right| -1}\frac{(\left| N\right| -\left| Z^{i}\right| -1)!}{l!(\left| N\right| -\left| Z^{i}\right| -1-l)!}\frac{(l+k)!(\left| N\right| -k-l-1)!}{ \left| N\right| !}\right) ,\) which simplifies to \(1-\frac{\left| Z^{i}\right| }{2}.\) As for the folk solution, the irreducible matrix is \( \tilde{c}_{jk}^{*}=0\) for any \(j,k\in N.\) Therefore, \(y_{i}^{f}=\frac{1}{ \left| N\right| }\).

7. I would like to ackowledge the contribution of an anonymous referee, who found and corrected a flaw in this part of the proof.

8. We can also replace Core Selection by Population Monotonicity, given that the former is implied by the latter and that the folk solution satisfies both (Bergantinos and Vidal-Puga 2007a). Population Monotonicity requires that no agent be made worse off when agents join the coalition.

Special thanks to an anonymous referee who went the extra mile to improve the proof of the main theorem. I also thank Hervé Moulin and Yuntong Wang for useful comments. Financial support from the Social Sciences and Humanities Research Council of Canada (SSHRC) is gratefully acknowledged.

Authors and Affiliations

1. Department of Economics, University of Windsor, Windsor, ON, Canada

   Christian Trudeau

Corresponding author

Correspondence to Christian Trudeau.

Appendix

Lemma 2

All \(y\in Y\) as defined in Theorem 1 satisfy Weak Problem Separation, Group Independence, Piecewise Linearity, Anonymity, Weak Equal Treatment and Independence of Irrelevant Edges.

Proof

Notice that the weight on the Kar solution is \(2a\) while the weight on the folk solution is \(1-2a.\) Let \(\theta =2a\) and rewrite the family of solutions as \(\theta y^{k}+(1-\theta )y^{f}.\) The family of solutions is a weighted sum of the Kar and folk solutions, with the weights summing to one, but the weights being possibly negative. Since both solutions are budget balanced and the weights sum to one, all of the solutions of Theorem are also budget balanced.

Since the Kar and folk solutions are part of the family, we first show that they satisfy all properties. This result then trivially extends to solutions \(y=2a(y^{k}-y^{f})+y^{f},\) the weighted sums of these two solutions.

We start with the Kar solution. Symmetry is proven in Bergantinos and Vidal-Puga (2007a); Anonymity carries over easily. Group Independence is proven in Kar (2002) (the proof easily extends when we remove strict inequality). Piecewise Linearity is proven in Bogomolnaia and Moulin (2010).

We show that the Kar solution satisfies the stronger property of Problem Separation: By Lemma 1, \(C(S,c)=C(S,\hat{c})+C(S,\tilde{c} )-C(S,\dot{c}).\) By the properties of the Shapley value, \(y^{k}(N,c)=y^{k}(N, \hat{c})+y^{k}(N,\tilde{c})-y^{k}(N,\dot{c}).\)

Weak Equal Treatment: It is implied by Equal Treatment (Kar (2002)).

Independence of Irrelevant Edges: Clearly, \(C(S,c)=C(S,\bar{c})\) for all \( S\subseteq N.\) Therefore, \(y^{k}(N,c)=y^{k}(N,\bar{c}).\)

Next, we show that the folk solution satisfies all of these properties.

Bergantinos and Vidal-Puga (2007a) show that it satisfies Symmetry; Anonymity carries over easily. They also show that it satisfies Reductionism \((y(N,c)=y(N,c^{*}))\) and Separability, which says that if \( C(S,c)+C(N\backslash S,c)=C(N,c),\) then \(y_{i}(N,c)=y_{i}(S,c^{S})\) if \(i\in S.\)

Reductionism clearly implies Independence of Irrelevant Edges, as the irreducible edges cannot have any impact on the irreducible matrix. It also clearly implies Weal Equal Treatment.

Separability is clearly a stronger property than Group Independence.

Bergantinos and Vidal-Puga (2009) show that it satisfies Restricted Additivity, which says that if \(c,c^{\prime }\) have an MCST \(t^{*}\) in common and that the edges of that \(t^{*}\) have a common order of its edges from cheapest to most expensive, then \(y(N,c+c^{\prime })=y(N,c)+y(N,c^{\prime }).\) It clearly implies Piecewise Linearity. It also implies Weak Problem Separation. To see this, notice that \(c+\dot{c}=\tilde{c }+\hat{c}\) and that under the assumption that \(c\in \bar{\varGamma }(N),\) if \( c_{e}\le \min _{i\in N}c_{0i}\) for all \(e\in t^{*}(c),\) all \(t^{*}\in T^{*}(c),\) they all have a common MCST \(t\) that has a common order of its edges from cheapest to most expensive. Then, Restricted Additivity implies that \(y^{f}(N,c)+y^{f}(N,\dot{c})=y^{f}(N,\hat{c})+y^{f}(N,\tilde{c} ).\)

It is easy to show that Weak Problem Separation, Group Independence, Piecewise Linearity, Anonymity, Weak Equal Treatment and Independence of Irrelevant Edges extend to any solution \(y^{a}=2a(y^{k}-y^{f})+y^{f}\) since they are satisfied by both \(y^{k}\) and \(y^{f}\). \(\square \)

Lemma 3

The six properties of Theorem 1 are independent.

Proof

Since \(N\) is fixed throughout, we define a solution as \(y(c)\) instead of \( y(N,c).\)

1. i)

   Weak Problem Separation: Define \(c^{1}\) as follows: for each \(i\in N,\) look at cycles that go through \(0\) and \(i.\) Let \(F_{0i}\) be the set of all such cycles. Let \(c_{0i}^{1}=\min \left\{ c_{0i},\min _{f\in F_{0i}}\max _{e\in f}c_{e}\right\} \) and \(y^{i}(c)=Sh\left( C(\cdot ,c^{1}\right) ).\)

   It clearly satisfies Piecewise Linearity, Weak Equal Treatment, Anonymity, Group Independence and Independence of Irrelevant Edges. It fails Weak Problem Separation. To see this, consider a 3-player example such that \( c_{03}=c_{23}=1\) and \(c_{e}=0\) else. We have that \(c^{1}=c,\) yielding \( y^{i}(c)=(-\frac{1}{2},0,\frac{1}{2}).\) Now, divide the problem in its source connection and agent connection problems. We have that \(\hat{c} _{03}^{1}=0\) while \(\hat{c}_{03}=1\) and \(\tilde{c}=\tilde{c}^{1}.\) Therefore, we have \(y^{i}(\hat{c})=(0,0,0)\) and \(y^{i}(\tilde{c})=(0,\frac{1 }{2},\frac{1}{2}).\) Thus, \(y^{i}(c)\ne y^{i}(\hat{c})+y^{i}(\tilde{c} )-\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) .\)

2. ii)

   Group Independence. Let \(y_{j}^{ii}(c)=\frac{C(N,c)}{n}\) for all \(j\in N. \) It is easy to see that it satisfies Piecewise Linearity, Weal Equal Treatment, Anonymity, Independence of Irrelevant Edges and Weak Problem Separation. Suppose a two-player example where \(c_{01}=3,\) \(c_{02}=c_{12}=5.\) By Group Independence, we should have \(y=(3,5)\) but \(y^{ii}=(4,4).\)

3. iii)

   Piecewise Linearity. Let \(\gamma (c)\) be the cost of the most expensive edge in an MCST of \(c.\) If we order edges from cheapest to most expensive, then rank \(K^{\gamma }\) is such that \(c_{e}\le \gamma (c)\) if the rank of \( e \) is below \(K^{\gamma }\) and \(c_{e}>\gamma (c)\) if the rank of \(e\) is above \(K^{\gamma }.\) Let \(y^{iii}(c)=\left\{ \begin{array}{c} y^{k}(c)\text { if }c_{e}\le \min _{i\in N}c_{0i}\text { for all }e\in t^{*}(c),\text { all }t^{*}\in T^{*}(c) \\ \sum _{k=1}^{K^{\gamma }}\left( c_{e^{\sigma (k)}-}c_{e^{\sigma (k-1)}}\right) y^{k}(b^{k})\text { else} \end{array} \right\} .\) It clearly fails Piecewise Linearity, as between ranks \( K^{\gamma }\) and \(q,\) \(y^{k}(b^{k})\) is typically not equal to \((0,0,\ldots ,0).\) It satisfies Weak Equal Treatment as the Kar solution satisfies it (for the first segment). In the second segment, if an eligible edge is such that its cost is above \(\gamma (c)\), a reduction in cost won’t have any effect. Anonymity, Group Independence and Independence of Irrelevant Edges are clearly satisfied. Weak Problem Separation only applies in the first part, where it is satisfied by the Kar solution.

4. iv)

   Anonymity. Order agents randomly and let \(y_{1}^{iv}(c)=C(\left\{ 1\right\} ,c^{*})\) and \(y_{j}^{iv}(c)=C(\left\{ 1,\ldots ,j\right\} ,c^{*})-C(\left\{ 1,\ldots ,j-1\right\} ,c^{*})\) for all \(j=2,\ldots ,n.\) It is easy to see that it satisfies Piecewise Linearity, Weak Problem Separation, Group Independence and Independence of Irrelevant Edges. It satisfies Weak Equal Treatment because edges on which it applies do not affect the irreducible cost matrix. Suppose that \(c_{01}=c_{02}=3\), \(c_{12}=1\) and \(c_{1j}=c_{2j}\) else\(.\) Then, \(y_{1}^{iv}=3\) and \(y_{2}^{iv}=1.\) It fails Anonymity.

5. v)

   Weak Equal Treatment. For any \(c\in \hat{\varGamma }^{e}\) and \(c\in \tilde{ \varGamma }^{e}\backslash \tilde{\varGamma }_{P^{*}}^{e},\) let \( y^{v}(c)=y^{k}(c).\) For \(c\in \tilde{\varGamma }_{P^{*}}^{e},\) let \( y^{v}(c)=y^{f}(c).\) Through Piecewise Linearity, Independence of Irrelevant Edges and Weak Problem Separation, extend the definition of \(y^{v}\) to any \( c\in \varGamma .\) By definition, Piecewise Linearity, Independence of Irrelevant Edges and Weak Problem Separation are satisfied. Since both the Kar and the folk solutions satisfy Anonymity and Group Independence, so does \(y^{v}.\) It clearly fails Weak Equal Treatment: Suppose that we start from \( c\in \tilde{\varGamma }^{e}\backslash \tilde{\varGamma }_{P^{*}}^{e},\) and that changing the cost of \(c_{ij}\) from \(1\) to \(0\) creates a free cycle, we obtain a cost matrix in \(\tilde{\varGamma }_{P^{*}}^{e}\). Going from the folk to the Kar solution will typically affect agents \(i\) and \(j\) differently.

6. vi)

   Independence of Irrelevant Edges: We define \(y^{vi}\) as follows on elementary matrices. For \(c\in \bar{\varGamma }^{e},\) we have that \( y^{vi}(c)=y^{k}(c).\) Take \(c\in \bar{\varGamma }^{e}\) such that \( c_{0i}=c_{0j}=c_{ij}=0.\) Let \(c^{\prime }\) be such that \(c_{ij}^{\prime }=1\) and \(c_{e}^{\prime }=c_{e}\) else. Let \(N_{i}(c)\) be the set of players to which \(i\) can connect freely to without going through the source. Define \( y^{vi}(c^{\prime })\) as follows:

   $$\begin{aligned} y_{l}^{vi}(c^{\prime })=\left\{ \begin{array}{c} y_{l}^{vi}(c)+b\quad \text {for}\quad l=i,j,\quad \text {with}\quad b>0 \\ y_{l}^{vi}(c)-\frac{2b}{\left| N_{i}(c)\right| }\quad \text {for}\quad l\in N_{i}^{*}(c)\backslash \left\{ i,j\right\} \\ y_{l}^{vi}(c)\quad \text {else} \end{array} \right. . \end{aligned}$$

   Having defined all cost shares for elementary matrices with one irrelevant edge in this manner, we proceed in the same manner for all elementary matrices with 2 irrelevant edges, then recursively for any number of irrelevant edges. We then extend to any \(c\in \varGamma \) through Piecewise Linearity.

By definition, \(y^{vi}\) satisfies Piecewise Linearity. It is easy to see that it satisfies Anonymity and Weak Equal Treatment. Since Weak Problem Separation applies only to matrices without irrelevant edges, only its properties on \(\bar{\varGamma }^{e}\) matter. Since it is equal to the Kar solution for those matrices, Weak Problem Separation is satisfied. Group Independence is satisfied since the difference between \(y_{l}^{vi}(c^{\prime })\) and \(y_{l}^{vi}(c)\) depends if you are freely connected to \(i\) and \(j\) or not. It is easy to see that Independence of Irrelevant Edges is not satisfied. \(\square \)

The following table summarizes the results of the previous two lemmas, with “+” meaning that the property is satisfied and “\(-\)” that it is not.

Satisfaction of the properties characterizing \(Y\) by the folk and Kar solutions as well as solutions defined in Lemma 3.

Lemma 4

1. i)

   The folk solution satisfies Core Selection but it does not satisfy Problem Separation.

2. ii)

   The Kar solution satisfies Problem Separation but it does not satisfy Core Selection.

Proof

i) Bergantinos and Vidal-Puga (2007a) show that the folk solution satisfies Core Selection.

Take \(c\in \bar{\varGamma }^{e}\) such that \(c_{0i}=c_{0j}=c_{ij}=0\) and \(c_{e}=1\) else. We have \(y_{l}^{f}(N,c)=0\) if \(l=\left\{ i,j\right\} \) and \(1\) else. Also, we have \(y_{l}^{f}(N,\hat{c})=0\) for all \(l\in N\) and \(y_{l}^{f}(N, \tilde{c})=\frac{1}{2}\) if \(l=\left\{ i,j\right\} \) and \(1\) else\(.\) Therefore, \(y_{l}^{f}(N,\hat{c})+y_{l}^{f}(N,\tilde{c})-\frac{1}{\left| N\right| }\ne y_{l}^{f}(N,c).\) Problem Separation is not satisfied.

ii) Problem Separation was proved in Lemma 2.

Consider the problem \(c\) such that \(c_{jk}=0\) for all \(j,k\in N\), \(c_{0j}=0\) for all \(j\in N\backslash \left\{ i\right\} \) and \(c_{0i}=1,\) with \( \left| N\right| >2.\) Then, \(y_{i}^{k}(N,c)=\frac{1}{\left| N\right| }\) and \(y_{j}^{k}(N,c)=-\frac{1}{\left| N\right| (\left| N\right| -1)}\) for all \(j\in N\backslash \left\{ i\right\} .\) We have \(C(S,c)=0\) for all \(S\ne \left\{ i\right\} .\) Take \(l\in N\backslash \left\{ i\right\} .\) We obtain \(y_{i}(N,c)+y_{l}(N,c)=\frac{ (\left| N\right| -2)}{\left| N\right| (\left| N\right| -1)}>0.\) The Kar solution fails to satisfy Core Selection.\(\square \)

Lemma 5

Suppose that \(y^{a}(N,c)=2ay^{k}(N,c)+(1-2a)y^{f}(N,c)\) with \(a\in \mathbb {R}.\) We have that:

1. i)

   \(y^{a}(N,c)\) satisfies Individual Rationality if and only if \(a\in \left[ 0,1\right] .\)

2. ii)

   \(y^{a}(N,c)\) satisfies Strict Cost Monotonicity if and only if \(a>0.\)

3. iii)

   \(y^{a}(N,c)\) satisfies Strict Ranking if and only if \(a>0.\)

Proof

i) Example 1 shows that Individual Rationality is not satisfied if \(a<0\) or \( a>1.\) We show that \(a\in \left[ 0,1\right] \) is a sufficient condition for Individual Rationality.

For \(a\in \left[ 0,\frac{1}{2}\right] ,\) \(y^{a}\) is a convex combination of the Kar and folk solutions, who both satisfy Individual Rationality, \(y^{a}\) also satisfies it.

For \(a\in \left[ \frac{1}{2},1\right] ,\) we have that \( y^{a}(N,c)=y^{k}(N,c)+b\left( y^{k}(N,c)-y^{f}(N,c)\right) \) with \( b=2a-1\ge 0.\)

For any \(c\in \varGamma ^{e},\) if \(c_{0i}=0,\) we have that \(y_{i}^{f}(N,c)=0\) (since it satisfies Individual Rationality and Non-Negativity) while \( y_{i}^{k}(N,c)\le 0\) (by Individual Rationality). Therefore, \( y^{k}(N,c)-y^{f}(N,c)\le 0\), which implies that \(y_{i}^{a}(N,c)\le 0=c_{0i} \) for any \(a\in \left[ \frac{1}{2},1\right] .\)

Suppose that \(c_{0i}=1\) and \(Z_{i}(c)=\emptyset .\) Then it is easy to see that \(y_{i}^{k}(N,c)=y_{i}^{f}(N,c)=1,\) as agent \(i\) has no free path connecting him to anybody else. Thus, \(y_{i}^{a}(N,c)=1=c_{0i}.\)

Suppose that \(c_{0i}=1\) and \(j\in Z_{i}(c).\) Then, we have that \( y_{i}^{k}(N,c)\le \frac{1}{2}.\) To see this notice that when agent \(i\) comes in after agent \(j,\) his incremental cost is zero, as he can connect freely to agent \(j.\) There is a probability \(\frac{1}{2}\) that he comes in after agent \(j.\) Any other incremental cost cannot be larger than 1. We thus have that \(y_{i}^{a}(N,c)\le \frac{1}{2}+b\left( \frac{1}{2} -y_{i}^{f}(N,c)\right) .\) By the Non-Negativity of the folk solution, we have that \(y_{i}^{a}(N,c)\le \frac{1}{2}+\frac{b}{2}.\) For any \(b\le 1,\) we have \(y_{i}^{a}(N,c)\le 1=c_{0i}.\) We have that \(b\le 1\) if and only if \(a\le 1.\)

Therefore, Individual Rationality is satisfied for all \(c\in \varGamma ^{e}\) if \(a\in \left[ 0,1\right] .\)

For \(c\in \varGamma ,\) we can apply Piecewise Linearity. We have \( y_{i}^{a}(N,c)=\sum _{k=1}^{q}\left( c_{e^{\sigma (k)}}-c_{e^{\sigma (k-1)}}\right) y_{i}^{a}(N,b^{k})\) with all \(b^{k}\in \varGamma ^{e}\). Therefore, \(y_{i}^{a}(N,b^{k})\le b_{0i}^{k}\) for all \(k.\) Since \( c_{0i}=\sum _{k=1}^{q}\left( c_{e^{\sigma (k)}}-c_{e^{\sigma (k-1)}}\right) b_{0i}^{k}\) and all the weights are positive, we have \(y_{i}^{a}(N,c)\le c_{0i}.\) Individual Rationality is satisfied for all \(c\in \varGamma \) if \(a\in \left[ 0,1\right] .\)

ii) Suppose that \(c_{ij}\le \max \left\{ c_{0i},c_{0j}\right\} \) and \( c,c^{\prime }\) such that \(c_{ij}^{\prime }<c_{ij}\) and \(c_{e}^{\prime }=c_{e} \) else.

Define \(\varDelta y_{l}^{k}=y_{l}^{k}(N,c)-y_{l}^{k}(N,c^{\prime })\) and \( \varDelta y_{l}^{f}=y_{l}^{f}(N,c)-y_{l}^{f}(N,c^{\prime }).\) By the properties of the Kar and folk solutions, \(\varDelta y_{l}^{k}>0\) and \(\varDelta y_{l}^{f}\ge 0\) for \(l\in \left\{ i,j\right\} .\) We have Strict Cost Monotonicity if \(2a\varDelta y_{l}^{k}+(1-2a)\varDelta y_{l}^{f}>0\) for \(l\in \left\{ i,j\right\} .\)

For the following, suppose that \(l\in \left\{ i,j\right\} .\) Suppose that \( \varDelta y_{l}^{f}=0\) (which happens when \(c_{ij}^{\prime }\ge \bar{c}_{ij}).\) We have \(2a\varDelta y_{l}^{k}>0\) if and only if \(a>0\).

We need to show that \(2a\varDelta y_{l}^{k}+(1-2a)\varDelta y_{l}^{f}>0\) when \( \varDelta y_{l}^{f}>0.\) If \(0<a\le \frac{1}{2},\) we have \(2a>0\) and \(1-2a\ge 0.\) Combined with \(\varDelta y_{l}^{k}>0\) and \(\varDelta y_{l}^{f}\ge 0,\) it assures that \(2a\varDelta y_{l}^{k}+(1-2a)\varDelta y_{l}^{f}>0.\)

We have that \(\varDelta y_{l}^{k}\ge \varDelta y_{l}^{f}.\) To see this, notice that the reduction of the cost on \((i,j)\) reduces \(C(S,c)\) for all coalitions \(S\supseteq \left\{ i,j\right\} \) that uses that edge. The reduction of the cost on \((i,j)\), if it modifies the irreducible matrix, will change the value of \(\bar{c}_{ij}\) but potentially of some other edge \( \bar{c}_{e},\) meaning that \(\bar{C}(S,c)\) can decrease for some \( S\varsupsetneq \left\{ i,j\right\} .\) Therefore, if \(a>\frac{1}{2},\) we have \(2a\varDelta y_{l}^{k}+(1-2a)\varDelta y_{l}^{f}\ge 2a\varDelta y_{l}^{k}+(1-2a)\varDelta y_{l}^{k}=\varDelta y_{l}^{k}>0.\)

Therefore, Strict Cost Monotonicity is satisfied if and only if \(a>0.\)

iii) Suppose that \(c_{ik}\le c_{jk}\) for all \(k\in N_{0}\backslash \left\{ i,j\right\} \) and \(c_{il}<c_{jl}\) for some \(l\in N_{0}\backslash \left\{ i,j\right\} ,\) with \(c_{il}<\max \left\{ c_{0i},c_{0l}\right\} .\)

Define \(\varDelta y_{ij}^{k}=y_{j}^{k}-y_{i}^{k}\) and \(\varDelta y_{ij}^{f}=y_{j}^{f}-y_{i}^{f}.\) By the properties of the Kar and folk solutions, \(\varDelta y_{ij}^{k}>0\) and \(\varDelta y_{ij}^{f}\ge 0.\) We have Strict Ranking if \(2a\varDelta y_{ij}^{k}+(1-2a)\varDelta y_{ij}^{f}>0.\) Suppose that \(\varDelta y_{ij}^{f}=0\) (which happens when \(\bar{c}_{il}=\bar{c}_{jl}\)). We have \(2a\varDelta y_{ij}^{k}>0\) if and only if \(a>0\).

We need to show that \(2a\varDelta y_{ij}^{k}+(1-2a)\varDelta y_{ij}^{f}>0\) when \( \varDelta y_{ij}^{f}>0.\) If \(0<a\le \frac{1}{2},\) we have \(2a>0\) and \(1-2a\ge 0.\) Combined with \(\varDelta y_{ij}^{k}>0\) and \(\varDelta y_{ij}^{f}\ge 0,\) it assures that \(2a\varDelta y_{ij}^{k}+(1-2a)\varDelta y_{ij}^{f}>0.\)

We have that \(\varDelta y_{ij}^{k}\ge \varDelta y_{ij}^{f}.\) To see this, start with a case where \(c_{ik}=c_{jk}\) for all \(k\in N_{0}\backslash \left\{ i,j\right\} .\) Solutions satisfying Anonymity, like the Kar and folk solutions, will be such that \(y_{i}=y_{j}.\) Then, reduce the cost of some edges \((i,k).\) As \(C(S,c)\) can decrease only if \(\left\{ i,k\right\} \subseteq S,\;i\) and \(k\) are the main beneficiaries. If the reductions change the irreducible matrix, in particular if it reduces the cost of some edges \((j,l),\) then part of the savings are passed on to other agents, including agent \(j.\) Therefore, if \(a>\frac{1}{2}.\) we have \(2a\varDelta y_{ij}^{k}+(1-2a)\varDelta y_{ij}^{f}\ge 2a\varDelta y_{ij}^{k}+(1-2a)\varDelta y_{ij}^{k}=\varDelta y_{ij}^{k}>0.\)

Therefore, Strict Ranking is satisfied if and only if \(a>0\). \(\square \)

Reprints and permissions