Binding Budgets Destabilize Primal-Dual Learning in Random Games

Primal-dual learners raise a Lagrange multiplier while spending exceeds a budget and lower it while under. No prior study measures how often such learners fail to converge in random games, or for which budgets. We measure both in random two-player games with per-action costs and one budget each. Outside zero-sum games, binding budgets make more runs from almost the same start separate, with a peak at intermediate budgets. A Lyapunov exponent confirms this trend for chaos. The peak is intermediate because tighter budgets bind harder but leave fewer games feasible, and infeasible games separate less often. We trace this non-convergence to delay: because the multiplier lags spending, each strategy and its multiplier overshoot and oscillate. We prove for two actions that competitive coupling enlarges the linearized oscillation, averaged over both players' independent phases. Learning the multiplier is the main cause of the added separation: learners instead projecting strategies inside the budget almost never separate on the same feasible games. Damping or a proportional term on the multiplier restores convergence on most feasible games, the latter with far less late-run spending above the budget.