Stable multicommodity flows

Tamás Király, Júlia Pap

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


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.

Previous version can be found here.

Bibtex entry:

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

Last modification: 13.3.2018. Please email your comments to Tamás Király!