## 4 The Structure of Stable Flows  
For the stable marriage problem, it is well known about the stable marriage problem that in each stable marriage scheme, the same set of participants get married. That is, if someone does not get a marriage partner in some stable scheme, then this very person remains single in all stable marriage schemes. A generalization of this property is the rural hospital theorem by [PERSON] [12] (see also Theorem 5.13 in [13]). It is about the college model, where instead of men, we work with colleges, women correspond to students and each college has a quota on the maximum number of admissible students. In the college admission problem, it is true that if a certain college, \(c\), cannot fill up its quota in a stable admission scheme, then \(c\) receives the same set of students in any stable admission scheme (the phenomenon is named after the assignment problem of medical interns to hospitals). It seems that the rural hospital theorem cannot be generalized to the stable flow problem. It may happen in a network that a certain vertex transmits different amounts of flow in two stable flows. An example is shown in the figure, where each arc has a unit capacity. There are two stable flows: one is along path \(sact\), and the other follows path \(sbct\). Therefore, in one stable flow, vertex \(a\) transmits one unit of flow, and no flow passes through \(a\) in the other one. There is, however, a consequence of the rural hospital theorem that can be generalized; namely, that the size of a stable matching is always the same. More generally, it can also be proven that in any instance of the stable allocation problem, the size of any two stable allocations is the same. (The size of an allocation is the total amount of assignments in it). If we consider a stable allocation instance as a stable flow, then the size of the allocation corresponds to the value of the flow. **Theorem 4**. : _If network \((D,s,t,c)\) and preference orders \(<_{v}\) describe a stable flow problem and \(f_{1}\) and \(f_{2}\) are stable flows, then the value of \(f_{1}\) and \(f_{2}\) are the same. Moreover, \(f_{1}(a)=f_{2}(a)\) for any arc of \(D\) that is incident to terminal vertex \(s\) or \(t\)._  
Figure 3: Network for a stable flow. Figure 2: Stable flows have a blocking cycle. Proof. : As the value of a flow is the net amount that leaves \(s\), one can calculate it in \(G_{D}\) as the difference of the total allocation of \(s^{out}\) and \(s^{in}\). This means that the second part of the theorem directly implies the first one. Therefore, below, we prove only the second part of Theorem 4. Let \(g_{1}\) and \(g_{2}\) be the canonical representations of flows \(f_{1}\) and \(f_{2}\) defined in Lemma 3. As there is no edge between \(s^{out}\) and \(s^{in}\), the definition of \(q(s)\) implies that both \(s^{out}\) and \(s^{in}\) are \(g_{1}\)-unsaturated. Hence, property Equation (13) can hold neither for \(s^{in}\) nor for \(s^{out}\). However, Theorem 1 implies that \(g_{1}\) and \(g_{2}\) are \(\leq_{s^{out}}\) and \(\leq_{s^{in}}\)-comparable. Therefore, property Equation (12) must be true for flows \(g_{1}\) and \(g_{2}\) for both vertices \(v=s^{out}\) and \(v=s^{in}\). In particular, \(g_{1}(a)=g_{2}(a)\) holds for each arc, \(a\), incident to \(s\). This shows the second part of the Theorem for \(s\). The argument for \(t\) is analogous to the above one. As we have seen in Theorem 1, stable allocations have a lattice structure. Based on the connection of stable allocations and stable flows described in Lemma 3, we can prove that stable flows of a network with preferences also form a natural lattice. Therefore, assume that \(f\) is a stable flow in network \((D,s,t,c,)\) with preferences, and let stable allocation \(g_{f}\) of \(G_{D}\) be the canonical representation of \(f\), as in the proof of Lemma 3. Observe that any nonterminal vertex, \(v\), of \(D\), exactly one of \(g_{f}(v^{in}v^{out})\) and \(g_{f}(v^{out}v^{in})\) is positive by the choice of \(q\) and \(g_{f}\).