## 2 Stable Flows
### Basic Notions  
We consider a network, \((D,c)\), where \(D\) is a directed graph, whose vertices \(V(D)\) are partitioned into a set of terminals, \(S\subseteq V(D)\), and non-terminal vertices, \(V(D)\setminus S\). Moreover, there is a capacity function, \(c:E(D)\rightarrow\mathbb{R}_{>0}\), on the edges. The digraph, \(D\), might contain multiple edges, as well as loops. This concession forces us to slightly modify the structure of the preference lists: each vertex, \(v\in V(D)\), sets up a strictly ordered list of the neighboring edges instead of the neighboring vertices. For convenience, we consider the orderings on incoming and outgoing edges as two separate lists. The set of these lists are denoted by \(O\). Vertex \(v\) prefers \(uv\) to \(wv\), if \(uv\) has a lower number on \(v\)'s preference list than \(vw\). In this case, we say that \(uv\)_dominates_\(wv\) at \(v\) and denote it by \(uv<_{v}wv\). The same notation is used for outgoing edges. **Definition 1** (flow). : _A flow, \(f\), in network, \((D,c)\), is a function, \(f:E(D)\rightarrow\mathbb{R}_{\geq 0}\), such that the following properties hold:_  
1. \(f(uv)\leq c(uv)\) _for all edges,_ \(uv\in E(D)\)_;_
2. \(\sum_{uv\in E(D)}f(uv)=\sum_{vw\in E(D)}f(vw)\) _for all vertices,_ \(v\in V(D)\setminus S\)_._  
We would like to emphasize that we do not distinguish sources and sinks in \(S\); their role is the same: they are the vertices in \(D\) that do not have to obey the Kirchhoff law. **Definition 2** (stable flow). : _A blocking walk of flow \(f\) is a directed walk, \(W=(v_{1},e_{1},...,e_{k-1},v_{k})\), such that all of the following properties hold:_  
1. _each edge,_ \(e_{i}\)_,_ \(i=1,...,k-1\)_, is unsaturated;_
2. \(v_{1}\in S\) _or there is an edge,_ \(e^{\prime}=v_{1}u\)_, such that_ \(f(e^{\prime})>0\) _and_ \(e_{1}<_{v_{1}}e^{\prime}\)_;_
3. \(v_{k}\in S\) _or there is an edge,_ \(e^{\prime\prime}=wv_{k}\)_, such that_ \(f(e^{\prime\prime})>0\) _and_ \(e_{k-1}<_{v_{k}}e^{\prime\prime}\)_._  
_A network flow is stable, if there is no blocking walk in the graph._  
The network can be seen as a market situation, where the vertices are the traders and the edges connecting them are possible deals. All participants rank their partners for arbitrary reasons: e.g., quality, price or location. These rankings are the preference lists of our instance. Notice that edges do not necessarily correspond to deals involving the same product, and there may be cycles on the graph, even of a length of two. An unsaturated walk is a possible deal between vendors \(v_{1}\) and \(v_{k}\). If they are suppliers or consumers (terminals) or can improve their situation using the unsaturated walk, then they will agree to send some flow along it and break the existing scheme. It was shown by [PERSON] (1980) that each instance, \(\mathcal{I}\), of the stable flow problem can be converted into an equivalent instance, \(\mathcal{I}^{\prime}\), of the stable allocation problem, such that every stable flow corresponds to a stable allocation and _vice versa_. Since there always exists a stable allocation [PERSON] (1980), the existence of stable flows directly follows from the equivalence of stability on \(\mathcal{I}\) and \(\mathcal{I}^{\prime}\). The construction shows that stable flows can be found in polynomial time. **Theorem 2.3** ([PERSON], 2010 [6]). : _There is a stable flow on every instance, \((D,c,O)\)._  
**Theorem 2.4** ([PERSON], 2010 [6]). : _For a fixed instance, each edge incident to a terminal vertex has the same value in every stable flow._  
The stable flow problem can be seen as a generalization of the stable allocation problem. We introduce two terminal vertices to \(G\) and connect \(s\) with all vertices representing jobs and \(t\) with all vertices representing a machine. The new edges get the quota of their non-terminal end vertex as capacity. Now, we orient all edges from \(s\) to the jobs, from the jobs to the machines and from the machines to \(t\), in order to get a directed network.