## 1 Introduction
### Stable Multicommodity Flows  
In this paper we present a way to include multiple commodities in the above network trading model. In the multicommodity setting, every arc has individual capacities for specific commodities as well as a cumulative capacity, and each trader has a preference order for each commodity on the possible buyers and sellers, so the preferred trading partners may be different for different commodities. In addition, for each trading pair (_i.e._, arc in \(D\)) there is a preference order on the commodities, which expresses that the pair is more inclined to trade certain goods than others. A blocking walk in our model represents a chain of transactions for a specific commodity, with which the first and the last trader of the walk would be more pleased than before (the chain may also start at the producers, or end at the consumers), and each intermediate transaction either corresponds to an arc with free capacity or it can replace the trade of a less preferred commodity. The formal definitions are as follows. The network consists of a digraph \(D=(V,A)\) with capacities \(c\in\mathbb{R}^{A}_{+}\) (these will be called _cumulative capacities_, in order to distinguish from capacities of individual commodities). There are \(\ell\) commodities, and each has its own capacity bound \(c^{j}\in\mathbb{R}^{A}_{+}\) (\(j\in[\ell]\)). Each commodity has a _source_\(s^{j}\in V\) and a _sink_\(t^{j}\in V\). Sources and sinks of different commodities may coincide, but we assume that \(c^{j}\) is 0 on every arc entering \(s^{j}\) and on every arc leaving \(t^{j}\). For each commodity \(j\in[\ell]\), there are linear orders \(<_{v}^{j}\) for each node \(v\in V\setminus\{s^{j},t^{j}\}\) on the arc set incident to \(v\). In addition, for each arc \(a\in A\) there is a linear order \(<_{a}\) on the set of commodities. The network, together with these preference orders, is called a _multicommodity network with preferences_. We say that \(f=(f^{1},\ldots,f^{\ell})\) is a feasible multicommodity flow of the network if \(f^{j}:A\rightarrow\mathbb{R}_{+}\) satisfies [PERSON]'s law at every node except at \(s^{j}\) and \(t^{j}\), \(f^{j}(a)\leq c_{a}^{j}\) for every \(a\in A\) and \(j\in[\ell]\), and \(\sum_{j=1}^{\ell}f^{j}(a)\leq c_{a}\) for every \(a\in A\). A walk \(P=(v_{1},a_{1},v_{2},a_{2},\ldots,a_{k-1},v_{k})\) is said to be _blocking with respect to commodity \(j\)_ if the following hold:  
1. each arc \(a_{i}\) is unsaturated by \(f^{j}\), that is, \(f^{j}(a_{i})<c_{a_{i}}^{j}\),
2. \(v_{1}=s^{j}\) or there is an arc \(a^{\prime}=v_{1}u\) for which \(f^{j}(a^{\prime})>0\) and \(a^{\prime}<_{v_{1}}^{j}a_{1}\),
3. \(v_{k}=t^{j}\) or there is an arc \(a^{\prime\prime}=wv_{k}\) for which \(f^{j}(a^{\prime\prime})>0\) and \(a^{\prime\prime}<_{v_{k}}^{j}a_{k-1}\),
4. if an arc \(a_{i}\) of \(P\) is saturated by \(f\), _i.e._, \(\sum_{j=1}^{\ell}f^{j}(a_{i})=c_{a_{i}}\), then there is a commodity \(j^{\prime}\) such that \(f^{j^{\prime}}(a_{i})>0\) and \(j^{\prime}<_{a_{i}}j\). The last condition expresses that a chain of transactions can be blocking even if some of them have to replace transactions of other commodities, provided that the latter are less preferred commodities for the trading pairs. A feasible multicommodity flow is called _stable_ if there is no walk blocking it. As in the single flow case, it is enough to prohibit blocking quasi-paths, since each blocking walk contains a blocking quasi-path. _Remark_. : It can be decided in polynomial time if a feasible multicommodity flow is stable. To see this, we show that for a given commodity \(j\) and nodes \(u,v\), checking whether there is a blocking walk from \(u\) to \(v\) with respect to commodity \(j\) can be done in polynomial time. Conditions (i) and (iv) restrict the possible arcs that can appear in the walk. Among these, condition (ii) determines which arcs can be the starting arcs of the walk, and condition (iii) determines the possible ending arcs.