## 3 Stable Flows  
Our goal in this section is to prove a generalization of Theorem 1. The \"natural\" approach to achieve this would be an appropriate generalization of the deferred acceptance algorithm of [PERSON] and Shapley. The difficulty is that though the Gale-Shapley algorithm can handle quota function \(q\), somehow, it has problems with ensuring [PERSON]'s law. **Theorem 2**. : _If network \((D,s,t,c)\) and preference orders \(<_{v}\) describe a stable flow problem, then there always exists a stable flow, \(f\). If capacity function \(c\) is integral, then there exists an integral stable flow._Note that it is possible to prove Theorem 2 by a mixture of the deferred acceptance algorithm and the augmenting path algorithm. That is, starting from some terminal vertex, we follow a \"first choice walk\" until they arrive to some terminal vertex. We augment along this walk while observing the capacity constraints and iterate. If a vertex has no more outgoing capacity, then some amount of flow is refused by the receiving vertex, and we try to reroute the flow excess from the starting point of the refused arc (that might be different from the last arc of the current path). We have a stable flow as soon as we cannot find an augmenting path between terminals. Our proof of Theorem 2 follows a different approach for two reasons. On the one hand, it seems that in the area of stable matchings, neither the reduction of one problem to another nor the use of graph terminology is routine. We demonstrate here that these methods may be fruitful. On the other hand, the \"deferred augmentation\" algorithm we sketched above does not give much information about the rich structure of stable flows that easily follows from the lattice property of stable allocations. With the help of the given instance of the stable flow problem, we shall define a particular instance of the stable allocation problem. For each vertex, \(v\), of \(D\), calculate:  
\[M(v):=\max\left(\sum_{x:xv\in A(D)}c(xv),\sum_{x:vx\in A(D)}c(vx)\right)\]  
that is, \(M(v)\) is the maximum total capacity of those arcs of \(D\) that enter and leave \(v\). Therefore, \(M(v)\) is an upper bound on the amount of flow that can flow through vertex \(v\). Choose \(q(v):=M(v)+1\). Construct graph \(G_{D}\) as follows. Split each vertex, \(v\), of \(D\) into two distinct vertices, \(v^{in}\) and \(v^{out}\), and for each arc, \(uv\), of \(D\), add edge \(u^{out}v^{in}\) to \(G_{D}\). For each nonterminal vertex, \(v\), of \(D\), add two parallel edges between \(v^{in}\) and \(v^{out}\); to distinguish between them, we will refer to them as \(v^{in}v^{out}\) and \(v^{out}v^{in}\). Let \(p(v^{in}v^{out})=p(v^{out}v^{in}):=q(v)\), \(p(u^{out}v^{in}):=c(uv)\) and \(q(v^{in})=q(v^{out}):=q(v)\). To finish the construction of the stable allocation problem, we need to fix a linear preference order for each vertex of \(G_{D}\). For vertex \(v^{in}\), let \(v^{in}v^{out}\) be the most preferred and \(v^{out}v^{in}\) be the least preferred edge (if these edges are present, that is, if \(v\) is nonterminal), and the order of the other edges incident to \(v^{in}\) are coming from the preference order of \(v\) on the corresponding arcs. For vertex \(v^{out}\), the most preferred edge is \(v^{out}v^{in}\) and the least preferred one is \(v^{in}v^{out}\) (if these edges are present), and the other preferences are coming from \(<_{v}\). Figure 1: Node splitting to create \(G_{D}\). The proof of Theorem 2 is a consequence of Theorem 1 and the following Lemma that describes a close relationship between stable flows and stable allocations. **Lemma 3**. : _If network \((D,s,t,c)\) and preference orders \(<_{v}\) describe a stable flow problem, then \(f:A(D)\rightarrow\mathbb{R}\) is a stable flow if and only if there is a stable allocation, \(g\), of \(G_{D}\), such that \(f(uv)=g(u^{out}v^{in})\) holds for each arc, \(uv\), of \(D\)._  
Proof. : Assume first that \(g\) is a stable allocation in \(G_{D}\).