|
Algorithms 2013
Stable Multicommodity FlowsDOI: 10.3390/a6010161 Keywords: stable matching problem, stable flows, multicommodity flows, PPAD-completeness, Sperner’s Lemma Abstract: 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.
|