A Complete Characterization of Convexity in Flow Games

Abstract

Flow games coincide precisely with non-negative totally balanced games. We give a complete characterization of convexity for flow games with one arc per player. We prove that such a game is convex if and only if all simple source-to-sink paths can simultaneously carry their full path capacities. Equivalently, after deleting null arcs, the topology is a funnel network, and every arc can meet the combined demand of the paths through it. We provide polyhedral characterizations of convexity. In primal form, the game is convex if and only if the path-flow polytope is a box, allowing each path flow to vary independently up to its capacity. In dual form, convexity is equivalent to the existence of a minimum source-to-sink cut consisting entirely of private arcs. An arc is private if it belongs to exactly one simple source-to-sink path. We also give a polynomial-time algorithm that tests whether a given flow game is convex.