Stable multicommodity flows
type: Item
instance of: scholarly article
title: Stable multicommodity flows
zbMATH Open document ID: 1461.91198
author: Tamás Király
author: Júlia Pap
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 91B68
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C21
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 7042156
zbMATH Keywords: stable matching problem
zbMATH Keywords: stable flows
zbMATH Keywords: multicommodity flows
zbMATH Keywords: PPAD-completeness
zbMATH Keywords: Sperner's lemma
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6010161
OpenAlex ID: W1984454127
cites work: On Stable Matchings and Flows
cites work: The Stable Allocation (or Ordinal Transportation) Problem
cites work: Stable flows over time
cites work: A note on kernels and Sperner's Lemma
cites work: Reducibility among Fractional Stability Problems
DOI: 10.3390/A6010161
description: scientific article; zbMATH DE number 7042156