A Complete Characterization of Convexity in Flow Games
This provides a foundational characterization for cooperative game theory, specifically for network flow problems, addressing a long-standing gap in the literature.
The paper tackles the open problem of characterizing convexity in flow games, showing that a flow game is convex if and only if the underlying network is acyclic and has an arc cover by s-t paths disjoint at bottleneck arcs, with verification possible via a polynomial-time algorithm.
We investigate the convexity of cooperative games arising from network flow problems. While it is well-known that flow games are totally balanced, a complete characterization of their convexity has remained an open problem. In this paper, we provide a necessary and sufficient characterization of the networks that induce convex flow games. We show that a flow game is convex if and only if the underlying network is acyclic and admits an arc cover by $s$-$t$ paths that are disjoint at their bottleneck arcs. Specifically, every bottleneck arc must belong to exactly one path, and every non-bottleneck arc must possess sufficient capacity. To derive this characterization, we establish six structural properties of convex flow games. Additionally, we prove that our characterization can be verified efficiently, yielding a polynomial-time algorithm to recognize convex flow games. Since the class of flow games coincides exactly with the class of non-negative totally balanced games, as established by Kalai and Zemel (1982), our structural and algorithmic characterization applies to all such games, provided they are represented in their network form.