Stable flow

Stable flows in networks with preferences were introduced by Fleiner .

Network with preferences

A network with preferences is given by

• a digraph D=(V,A),
• two special nodes [math]s \in V[/math] and [math]t \in V[/math],
• a capacity function [math]c:A \to {\mathbb R}_+[/math],
• for each vertex [math]v \in V[/math], a preference order [math]\leq_v[/math] on the arcs incident to v.

Note that we do not require the in-degree of s and the out-degree of t to be 0. A flow is a function [math]f:A \to {\mathbb R}_+[/math] such that [math]f(a) \leq c(a)[/math] for every [math]a \in A[/math] and each node [math]v \in V \setminus\{s,t\}[/math] satisfies Kirchhoff's law: [math]\sum_{uv \in A} f(uv)=\sum_{vw \in A} f(vw).[/math]

An arc [math]a \in A[/math] is f-saturated if f(a)=c(a); it is f-unsaturated otherwise.

Stable flow

A blocking walk 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,a_{k-1},v_k[/math], such that

• [math]v_i \in V\setminus\{s,t\}[/math] (i=2,...,k-1),
• [math]a_i=v_iv_{i+1}[/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)\gt0[/math] and [math]a_1 \lt_{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)\gt0[/math] and [math]a_{k-1} \lt_{v_k} uv_k[/math].

A flow f is stable if there is no blocking 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).

Fleiner proved that every network with preferences has a stable flow.

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 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 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 completely stable flow, the cycle abc must be saturated, but then sa is a blocking path, a contradiction.

Generalizations

Király and Pap generalized the model to stable multicommodity flows. They showed that there always exists a stable (fractional) multicommodity flow, but, contrary to the stable flow problem, it is PPAD-complete to find one. Cseh, Matuschke, and Skutella studied an extension to flows over time, and Cseh gave polynomial time algorithms for stable flows with forced and forbidden edges.