AI summaryⓘ
The authors examine a type of game where players share resources and face costs that depend on how much everyone uses them. They identify precise mathematical conditions on the cost functions that ensure certain stability and predictability in the game's outcomes, focusing on monotonicity properties. These conditions also relate to how a particular algorithm (Frank--Wolfe dynamics) behaves when players adjust their strategies over time. Interestingly, the authors find that even without these conditions, some stability still holds for games played on simple strategy sets. Overall, their work connects game theory, optimization, and learning dynamics with clear criteria for when stable behavior occurs.
atomic splittable congestion gamesmonotonicityvariational inequalitycurvature inequalitycost functionsFrank--Wolfe dynamicsEuclidean regularizationstrategy spaceslocal stabilityexponential stability
Abstract
We study universal monotonicity and Frank--Wolfe stability properties for atomic splittable congestion games. Specifically, we characterize the largest resource cost class for which the associated variational inequality operator is monotone for every game. This characterization is given by a curvature inequality involving the first two derivatives of the allowable cost functions and the number of players. Our framework yields exact characterizations for universal monotonicity, strict monotonicity, and strong monotonicity; the strict and strong variants require corresponding stricter curvature conditions. We then draw a perhaps surprising connection to learning dynamics in atomic splittable congestion games. We show that the very same curvature condition also characterizes universal \emph{local and global stability} of the Euclidean-regularized Frank--Wolfe dynamics on arbitrary convex strategy spaces, provided the cost class is closed under positive affine transformations. Finally, we study games on simplices and show that an interior equilibrium of the regularized Frank--Wolfe dynamic is locally exponentially stable, even without the curvature condition.