Stable Multicommodity Flows

Algorithms

Tamás Király¹ 

关键词: stable matching problem;    stable flows;    multicommodity flows;    PPAD-completeness;    Sperner’s Lemma;   

DOI  :  10.3390/a6010161

来源: mdpi

【 摘 要 】

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 walk (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded along the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.