Monotonicity, Uniqueness and Frank--Wolfe Dynamics in Atomic Splittable Congestion Games

Abstract

We study atomic splittable congestion games with $n\ge 2$ players and nondecreasing $C^2$ resource costs $f$ with convex $x\mapsto xf(x)$. We characterize the largest resource cost class for which the Nash equilibrium is unique. This characterization combines a curvature inequality involving the first two derivatives and the number of players with strict increase of the scalar marginal costs $x\mapsto f(x)+x{f}^{\prime }(x)$. The proof rests on first characterizing the largest resource cost classes for which the associated variational inequality operator is monotone, strictly monotone, or strongly monotone. We also draw a perhaps surprising connection to learning dynamics: the same curvature inequality characterizes universal local and global stability of Euclidean-regularized Frank--Wolfe dynamics on arbitrary compact convex strategy spaces. Both the uniqueness and stability characterizations assume closure under positive affine transformations. Both characterizations remain exact for network games; the necessity constructions use acyclic directed graphs whose arc costs can be chosen strictly positive. Finally, we show that on parallel-link networks, every interior equilibrium of the regularized Frank--Wolfe dynamics is locally exponentially stable even without the curvature condition.

38 pages, added characterization on uniqueness and network representations