Equilibria in multiplayer multicommodity flow problems

Tamás Király, Júlia Pap


We investigate equilibria in multiplayer multicommodity flow problems where players have separate networks, and contracts regulate how certain players may hand over some of their traffic to others, which the latter have to route in their own network. This model was introduced by the authors with coauthors in an earlier paper, where it was shown that for fixed per-unit payments, equilibria always exist under some natural conditions. The present paper has three main results. First, we prove that finding an equilibrium is PPAD-complete. Second, we show a polynomial algorithm for the case when the digraph of contracts has a special structure: every strong component is a cycle. This result is based on an algorithm for finding approximate fixed points that may be of interest on its own. Finally, we show that it is possible to specify the prices in the contracts in such a way that the social optimum is in equilibrium, and furthermore the players are not motivated to cancel their contracts.

The results of this report are extended to a more general setting in report no. 2012-18.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {Equilibria in multiplayer multicommodity flow problems},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-12}

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