**Monday, 15:45 - 16:10 h, Room: H 3021**

**Tamás Király**

Multiplayer multicommodity flows

**Coauthors: Attila Bernáth, Mádi-Nagy Gergely, Pap Gyula, Pap Júlia**

**Abstract:**

We investigate the Multiplayer Multicommodity Flow Problem, a version of the multicommodity flow problem where players have different subnetworks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value.

We show that the social optimum can be computed by linear programming. In contrast, an equilibrium solution, although it always exists under some natural conditions, is PPAD-hard to find. We analyze hardness in relation to the structure of the digraph formed by the contracts between players, and prove that an equilibrium can be found in polynomial time if every strongly connected component of this digraph is a cycle.

Talk 2 of the invited session Mon.3.H 3021

**"Equilibria and combinatorial structures"** [...]

Cluster 2

**"Combinatorial optimization"** [...]