Payoff-Based Dynamics for Multiplayer Weakly Acyclic Games

TLDR

Repeated multiplayer games with payoff‑based adjustment processes, where players only observe their own actions and noisy payoffs, are studied in the context of weakly acyclic games relevant to multiagent cooperative control. The authors introduce three payoff‑based processes and prove that, after enough stages, players’ actions converge to a Nash equilibrium with arbitrarily high probability. They further demonstrate that by adding tolls and incentives to utility functions in congestion games, a centralized objective can be enforced as a Nash equilibrium. A simulation of distributed routing over a network illustrates the effectiveness of these methods.

Abstract

We consider repeated multiplayer games in which players repeatedly and simultaneously choose strategies from a finite set of available strategies according to some strategy adjustment process. We focus on the specific class of weakly acyclic games, which is particularly relevant for multiagent cooperative control problems. A strategy adjustment process determines how players select their strategies at any stage as a function of the information gathered over previous stages. Of particular interest are “payoff-based” processes in which, at any stage, players know only their own actions and (noise corrupted) payoffs from previous stages. In particular, players do not know the actions taken by other players and do not know the structural form of payoff functions. We introduce three different payoff-based processes for increasingly general scenarios and prove that, after a sufficiently large number of stages, player actions constitute a Nash equilibrium at any stage with arbitrarily high probability. We also show how to modify player utility functions through tolls and incentives in so-called congestion games, a special class of weakly acyclic games, to guarantee that a centralized objective can be realized as a Nash equilibrium. We illustrate the methods with a simulation of distributed routing over a network.