Source-linked AI summary
Decentralized Optimal Equilibrium Learning Over Dynamic Networks
Seref Taha Kiremitci, Muhammed O. Sayin
TL;DR
Decentralized learning of socially optimal equilibria is challenging when agents know neither the game nor others' payoffs and communicate over dynamic, unreliable links. Networked-DOEL combines semantic signals with time-stamped information tables, and the paper proves logarithmic regret guarantees while reporting effective equilibrium selection in simulations.
Problem
Decentralized optimal equilibrium learning remains largely unexplored when agents know neither the game nor others' realized payoffs and communicate over dynamic, unreliable links.
Source: §I · p. 1Method
Networked-DOEL uses randomized content/discontent signaling and time-stamped, time-stacked tables with conservative fusion and temporal majority polling.
Source: §I · p. 1, §VI · p. 8Results
E[RT] ∈ O(εT + log T) under the theorem's stated assumptions, and simulations show both networked scenarios approach target equilibrium welfare.
Source: §IV · p. 6, §V · p. 8Takeaways & Limitations
The reported results show equilibrium selection remains effective under intermittent connectivity, with temporal redundancy improving robustness.
Source: §VI · p. 8
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Equilibrium can provide stability without social desirability, while welfare maximization can be socially desirable without being stable; optimal equilibrium selection addresses this tension. The paper studies that selection problem under dynamic, unreliable communication, where earlier approaches have important communication or scope constraints.
I. INTRODUCTION
- Optimal equilibrium selection balances equilibrium stability and social welfare, a problem described as largely unexplored in decentralized learning.Equilibria resist unilateral deviations, but welfare-maximizing outcomes need not be stable under strategic behavior.Source: §I · p. 1
- Earlier semantic-signal schemes provide logarithmic finite-time guarantees but assume fully connected, reliable communication.They use probabilistic content/discontent signals rather than sharing model parameters or estimates.Source: §I · p. 1
- Networked-DOEL reconstructs network-wide content from time-stamped, time-stacked tables using conservative fusion and temporal majority polling.The design addresses phase-specific signals and delayed, missing, statistically dependent bits caused by neighbor-only failing links.Source: §I · p. 1
- The paper establishes a finite-time regret bound for dynamic neighbor-only graphs by restoring independence of delayed access events.The bound is described as having the same form as those in, [13].Source: §I · p. 1
- Experiments use a restricted Erdős–Rényi backbone with dropouts and include the complete-graph setting of [13].The paper examines utilitarian welfare, defined by the sum of local payoffs, and proportional-fair welfare, defined by their product.Source: §I · p. 2
- Unlike cooperative distributed optimization and consensus, this problem targets optimal equilibria in a strategically coupled game with a highly unstructured equilibrium set.The welfare objectives extend beyond payoff-sum maximization.Source: §I · p. 2
II. PROBLEM FORMULATION
The problem is to learn an optimal equilibrium in a finite normal-form game when agents have only local payoff observations and limited, changing communication. The formulation uses approximate equilibrium and weighted transformed welfare to define the target, and cumulative regret to assess performance.
II. PROBLEM FORMULATION
- Agents repeatedly play a finite normal-form game, with each agent having a finite action set and a payoff function over joint actions.Agents do not know the game or observe others' actions; they observe only their own payoff with perfect recall.Source: §II · p. 2
- A pure-strategy ε-equilibrium allows each agent's deviation gain to be bounded by its tolerance level.Tolerance levels can represent differing sensitivities to suboptimal responses, from noncooperation as ε_i approaches zero to cooperation as ε_i grows.Source: §II · p. 2
- Social welfare is defined using positive weights and monotonically increasing transformations of agents' payoffs.With unit weights, identity transformations give payoff-sum welfare, while logarithmic transformations give product welfare associated with fair solutions across agents.Source: §II · p. 2
- The communication network may change or fail, and agents can communicate only with certain other agents using finite-support messages.The paper motivates proximity-based communication as an example.Source: §II · p. 2
- Cumulative regret over a time budget T is measured relative to the optimal welfare.The regret definition uses the agents' joint play at time t and the optimal welfare in equation (4).Source: §II · p. 2
III. DECENTRALIZED OPTIMAL EQUILIBRIUM LEARNING OVER NETWORKS
The section moves from the fully connected DOEL framework to Networked-DOEL, which permits communication with only a subset of agents over a dynamic network.
III. DECENTRALIZED OPTIMAL EQUILIBRIUM LEARNING OVER NETWORKS
- DOEL addresses decentralized equilibrium selection but assumes agents can reliably communicate with everyone.Even its single-bit messages do not remove the practical challenge of full connectivity.Source: §III · p. 2
- Networked-DOEL allows agents to communicate temporarily with only a subset of agents over a dynamic network.This design is introduced to mitigate the full-connectivity requirement.Source: §III · p. 2
- The section first describes DOEL, then introduces Networked-DOEL for settings without reliable all-to-all links.The transition retains the DOEL framework while changing the communication setting.Source: §III · p. 2
A. DOEL Dynamics
DOEL uses phased exploration to identify tolerable equilibria and randomized content signals to compare their social welfare. Agents then commit to locally observed actions associated with the most frequently endorsed profiles.
A. DOEL Dynamics
- Exploration is divided into phases, with agents selecting an action per phase and playing a distribution that includes in-phase exploration.The in-phase exploration probability is ε_i ∈ (0, 1).Source: A. DOEL Dynamics · p. 3
- Agents estimate local action values by averaging the payoffs received when taking the associated action.These local estimates are used to assess whether the explored profile is an ε-equilibrium.Source: A. DOEL Dynamics · p. 3
- Agents signal whether explored actions are tolerable and use shared signals to determine whether the profile is an ε-equilibrium.If everyone signals 1, agents can conclude the profile is an ε-equilibrium based on local value estimates.Source: A. DOEL Dynamics · p. 3
- For tolerable actions, randomized content/discontent signals let agents assess social welfare beyond their locally observed payoffs.The signals are used because local payoffs are not necessarily aligned with social welfare.Source: A. DOEL Dynamics · p. 3
- The probability of unanimous content endorsement is maximized by the action profile with the highest social welfare.Conditioned on unanimous content endorsement, the distribution over profiles corresponds to entropy-regularized welfare maximization over the equilibrium set.Source: A. DOEL Dynamics · p. 3
- Agents commit to the local action most frequently content-endorsed by all agents, and DOEL has at most logarithmic regret up to an in-phase exploration offset under mild assumptions.The described scheme focuses on explore-and-commit for repeated normal-form games with a single state and single-stage objectives.Source: A. DOEL Dynamics · p. 3
B. Networked-DOEL Dynamics
Networked-DOEL exchanges time-stamped, time-stacked content/discontent tables so agents can track phase-specific signals over changing neighbor links. Conservative fusion and temporal majority polling reconstruct network-wide endorsement while reducing sensitivity to erroneous transmissions.
B. Networked-DOEL Dynamics
- Time-stamped signals preserve the phase associated with each content/discontent bit, which cannot be averaged across phases like consensus information.Agents also relay the most recent signals they know about other agents.Source: B. Networked-DOEL Dynamics · p. 3
- Agents share older signals as well as recent ones, adding redundancy when signals fail to reach other agents.The stored table memory scales with its depth m; m ≥ n − 1 ensures access to all agents’ signals when networks remain connected.Source: B. Networked-DOEL Dynamics · pp. 3–4
- Each agent’s n × m table records its beliefs about every agent’s signal at each stored phase, with ∅ marking missing or inconsistent information.Agents update and share tables using locally received neighbor tables.Source: B. Networked-DOEL Dynamics · pp. 3–4
- Spatial fusion accepts only signals consistent across neighboring tables, and temporal majority polling detects network-wide content endorsement from available signals.Endorsement is detected when at least half of the available network-wide signals are ones.Source: B. Networked-DOEL Dynamics · pp. 4–5
- Conservative fusion and majority polling reduce sensitivity to erroneous signal transmissions beyond link failures.Source: B. Networked-DOEL Dynamics · p. 5
IV. ANALYTICAL RESULTS
The analysis establishes a logarithmic regret bound, with an in-phase exploration offset, under an Erdős–Rényi communication model and stated assumptions. It accounts for delayed access to network-wide signals and evaluates tolerability using exploration-perturbed payoffs.
Effective game
- In-phase exploration leads agents to assess tolerability against opponents’ exploration-perturbed actions, represented through effective payoffs.The effective payoff evaluates agent i’s action against the randomized actions E_j(a_j) of the other agents.Source: §IV · p. 5
Regret bound
- Under the theorem assumptions, K=O(log T/q_m^2) yields expected regret O(εT+log T).The communication network is generated according to the Erdős–Rényi G(n,p) model.Source: §IV · pp. 5–6
Communication conditions
- The lower bound q_m increases with table depth and connectivity probability, and decreases with the number of agents.The exploration-length requirement is inversely proportional to q_m^2.Source: §IV · p. 6
Regret analysis
- Overlapping table windows make signal-access events dependent, so the proof separates observations into m empirical averages to recover independence.Network-wide signals may arrive with delay, and access probability q_m is the probability of accessing all agents’ signals within m consecutive phases.Source: §IV · pp. 5–6
V. NUMERICAL RESULTS
Across utilitarian and proportional-fair welfare objectives, the experiments compare equilibrium selection with unconstrained welfare maximization over fully connected and restricted dynamic networks. The restricted network with a longer table window tracks the fully connected baseline more closely than the shorter-window setting.
V. NUMERICAL RESULTS
- The experiments use one randomly generated seven-agent game with three actions per agent and three pure Nash equilibria; its unique social-welfare maximizer is not an equilibrium.Both equilibrium selection and unconstrained welfare maximization are evaluated under utilitarian and proportional-fair objectives.Source: §V · p. 7
- The restricted Erdős–Rényi backbone has link dropouts, and the two restricted scenarios differ in table depth: m = 5 versus m = 3.The backbone has diameter D ∈ {3, 4}; the longer table window meets or exceeds that diameter, whereas the shorter one can fall below it.Source: §V · p. 8
- In unconstrained welfare maximization, the longer-window scenario stays close to the fully connected baseline, while the shorter-window scenario is slower and more variable but still reaches the target.The shorter table window may not recover all information when it is smaller than the backbone diameter.Source: §V · p. 8
- Both restricted-network scenarios approach the target equilibrium welfare, with the longer-window scenario closer to the fully connected baseline.Equilibrium selection converges more slowly and shows a more pronounced separation between scenarios than unconstrained welfare maximization.Source: §V · p. 8
VI. CONCLUSION
The conclusion presents Networked-DOEL as a decentralized approach to socially optimal equilibrium learning over dynamic networks, combining semantic signaling with time-stamped, time-stacked exchange. It reports logarithmic regret guarantees and effectiveness under intermittent connectivity, while identifying more efficient exploration, stochastic games, and function approximation as future directions.
VI. CONCLUSION
- Networked-DOEL combines low-bandwidth semantic signaling with time-stamped, time-stacked information exchange for repeated normal-form games over dynamic networks.Source: §VI · p. 8
- The paper establishes logarithmic regret guarantees with an in-phase exploration perturbation and reports effectiveness under intermittent connectivity.Dropped or delayed bits can be reconstructed within a table window of length m.Source: §VI · p. 8
- Future directions include more efficient exploration, extensions to stochastic games, and function approximation for large action spaces.Source: §VI · p. 8