A note on the rationing of divisible and indivisible goods in a general network

We define an allocation on the edges as $f_{ab}\hskip 5.69054pt,ab\in E$ as feasible, if $f_{ab}=f_{ba}\hskip 5.69054pt\forall ab\in E$ and the flow induced on the nodes by $f$ (as $x$ defined earlier) and for feasibility, $x_{a}\leq b_{a}\hskip 5.69054pt\forall a\in V$. Any rule which picks an allocation from this set is called a feasible allocation rule. In the rest of the section, we discuss the egalitarian rule for this model.

Given a network $(G,N,E)$, we make the following transformation to construct the bipartite network $(G_{b},V_{b},E_{b})$. We represent $V_{b}=A\cup B$ where $A=V$ and $B=V$. are either sides of the network. There is an edge between agent $i\in A$ and $j\in B$ only if there is an edge $ij$ in the given network $G$. Connect the agents in $A$ to a supply node $s$ and the agents in $B$ to a sink node $t$. We refer to as a flow, any feasible shipment of goods from the source node to the sink node.

Proof : Consider a solution $(y_{a},y_{b},g_{ab})$ for the agents in the modified bipartite network where $y_{a},y_{b}$ refers to an allocation for agent $a\in A$ and $b\in B$ respectively. $g_{ab}$ is the flow on the edge $ab$. We will try to show that every feasible solution in the modified bipartite network maps to a solution in the original network and vice-versa. Once we have that, the second part of the statement follows (As Bochet et al. [7, 8] have established the fairness properties of egalitarian mechanism in bipartite networks).

Firstly, consider a feasible exchange in the original problem. Denote the solution by $(x_{a},f_{ab})$ for agent $a,b$ in the network. $x,f$ are node and edge allocations respectively. In the modified network, set $g_{a_{i}b_{j}}=g_{a_{j}b_{i}}=f_{a_{i}a_{j}}\hskip 5.69054pt\forall i,j\in V$. Clearly, this solution is feasible in the modified network and $y_{a_{i}}=y_{b_{i}}=x_{a_{i}}\hskip 5.69054pt\forall i\in V$.

Now, consider a solution $(y_{a},y_{b},g_{ab})$ in the modified bipartite network. Construct the following solution, $f_{a_{i}a_{j}}=(g_{a_{j}b_{i}}+g_{a_{i}b_{j}})/2\hskip 5.69054pt\forall i,j\in V$. This also defines a node allocation in the original network with $x_{a_{i}}=(y_{a_{i}}+y_{b_{i}})/2\hskip 5.69054pt\forall i\in V$. This is a feasible allocation since, $f_{ij}=f_{ji}\hskip 5.69054pt\forall ij\in E$ and $x_{i}\leq b_{i}\hskip 5.69054pt\forall i\in V$.  

Hence, the case of exchanging divisible goods in an economic network is done by a simple transformation into a bipartite network. The mechanism is also peak strategyproof if the preference profiles are private information of the agents. In the next section, we discuss the case of exchanging indivisible goods among agents in a network. We show that there is no mechanism that is peak strategyproof but we design a mechanism which is egalitarian in nature and retains many other attractive properties.

b-matchings is a generalized notion of a matching type problems on networks. Given a network $G$ and a positive number $b_{i}$ for each node $i\in V$ and capacity $u_{e}$ for each edge $e\in E$ We define the u-capacitated b-matching or (b,u) matching is a vector $x$ such that

	$\displaystyle x_{i}(f)\leq b_{i}\hskip 5.69054pt\text{for all}\hskip 5.69054pti\in V$		(5)
	$\displaystyle 0\leq f_{ij}\leq u_{ij}\hskip 5.69054pt\text{for all}\hskip 5.69054ptij\in E$		(6)

In the case when all the $u_{e}=\infty$ and $b_{i}=1$, we arrive at the problem of finding a matching in network $G$. The set of all $x$ which satisfies [5] is the set of all feasible b-matchings. Clearly, a given graph $G$ can have more than one b-matching. From an operations research as well as economics point of view we will be interested in finding the maximum b-matching among all feasible b-matchings. Here, the maximum b-matching is the one with the highest $\sum_{i}x_{i}$ among all the feasible b-matchings.

A maximum weight u-capacitated b-matching problem can be solved in strongly polynomial time by a reduction to the maximum weight b-matching problem. Following is a linear programming formulation of the maximum weight b-matching problem:

	$\displaystyle\text{Max}\hskip 5.69054pt\sum_{i}\sum_{j}X_{ij}$		(7)
	subject to		(8)
	$\displaystyle\sum_{j\in N(i)}X_{ij}\leq b_{i}\hskip 5.69054pt\forall i\in V(G)$		(9)
	$\displaystyle X_{ij}\in Z$		(10)

The maximum weight u-capacitated b-matching problem would encode the additional constraint $X_{ij}\leq u_{ij}\hskip 5.69054pt\forall ij\in E(G)$. In this section, we assume $u_{ij}=\infty$ but we discuss the capacitated case in later sections.

Algorithms for finding a maximum weight b-matching: Cook and Cunningham [15] discuss polynomial algorithms to solve the b-matching problem. We briefly discuss about the b-matching matroid. This discussion follows from the well-known matching matroid formulation. For details on matching matroid, refer to cook [15].

For an undirected graph $G(V,E)$ define, $\mathcal{I}=\{x_{vec}|x_{vec}\hskip 5.69054pt\text{is the node allocation from some b-matching of G}\}$ where $x_{vec}\in R^{V}$, the $i^{th}$ component of the vector, $x_{vec}^{i}=x_{i}$ where $x_{i}$ is the number of times node $i$ is matched in that particular b-matching. Then the pair, $(V,\mathcal{I}):=M$ is a matroid. We will refer to it as the b-matching matroid. A base in $M$ is a vector $x_{vec}$ that is generated by some maximum b-matching of $G$.

The ”rank” function : $2^{V}\rightarrow Z^{+}\cup\{0\}$ of the matroid $M$ is defined to be rank(S) = $\max_{I\subset S,I\in\mathcal{I}}|I|\hskip 5.69054pt\forall\hskip 5.69054ptS\subseteq V$. The rank function is submodular and in our context rank(S) can be interpreted as the size of a maximum b-matching in the set S. $P_{rank}$ refers to the polymatroid associated with this particular rank function and is given by

$$P_{rank}=\{x\in R^{V}|x\geq 0,x(S)\leq f(S),\hskip 5.69054pt\forall\hskip 5.69054ptS\subseteq V\}$$

(11)

where $x(S)=\sum_{i\in S}x_{i}$

From an Operations Research perspective, we have obtained an optimal solution to the maximum weight b-matching problem. But the aforementioned linear program can have many solutions. From an Economics perspective, we would like to pick a particular maximum weight b-matching from the optimal set such that the utility of the agents satisfy fairness constraints. Inoder to find such an allocation, we would understand the structure of maximum weight b-matchings for the uncapacitated problem in the rest of this section. Towards the end, we analyze the case with capacities.

A feasible allocation $x\in\mathcal{A}(G)$ is Pareto Optimal if for any other $x^{\prime}\in\mathcal{A}(G)$ we have

$$\{\text{for all i:}\hskip 5.69054ptx_{i}^{\prime}R_{i}x_{i}\}\implies\{\text{for all i:}\hskip 5.69054ptx_{i}^{\prime}I_{i}x_{i}\}$$

(12)

i.e. there is no other allocation $x^{\prime}$ that is weakly better for every agent and strictly better for at least one agent in the allocation $x$.

Proof: If $x$ denotes the utiliy profile of the agents in the network, then the size of the b-matching that produced this utility profile is $x/2$. As each exchange between 2 agents on a network adds an utility of one to each of those agents.

Suppose, we have an exchange of goods in the network that is produced by a maximum b-matching resulting in the allocation profile $x$. Since, it is a maximum b-matching, we cannot have more feasible exchanges in this network. There is no alternating path of odd length connecting two unsaturated nodes. Any other path of even length from an unsaturated node $a$, to another unsaturated node $b$ will result in another maximum b-matching with the utility of node $b$ strictly below the current solution. Hence, picking any maximum b-matching to the problem should result in an pareto optimal allocation for the agents.

Now, suppose $x$ is a pareto optimal allocation for the agents in the network, then there exists no allocation $y$ in the network such that every agent is weakly better under allocation $y$, and there is atleast one agent strictly better off under $y$. This implies, there is no alternating path of odd length connecting two unsaturated nodes. This implies the given solution is a maximum b-matching.  

The following generalization of Gallai and Edmonds theorem further helps us understand the structure of pareto optimal solutions

Gallai and Edmonds decompose any given network into smaller sub-components namely, over demanded, under demanded and pefectly demanded components. Bochet et al. [7, 8] use this decmposition to establish the structure of pareto optimal allocations in bipartite networks. Roth et al. [29] establish the structure of Pareto-efficient pairwise matchings using the Gallai-Edmonds decomposition (GED). We generalize the GED idea to our problem where the nodes have arbitrary peaks associated with them. Hence, we obtain a characterization of pareto efficient b-matchings in this problem. $M$ is the set of maximum b-matchings and let $\mu$ denote an arbitrary matching in the set $M$, $\mu(i)$ denotes the matched neighbors of agent $i$ in matching $\mu$. Setting up the notation partition $V$ as $\{V^{U},V^{O},V^{P}\}$ such that

	$\displaystyle V^{U}$	$\displaystyle=$	$\displaystyle\{i\in V:\exists\mu\in M\hskip 5.69054pts.t.\hskip 5.69054pti\in\mu(i)\}$		(13)
	$\displaystyle V^{O}$	$\displaystyle=$	$\displaystyle\{i\in V\backslash V^{U}:\exists\text{set of agents}\hskip 5.69054pt\tilde{j}\in V^{U}s.t.\sum_{j\in\tilde{j}}n_{i,j}=b_{i}\},$		(14)
	$\displaystyle V^{P}$	$\displaystyle=$	$\displaystyle V\backslash(V^{U}\cup V^{O})$		(15)

where $n_{i,j}=1$ if $i,j$ is matched in a feasible solution. $V^{U}$ is the set of agents unmatched ($x_{i}<b_{i}$) in atleast one maximum b-matching. $V^{O}$ is the set of agents completely matched ($x_{i}=b_{i}$) in every maximum b-matching and have atleast 1 neighbor in $V^{U}$. $V^{P}$ is the set of agents who are again perfectly matched but does not have a link with any agent in $V^{U}$.

Let $I\subseteq V$ and $N(I)=\{j|ij\in E,i\in I\}$. Then $(I,N(I))$ is a reduced sub problem of the original problem.

Proof : The Gallai-Edmonds decomposition precisely proves the above lemma when all the peaks $b_{j}=1$. Roth et al. [29] which this paper builds upon has a statement when the nodes have unit capacity. Now, lets construct a matching instance of the given b-matching problem. From the given graph $(G,V,E)$ construct the following graph $(G^{\prime},V^{\prime},E^{\prime})$: Create $b_{i}$ duplicate copies of node $i$ with unit peak each. Label these nodes as $(i^{1},i^{2}....i^{b_{i}})$. In the graph $G^{\prime}$, nodes $i^{k},(k\in 1,2,..b_{i})$ and $j^{l},(l\in 1,2,..b_{j})$ is connected by an edge if $ij$ is conencted in the original graph $G$. There is no edge between $i^{k}$ and $i^{r},(k,r\in(1,2,...b_{i}))$ in $G^{\prime}$. Now, we have a graph with unit peaks. Applying the GED on this unit graph would establish the result.

We just stress a bit on the third statement. When $(|J|=1)$ the odd component has only 1 element, then there is no b-matching within that component. When $|J|>=2$, we highlight that the maximum size of any matching within every odd component in a unit capacity graph is one less than the number of nodes in the component (refer to Roth et al. [29] for a proof). By symmetry, all the duplicate (identical) copies of a node will be in the same component. Hence, we can shrink these duplicate nodes into the parent node with original peak. Thus, from the decomposition above, the sum of the peaks of the agents in a odd component is $\Sigma_{j=1}^{|J|}b_{j}$ and the result follows.  

A utility profile $U\in R^{V}$ is said to be a feasible utility profile if the profile is an outcome of a feasible b-matching in the network. Since, we are looking for pareto optimal solutions, the outcome of our mechanisms is an utility profile induced by a maximum b-matching in the network.

A mechanism is deterministic if for a given network, it picks a maximum b-matching as an outcome from the set of maximum b-matchings. Roth et al. [29] study priority mechanisms in the context of deterministic mechanisms. They also show establish that the randomized ”Egalitarian” mechanism is superior in the sense that it not only retains the efficiency, strategyproof properties of deterministic mechanism, but it also produces an outcome which is envy free and strongly efficient in the sense of lorenz dominance. The mechanism of Roth et al. is a ”lottery” mechanism, that randomly picks a maximum b-matching from the pareto optimal set. The distribution or lottery is chosen in such a way that the aforementioned economic properties are exhibited by the mechanism. We define this more mathematically below.

Let $\mathcal{U}$ be the set of all b-matchings in $G$. A matching lottery $l:$ $P_{\mu},\mu\in M$ is a probability distribution over $\mathcal{U}$. For each matching $\mu\in\mathcal{U}$, $P_{\mu},\mu\in[0,1]$ is the probability of choosing matching $\mu$ in lottery l, and $\sum_{\mu\in\mathcal{U}}P_{\mu}=1$. A matching lottery $l$ can be also viewed as a fractional b-matching which

is defined to be a convex combination of several integral b-matchings. Let $\mathcal{L}$ be the set of matching lotteries. Given $l\in\mathcal{L}$, define the utility $x^{l}_{i}$ of vertex i to be the expected total exchanges that i is involved , i.e., $x^{l}_{i}=\sum_{\mu\in\mathcal{U}}l_{\mu}x_{i}^{\mu}$. Define the utility profile induced by lottery $l$ to be the vector $x_{l}=(x^{l}_{i}),i\in V$ . Let $P={x_{l}},l\in\mathcal{L}$ be the set of all feasible utility profiles.

It is now clear from our definition that a feasible utility profile can be understood as a fractional b-matching (a convex combination of integral b-matchings). The $P_{rank}$ polymatroid we defined earlier is exactly the set of feasible utility profiles.

Roth et al. [29] described the Egalitarian Mechanism for the pairwise kidney exchange problem. Jianli et al. [1] develop a water filling algorithm which gives a simpler and intuitive proof of the Roth’s mechanism. Here, we use the ideas from jianli et al. to develop an Egalitarian Mechanism for the generalized maximum indivisible exchange problem. The idea is similar in the sense that the problem on a general network can be suitably reduced to a problem on a bipartite network. This can be done if one could establish the equivalence between the solutions in both network. Once the above step is completed, we could run the familiar allocation rules for bipartite networks to establish a allocation for our original general network. We describe this procedure below in more detail

Construction of Nodes: Define $\mathcal{C}=\{C_{1},C_{2}....C_{k}\}$ as the set of odd components in the underdemanded component $V^{U}$ where $k=|C|$. Construct the following bipartite graph $G_{B}=(A,B,E)$ where each node in $A$ corresponds to a node in $V$. We use $A^{C_{1}},...,A^{C_{k}}$ to denote $k$ disjoint sets corresponding to $C_{1},C_{2},..C_{k}$ respectively. Let $A^{PO}=\{a_{i}|i\in V^{P}\cup N^{O}\}$; $A^{U}=\{a_{i}|i\in V^{U}\}$.

The construction of B is as follows. B Can be partitioned into 3 parts: $B^{PO}\cup B^{O}\cup B^{C}$. Each node in $B^{PO}$ corresponds to a node in $B^{P}\cup B^{O}$. We use $c_{i}\in B^{PO}$ to denote the node corresponding to $i\in B^{P}\cup B^{O}$. Each node in $B^{P}$ corresponds to a node $V^{P}$. We use $c_{i}^{\prime}\in B^{O}$ to denote the node corresponding to $i\in V^{P}$. $B^{C}$ consists of $k$ disjoint sets $B^{C_{1}},B^{C_{2}}....B^{C_{k}}$, where $B^{C_{i}}$ contains a node with value $\Sigma_{j\in C_{i}}b_{j}-1$ (this is the maximum b-matching within a particular odd component) if and only if $|B^{C_{i}}|\geq 2$; $B^{C_{i}}$ is empty otherwise.

Construction of Edges:
(1) For each $i\in V^{P}\cup V^{O}$, we have edge $(a_{i},c_{i})\in E$ where $a_{i}\in A^{PO}$ and $c_{i}\in B^{PO}$
(2) For a vertex $a_{i}\in A^{C}$ and another vertex $c^{\prime}_{j}\in B^{O}$ we have $(a_{i},c^{\prime}_{j})\in E$ if $(i,j)\in E$
(3) For each vertex, $a\in A^{C_{i}}$ add an edge to the node in $B^{C_{i}}$.

Step 2: Apply the egalitarian mechanism (BIMS): Apply the Egalitarian Mechanism for indivisible goods in a bipartite network.

1) Step 1. Solve the linear program $LP_{1}$

	$\displaystyle\text{Maximize}\hskip 5.69054pt\lambda_{1}$
	subject to
	$\displaystyle x_{v}=\lambda_{1},\forall v\in V,x\in P_{rank}$

We call an element $v\in V$ a tight element if $x_{v}$ participates in some tight constraint in $P_{rank}$. Let $D_{1}$ be the set of tight elements. In other words, increasing $x_{v}$ would violate some constraint in $P_{rank}$ when other $x_{u}$ for $u\neq v$ are fixed. In many linear programming algorithms, we can easily detect such tight elements. Another way to test the tightness of an element is to solve a closely related linear program in which we fix other $x_{u}$ and maximize $x_{v}$.

(2) In general, at Step $k$, we solve the linear program

	$\displaystyle LP_{k}=\text{maximize}\hskip 5.69054pt\lambda_{k},\text{subject to}\hskip 5.69054ptx_{v}=\lambda_{j},\hskip 5.69054pt\forall\hskip 5.69054ptv\in D_{j}\hskip 5.69054pt\forall\hskip 5.69054ptj<k,$
	$\displaystyle x_{v}=\lambda_{k},\forall v\in V\backslash\cup_{j<k}D_{j},\hskip 5.69054ptx\in P_{rank}.$

Let $D_{k}$ be the set of elements that become tight in this step.

(3) The algorithm return $x={x_{v}=\lambda_{j}\hskip 5.69054pt\text{for}\hskip 5.69054ptv\in D_{j}}\hskip 5.69054pt\text{if}\hskip 5.69054pt\cup_{j=1}^{k}D_{j}=V$  

Proof: A utility profile in the original network is induced by a maximum b-matching $\mu$ or a lottery (linear combination) over the set of maximum b-matchings. Also, it is well known that the polytope of maximum flows is convex with integral extreme points. Hence, to prove that every utility profile in original network implies a feasible maximum flow in the modified network, it is sufficient to prove the statement only for integral utility profiles (as every deterministic maximum b-matching corresponds to a integral utility profile). Now, given this maximum b-matching, we will match it to a unique maximum flow, $f$ in the modified network. Since each agent $i\in N^{P}\cup N^{O}$ is saturated, send flow $f_{ij}=b_{i}$ on all edges $ij,i\in A^{PO},j\in B^{PO}$. Now, focus on each component $C_{k}$, if $C_{k}$ has only one node $i$ with utility $U_{i}$. Then this utility is derived only by exchanging with the agents in $B^{O^{\prime}}$. Send a flow, $f_{ij}=x_{ij}\hskip 5.69054pt\forall ij$ such that $j\in N(i)\cap B^{O^{\prime}}$ where $x_{ij}$ is the number of units exchanged between agents $i$ and $j$ in the given maximum b-matching. On a similar note, we fix the flow for the other components $C_{k}$. We know in any $C_{k}$, $|C_{k}|-1$ of the vertices are matched in the same component, so a flow of $|C_{k}|-1$ can be obtained by sending $x_{ij}$ units of flow to the agents in $B^{C_{k}}$. If $ij\in\mu,i\in V^{C}$ and $j\in V^{O}$, then node $i$ is saturated in that particular b-matching; If we send a unit flow in modified network, it is also saturated in the bipartite network.

To prove the other direction that every integral maximum flow corresponds to a feasible utility profile in the original network. Consider a maximum flow of $|F|$ in the modified bipartite network. First lets say the maximum flow value is $|B|$, this is also the size of the maximum b-matching in the original network. For a given set $A^{C_{i}}$ with $|A^{C_{i}}|>=2$, there is at most one vertex $a_{j}\in A^{C_{i}}$ such that there exists a vertex $c^{\prime}_{h}\in B^{O}$ with $f(a_{j},c^{\prime}_{h})=1$.In this case, we include in the matching $\mu$. In any maximum flow, for each $C_{i}$, agents in $A^{C_{i}}$ send $|C_{i}|-1$ units of flow to $B^{C_{i}}$. Consequently from GED lemma, $|C_{i}|-1$ vertices can be matched among themselves. There are exactly $|V^{O}|$ units exchanged by agents in $A^{C}$ with agents in $V^{O}$. each such exchnge constitutes one unit flow to $B^{O}$. So all vertices in $V^{O}$ are matched. From GED Lemma, we can match all vertices in $V^{P}$ among themselves in $\mu$. It is easy to see that $u$ is exactly the utility profile corresponding to $\mu$.

Proof: From the lemma above, we have showed that every maximum flow in the modified network is equivalent to a maximum b-matching induced utility profile in the original network. The egalitarian allocation outputs a maximum flow allocation (not necessarily integral). But it is folklore that this non-integral maximum flow can be obtained as a convex combination of integral maximum flows. These convex combinations $\lambda$ are the probabilities with which we pick different matchings from the set of all maximum b-matchings.

As discussed in Klaus [17], No envy and ETE are not equivalent here. From theorem above, the egalitarian mechanism applied to this bipartite network is a feasible utility profile. Bochet et al. [8] have established the egalitarian mechanism is lorenz dominant among all feasible flows. No Envy also follows from the allocation rule of Bochet et al. [7, 8]

Extension of Rules: In the language of Moulin and Sethuraman [27], an allocation rule $\phi$ on a bipartite network $(G,V,E)$ is said to be an extension of the Sprumont’s Uniform rule if $\phi$ coincides with the allocation of uniform rule if $G$ is a network with unit demander (supplier) connected to multiple suppliers (demanders). i.e.

$$\phi_{i}=U_{i},\hskip 5.69054pt\forall\hskip 5.69054pti\in V$$

(16)

where $U_{i}$ is the utility of agent $i$ under uniform rule.

The notion of ”extending a rule” is such that we are not compromising on properties of existing fair allocation mechanisms. Instead, we are actually generalizing in a suitable way to more general network structures.

In this spirit, Bochet et al. [7, 8], Chandramouli and Sethuraman [12, 11] develop mechanisms which are extensions of the uniform rule. Moulin and Sethuraman [27] study a more general class of extensions of some basic well known rules. We extend this definiton further to general non-bipartite networks. An allocation rule $x$ on a general network $(G,V,E)$ is said to be an extension of the BIMS Egalitarian rule $\phi$ if $x$ coincides with $\phi$ if the network $G$ is bipartite i.e. $x_{i}=\phi_{i},\hskip 5.69054pt\forall\hskip 5.69054pti\in V$

Proof: If the network is bipartite, the odd components set, $V^{U}$ forms an independent set. So, $V^{U}$ is a collection of nodes (with peaks $b_{i}$) which are not saturated in atleast one maximum b-matching. Hence, the set $B^{U}$ is empty and each agent $i\in V^{U}$ is only connected to agents in $V^{O}$ who are completely saturated. In the bipartite context, if $i$ were a supplier then, any agent $j\in N(i)$ has $x_{j}=b_{j}$ in all pareto allocations. For a detailed derivation of GED for bipartite networks, follow the discussion in Chandramouli and Sethuraman [12]. It is clear from their proof that if the given network $G$ is bipartite, then the Step 1 of our algorithm which modifies the given network into a suitable bipartite network, outputs $G$. Since, we apply the probabilistic egalitarian rule in step 2, the result follows.  

Consistency: As discussed in Chandramouli and Sethuraman [11], the egalitarian rule is an extension of the uniform rule which is not consistent. They propose the edge fair rule which is a consistent extension of the uniform rule to bipartite networks. In the previous section, if after the transformation into bipartite network, if we apply the edge fair mechanism to that network, we would have a consistent extension of the uniform rule to non-bipartite indivisible goods network.

In the discussions so far, we have ignored the possibility of agents having control over the values $b_{i}$. Suppose agents report $b_{i}$ to the mechanism designer who then decides the final allocation, then the agents can misreport the peaks to improve their allocation. So far, the allocation of the agents was strictly less than $b_{i}$. If the agents report $b_{i}^{\prime}>b_{i}$, then there is a possibility of agents having an allocation more than his true $b_{i}$. In that case, we need assumptions on the preference profile of agents to compare his utilities when his allocations are on either side of his true peak $b_{i}$.

Single peaked preferences: In the spirit of Bochet et al. [7, 8], we would like to continue our assumption of single peaked preferences for the agent allocations. Mathematically, given a prefernce profile $R_{i}$ for agent $i$ and two possible allocations $x_{i},x_{i}^{\prime}$ then:

	$\displaystyle x_{i}^{\prime}<x_{i}\leq p[R_{i}]\implies x_{i}P_{i}x_{i}^{\prime}$		(17)
	$\displaystyle p[R_{i}]\leq x_{i}<x_{i}^{\prime}\implies x_{i}P_{i}x_{i}^{\prime}$		(18)

A mechanism is peak strategyproof if it is a dominant strategy for the agents to reveal their peaks truthfully. Given this preference structure, the following example shows that there is no peak strategyproof mechanisms in the set of pareto optimal allocations. Consider agents $(a,b,c)$ connected to each other and peak $b_{i}=1,i\in(a,b,c)$. If the agents report their true peaks, then any allocation mechanism is such that $\{(x_{a},x_{b},x_{c})|x_{a}+x_{b}+x_{c}\leq 2\}$. W.l.o.g, lets say $x_{a}<1$. Suppose agent $a$ misreports his peak $b_{a}=2$, then we have a unique maximum b-matching and the allocation is $(2,1,1)$. If $2P_{a}x_{a}$ for agent $a$, he improves his allocation.

A mechanism is link strategyproof if it is dominant strategy for the agents to reveal all his/her neighbors. Roth et al. [29] established the link strategyproofness of the egalitarian mechanism in the kidney exchange problem. The egalitarian mechanism is not link group strategyproof even in the kidney exchange problem. To see that, consider the following network where each node has 1 unit of good to exchange. Agent $s_{4}$ is matched in every maximum matching, but $s_{7}$ is missed in some maximum matching and recieves a utility strictly less than 1 in the egalitarian allocation. Now, $s_{4},s_{7}$ can coordinate and misreport about the existence of the link between $s_{4}$ and $s_{3}$. If that link is not reported, then, $(s_{4},s_{5},s_{6},s_{7})$ form a separate group and all the agents are matched and receive peak utility. Hence, agent $s_{7}$ improves his allocation.

The agents in over demanded and perfectly demanded component doesn’t misreport since they already recieve their peak allocation. The only deviating subsets are those agents in the odd components. Hence, for the rest of the proof we restrict our attention to coalition groups which consists only of agents of the odd components.

Proof. We prove the result for an arbitrary coalition of agents. Let $A_{i}$ be the set of agents that agent $i$ is linked to, and let $A^{\prime}_{i}$ be agent $i$’s report. We may assume without loss of generality that any given agent $\in V^{PO}$ finds all the agents in odd components acceptable: if even component agent $j$ finds add component agent $i$ unacceptable, then agent $i$ cannot have a link to demander $j$ regardless of his report, so clearly $i$’s manipulation opportunities are more restricted. Let $\phi$ and $\phi^{{}^{\prime}}$ be (any) egalitarian flows when the suppliers report $A$ and $A^{\prime}$ respectively, and let $x$ and $x^{\prime}$ be the corresponding allocation to the agents. We show that no coalition of odd component agents can weakly benefit by misreporting their links unless each agent in the coalition gets exactly their egalitarian allocation.

Consider the transformed bipartite network of the given network when going through the analysis below:

The proof is by induction on the number of type 2 breakpoints in the algorithm to compute the egalitarian allocation in the transformed network. Suppose the given instance has $n$ type 2 breakpoints, and suppose $X_{1},X_{2},\ldots,X_{n}$ are the corresponding bottleneck sets of suppliers. If $n=0$, every odd component agent is at his peak value in the egalitarian allocation, and clearly this allocation cannot be improved. Suppose $n\geq 1$. Define

$$\tilde{X}_{\ell}=\{i\in X_{\ell}\mid\sum_{j\in A_{i}}\phi^{\prime}_{ij}\;\geq\;\sum_{j\in A_{i}}\phi_{ij}\},$$

and

$$\hat{X}_{\ell}=\{i\in X_{\ell}\mid\sum_{j\in A_{i}}\phi^{\prime}_{ij}\;\leq\;\sum_{j\in A_{i}}\phi_{ij}\}.$$

We shall show, by induction on $\ell$, that for each $\ell=1,2,\ldots,n$:

• (a)

  $\phi^{{}^{\prime}}_{ij}=0$ for any $i\in\tilde{X}_{\ell^{\prime}}$, $j\in\cup_{i^{\prime}\in X_{\ell}}A_{i^{\prime}}$, $\ell^{\prime}>\ell$; and

• (b)

  $X_{\ell}\subseteq\hat{X}_{\ell}$.

The theorem follows from part (b) above.

Any supplier $k\in X_{\ell}\setminus\tilde{X}_{\ell}$ must have $A_{k}=A^{\prime}_{k}$ as otherwise supplier $k$ is part of the deviating coalition and does worse. Consider now a supplier $i\in\tilde{X}_{\ell}$ with $x_{i}<s_{i}$ and a supplier $k\in X_{\ell}\setminus\tilde{X}_{\ell}$. We have the following chain of inequalities:

$$\sum_{j\in A^{\prime}_{k}}\phi^{{}^{\prime}}_{kj}\;=\;\sum_{j\in A_{k}}\phi^{{}^{\prime}}_{kj}\;<\;\sum_{j\in A_{k}}\phi_{kj}=x_{k}\;\leq\;x_{i}\;=\;\sum_{j\in A_{i}}\phi_{ij}\;\leq\;\sum_{j\in A_{i}}\phi^{{}^{\prime}}_{ij}\;\leq\;\sum_{j\in A^{\prime}_{i}}\phi^{{}^{\prime}}_{ij}.$$

To see why, note that as $k\in X_{\ell}\setminus\tilde{X}_{\ell}$, the second inequality is true by definition, and also $A_{k}=A^{\prime}_{k}$ (justifying the first equality). Also $k,i\in X_{\ell}$ and $x_{i}<s_{i}$, implies $x_{k}<s_{i}$, as suppliers $k$ and $i$ both belong to the same bottleneck set and supplier $i$ is below his peak; this justifies the third inequality. The fourth and fifth inequalities follow from the fact that $i\in\tilde{X}_{\ell}$ and the fact that $\phi^{{}^{\prime}}_{ij}$ must be zero for all $j\in A_{i}\setminus A^{\prime}_{i}$. This chain of inequalities implies that $x^{\prime}_{k}<x_{k}\leq s_{k}$ and $x^{\prime}_{k}<x^{\prime}_{i}$. Therefore, when the suppliers report $A^{\prime}$, supplier $k$ must be a member of an “earlier” bottleneck set than supplier $i$. An immediate consequence is that demanders in $A^{\prime}_{k}=A_{k}$ do not receive any flow from supplier $i$ when the report is $A^{\prime}$.

By the induction hypothesis, supplier $i\in X_{\ell}$ does not send any flow to the demanders in $\cup_{1\leq i^{\prime}\leq\ell-1}\cup_{k\in X_{i^{{}^{\prime}}}}A_{k^{\prime}}$. Therefore

$$\{j\mid\phi^{{}^{\prime}}_{ij}>0,j\in A_{i}\}\subseteq\{j\mid\phi_{ij}>0,j\in A_{i}\}.$$

This observation, along with the fact that every $i\in\tilde{X}_{\ell}$ weakly improves, and the fact that $X_{\ell}$ is a type 2 breakpoint implies that $\sum_{j\in A_{i}}\phi^{{}^{\prime}}_{ij}=\sum_{j\in A_{i}}\phi_{ij}$, establishing (b). Furthermore, in such a solution, every demander $j\in A_{i}$ for $i\in\tilde{X}_{\ell}$ must receive all his flow from the suppliers in $\tilde{X}_{\ell}$.In particular, the demanders in $X_{\ell}$ cannot receive any flow from suppliers in $X_{\ell^{\prime}}$ for $\ell^{\prime}>\ell$, establishing (a). To complete the proof we need to establish the basis for the induction proof, i.e., the case of $\ell=1$. This, however, follows easily: it is easy to verify that the set $X_{1}\setminus\tilde{X}_{1}$ must be empty, so $X_{1}=\tilde{X}_{1}$. As $X_{1}$ is a type 2 bottleneck set, it is not possible for every member of $X_{1}$ to do weakly better unless the allocation remains unchanged. Thus, both (a) and (b) follow.  

We fix a problem $(G,s,d)$ such that $s_{i},d_{j}>0$ for all $i,j$ (clearly if $s_{i}=0$ or $d_{j}=0$ we can ignore supplier $i$ or demander $j$ altogether). We define independently our solution for the suppliers and for the demanders.

The definition for suppliers is by induction on the number of agents $|S|+|D|$. Consider the parameterized capacity graph $\Gamma(\lambda),\lambda\geq 0$: the only difference between this graph and $\Gamma(G,s,d)$ is that the capacity of the edge $\sigma i,i\in S_{-}$ is $\min\{\lambda,s_{i}\}$, which we denote $\lambda\wedge s_{i}$. (In particular, the edge from $j$ to $\tau$ still has capacity $d_{j}$). We set $\alpha(\lambda)$ to be the maximal flow in $\Gamma(\lambda)$. Clearly $\alpha$ is a piecewise linear, weakly increasing, strictly increasing at $0$, and concave function of $\lambda$, reaching its maximum when the total $\sigma$-$\tau$ flow is $d_{D_{+}}$. Moreover, each breakpoint is one of the $s_{i}$ (type 1), and/or is associated with a subset of suppliers $X$ such that

$$\sum_{i\in X}\lambda\wedge s_{i}=\sum_{j\in f(X)}d_{j}$$

(19)

Then we say it is of type 2. In the former case the associated supplier reaches his peak and so cannot send any more flow. In the latter case the group of suppliers in $X$ is a bottleneck, in the sense that they are sending enough flow to satisfy the collective demand of the demanders in $f(X)$ and these are the only demanders they are connected to; any further increase in flow from any supplier in $X$ would cause some demander in $f(X)$ to accept more than his peak demand.

If the given problem does not have any type-2 breakpoint, then the egalitarian solution obtains by setting each supplier’s allocation to his peak value. Otherwise, let $\lambda^{\ast}$ be the first type-2 breakpoint of the max-flow function; by the max-flow min-cut theorem, for every subset $X$ satisfying (19) at $\lambda^{\ast}$ the cut $C^{1}=\{\sigma\}\cup X\cup f(X)$ is a minimal cut in $\Gamma(\lambda^{\ast})$ providing a certificate of optimality for the maximum-flow in $\Gamma(\lambda^{\ast})$. If there are several such cuts, we pick the one with the largest $X^{\ast}$ (its existence is guaranteed by the usual supermodularity argument). The egalitarian solution obtains by setting

$$x_{i}=\min\{\lambda^{\ast},s_{i}\},\;\text{for}\;i\in X^{\ast},\;y_{j}=d_{j},\;\text{for}\;j\in f(X^{\ast}),$$

and assigning to other agents their egalitarian share in the reduced problem $(G(S\diagdown X^{\ast},D\diagdown f(X^{\ast})),s,d)$. That is, we construct $\Gamma^{S\diagdown X^{\ast},D\diagdown f(X^{\ast})}(\lambda)$ for $\lambda\geq 0$ by changing in $\Gamma(G(S\diagdown X^{\ast},D\diagdown f(X^{\ast})),s,d)$ the capacity of the edge $\sigma i$ to $\lambda\wedge s_{i}$, and look for the first type-2 breakpoint $\lambda^{\ast\ast}$ of the corresponding max-flow function. An important fact is that $\lambda^{\ast\ast}>\lambda^{\ast}$. Indeed there exists a subset $X^{\ast\ast}$ of $S\diagdown X^{\ast}$ such that

$$\sum_{i\in X^{\ast\ast}}\lambda^{\ast\ast}\wedge s_{i}=\sum_{j\in f(X^{\ast\ast})\diagdown f(X^{\ast})}d_{j}$$

If $\lambda^{\ast\ast}\leq\lambda^{\ast}$ we can combine this with equation (19) at $X^{\ast}$ as follows

$$\sum_{i\in X^{\ast}\cup X^{\ast\ast}}\lambda^{\ast}\wedge s_{i}\geq\sum_{i\in X^{\ast}}\lambda^{\ast}\wedge s_{i}+\sum_{i\in X^{\ast\ast}}\lambda^{\ast\ast}\wedge s_{i}=\sum_{j\in f(X^{\ast}\cup X^{\ast\ast})}d_{j}$$

contradicting our choice of $X^{\ast}$ as the largest subset of $S_{-}$ satisfying (19) at $\lambda^{\ast}$.