Decentralized Optimal Equilibrium Learning Over Dynamic Networks

Seref Taha Kiremitci; Muhammed O. Sayin

cs.GTSep 13, 2026

Decentralized Optimal Equilibrium Learning Over Dynamic Networks

Authors: Seref Taha Kiremitci, Muhammed O. Sayin

Organizations: Department of Electrical and Electronics Engineering, Bilkent University, Ankara, Türkiye.

Abstract

This paper studies decentralized learning of socially optimal equilibria in finite normal-form games over dynamic communication networks. Each agent observes only its own realized payoffs, does not know the game a priori, and can communicate only with time-varying neighbors using low-bandwidth messages. We propose networked decentralized optimal equilibrium learning dynamics in which agents generate randomized semantic content/discontent signals from local payoff comparisons and exchange time-stamped time-stacked tables rather than raw actions, payoff information or local estimates/parameters. The method combines table fusion with temporal majority reconstruction to mitigate dynamic communication while preserving fully decentralized operation. We establish finite-time logarithmic regret guarantees, with an in-phase exploration perturbation, for optimal equilibrium selection under utilitarian and proportional-fair social welfare objectives. Simulation results further show that the proposed approach can effectively select socially desirable equilibria over dynamic communication networks.

Figures & tables

Panel of Figure 1 — Fig. 1 : An illustration of decentralized learning over dynamic communication networks. Layers depict time-varying topology at instances $k-2,k-1,k$ .

Fig. 2 : A figurative illustration of spatial table fusion and temporal table processing procedures for agent

i=1

at phase

k

over the four-agent communication network depicted at the top-right corner. The agent construct the table

o_{(k)}^{i}

based on the current content/discontent signal

s_{(k)}^{i}

and the previous beliefs

\{\hat{s}_{(k),(k-l)}^{i,j}\}

about the content/discontent signals of all agents

j\in\mathcal{N}

and at previous phases

l=k-m+1,\ldots,k-1

. The agent receives the neighbor tables

\{o_{(k)}^{j}\}_{j\in\mathcal{N}_{(k)}^{i}}

and fuse them with the local table

o_{(k)}^{i}

to compute

\overline{o}_{(k)}^{i}

. Then, the agent uses

\overline{o}_{(k)}^{i}

and

\{\overline{o}_{(k-l)}^{i}\}_{l=1}^{n-1}

to determine whether all agents were content at phase

k-n+1

through majority polling.

Panel of Table 3 — Algorithm 1 Networked-DOEL Dynamics

Panel of Figure 4 — Fig. 3 : Comparison of the proposed networked learning scheme for optimal equilibrium selection and social welfare maximization under three communication scenarios. Panels (a) and (c) use utilitarian welfare (sum of local payoffs), while panels (b) and (d) use proportional-fair welfare (sum of log-payoffs). Scenario 1 is a fully connected baseline (ideal communication), i.e., the same communication setting as the original DOEL dynamics. Scenario 2 and Scenario 3 use the restricted Erdős–Rényi graph (edge probability $p=0.2$ , conditioned on connectivity) with per-phase independent link drops with probability $0.1$ for each edge, and differ in the table depth: $m=5$ ( Scenario 2 ) versus $m=3$ ( Scenario 3 ), so that $m$ is above versus possibly below the backbone diameter $D\in\{3,4\}$ . The dashed horizontal line indicates the target welfare level; curves show averages over 50 runs with shaded $\pm 1$ standard deviation.

Decentralized Learning

Decentralized learning trains models through local computation and peer-to-peer information exchange rather than relying on a central coordinator.

See all 101 papers

Decentralized Bandit Learning of Markov Perfect Equilibria
Oct 9, 2026Felix Höfer, H. Mete SonerBandit Learning Nash Equilibrium
Booth School of Business, The University of Chicago, Chicago, IL, 60637, USA · Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 08540, USA
Paradoxes of Game Theoretic Equilibria and Price of Anarchy
Jul 13, 2026Georgios Piliouras, Ian Gemp, Siqi Liu +1Nash Equilibrium Game Theory
Google Deepmind, UK
Decentralized Parameter-Free Online Learning with Compressed Gossip
May 27, 2026Tomas Ortega, Hamid JafarkhaniOnline Convex Optimization Decentralized Learning
Center for Pervasive Communications & Computing and EECS Department, University of California, Irvine, Irvine, CA 92697 USA

Oct 9, 2026J/K move · Enter open · S save

Decentralized Bandit Learning of Markov Perfect Equilibria

Felix Höfer, H. Mete Soner

Booth School of Business, The University of Chicago, Chicago, IL, 60637, USA · Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 08540, USA

Bandit Learning Nash Equilibrium Multi-Armed Bandits

Open paper AskPDF arXiv

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an

O(n^{-1/2})

convergence rate and present a natural extension to episodic finite-horizon learning.

Abstract

Decentralized Learning

Explore similar work

Decentralized Bandit Learning of Markov Perfect Equilibria

Paradoxes of Game Theoretic Equilibria and Price of Anarchy

Decentralized Parameter-Free Online Learning with Compressed Gossip