# Stable flow

Stable flows in networks with preferences were introduced by Fleiner ^{[1]}.

## Contents

## 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 ^{[1]} 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 ^{[2]} 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 ^{[3]} studied an extension to flows over time, and Cseh ^{[4]} gave polynomial time algorithms for stable flows with forced and forbidden edges.

## References

- ↑
^{1.0}^{1.1}T. Fleiner,*On stable matchings and flows*, DOI link - ↑ T. Király, J. Pap,
*Stable multicommodity flows*, DOI link, EGRES Technical Report no. 2012-13 - ↑ Á. Cseh, J. Matuschke, M. Skutella,
*Stable Flows over Time*, DOI link - ↑ Á. Cseh,
*Stable flows with restricted edges*, arXiv link