Changes

A '''blocking pathwalk''' for a flow ''f'' in a network with preferences is a sequence of vertices in ''V'' and arcs in ''A'', <math>v_1,a_1,v_2,a_2,\dots,v_k</math> such that* they are differenta_{k-1}, except possibly <math>v_1=v_k</math>,such that

* <math>a_i=v_iv_{i+1} \in A</math> (''i=1,...,k-1'') and all of these arcs are ''f''-unsaturated,* if <math>v_1 \notin \{s,t\}</math>, then there is an arc <math>v_1u \in A</math> such that <math>f(v_1u)>0</math> and <math>v_1v_2 a_1 <_{v_1} v_1u</math>,* if <math>v_k \notin \{s,t\}</math>, then there is an arc <math>uv_k \in A</math> such that <math>f(uv_k)>0</math> and <math>v_a_{k-1}v_k <_{v_k} uv_k</math>.

A flow ''f'' is '''stable''' if there is no blocking path walk for ''f''. An intuitive motivation for this definition is that the nodes represent traders, who want to buy and sell as much as possible, but also have a preference order on the other traders they can buy from or sell to (''s'' and ''t'' are special in that they are not required to buy and sell the same amount).

==Strongly Completely stable flow==

One can observe that for a stable flow ''f'' there may be a directed cycle where every arc is ''f''-unsaturated. This contradicts the intuitive explanation that every trader wants to buy and sell as much as possible, since we may increase trading along the cycle. This motivates the notion of '''strongly completely stable flow''', which is a stable flow ''f'' where every directed cycle has at least one ''f''-saturated arc. The following example is a network where there is no strongly completely stable flow.

Each arc has unit capacity, and the preferences are indicated by the numbers around the vertices. Since no arc leaves the set ''{a,b,c}'', no arc entering it can have positive flow, in particular ''sa'' has zero flow. In a strongly completely stable flow, the cycle ''abc'' must be saturated, but then ''sa'' is a blocking path, a contradiction.

<ref name="Fl">T. Fleiner, ''On stable matchings and flows'', [http://dx.doi.org/10.1007/978-3-642-16926-7_7 DOI link], [http://www.cs.elte.hu/egres/tr/egres-09-11.pdf preliminary EGRES Technical Report no. 2009-11report].</ref>