## 2 Preliminaries  
Recall that by a _network_, we mean a quadruple \((D,s,t,c)\), where \(D=(V,A)\) is a digraph, \(s\) and \(t\) are different nodes of \(D\), and \(c:A\to\mathbb{R}_{+}\) is a function that determines the capacity, \(c(a)\), of each arc, \(a\), of \(A\). (Sometimes it is assumed that no arc enters vertex \(s\) and no arc leaves vertex \(t\). We do not require this assumption for the reason that this way, we prove a more general result. Still, if the reader finds it difficult to follow the argument, it might be convenient to consider the source-sink case and skip the irrelevant parts.) Vertices \(s\) and \(t\) are called _terminals_; other vertices of \(G\) are _nonterminals_. A _flow_ of the network \((D,s,t,c)\) is a function \(f:A\to\mathbb{R}\), such that the capacity condition \(0\leq f(a)\leq c(a)\) holds for each arc, \(a\), of \(A\) and each nonterminal vertex, \(v\), of \(D\) satisfies the Kirchhoff law: \(\sum_{u:uv\in A}f(uv)=\sum_{uvu\in A}f(vu)\), that is, the amount of the incoming flow equals the amount of the outgoing flow for \(v\). Note that there is no conceptual difference between terminals \(s\) and \(t\): both are ordinary vertices that are exempt from [PERSON]'s law. (It seems that this fact is not completely clear for many. Perhaps, the reason is that when network flows are taught, it is usually emphasized that the role of \(s\) and \(t\) are different: the former is \"the source\", and the latter one is \"the sink\". To convince the skeptic, it is illuminative to find a formula for the _minimum_ value of an \(st\)-flow in a network. Surprisingly to some, this minimum is not zero in general.) A _network with preferences_ is a network \((D,s,t,c)\) along with a preference order, \(\leq_{v}\), for each vertex, \(v\), such that \(\leq_{v}\) is a linear order on the arcs that are incident to \(v\), and we say that \(v\) prefers \(a\) to \(a^{\prime}\) if \(a\leq_{v}a^{\prime}\) holds. (Note that preference orders \(\leq_{s}\) and \(\leq_{t}\) of the terminals do not play a role in the notion of stability, as we shall never compare an incoming and an outgoing arc of the same vertex. Therefore, we may think that for each nonterminal vertex, \(v\), there are two independent preference orders: one is on the incoming arcs and the other one on the outgoing ones.) For a given network with preferences, it is convenient to think that vertices of \(D\) are \"players\" that trade with a certain good. An arc \(uv\) of \(D\) from player \(u\) to player \(v\) with capacity \(c(uv)\) represents the possibility that player \(u\) can supply at most \(c(uv)\) units of goods to player \(v\). A \"trading scheme\" is described by a flow, \(f\), of the network, as for any two players, \(u\) and \(v\), flow \(f(uv)\) determines the amount of goods that \(u\) sells to \(v\). Everybody in the market would like to trade as much as possible, that is, each player \(v\) strives to maximize the amount of flow through \(v\). In particular, if flow \(f\) allows player \(v\) to receive some more flow (that is, there are goods on the market offered to \(v\) and \(v\) is happy to buy them) and \(v\) can also send some more flow (_i.e._, some other player would be happy to buy more goods from \(v\)), then flow \(f\) does not correspond to a stable market situation. Another instability occurs when \(vw\leq_{v}vu\) (player \(v\) prefers to sell to \(w\) rather than to \(u\)), and flow \(f\) is such that \(w\) would be happy to buy more goods from \(v\) (that is \(f(vw)<c(vw)\), and \(w\) has some extra selling opportunity); moreover, \(f(vu)>0\) (\(v\) sells a positive amount of goods to \(u\)). In this situation, \(v\) would send flow rather to \(w\) than to \(u\); hence, this cannot occur in a stable market situation. A similar instability can be described if we talk about entering arcs instead of outgoing ones, that is, if we exchange the roles of buying and selling. To formalize our concept of stability, we need a few definitions.