TR-2012-13

Stable multicommodity flows

Tamás Király, Júlia Pap

Published in:
Algorithms 6:1 (2013), 161-168. DOI link

We extend the stable flow model of Fleiner to multicommodity flows. In addition to the preference lists of agents on trading partners for each commodity, every trading pair has a preference list on the commodities that the seller can sell to the buyer. A blocking path (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded on the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.

• July_2012

Bibtex entry:

@techreport{egres-12-13,

AUTHOR	=	{Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE	=	{Stable multicommodity flows},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-13}

}