## 2 Existence of a Stable Multicommodity Flow
\(\Diamond\)  
We obtained that \(\overline{x}\) is positive only on the arcs (that is, on quasi-paths of length 1), and by Claim 2.3, \(\overline{x}_{a}^{j}=\overline{y}_{a}^{j}\) for every arc \(a\) and every \(j\in[\ell]\). By inequalities (4) and (5), we have  
\[\overline{x}^{j}(\delta^{out}(v))\leq\overline{y}^{j}(\delta^{in}(v))= \overline{x}^{j}(\delta^{in}(v))\leq\overline{y}^{j}(\delta^{out}(v))= \overline{x}^{j}(\delta^{out}(v))\]  
for every \(v\in V\setminus\{s^{j},t^{j}\}\), so \(\overline{y}^{j}\) is a flow. By inequality (3), it satisfies the capacity constraints for commodity \(j\), and by inequality (6), \(\overline{y}\) satisfies the cumulative capacity constraints, so it is a feasible multicommodity flow. We are done by proving our last claim. **Claim 2.5**. : _No quasi-path blocks \(\overline{y}\) with respect to any commodity._  
Proof. : Let \(P=(v_{1},a_{1},\ldots,v_{k})\) be an arbitrary quasi-path and \(j\) an arbitrary commodity. Since \((\overline{x},\overline{y})\) is a multicoloured vertex, there is a tight inequality of colour \(x_{P}^{j}\). If it is of the form (3), then the arc \(a\) is saturated for commodity \(j\), so \(P\) does not block \(\overline{y}\) with respect to commodity \(j\). If it is of the form (4) for node \(v_{1}\), \(\mathcal{P}^{\prime}\subseteq\mathcal{P}_{v_{1}}^{\mathrm{out}}\) and \(\delta^{\prime}\subseteq\delta^{in}(v_{1})\), then \(a^{\prime}\
otin\mathcal{P}^{\prime}\) whenever \(a^{\prime}\in\delta^{out}(v_{1})\) and \(a^{\prime}<_{v_{1}}^{j}a_{1}\). Thus \(\overline{x}_{a^{\prime}}^{j}=0\), because if \(\overline{x}_{a^{\prime}}^{j}\) was positive, then adding \(x_{a^{\prime}}^{j}\) to this tight inequality would not hold for \((\overline{x},\overline{y})\), although it is also an inequality of the system. This implies that \(P\) does not block the flow \(\overline{y}\) with respect to commodity \(j\). The case when the tight inequality of colour \(x_{P}^{j}\) is of type (5) is analogous. Finally, if the inequality of colour \(x_{P}^{j}\) is of type (6), then the arc \(a\) is saturated, and furthermore \(a\
otin\mathcal{P}_{j^{\prime}}^{\prime}\) whenever \(j^{\prime}<_{a}j\) since \(x_{P}^{j}\) is selected as colour. This implies that \(\overline{x}_{a}^{j^{\prime}}=0\) whenever \(j^{\prime}<_{a}j\): if \(\overline{x}_{a}^{j^{\prime}}>0\) would hold, then by adding \(a\) to \(\mathcal{P}_{j^{\prime}}^{\prime}\) we would obtain an inequality that is violated by \((\overline{x},\overline{y})\). Again, this means that \(P\) is not blocking for commodity \(j\). \(\Diamond\)  
We obtained that there is no blocking quasi-path, so \(\overline{y}\) is a stable multicommodity flow. We remark that even if the capacities are integer, there might be no integer stable multicommodity flow. In fact, for any integer \(N\) there is an instance where there is no stable solution with denominators at most \(N\). As an example, consider the network consisting of nodes \(v_{1},\ldots,v_{n}\) and arcs \(v_{i}v_{i+1}\) (\(i\in[n]\)), where we use the notation \(v_{n+1}=v_{1}\). There are \(n\) commodities; the sources and sinks are defined by \(s^{j}=v_{j+1}\), \(t^{j}=v_{j}\), and the capacity \(c^{j}\) is 1 on all arcs except for \(v_{j}v_{j+1}\) where it is 0. This means that commodity \(j\) has a unique quasi-path from \(s^{j}\) to \(t^{j}\), namely \((v_{j+1},v_{j+2},\ldots,v_{1},\ldots,v_{j})\), so the preference orders at the nodes do not play any role. The cumulative capacity \(c\) is 1 everywhere. The preference order at arc \(a=v_{i}v_{i+1}\) is defined by \(i-1>_{a}\cdots>_{a}1>_{a}n>_{a}\cdots>_{a}i+1\) (commodity \(i\) does not appear in the ordering because it has capacity 0 on this arc). We claim that the only stable multicommodity flow is obtained by setting \(f^{j}(a)=\frac{1}{n-1}\) on every arc \(a\) except for \(v_{j}v_{j+1}\).