## 3 Stable Flows
Therefore, if \(v\
eq s,t\), then the total allocation of \(v^{in}\) and \(v^{out}\) is \(q(v)\) by [PERSON]'s law. The total allocations of \(s^{in},s^{out}\) and \(t^{in},t^{out}\) is less than \(q(s)\) and \(q(t)\), respectively, by the choice of \(q\). That is, \(g_{f}\) is an allocation on \(G_{D}\). To justify the stability of \(g_{f}\), we have to show that no blocking edge exists. To see that neither \(v^{in}v^{out}\) nor \(v^{out}v^{in}\) is blocking, observe that both \(v^{in}\) and \(v^{out}\) are saturated in \(g_{f}\). Therefore, \(v^{in}v^{out}\) is dominated at \(v^{out}\), and \(v^{out}v^{in}\) is dominated at \(v^{in}\). Assume now that \(g_{f}(v^{out}u^{in})<p(v^{out}u^{in})=c(vu)\) holds. Our goal is to prove that \(v^{out}u^{in}\) is not blocking. If there is an \(f\)-unsaturated walk, \(P\), ending with arc \(vu\) that is not \(f\)-dominated at its starting node, then \(u\in S\) by the definition of \(S\); hence, \(g_{f}(u^{out}u^{in})=0\). Moreover, if some edge, \(w^{out}u^{in}\), with \(v^{out}u^{in}<_{u^{in}}w^{out}u^{in}\) would have a positive allocation, then walk \(P\) would block \(f\), a contradiction. As \(u^{in}\) has a \(q(u^{in})\) amount of total allocation, edge \(v^{out}u^{in}\) is \(g_{f}\)-dominated at \(u^{in}\). The last case is when any \(f\)-unsaturated walk that ends with arc \(vu\) is \(f\)-dominated at its starting vertex. In particular, \(v\
ot\in S\); so, \(g_{f}(v^{in}v^{out})=0\). Moreover, \(f\)-unsaturated walk \((v,u)\) must be \(f\)-dominated at \(v\); hence, \(v\
ot\in\{s,t\}\), and \(v^{out}u^{in}\) is \(g_{f}\)-dominated at \(v^{out}\) as \(v^{out}\) has a \(q(v)=q(v^{out})\) amount of allocation. The conclusion is that \(g:=g_{f}\) is a stable allocation, just as we claimed. At this point, we are ready to prove our main result. Proof of Theorem 2.: There is a stable allocation for \(G_{D}\) by Theorem 1; hence there is a stable flow for \(D\), due to the first part of Lemma 3. If \(c\) is integral, then \(q(v)\) is an integer for each vertex, \(v\), of \(D\); hence, \(p\) is integral for \(G_{D}\). The integrality property of stable allocations in the first part of Theorem 1 shows that there is an integral stable allocation, \(g\), of \(G_{D}\) that describes an integral stable flow, \(f\), of \(D\). At the end of this section, let us point out a weakness of our stability concept. The motivation behind the notion is that we look for a flow that corresponds to an equilibrium situation, where the players represented by the vertices of the network act in a selfish way. This equilibrium situation occurs if no coalition of the players can block the underlying flow, \(f\), and this blocking is defined by an \(f\)-unsaturated walk with a certain property. Along such a walk, the players are capable and prefer to increase the flow. However, any closed \(f\)-unsaturated walk, \(C\), per se causes some kind of instability, because the players along \(C\) mutually agree to send some extra flow along \(C\), even if properties Equations (4) and (5) do not hold for vertex \(v_{1}=v_{k}\) of \(C\). This motivates us to define flow \(f\) of network \((D,s,t,c)\) with preferences to be _completely stable_ if \(f\) is stable and there exists no \(f\)-unsaturated cycle in \(D\) whatsoever. If \(f\) is a stable flow, then we can \"augment\" along \(f\)-unsaturated cycles, and hence, we can construct a flow, \(f^{\prime}\geq f\), such that there no longer exists an \(f^{\prime}\)-unsaturated cycle. However, unfortunately, flow \(f^{\prime}\) might not be stable any more, because we might have created a blocking walk by the cycle augmentations. In fact, there exist networks with preferences that do not have a completely stable flow. One example is in the figure: each arc has a unit capacity; preferences are indicated around the vertices (a lower rank is preferred to the higher). As no arc leaves subset \(U:=\{a,b,c\}\) of the vertices, no flow can leave \(U\); hence, no flow enters \(U\). In particular, arc \(sa\) has zero flow.