|
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 www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2012}, |
| NUMBER | = | {TR-2012-12} |