PaperlayerView exact revision on arXiv

Source-linked AI summary

Competitive One-Step-Ahead Control of Friedkin--Johnsen Networks: Potential Games, Stability, and the Price of Competition

Gabriel Gentil, Amit Bhaya

arXiv:2608.27623v1eess.SY

TL;DR

The paper asks how overlapping influence changes competitive one-step-ahead control in Friedkin–Johnsen networks and whether equilibrium, implementation, and welfare can be analyzed together. It formulates the interaction as an exact potential game, derives stability and reachability results, and distinguishes structural target error from competition-induced welfare loss. The main conclusions characterize protocol-dependent convergence, closed-loop stability tests, constrained equilibrium geometry, and same-state welfare effects.

  • Problem

    The paper studies competitive one-step-ahead control with overlapping influence, where every scalar action enters every player’s tracking cost and raises questions about equilibrium, implementation stability, and welfare.

  • Method

    The paper uses an exact-potential-game formulation, symmetric positive-definite equilibrium systems, protocol-specific stability analysis, resolvent feedback geometry, and constrained-goal and welfare characterizations.

  • Results

    Sequential frozen-state sweeps always converge, two-player parallel sweeps always converge, and one-sweep closed-loop implementations require augmented stability analysis; the paper also characterizes equilibrium geometry and same-state welfare loss.

  • Takeaways & Limitations

    Common Nash fixed points do not determine implementation behavior, while influence rank and goal restrictions govern attainable equilibria and same-state cost gaps isolate competitive welfare loss.

Abstract

from arXiv · show

This paper studies competitive one-step-ahead control of Friedkin-Johnsen networks with overlapping player influence. The one-step interaction is an exact potential game with a unique Nash equilibrium obtained from a symmetric positive-definite system. Sequential best-response sweeps converge for every frozen network state, parallel sweeps obey an exact Jacobi condition (and always converge with two players), and one-sweep implementations require an augmented state-action stability test. For marginal networks, a signed left-right damping condition is sufficient for exact-equilibrium stability and becomes a sharp first-order instability test when its sign is reversed. A resolvent identity clarifies the feedback geometry, while a control-aware centrality identifies the goal conflicts that matter most. We characterize attainable equilibria under unconstrained, convex, and sparse goal restrictions and give a closed form for the same-state welfare loss caused by competition. Numerical examples verify the stability thresholds, geometry, and welfare predictions.

I. INTRODUCTION

The paper formulates overlapping-influence competitive one-step control as an exact potential game and develops a unified framework for equilibrium, stability, reachability, and welfare analysis.

  • B. Controlled Friedkin–Johnsen Model: The controlled FJ dynamics allow persistent disagreement through attachment to initial opinions and permit general signed influence directions.The network model uses row-stochastic influence with stubbornness and player-specific influence vectors.
  • I. INTRODUCTION: Overlapping influence couples every scalar action to every player’s tracking cost, unlike earlier disjoint-domain competitive OSAOC.The resulting questions concern equilibrium structure, implementation convergence, closed-loop stability, and welfare loss.
  • A. Contributions of the Present Work: The paper characterizes unconstrained, support- and amplitude-constrained equilibrium families and introduces resolvent and conflict-sensitivity analyses.These tools distinguish structural target error from welfare loss caused by noncooperative play.
  • III. THE OSAOC AS AN EXACT POTENTIAL GAME: The one-step game is an exact potential game with a unique Nash equilibrium obtained from a symmetric positive-definite system.The potential is strictly convex and coercive, so its stationary point uniquely determines the Nash equilibrium.
  • III. THE OSAOC AS AN EXACT POTENTIAL GAME: Goal conflict changes the equilibrium’s linear term but not the potential Hessian, strict convexity, or uniqueness.Thus conflict displaces the equilibrium while the structural curvature is determined by influence and penalty matrices.

IV. EQUILIBRIUM COMPUTATION AND PROTOCOL EQUIVALENCE

The paper compares exact, parallel, and sequential implementations through common fixed-point equations and distinct iterative transients, separating frozen-state convergence from evolving closed-loop stability.

  • IV. EQUILIBRIUM COMPUTATION AND PROTOCOL EQUIVALENCE: Exact Nash-equilibrium feedback solves the symmetric-positive-definite equilibrium system directly, while parallel and sequential updates implement Jacobi and Gauss–Seidel iterations.The protocols therefore differ computationally despite targeting the same equilibrium equations.
  • IV. EQUILIBRIUM COMPUTATION AND PROTOCOL EQUIVALENCE: One parallel or sequential best-response sweep can be applied per network time step instead of computing the exact equilibrium.This implementation choice must be analyzed as a state-action closed loop rather than only as a frozen-state iteration.
  • IV. EQUILIBRIUM COMPUTATION AND PROTOCOL EQUIVALENCE: Exact, parallel, and sequential protocols share the same closed-loop fixed-point equations whenever their iterations converge.Protocol choice changes the transient trajectory and the conditions under which the common fixed point is reached.
  • IV. EQUILIBRIUM COMPUTATION AND PROTOCOL EQUIVALENCE: Common fixed points do not imply common convergence because frozen-state splitting matrices and augmented closed-loop dynamics govern different stability questions.This distinction is central when actions and network states evolve together.

A. Convergence of Best-Response Sweeps at a Frozen State

At a frozen network state, exact equilibrium uses one solve, sequential sweeps always converge, and parallel sweeps converge precisely under an exact Jacobi condition.

  • A. Convergence of Best-Response Sweeps at a Frozen State: Frozen-state iteration convergence is distinct from one-sweep closed-loop convergence, which requires augmented state-action analysis.The inner sweep index must be separated from the network time index.
  • A. Convergence of Best-Response Sweeps at a Frozen State: Exact equilibrium feedback obtains the Nash equilibrium in one solve.All three protocols target the same frozen-state equilibrium, but their convergence properties differ.
  • A. Convergence of Best-Response Sweeps at a Frozen State: Sequential best-response (Gauss–Seidel) sweeps converge to the Nash equilibrium from every initialization.The proof uses a positive-definite splitting and yields spectral radius below one.
  • A. Convergence of Best-Response Sweeps at a Frozen State: Parallel best-response (Jacobi) sweeps converge from every initialization if and only if the exact Jacobi spectral condition holds.For the stated splitting, this is equivalently 2 diag(G) + Γ − G ≻ 0.
  • A. Convergence of Best-Response Sweeps at a Frozen State: Two-player parallel sweeps converge for every B and every Γ ≻ 0.For p = 2, the matrix condition follows from the positive definiteness of the relevant symmetric system.
  • A. Convergence of Best-Response Sweeps at a Frozen State: For more than two players, strict diagonal dominance provides a sufficient but not necessary convergence condition.A conservative bound follows by enforcing positive definiteness of the corresponding matrix expression.

B. Exact Nash-Equilibrium Closed-Loop Stability

Exact-equilibrium feedback admits a resolvent representation that clarifies its geometry and supports stability results for strictly stable and marginal networks. Large penalties stabilize strictly stable networks, while marginal networks require signed modal damping conditions.

  • Feedback geometry: 0 ⪯ P_EQ(Γ) ≺ I, and as Γ = εΓ̄ with ε ↓ 0, P_EQ(Γ) approaches the projector Π_B onto im(B).The corresponding closed-loop matrix approaches (I − Π_B)A.
  • Large-penalty stability: For ρ(A) < 1, sufficiently large common penalty scale t guarantees exact-equilibrium closed-loop stability.The theorem establishes a threshold t0 such that the relevant spectral radius remains below one for every t ≥ t0.
  • Marginal networks: For marginal networks with simple peripheral eigenvalues, positive signed modal damping for every peripheral mode is sufficient for stability at sufficiently large penalties.The damping condition depends on both left and right eigenvectors, not merely on whether B^T w_μ is nonzero.
  • Marginal networks: A negative damping coefficient for any peripheral mode yields instability for all sufficiently large penalties, making the sign test sharp to first order.When α_μ = 0, higher-order terms determine the outcome.
  • Marginal networks: For primitive marginal networks with nonnegative B and at least one nonzero column, sufficiently large penalties stabilize exact-equilibrium feedback.The conclusion follows from the Perron mode and Theorem 2.

C. Iterative Modes and the Coupling Caveat

One-sweep parallel and sequential implementations must be analyzed as coupled state-action systems. Their global convergence is equivalent to Schur stability of an augmented transition matrix, not separate stability of its diagonal blocks.

  • Coupling caveat: With one PBR or SBR sweep per network step, state and action evolve simultaneously and form one augmented dynamical system.Frozen-state convergence does not by itself characterize the one-sweep closed loop.
  • Stability criterion: The one-sweep affine system is globally attracted to a unique fixed point if and only if ρ(A_ν) < 1.This criterion applies to both ν = PBR and ν = SBR.
  • Coupling caveat: The matrix (I − Q_ν)A is only a diagonal block of A_ν, so one-sweep stability must be tested using the full augmented matrix.Neither frozen-state convergence nor one-sweep stability implies the other.
  • Example: For a valid row-substochastic FJ matrix with nonnegative influence directions, the example gives ρ(A_PBR) = 0.743752 < 1.Thus the reported separation between implementation properties persists under B ≥ 0.

VI. EQUILIBRIUM GEOMETRY AND WELFARE

EQ, PBR, and SBR share the same closed-loop fixed point whenever the equilibrium equations are nonsingular, despite differing transient dynamics and stability properties. The equilibrium map is determined by the Nash equilibrium matrix rather than protocol-specific splittings.

  • Protocol-independent equilibria: EQ, PBR, and SBR generally have different transient dynamics but identical fixed-point equations.Therefore their closed-loop equilibria are governed by the common Nash equilibrium matrix S.
  • Protocol-independent equilibria: When the relevant matrix K is nonsingular, every implementation protocol has the same closed-loop fixed point and corresponding equilibrium control.The proof uses only the common fixed-point equations, so the equilibrium map is protocol independent.
  • Stability connection: For EQ, ρ(F_EQ) < 1 implies that K = I − F_EQ is nonsingular.

B. The Reachable Equilibrium Set

The attainable equilibrium family is an affine image determined by influence structure, while support, amplitude, and sparsity restrictions impose distinct geometric constraints. Control-aware sensitivities and same-state welfare comparisons separate structural target limitations from competitive loss.

  • Reachable equilibrium set: Varying the aggregated goal vector produces an affine equilibrium set common to every protocol converging to the Nash fixed point.This set concerns steady-state equilibria rather than finite-time controllability.
  • Reachable equilibrium set: The equilibrium set is a proper affine subspace of R^n if and only if rank(B) < n.Its dimension follows from the image of the equilibrium sensitivity matrix H.
  • Constrained goals: Compact convex conflict sets produce compact convex equilibrium images, including possibly degenerate zonotopes for boxes and ellipsoids for Euclidean balls.
  • Constrained goals: Fixed support preserves affinity, whereas bounded amplitudes generally do not; allowing conflict on any support of size at most r yields a generally nonconvex union.The support-restricted parameterization is obtained by substituting v = v0 + T_Cη into the affine equilibrium map.
  • Constrained goals: Projection onto a fixed convex image is a convex least-squares problem, while projection onto the support union is generally nonconvex and may be nonunique.Without zero-sum coupling, unbounded support restrictions can sometimes recover the full equilibrium family.
  • Conflict sensitivity: Control-aware equilibrium sensitivities identify conflict amplification and induced equilibrium directions more directly than centrality measures based only on A.The score ||HD_iU_⊥||_2 measures single-node sensitivity, while rank(H T_C) counts induced directions.

D. Closest Reachable Equilibrium

The attainable equilibrium set is characterized geometrically through orthogonal projection, separating structural target limitations from within-set mismatch. This distinction is separate from the welfare loss caused by noncooperative play.

  • Welfare distinction: For p ≥ 2 and B ≠ 0, the competition-loss zero set is a proper affine set with direction ker(B⊤), while for p = 1 loss vanishes identically.The loss is a convex quadratic in the free-response vector z.
  • Reachable equilibrium: The minimum-norm goal is v† = H†y, while all minimizing goals add a component from ker(H).The closest equilibrium is unique even when the minimizing goal is not.
  • Projection geometry: The target error decomposes into within-set mismatch and structural distance using the orthogonal projector HH†.HH†, rather than the nonidempotent PEQ, defines the relevant projection.
  • Projection geometry: The within-set mismatch is not noncooperative inefficiency; welfare requires a same-state Nash–social comparison.This prevents geometric target error from being interpreted as a price of competition.
  • Welfare distinction: Additive welfare loss is preferred when the social optimum is zero or a ratio is numerically ill-conditioned, and these measures are instance- and state-specific.They are not worst-case price-of-anarchy bounds over a game class.

F. Price of Competition at the Closed-Loop Equilibrium

The paper compares Nash and socially optimal actions at the same closed-loop state, distinguishing noncooperative welfare loss from structural target error. Numerical examples illustrate both the comparison and its stability context.

  • Social comparison: The same-state comparison defines additive and multiplicative competition losses without conflating them with target-reachability error.The ratio is used when defined, while additive loss handles zero or ill-conditioned social optima.
  • Social comparison: The potential and total social-cost Hessians are 2(G + Γ) and 2(pG + Γ), respectively.The social planner internalizes the same influence Gramian at p times the strength.
  • Numerical validation: The numerical examples compute spectral radii directly from the corresponding matrices and provide publicly available reproduction code.The examples are used to assess stability, geometry, and welfare results.
  • Numerical validation: The primitive-network example has spectral radii 0.140270, 0.299121, 0.810623, 0.977221, and 0.997675 for t = 0.1, 1, 10, 100, and 1000.The closed loop remains stable and approaches the unit circle from below.
  • Numerical validation: The periodic example has spectral radii 1.096492, 1.088145, 1.009069, and 1.000990 for γ = 0.1, 10, 1000, and 10000.The spectral radius approaches one from above because of the negatively damped −1 mode; welfare loss is zero for the single player.

C. Frozen-State Convergence versus Closed-Loop Stability

Frozen-state best-response convergence and one-sweep closed-loop stability are distinct properties, despite sharing fixed-point equations. The examples expose exact threshold gaps and separate stability, geometry, and welfare effects.

  • Frozen versus closed-loop: The spectral radii in the three-player experiment are independent of v, which changes only the affine term.This isolates convergence and stability properties from goal-dependent affine shifts.
  • Frozen versus closed-loop: Frozen PBR converges if and only if γ > 3, while augmented PBR is Schur if and only if γ > 15/2.Thus the separation gap is γ ∈ (3, 15/2], whereas SBR converges for every γ > 0.
  • Frozen versus closed-loop: At γ = 6, ρ(TPBR) = 0.666667 but ρ(APBR) = 1.215250, so frozen convergence coexists with unstable one-sweep dynamics.This is the concrete distinction between frozen-state and augmented analyses.
  • Exact-equilibrium feedback: Exact-equilibrium feedback approaches the Schur boundary from below on the primitive network and from above on the periodic network.The periodic case contains a negatively damped −1 mode.
  • Geometry and welfare: In the primitive example, Nash and centralized closed loops have spectral radii 0.299121 and 0.221680, respectively, with steady-state separation 0.371726.At the Nash state, noncooperative play raises same-state social cost by approximately 16.8%.
  • Geometry and welfare: Node 2 has the largest Perron weight, but node 1 has the largest equilibrium gain and endpoint welfare loss.The control-aware gain predicts the exact worst-case displacement, unlike network centrality alone.

APPENDIX I PROOFS OF THE LARGE-PENALTY RESULTS

The large-penalty analysis uses perturbation expansions around peripheral eigenvalues to establish stability under positive signed damping and instability when the sign reverses. A uniform version extends the result across admissible diagonal penalty scalings.

  • Perturbation argument: A Neumann expansion with ε = t^-1 provides the large-penalty asymptotic framework.The expansion is applied to the feedback matrix through G = B⊤B.
  • Perturbation argument: When ρ(A) = 1, strictly stable eigenvalues remain inside the unit disk while simple peripheral modes determine first-order behavior.The argument uses first-order eigenvalue perturbation theory and Awµ = µwµ.
  • Stability condition: Positive signed damping moves every peripheral eigenvalue strictly inside the unit disk for sufficiently small positive ε.Finiteness of the peripheral spectrum yields a common bound.
  • Instability condition: Negative damping gives |λµ(ε)| = 1 + ε|αµ| + O(ε2) > 1 for sufficiently small positive ε.Reversing the damping sign therefore produces a first-order instability test.
  • Uniform extension: The uniform extension normalizes Γ−1 = δR over a compact diagonal-scaling set and remains bounded away from zero for every peripheral mode.The perturbation argument consequently applies uniformly whenever δ is sufficiently small.
Loading 2608.27623v1…