## 2 Stable Flows
### Algorithms to Find Stable Flows  
The stable allocation problem can be solved in polynomial time [2,4]. As mentioned in the introduction, the augmenting path algorithm is not always the most efficient way to find stable allocations; the Gale-Shapley algorithm terminates faster in some cases. It can be run on \(\mathcal{I}^{\prime}\) in order to give a stable allocation, which yields a stable flow on \(\mathcal{I}\). Note that this holds for irrational data, as well. The fact that this method can be directly applied to instance \(\mathcal{I}\) is briefly mentioned by [PERSON] [6]. In the following, we will show how to interpret the direct application of the Gale-Shapley algorithm on the network as a preflow-push-type algorithm and prove its correctness. We will provide two variants, a basic preflow-push variant that is easy to understand and one that resembles the alternating proposal/refusal scheme of the original Gale-Shapley algorithm. Proposal and refusal pointers:For each vertex, \(v\in V(D)\), the algorithm maintains two pointers, \(p[v]\) and \(r[v]\). The first pointer, \(p[v]\), iterates through \(v\)'s list of outgoing edges from the highest to the lowest priority edge. It points to that edge along which \(v\) is currently willing to offer more flow. Likewise, \(r[v]\) iterates through \(v\)'s list of incoming edges from the lowest to the highest priority edge. It points to that edge that \(v\) is going to refuse next, if necessary. For technical reasons, we introduce one more element to each preference list: after passing through all neighbors, \(p[v]\) reaches a state encoded by \(p[v]=0\). This means that \(v\) cannot submit any more offers. Likewise, \(r[v]=0\) initially, as \(v\) has no intention to refuse flow in the beginning. Initialization:The algorithm starts by saturating all edges leaving the terminal set, _i.e._, \(f(sv)=c(sv)\) for all \(sv\in E(D)\) with \(s\in S\). We define the _excess_ of a vertex, \(v\), w.r.t. \(f\), by \(\mathrm{ex}(v,f):=\sum_{uv\in\delta^{-}(v)}f(uv)-\sum_{vw\in\delta^{+}(v)}f( vw)\), where \(\delta^{-}(v)\) denotes the set of incoming edges, while \(\delta^{+}(v)\) stands for the outgoing ones. Note that \(f\) initially is not a feasible flow, as \(\mathrm{ex}(v,f)>0\) for some non-terminal vertices, \(v\in V(D)\setminus S\)--we will call such vertices _active_. Preflow-push variant:The algorithm iteratively selects an active vertex, \(v\in V(D)\), and pushes as much flow as possible along \(p[v]\), advancing the proposal pointer whenever the edge is saturated or an already refused edge is encountered. If \(p[v]\) reaches the zero-state before all excessive flow has been pushed out of the vertex, it continues by decreasing the flow on the incoming edge, \(r[v]\), advancing therefusal pointer whenever the flow on the edge reaches zero. After a push operation, the excess of the vertex is zero, and another active vertex is selected. The algorithm terminates once there is no active vertex left. For a pseudo-code listing of this preflow-push approach, see Algorithm 1. ```
Initialize \(p,r\). Saturate all edges, leaving \(S\). while\(\exists v\in V(D)\setminus S:\ \mathrm{ex}(v,f)>0\)do while\(\mathrm{ex}(v,f)>0\)do if\(p[v]\
eq 0\)then  propose(\(p[v]\)) else  refuse(\(r[v]\)) endif endwhile endwhile
```  
**Algorithm 1** Preflow-push algorithm. Simultaneous variant:An alternative variant that resembles the Gale-Shapley algorithm more closely can be obtained by performing alternating rounds of proposal and refusal steps, respectively, on all active vertices simultaneously (_cf._, Algorithm 2). This variant of the algorithm will prove useful when analyzing stable flows in a time-expanded network later in this paper. ```
Initialize \(p,r\). Saturate all edges, leaving \(S\). while\(\exists v\in V(D)\setminus S:\ \mathrm{ex}(v,f)>0\)do for all\(v\in V(D):\ p[v]\
eq 0\)do  propose(\(p[v]\)) endfor for all\(v\in V(D):\ p[v]=0\)do  refuse(\(r[v]\)) endfor endwhile
```  
**Algorithm 2** Simultaneous push algorithm. ```
Initialize \(p,r\). Saturate all edges, leaving \(S\).