Distributed Algorithms for Aggregative Games on Graphs

Jayash Koshal; Angelia Nedić; Uday V. Shanbhag

Source-linked AI summary

Distributed Algorithms for Aggregative Games on Graphs

Jayash Koshal, Angelia Nedić, Uday V. Shanbhag

arXiv:1605.00267v2May 1, 2016math.OC

TL;DR

Aggregative games require equilibrium computation when players cannot directly observe the aggregate of decisions and can communicate only with local neighbors. The paper proposes synchronous and asynchronous distributed algorithms that estimate aggregates through neighbor exchange and establishes almost-sure convergence under stated conditions, while extending the framework to more general aggregate couplings.

Problem
Agents lack ready access to aggregate decisions in networked aggregative games, preventing direct implementation of payoff- or gradient-based equilibrium schemes.
Method
The paper develops synchronous consensus-based and asynchronous gossip-based distributed algorithms for aggregate estimation and equilibrium computation.
Results
Under strict monotonicity and related regularity conditions, the proposed algorithms converge almost surely to the unique equilibrium, including an extension to more general aggregate coupling.
Takeaways & Limitations
The schemes support equilibrium computation under local communication, informational restrictions, and possibly evolving network structures.
Takeaways & Limitations
Convergence speed depends on network connectivity, with poor connectivity making aggregate estimates and decisions take longer to converge.

Abstract

from arXiv · show

We consider a class of Nash games, termed as aggregative games, being played over a networked system. In an aggregative game, a player's objective is a function of the aggregate of all the players' decisions. Every player maintains an estimate of this aggregate, and the players exchange this information with their local neighbors over a connected network. We study distributed synchronous and asynchronous algorithms for information exchange and equilibrium computation over such a network. Under standard conditions, we establish the almost-sure convergence of the obtained sequences to the equilibrium point. We also consider extensions of our schemes to aggregative games where the players' objectives are coupled through a more general form of aggregate function. Finally, we present numerical results that demonstrate the performance of the proposed schemes.

1 Introduction

The paper develops distributed algorithms for aggregative Nash games when agents lack direct access to aggregate decisions and communicate only with local neighbors. It studies synchronous and asynchronous information exchange, convergence, error bounds, extensions, and numerical demonstrations.

Motivation: Aggregative games model payoffs as functions of each player’s action and an aggregate of all players’ actions.Nash-Cournot, supply-function, common-agency, and communication-network control games are cited as examples.
Motivation: Networked equilibrium computation is difficult because agents may observe only neighbors’ decisions and therefore cannot directly evaluate payoffs or gradients.The underlying connectivity graph may also evolve over time.
Algorithms: The synchronous algorithm has all agents exchange information and update aggregate estimates and decisions simultaneously using gradient-based steps.It uses time-varying neighbor connectivity.
Algorithms: The asynchronous algorithm uses a gossip protocol in which one randomly selected neighboring pair exchanges information and updates aggregate estimates and individual decisions.This scheme combines the synchronous method with gossip-based consensus.
Results and scope: Both algorithms are analyzed with diminishing stepsizes for convergence and constant steplengths for error bounds.The paper also reports numerical applications to networked Nash-Cournot games and discusses broader distributed equilibrium computation.
Results and scope: The paper assumes strict monotonicity, while noting that regularization and stochastic-regime extensions could weaken or broaden the framework.The algorithms are positioned as a first step toward distributed equilibrium computation under informational and network restrictions.

2 Problem Formulation and Background

The paper formulates aggregative games with locally interacting players, represents equilibrium conditions through a variational inequality, and establishes uniqueness under compactness, convexity, continuity, and strict monotonicity assumptions.

2 Problem Formulation and Background: Players interact over time through time-varying connectivity graphs, motivating distributed equilibrium computation and auxiliary connectivity analysis.The formulation section introduces the game, sufficient equilibrium conditions, and the distributed algorithm.
2.1 Formulation and Examples: Each player has a strategy set Ki and payoff fi(xi, ¯x), where the aggregate is the sum ¯x = ∑i=1^N xi.The aggregate excluding player i is denoted ¯x−i.
2.1 Formulation and Examples: The generic player problem is parameterized by the aggregate of other players, with strategy sets and payoff functions known locally to each agent.The feasible aggregate set is represented by the Minkowski sum ¯K.
2.1 Formulation and Examples: In the Nash-Cournot example, firm payoffs depend on nodal aggregate sales, while communication and physical production-layout networks are modeled separately.The communication network may be dynamic, whereas the layout network is static.
2.2 Equilibrium Conditions and Assumptions: Assumption 1 requires compact convex strategy sets, differentiable payoffs, and convexity in each player’s own decision.Transportation costs in the example are assumed to be zero.
2.2 Equilibrium Conditions and Assumptions: Under Assumption 1, the game’s sufficient equilibrium conditions can be expressed as the variational inequality VI(K, φ).The mapping is constructed from component gradients Fi(xi, ¯x) = ∇xifi(xi, ¯x).
2.2 Equilibrium Conditions and Assumptions: Strict monotonicity of φ is imposed as Assumption 2, while Assumption 3 requires each Fi to be uniformly Lipschitz continuous in the aggregate argument.The paper notes that strict monotonicity holds in several practical settings and that the example satisfies the assumptions.
2.2 Equilibrium Conditions and Assumptions: Assumptions 1 and 2 together guarantee that the aggregative Nash game admits a unique Nash equilibrium.Existence follows from compactness and continuity, while uniqueness follows from strict monotonicity.

3 Distributed Synchronous Algorithm

The synchronous algorithm has agents mix neighbors’ aggregate estimates and then update decisions and estimates simultaneously over a time-varying network. Under graph, weight, and diminishing-stepsize assumptions, the estimates approach the true aggregate and the decisions converge to the unique Nash equilibrium.

Algorithm outline: Agents estimate the aggregate by mixing information from local neighbors before applying a projection-based gradient update.Each agent uses the mixed estimate in place of the true aggregate when updating its decision and average estimate.
Algorithm outline: The communication graph may vary over time, with every agent exchanging information with its current neighbors at each synchronous epoch.A bounded intercommunication interval requires the union of edges across every Q consecutive intervals to remain connected.
Assumptions: The weight matrices assign positive weight to neighbors’ information and are doubly stochastic under the stated assumptions.Neighbor weights are at least δ, while non-neighbor weights are zero.
Assumptions: The diminishing stepsize is non-increasing; αk = (k + 1)^−b satisfies the stated condition when 0.5 < b ≤ 1.The stepsize assumptions support the convergence analysis of the synchronous method.
Preliminary results: The average of agents’ estimates represents the true average information, while individual estimates converge toward the true aggregate under the mixing assumptions.The transition matrices converge geometrically, and the aggregate-estimation error depends on network connectivity.
Convergence theory: Under Assumptions 1–6, the decision sequence converges to the unique solution x∗ of VI(K, φ), the Nash equilibrium.The associated aggregate estimates converge to the true aggregate at equilibrium under the stated conditions.

4 Distributed Asynchronous Algorithm

The paper develops an asynchronous gossip algorithm in which randomly selected neighboring agents exchange aggregate estimates and update their decisions. Under connectivity and strict monotonicity assumptions, the algorithm converges almost surely to the unique equilibrium.

4.1 Outline of Algorithm: Connectedness of the undirected communication graph is required for the asynchronous analysis.The graph assumption supports the gossip communication model and the subsequent convergence results.
4.1 Outline of Algorithm: A randomly selected neighboring pair exchanges information and updates estimates of the aggregate and individual decisions.The gossip protocol uses Poisson clocks; one agent wakes, contacts a neighbor, and the selected pair updates while other agents remain idle.
4.1 Outline of Algorithm: The asynchronous method uses agent-specific diminishing stepsizes based on each agent’s update frequency.Agent i uses αk,i = 1/Γk(i), where Γk(i) counts updates through time k; these stepsizes are asymptotically of order 1/k.
4.2 Convergence Theory: The analysis also establishes intermediate estimate bounds under the asynchronous update process.These results characterize the evolution of aggregate estimates before the equilibrium convergence conclusion.
4.2 Convergence Theory: The second-largest eigenvalue controls how quickly information spreads and agents agree on aggregate estimates.Networks with larger λ achieve agreement faster than networks with smaller λ, motivating topology comparisons through λ.
4.2 Convergence Theory: Under the stated assumptions and frequency-based stepsizes, the iterates converge almost surely to the game’s unique equilibrium.The proof uses strict monotonicity and establishes convergence of the entire sequence, not only a subsequence.

5 Generalizations and Extensions

The paper extends its distributed schemes beyond equal-dimensional aggregative games and discusses routes for weakening core assumptions. The generalized algorithms retain almost-sure convergence under the corresponding assumptions, while stochastic payoff functions remain an extension requiring further analysis.

5 Generalizations and Extensions: The synchronous and asynchronous schemes converge almost surely to the unique equilibrium under strict monotonicity, Lipschitz requirements, compactness, and suitable communication conditions.The synchronous scheme addresses time-varying connected networks, while the asynchronous gossip scheme addresses fixed graphs.
5.1 Weakening assumptions on problem parameters: The convergence theory currently relies on strict monotonicity and uniform Lipschitz continuity, though regularization, extragradient, and smoothing approaches may weaken these requirements.These are discussed as possible extensions rather than results established by the present convergence theory.
5.1 Weakening assumptions on problem parameters: Stochastic payoff functions are not treated by the current schemes and would require distributed stochastic-approximation counterparts under suitable assumptions.The paper identifies convergence analysis for this setting as likely but more complicated.
5.2 Extensions to model: The framework can generalize coupling through functions hi(xi), allowing players’ decisions to have different dimensionalities.The original formulation is recovered by setting hi(xi) = xi for all players.
5.2 Extensions to model: The generalized synchronous algorithm modifies initialization and iterate or aggregate-estimate updates while retaining the mixing step.Each agent’s estimate represents the aggregate sum of the transformed decisions, ∑i=1^N hi(xi).
5.2 Extensions to model: Under the generalized problem’s assumptions, the synchronous algorithm converges to the unique solution.The result is stated for the mapping φ with coordinates defined by the players’ gradients.
5.2 Extensions to model: The generalized asynchronous algorithm preserves gossip estimate mixing while adapting initialization and updates to the transformed aggregate.Its frequency-based stepsizes yield almost-sure convergence to the unique equilibrium under the stated assumptions.

6 Numerics

The numerics instantiate the proposed analysis on networked Nash-Cournot games and compare synchronous and asynchronous performance under different network conditions. Results show that convergence error generally falls with longer runs, while dynamic, larger, and asynchronous networks perform worse.

6.1 Nash-Cournot Game: The numerical study applies the proposed algorithms to networked Nash-Cournot games, an aggregative-game instance with total sales as the aggregate.The game uses production and sales decisions across ten locations and verifies regularity conditions for the analysis.
6.1 Nash-Cournot Game: Under concave price functions with Lipschitz continuous derivatives, the Nash-Cournot coordinate maps satisfy the required Lipschitzian condition.The corresponding lemma establishes the stated relation under constants governing price-derivative regularity.
6.1 Nash-Cournot Game: The experimental setup uses ten locations, random a_il and b_il parameters, d_l drawn from U(90, 100), and cap_il = 500.The affine price specification yields a strongly monotone map and, with compact strategy sets, a unique Nash equilibrium.
6.2 Synchronous Algorithm: As termination threshold ˜k increases, empirical mean error and confidence-interval width decrease, while mean error increases with network size.This pattern is reported for the synchronous and asynchronous numerical results.
6.2 Synchronous Algorithm: Static complete networks achieve orders-of-magnitude better performance than dynamic networks because agents have access to the true aggregate throughout the run.The paper interprets the dynamic-network deterioration as the price of information for convergence.
6.3 Asynchronous Algorithm: Synchronous updates outperform asynchronous updates in mean error and confidence width, while graph topology matters more synchronously than asynchronously.The paper attributes the synchronous advantage to more frequent communication and faster diffusion of information.
6.3 Asynchronous Algorithm: A well-informed, up-to-date neighbor matters more than denser connectivity; wheel networks can outperform better-connected cycle networks.Complete networks provide broad communication, while grid performance lies between wheel and cycle networks.

7 Summary and Conclusions

The paper develops synchronous and asynchronous distributed algorithms for computing equilibria in aggregative Nash games over graphs with restricted communication. It establishes convergence and error bounds under stated settings, and extends the schemes to more general aggregates.

7 Summary and Conclusions: The paper studies aggregative Nash games in which player interactions depend on the aggregate sum of players’ actions over a limited-connectivity network.Agents exchange information locally while computing an equilibrium point.
7 Summary and Conclusions: It proposes a synchronous consensus-based algorithm for dynamic time-varying networks and an asynchronous gossip-based algorithm for static networks.Both algorithms respect the restriction that agents exchange information only through the network.
7 Summary and Conclusions: The asynchronous algorithm provides error bounds when agents use constant, player-specific stepsizes.The stepsize can be selected independently by each agent.
7 Summary and Conclusions: The extensions allow players’ decisions to be coupled through a more general form of aggregate.This broadens the aggregate structure considered by the distributed schemes.

Appendix

The appendix establishes probabilistic properties of the asynchronous update process used in the gossip algorithm. These properties support eventual update-frequency and disagreement relations needed in the convergence analysis.

Appendix: The asynchronous analysis models each agent’s update events as independent identically distributed indicators with mean p_i.The law of iterated logarithms is used to obtain almost-sure asymptotic bounds.
Appendix: With probability one, sufficiently large iteration thresholds exist beyond which the update-frequency bounds hold for all agents.The threshold may depend on q and the network size N.
Appendix: The resulting bounds imply the first relation of the lemma through the asynchronous stepsize relation α_k,i = 1.The proof then derives subsequent inequalities using the established bounds and the mixing parameter.
Appendix: The proof uses the minimum positive edge-selection probability to define a mixing quantity governing the subsequent disagreement bounds.The relevant quantity is introduced as ˆp = 1 + min_{i,j}∈E p_ij.