Robust bounds on iterative updates improve game and traffic algorithms
A Robust Perceptron Cycling Theorem and Applications
Computer Science and Game Theory
Summary
The authors studied a mathematical rule called the perceptron cycling theorem, which helps ensure sequences of updates don’t grow too large. They proved a stronger, more flexible version that works even with imperfect update choices. This new understanding helps improve algorithms used in game theory, traffic routing, and optimization problems by guaranteeing their steps remain stable and efficient. Their results extend previous work to more general situations where the problem’s math isn’t perfectly symmetric.
What this means in practice
- •For game designers: Guarantee stable best-response calculations in strongly stable linear population games for better strategic game design.
- •For traffic engineers: Ensure convergence and stability in traffic assignment models with asymmetric cost maps for improved routing and planning.
Authors
Tobias Harks
Abstract
The classical perceptron cycling theorem of Block and Levin \cite{BlockLevin1970} bounds correction sequences whose selected updates come from a finite set and have nonpositive inner product with the current state. We prove a robust variant for additive trajectories $z_{k+1}=z_k+u_k$, for all integers $k\geq0$, with increments in a finite set $U\subset E$, where $E$ is a finite-dimensional real inner-product space and $0\in\conv U$. Let $A\colon E\to E$ have positive-definite symmetric part, without requiring symmetry, and let $B\geq0$. If each $u_k$ is a $B$-approximate minimizer of $u\mapsto\ip{Az_k}{u}$ over $U$, then $\sup_{k\geq0}\norm{z_k}\leq C(1+\norm{z_0}+B)$, with $C=C(E,U,A)$ independent of the initial state, $B$, and all admissible update choices. Our central algorithmic consequence is an $O(k^{-1})$ last-iterate norm bound for harmonic vertex-returning Frank--Wolfe for affine strongly monotone variational inequalities on polytopes with relatively interior solutions. It extends the quadratic Frank--Wolfe/herding guarantee of Bach, Lacoste-Julien, and Obozinski \cite[Section~4.2]{BachEtAl2012} to nonsymmetric affine operators. We apply this bound to empirical best responses in strongly stable linear population games, quadratically regularized bilinear saddle problems, and traffic assignment with coercive affine asymmetric cost maps.