PaperlayerView exact revision on arXiv

Source-linked AI summary

Nash and Wardrop equilibria in aggregative games with coupling constraints

Dario Paccagnan, Basilio Gentile, Francesca Parise, Maryam Kamgarpour, John Lygeros

arXiv:1702.08789v2eess.SYcs.GTcs.SYmath.OC

TL;DR

In aggregative games, agents’ costs depend on their own strategies and the population average, raising questions about the relationship between Nash and Wardrop equilibria and coordination under coupling constraints. The paper uses variational-inequality characterizations to bound the distance between the equilibria and proposes decentralized algorithms. The distance bound decreases with population size, and the paper studies electric-vehicle charging and road routing applications.

  • Problem

    Earlier distance bounds known to the authors were specific to routing or congestion games and assumed population growth through identical agent replicas.

    Source: A. Comparison with the literature · p. 6

  • Method

    The paper uses variational-inequality characterizations to bound equilibrium distance and proposes an optimal-response two-level algorithm for Wardrop equilibrium.

    Source: A. Comparison with the literature · p. 6, A. Two-level algorithm based on… · p. 7

  • Results

    The Euclidean distance between Nash and Wardrop equilibria is bounded by a function that decreases as population size grows.

    Source: §IV · p. 5

  • Takeaways & Limitations

    The paper proposes decentralized algorithms for equilibria with coupling constraints and studies electric-vehicle charging and road-routing applications.

    Source: §VIII · p. 14

Abstract

from arXiv · show

We consider the framework of aggregative games, in which the cost function of each agent depends on his own strategy and on the average population strategy. As first contribution, we investigate the relations between the concepts of Nash and Wardrop equilibrium. By exploiting a characterization of the two equilibria as solutions of variational inequalities, we bound their distance with a decreasing function of the population size. As second contribution, we propose two decentralized algorithms that converge to such equilibria and are capable of coping with constraints coupling the strategies of different agents. Finally, we study the applications of charging of electric vehicles and of route choice on a road network.

I. INTRODUCTION

The paper studies aggregative games where costs depend on agents’ strategies and the population average, focusing on how Nash and Wardrop equilibria relate and how to coordinate them under coupling constraints. It develops distance bounds, decentralized algorithms, and applications to electric-vehicle charging and road routing.

Nash and Wardrop equilibria

  • The framework extends Wardrop equilibrium to generic aggregative games and uses variational inequalities to connect it with Nash equilibrium.Nash agents account for how their own strategy affects cost through the average, whereas Wardrop agents treat the average as fixed.Source: Nash and Wardrop equilibria · p. 1
  • Nash and Wardrop strategies become close as population size increases, with their Euclidean distance bounded by a decreasing function of population size.The result requires uniformly bounded strategy sets, as in the stated charging and traffic applications.Source: Nash and Wardrop equilibria · p. 1

II. PROBLEM FORMULATION

  • The game model combines individual strategy sets with constraints coupling agents’ decisions, and focuses on variational equilibria within that setting.These variational equilibria correspond intuitively to an equal split of the coupling-constraint burden.Source: Decentralized algorithms and coupling… · pp. 1–2

Decentralized algorithms and coupling constraints

  • The paper proposes decentralized coordination for coupled decisions through optimal-response and gradient-step algorithms, using a broadcast dual variable to separate agents’ strategy sets.The dual-variable scheme addresses privacy and centralized-computation concerns while targeting an equilibrium of the original game.Source: Decentralized algorithms and coupling… · p. 2

Applications

  • Electric-vehicle charging constraints model aggregate peak limits or local limits for vehicles connected to the same transformer; the paper also establishes uniqueness of the associated dual variables.Source: Applications · p. 2
  • For road routing, the paper uses a stationary rush-hour model and Oldenburg data to simulate the effects of road-access limits expressed as coupling constraints.Source: Applications · p. 2

III. CONNECTION WITH VARIATIONAL INEQUALITIES

The section characterizes Nash and Wardrop equilibria through variational inequalities with a common feasible set and different operators. This characterization is sufficient under coupling constraints, but its converse generally fails; bounded strategy sets and strong monotonicity provide existence and uniqueness conditions.

III. CONNECTION WITH VARIATIONAL INEQUALITIES

  • The Nash and Wardrop operators share the feasible set but differ in whether the cost gradient accounts for the effect of an agent’s strategy on the population average.Source: §III · p. 3
  • A solution of the Nash or Wardrop variational inequality is, respectively, a Nash or Wardrop equilibrium.Source: §III · p. 3
  • With coupling constraints, the converse does not generally hold: an equilibrium need not solve its corresponding variational inequality.When there are no coupling constraints, the VI characterization is equivalent to the equilibrium definition.Source: §III · p. 4
  • Bounded individual strategy sets guarantee solutions to both variational inequalities, while strong monotonicity of the relevant operator guarantees uniqueness.Source: §III · p. 4

A. Variational and normalized equilibria

The paper characterizes variational equilibria and derives conditions for monotonicity of the Nash and Wardrop operators. It then studies how Wardrop and Nash equilibria relate as the population grows.

A. Variational and normalized equilibria

  • Variational equilibria are the normalized equilibria in which agents split the coupling-constraint burden equally.The paper focuses on this subclass, while noting its results could be extended to normalized equilibria using a corresponding operator.Source: A. Variational and normalized equilibria · p. 4

B. Sufficient conditions for monotonicity

  • For costs of the form (10), convex individual terms and a monotone price function make the Wardrop operator monotone; strong convexity makes it strongly monotone.If the price function is also affine and strongly monotone, the Nash operator is strongly monotone when the individual terms are convex.Source: B. Sufficient conditions for… · p. 4
  • The paper uses monotonicity conditions to motivate distance bounds because often only one of the Nash and Wardrop operators has the properties needed to guarantee algorithmic convergence.Source: B. Sufficient conditions for… · p. 4

IV. DISTANCE BETWEEN NASH AND WARDROP EQUILIBRIA IN LARGE POPULATIONS

  • Every Wardrop equilibrium is an ε-Nash equilibrium, with ε tending to zero as the population grows.Source: §IV · p. 5
  • Strong monotonicity of either equilibrium operator ensures uniqueness of its corresponding variational equilibrium and bounds its distance from any opposite-type variational equilibrium.The bound scales with the operator discrepancy and the inverse monotonicity constant.Source: §IV · p. 5

A. Comparison with the literature

The paper distinguishes its equilibrium-distance results from prior work and develops decentralized methods for games with coupling constraints. Its algorithms use variational-inequality reformulations to target Nash or Wardrop equilibria.

A. Comparison with the literature

  • Unlike prior distance bounds specific to routing or congestion games with identical replicas, the paper addresses generic aggregative games and population growth through generic new agents.The authors also distinguish their bounds from earlier work that established convergence without a convergence-rate bound.Source: A. Comparison with the literature · p. 6

V. DECENTRALIZED ALGORITHMS

  • The decentralized design assumes agents keep their costs and individual constraints private, while a central operator measures population aggregates and broadcasts aggregate information.Source: §V · p. 6
  • An extended variational inequality is equivalent to the original VI, a variational equilibrium with suitable dual variables, and a VI in the extended strategy-dual space.Source: §V · p. 7
  • Two decentralized schemes address coupling constraints: a two-level optimal-response algorithm targets Wardrop equilibrium, while a one-level gradient algorithm targets Nash or Wardrop equilibrium.Source: §V · p. 7

A. Two-level algorithm based on optimal response for Wardrop equilibrium

The section presents two decentralized methods for reaching variational equilibria with coupling constraints: a two-level optimal-response algorithm for Wardrop equilibrium and an asymmetric projection algorithm for Nash or Wardrop equilibrium.

A. Two-level algorithm based on optimal response for Wardrop equilibrium

  • Under strong monotonicity of FW, Assumptions 1, 3, and 4, bounded individual sets, and the stated step-size condition, Algorithm 1 converges to a variational Wardrop equilibrium.The inner loop solves the game without coupling constraints using an iterative Wardrop algorithm.Source: A. Two-level algorithm based on… · p. 7
  • Algorithm 1's convergence rate is open overall, though geometric convergence is available for both loops under additional special-case assumptions.The inner-loop result requires a modification under Assumption 4-2; the outer-loop result additionally requires strong monotonicity of Φ.Source: A. Two-level algorithm based on… · p. 7
  • The two-level optimal-response algorithm is presented as the first to guarantee convergence to a Wardrop equilibrium in games with coupling constraints.Its outer loop updates dual variables from constraint violations, while agents update toward a Wardrop equilibrium of the game with the current dual variables.Source: A. Two-level algorithm based on… · p. 7

B. Asymmetric projection algorithm based on gradient step for Nash and Wardrop equilibrium

  • The asymmetric projection algorithm solves an equivalent extended variational inequality on a product set, enabling decentralized updates for Nash or Wardrop equilibrium.Each agent takes a gradient step using its strategy, the previous population average, and dual variables; a central operator updates and broadcasts the price.Source: B. Asymmetric projection algorithm… · p. 8
  • With the stated strong-monotonicity and Lipschitz conditions and a suitable step size, Algorithm 2 converges to a variational Nash or Wardrop equilibrium, depending on the operator used.For affine operators on a polyhedral set, the paper also reports R-linear convergence when the step size is sufficiently small.Source: B. Asymmetric projection algorithm… · p. 8

C. Convergence guarantees for quadratic games

For quadratic aggregative games, the section gives sufficient matrix conditions for operator monotonicity and algorithm convergence. It then introduces an electric-vehicle charging game with coupling constraints that limit grid power.

C. Convergence guarantees for quadratic games

  • Table I summarizes the conditions guaranteeing convergence of the two proposed algorithms.The table is framed under Assumptions 1 and 2.Source: C. Convergence guarantees for… · p. 8, Table I · p. 8
  • For quadratic costs, the paper gives sufficient conditions for strong monotonicity of the Nash operator FN and the Wardrop operator FW, supporting convergence guarantees for the proposed algorithms.FN is strongly monotone under either Q ≻ 0, C ⪰ 0 or Q ⪰ 0, C ≻ 0; FW is strongly monotone under Q ≻ 0, C ⪰ 0.Source: C. Convergence guarantees for… · p. 8
  • FW is strongly monotone and Assumption 4 holds if Q ≻ 0 and either C = C⊤ ≻ 0 or Q − C⊤Q−1C ≻ 0.Source: C. Convergence guarantees for… · p. 8

VI. CHARGING OF ELECTRIC VEHICLES

  • The electric-vehicle application models simultaneous charging and adds coupling constraints, while studying equilibria even when vi = 0 and the distance between aggregate Nash and Wardrop strategies.Source: §VI · p. 9

Constraints

  • The charging constraint limits the grid's total delivery at each time to M·Kt units of power.Source: Constraints · p. 9

Cost function

The vehicle cost is an electricity bill whose price depends on demand relative to production capacity. Under the stated assumptions, the section establishes equilibrium existence and further guarantees for Wardrop and Nash equilibria.

Cost function

  • Each vehicle's electricity-bill cost uses an energy price that depends on non-EV and aggregate EV demand relative to production capacity.The paper specifies the ratio as (dt + σt(x))/κt and notes that production capacity κt is generally unrelated to the grid limit Kt.Source: Cost function · p. 9

A. Theoretical guarantees

  • Under the stated assumptions, each charging game has Nash and Wardrop equilibria, and every Wardrop equilibrium is an ε-Nash equilibrium.Source: A. Theoretical guarantees · p. 9
  • When the price function p is strongly monotone, every variational Wardrop equilibrium has the same aggregate strategy; FW is monotone and FN is strongly monotone under the stated assumptions.Source: A. Theoretical guarantees · p. 9
  • If condition (33) is not satisfied, the paper states that a Nash equilibrium cannot be achieved, while a Wardrop equilibrium remains attainable with the extragradient algorithm.Source: A. Theoretical guarantees · p. 10

Uniqueness of dual variables.

The section gives a sufficient condition for uniqueness of the dual variables associated with the coupling constraint. Its numerical and application passages also describe equilibrium computation and route-choice constraints.

Uniqueness of dual variables.

  • A sufficient condition, checked a-posteriori using the Nash solution, guarantees unique dual variables for the coupling constraint.In the numerical analysis, this condition always holds; another result requires the price function to be affine.Source: Uniqueness of dual variables · p. 10

Quadratic cost function

  • For the quadratic cost, Algorithm 2 uses fewer primal updates, while Algorithm 1 uses fewer dual updates.The reported iteration counts do not appear to increase with population size.Source: Quadratic cost function · p. 11

VII. ROUTE CHOICE IN A ROAD NETWORK

  • Route choice is modeled on a directed road network, with each driver’s strategy specifying edge-use probabilities for travel from origin to destination.The individual constraints encode the requirement that drivers reach their destinations with probability 1.Source: §VII · p. 11
  • A coupling constraint can cap the number of vehicles on an edge, allowing authorities to target congestion on a road or in a neighborhood.The constraint is intended to help reduce noise or pollution.Source: §VII · p. 11

Cost function

The route-choice cost balances drivers’ travel time against deviation from a preferred route. The paper derives a smooth travel-time function and gives conditions for equilibrium uniqueness and algorithmic convergence.

Cost function

  • Drivers minimize travel time while avoiding too much deviation from their preferred route.The cost uses edge travel time and a penalty for deviation from the preferred strategy.Source: Cost function · p. 11

Travel time

  • Road capacity and rush-hour demand determine queue formation, and the resulting average queueing time contributes to edge travel time.When demand during the rush hour exceeds capacity, a queue accumulates and later dissipates at the edge’s capacity rate.Source: Travel time · p. 12
  • The piecewise-affine travel-time function is not continuously differentiable, so the model uses a smoothed, continuously differentiable version.The smooth approximation is illustrated alongside the piecewise-affine function in Figure 4.Source: Travel time · p. 12, Figure 4 · p. 12
  • The travel-time function is used in a stationary traffic model but incorporates average queueing time derived from a dynamic function.A thorough analysis of a dynamic traffic model is left to future work.Source: Travel time · p. 12

A. Theoretical guarantees

  • The theoretical guarantees establish a unique variational Wardrop equilibrium for any population size and a unique variational Nash equilibrium when condition (42) holds.For the specified conditions, Algorithm 2 converges to the corresponding variational equilibria.Source: A. Theoretical guarantees · p. 12

B. Numerical analysis

The numerical study applies the route-choice model to a reduced Oldenburg road network and examines queueing and equilibrium proximity. The conclusion emphasizes the equilibrium-distance results, decentralized algorithms, and two applications.

B. Numerical analysis

  • The route-choice analysis uses a reduced Oldenburg network and randomly selected driver origins and destinations.The reduced graph has 175 nodes and 213 undirected edges; free-flow speeds differ between main and secondary roads.Source: B. Numerical analysis · p. 13
  • The coupling-constraint experiment compares queueing before and after limiting traffic on an edge, with queueing visibly increasing on the alternative route.The setup compares a Wardrop equilibrium without coupling constraints against one with an edge-level cap.Source: B. Numerical analysis · p. 13
  • The numerical analysis reports the distance between the unique variational Wardrop equilibrium and the variational Nash equilibrium found by Algorithm 2.It also notes that the Wardrop equilibrium’s ε-Nash property is illustrated, but the plot is omitted.Source: B. Numerical analysis · p. 13

VIII. CONCLUSIONS

  • The conclusion highlights bounds on Nash–Wardrop equilibrium distance, decentralized algorithms for coupling constraints, and applications to EV charging and route choice.Local-communication distributed algorithms and proximity results between Nash equilibrium and social optimum are proposed as future research directions.Source: §VIII · pp. 13–14

APPENDIX: PROOFS

The appendix establishes operator monotonicity properties and links variational inequalities to equivalent KKT systems. These arguments support the paper’s equilibrium analysis.

Proof of Lemma 3

  • Convex individual costs make their gradients monotone, and combining this with a monotone price term establishes monotonicity of the Wardrop operator.For an affine price function with a positive-definite matrix condition, the Nash operator is strongly monotone.Source: Proof of Lemma 3 · p. 14
  • Strong convexity of the individual costs yields strong monotonicity of their gradients, supporting the strong-monotonicity argument for the Nash operator.The proof uses the equivalence between strong convexity and strong monotonicity of the gradient.Source: Proof of Lemma 3 · p. 14

Proof of Proposition 3

  • Under the stated assumptions, Slater’s condition makes the relevant variational inequalities and agents’ optimization problems equivalent to their KKT systems.The proof concludes their equivalence by direct inspection of the three KKT systems.Source: Proof of Proposition 3 · p. 14

Proof of Theorem 2

The proof establishes convergence in two stages: an inner iteration yields limiting strategies, and an outer multiplier iteration converges through a co-coercive variational inequality.

Proof of Theorem 2

  • Under Assumption 4, the inner-loop sequences z(h) and x̃(h) converge, with limiting aggregate z̄=σ(x̄).The proof identifies z̄ as the average of the limiting strategies.Source: Proof of Theorem 2 · p. 14
  • The limiting strategies form an ε-Nash equilibrium with ε=O(1/M) and a Wardrop equilibrium of G(λ(k)).The Wardrop conclusion follows from each agent's optimal-response condition.Source: Proof of Theorem 2 · p. 14
  • For each λ≥0, F_W+A⊤λ remains strongly monotone on Q, yielding a unique variational Wardrop equilibrium.The proof denotes this equilibrium by x̄_W(λ).Source: Proof of Theorem 2 · p. 14
  • The outer loop uses Φ(λ)=b−A x̄_W(λ), co-coercive with constant α/∥A∥², to establish multiplier convergence.The proof applies a projection algorithm to the variational inequality over nonnegative multipliers.Source: Proof of Theorem 2 · p. 14

Proof of Theorem 3

The proof recasts Algorithm 2 as an asymmetric projection algorithm for a variational inequality, then establishes its convergence through co-coercivity. It also analyzes the KKT system associated with the coupling constraints.

Proof of Theorem 3

  • Algorithm 2 is an asymmetric projection algorithm for VI(Y,T), and its convergence follows when G(y)=D_s^−1/2 y is co-coercive with constant 1.With the specified D, the projection-algorithm update coincides with the algorithm's steps.Source: Proof of Theorem 3 · p. 15
  • Condition (27) implies τ<1/∥A∥, which supports the positive-definiteness and convergence arguments for the chosen update.The proof uses this bound to establish convergence of a Neumann series and positivity under condition (27).Source: Proof of Theorem 3 · p. 15
  • The matrix in (55) has minimum eigenvalue bounded below by −M/4, with equality only when M is a multiple of 4.The proof obtains the bound by minimizing p−√(Mp) over the permitted integer values of p.Source: Proof of Theorem 3 · p. 15
  • For Γx≤γ, KKT retains active-constraint dual variables; Lemma 6 gives at most one ˜λ solution if A1x1 + A2x2 = 0 implies x1 = 0.Source: Proof of Theorem 3 · pp. 15–16
Loading 1702.08789v2…