Martins, Kara publish population games research on excess payoff evolutionary dynamics

A new paper by ECE and ISR researchers in IEEE Control Systems Letters shows that for a considered protocol class, established conditions that ensure convergence under strategy-independent revision rates may be violated when the revision rates are strategy-dependent. The authors also prove that a minor, well-motivated modification of the considered protocol class satisfies these conditions for any strategy-dependent revision rates.

Excess Payoff Evolutionary Dynamics with Strategy-Dependent Revision Rates: Convergence to Nash Equilibria for Potential Games was written by Professor Nuno Martins (ECE/ISR) and his Ph.D. advisee Semih Kara, and is available through IEEE Early Access.

Evolutionary dynamics in the context of population games models the dynamic non-cooperative strategic interactions among many nondescript agents. Each agent follows one strategy at a time from a finite set. A game assigns a payoff to each strategy as a function of the so-called population state vector, whose entries are the proportions of the population adopting the available strategies. Each agent repeatedly revises its strategy according to a revision protocol.

In their paper, Kara and Martins focus on a well-known class of protocols that prioritizes strategies with higher excess payoffs relative to a population-weighted average. In contrast to existing work for these protocols, they allow each agent’s revision rate to depend explicitly on its current strategy. Motivated by applications and relevance to distributed optimization, the authors focus on potential games and investigate the population state’s convergence to the game’s Nash equilibria.

The researchers consider the mean population state resulting from potential games and Excess Payoff Target (EPT) protocols and analyze the effects of strategy-dependent revision rates on its inﬁnite-horizon properties. They investigate the Nash Stationarity (NS) and Positive Correlation (PC) properties of the Evolutionary Dynamics Model (EDM) induced by EPT protocols. Contrary to the conclusions attained under identical revision rates, they show the existence of EPT protocols and (strategy-dependent) revision rates that lead to EDM instances that violate (NS) or (PC). They also propose a modiﬁcation of the EPT class, which they call “sign preserving rate-modiﬁed EPT (RM-EPT) protocols,” and show that the resulting EDM satisﬁes (NS) and (PC) under any revision rates. Finally, Martins and Kara use this result to derive a guarantee for the convergence of the mean population state to Nash equilibria.

The research is funded by the Air Force Office of Scientific Research.

Published December 20, 2022