## 2 Preliminaries
If Equation (6) holds with equality, then we say that player \(v\) is \(g\)_-saturated._ An allocation is _stable_ if for any edge, \(wf\), of \(E\), at least one of the following properties hold:  
\[\text{either }g(wf)=p(wf)\] (7) (the particular employment is realized with full capacity) or \[\sum_{wf^{\prime}\leq wf}g(wf^{\prime})=q(w)\text{, that is, worker $w$ is $g$-saturated and $w$ does not} \tag{8}\] \[\text{prefer }f\text{ to any of his employers (we say that $wf$ is $g$-dominated at $w$)}\] or \[\sum_{wf\leq_{f}wf}g(w^{\prime}f)=q(f)\text{, that is, firm $f$ is $g$-saturated and $f$ does not}\] (9) \[v_{2},v_{3},\ldots,v_{k-1}\text{ are nonterminal vertices and}\]0  
Note that Equations (8) and (9) imply that if \(g\) is a stable allocation, then for each firm, \(f\), and each worker, \(w\):  
\[v_{2},v_{3},\ldots,v_{k-1}\text{ are nonterminal vertices and}\]1 \[v_{2},v_{3},\ldots,v_{k-1}\text{ are nonterminal vertices and}\]2  
If \(g_{1}\) and \(g_{2}\) are allocations and \(w\in W\) is a worker, then we say that _allocation \(g_{1}\) dominates allocation \(g_{2}\) for worker \(w\)_ (in notation, \(g_{1}\leq_{w}g_{2}\)) if one of the following properties is true:  
\[v_{2},v_{3},\ldots,v_{k-1}\text{ are nonterminal vertices and}\]3 \[v_{2},v_{3},\ldots,v_{k-1}\text{ are nonterminal vertices and}\]4 (13) \[v_{2},v_{3},\ldots,v_{k-1}\text{ are nonterminal vertices and}\]5  
That is, if \(w\) can freely choose his allocation from \(\max(g_{1},g_{2})\), then \(w\) would choose \(g_{1}\), either because \(g_{1}\) and \(g_{2}\) are identical for \(w\) or because \(w\) is saturated in both allocations and \(g_{1}\) represents \(w\)'s choice out of \(\max(g_{1},g_{2})\). By exchanging the roles of workers and firms, one can define domination relation \(\leq_{f}\) for any firm, \(f\), as well. For any stable allocation problem, one can design a network \((D,s,t,c)\), such that \(V(D)=\{s,t\}\cup W\cup F\), \(A(D)=\{sw:w\in W\}\cup\{ft:f\in F\}\cup\{wf:wf\in E\}\), and \(c(sw)=q(w)\), \(c(ft)=q(f)\) and \(c(wf)=p(wf)\) for any worker \(w\) and firm \(f\). That is, we consider the underlying bipartite graph, orient its edges from \(W\) to \(F\), add new vertices, \(s\) and \(t\), with an arc from \(s\) to each worker-node and an arc from each firm-node to \(t\), and capacities are given by the original edge-capacities and the corresponding quotas. Preference orders \(<_{v}\) on the arcs incident to \(v\) are induced by the preference order on the corresponding edges incident to \(v\), or, if there is no such edge, then it is a trivial linear order. It is straightforward to see from the definitions that \(g\) is a stable allocation if and only if there exists a stable flow \(f\), such that \(g(e)=f(\vec{e})\) holds for each edge, \(e\in E\), where \(\vec{e}\) is the arc that corresponds to edge \(e\). The stable allocation problem was introduced by [PERSON] and [PERSON] as a certain \"continuous\" version of the stable marriage problem in [3]. It turned out that a natural extension of the deferred acceptance algorithm of [PERSON] and [PERSON] [1] works for the stable allocation problem, and the structure of stable allocations is similar to that of stable marriages. Below, we state the results of Baiou-Balinski. **Theorem 1** (See [PERSON] and [PERSON] [3]). : _1. In any stable allocation problem instance described by \(W,F,E,p\) and \(q\), there exists a stable allocation, \(g\). Moreover, if \(p\) and \(q\) are integral, then there exists an integral stable allocation, \(g\)._  
_2. If \(g_{1}\) and \(g_{2}\) are stable allocations and \(v\in W\cup F\), then \(g_{1}\leq_{v}g_{2}\) or \(g_{2}\leq_{v}g_{1}\) holds._  
_3. Stable allocations have a natural lattice structure. Namely, if \(g_{1}\) and \(g_{2}\) are stable allocations, then \(g_{1}\lor g_{2}\) and \(g_{1}\wedge g_{2}\) are stable allocations, where:_  
\[(g_{1}\lor g_{2})(wf) =\left\{ \begin{array}{ll}g_{1}(wf)&\mbox{if }g_{1}\leq_{w}g_{2}\\ g_{2}(wf)&\mbox{if }g_{2}\leq_{w}g_{1}\end{array} \right. \tag{14}\] \[(g_{1}\wedge g_{2})(wf) =\left\{