Source-linked AI summary
Convergence to Equilibrium in Local Interaction Games and Ising Models
Andrea Montanari, Amin Saberi
TL;DR
The paper asks how quickly noisy best-response dynamics in networked coordination games reaches the risk-dominant equilibrium, and how that time depends on network structure. It characterizes the time using tilted graph cuts and related path arguments, finding fast convergence on low-dimensional locally connected graphs but potentially exponential convergence on highly connected or expanding graphs. The analysis also supports estimating convergence through graph quantities and approximation algorithms.
Problem
The paper asks how network structure affects the typical time required for noisy coordination dynamics to reach the risk-dominant equilibrium.
Method
The paper relates hitting times to transition-kernel spectra and most-likely monotone paths, characterizing them with tilted cut and tilted cutwidth.
Results
Low-dimensional graphs converge in a very short time, while bounded-degree expanders and certain small-world networks may require time exponential in the number of nodes.
Takeaways & Limitations
The characterization provides a basis for estimating convergence times for specific graphs and for developing approximation algorithms for convergence to Nash equilibria.
Takeaways & Limitations
Some estimates could be improved by using more specific arguments instead of directly applying Theorem 3.1.
Abstract
from arXiv · showhide
Coordination games describe social or economic interactions in which the adoption of a common strategy has a higher payoff. They are classically used to model the spread of conventions, behaviors, and technologies in societies. Here we consider a two-strategies coordination game played asynchronously between the nodes of a network. Agents behave according to a noisy best-response dynamics. It is known that noise removes the degeneracy among equilibria: In the long run, the ``risk-dominant'' behavior spreads throughout the network. Here we consider the problem of computing the typical time scale for the spread of this behavior. In particular, we study its dependence on the network structure and derive a dichotomy between highly-connected, non-local graphs that show slow convergence, and poorly connected, low dimensional graphs that show fast convergence.
1 Introduction
The paper studies how network structure controls convergence to the risk-dominant equilibrium in noisy coordination dynamics. It characterizes convergence using graph quantities and derives a fast-versus-slow dichotomy across network classes.
- Motivation: A finite block of adopters cannot expand across a two-dimensional grid under deterministic threshold dynamics.Its influence remains limited to the smallest rectangle containing the initial block.
- Motivation: Noise enables nucleation: a sufficiently large initial block can spread at positive velocity despite possible erosion.A mistaken update can add a new layer at no extra probability cost, and the growth mechanism prevails under technical assumptions.
- Motivation: Small noise drives the system toward a particular equilibrium in which all players take the same action.This evolutionary selection resolves the multiplicity of coordination-game equilibria.
- Contribution: Tilted cutwidth and tilted cut are dual graph quantities that characterize convergence through paths and bottlenecks.They coincide for the slowest subgraph, where convergence time is exponential in the shared parameter.
- Results: Low-dimensional graphs converge quickly, whereas bounded-degree expanders and some small-world networks can require time exponential in the number of nodes.The characterization also supports estimates through the graph’s isoperimetric function and motivates approximation algorithms.
- Contribution: The convergence rate is governed by network properties beyond node interaction counts or total edge counts.The claim applies to a large class of noisy best-response dynamics, including Ellison’s dynamics.
2 Definitions
The paper formalizes asynchronous and synchronous noisy best-response dynamics for two-strategy coordination games on graphs. It connects these dynamics to an Ising-model energy landscape whose low-noise stationary behavior concentrates on the risk-dominant equilibrium.
- Game and state space: Players occupy graph vertices and choose strategies x_i ∈ {+1, −1}, with payoffs determined by interactions with neighboring vertices.The game is defined on an undirected graph, and each player’s payoff sums the pairwise payoff matrix over its neighbors.
- Game and state space: The coordination-game assumption is a > d and b > c, with +1 designated as risk-dominant when a − b > d − c.Under this assumption, the associated local field h_i is positive for every node of non-vanishing degree.
- Dynamics: The noise parameter β controls departure from best response, with β = +∞ representing noise-free dynamics.Both synchronous updates and asynchronous Poisson-clock updates are defined through conditional strategy distributions.
- Dynamics: The asynchronous logit or Glauber dynamics defines a reversible Markov chain with an Ising-model energy function.The model’s stationary distribution for large β concentrates around the all-(+1) configuration.
- Energy and hitting time: Representing configurations as subsets S of +1 vertices yields H(S) − H(∅) = 2 cut(S, V \ S) − 2|S|h.The energy is submodular, and the paper studies the hitting time T+ to the all-(+1) configuration.
3 Main results
The paper characterizes noisy best-response convergence using dual graph quantities, then derives exact and approximate implications for graph families. The results establish a dichotomy: low-dimensional, locally connected graphs converge quickly, while expander-like and highly connected structures can converge exponentially slowly.
- Main characterization: The paper defines tilted cutwidth and tilted cut as dual quantities that characterize convergence through paths to equilibrium and bottlenecks between configuration sets.Tilted cutwidth gives an upper-bound path to the +1 equilibrium, while tilted cut captures a bottleneck along a highest separating set.
- Main characterization: For the slowest subgraph, tilted cut and tilted cutwidth coincide, and the hitting time is exponential in this graph parameter.The coincidence holds under the stated nonnegative-bias condition.
- Main characterization: The exact characterizations are difficult to compute, motivating reductions to graph expansion, special graph families, and approximately optimal vertex orderings.The paper connects these quantities to isoperimetric functions and sparsest-cut algorithms.
- Relation to graph expansion: Finite-range networks spread +1 from a sufficiently large compact region, while expander-like networks are dominated by highly connected subgraphs that are loosely tied to the rest of the graph.The finite-range mechanism relies on the bias hmin > 0; small-world networks with r ≥ d can be blocked in their final stages by small highly connected regions.
- Approximating tilted cut and tilted cutwidth: The approximation result allows sparse-cut algorithms to find approximately optimal orderings, and polynomial-time orderings satisfy cut(St, V \ St) = O(|St|h log^2 n + L log n).The ordering guarantee applies under the theorem’s assumptions on induced-subgraph cutwidth and the condition in equation (9).
- Special graph classes: The propositions show that vertex degree alone does not determine convergence: broad classes of noisy best-response dynamics behave differently on regular expanders and low-dimensional grids.The comparison includes k-regular graphs with vertex expansion and d-dimensional grids, for both synchronous and asynchronous dynamics.
4 Proofs
The proofs connect low-temperature hitting times to energy barriers and characterize those barriers through monotone paths, tilted cutwidth, and induced subgraphs.
- Hitting-time characterization: Hitting times at low temperature scale exponentially with an energy barrier determined by the Markov chain's stationary measure and transition rates.The typical hitting time is expressed as τ_A = exp{βeΓ_A + o(β)}.
- Tilted graph quantities: Glauber dynamics satisfies the hypotheses needed to express the hitting-time exponent using tilted cutwidth and tilted cut quantities.The proof first establishes the tilted-cutwidth characterization and then the tilted-cut characterization.
- Monotone paths: The convergence analysis reduces to finding the most likely path from the worst-case configuration, whose barrier is minimized by a monotone path.The proof uses spectral arguments and a submodularity-based argument to establish monotonicity.
- Induced subgraphs: The optimal barrier can be realized on an induced subgraph, with the full graph and that subgraph having the same leading exponential hitting-time scale.The induced subgraph is selected to attain the maximum relevant barrier.
- Graph-specific bounds: Graph-specific bounds follow by estimating cutwidth and isoperimetric quantities for finite-range and embeddable graphs.The proofs use a relaxation, a generalized Cheeger inequality, and bounded-support functions to obtain the required cut bounds.
A Proof of Lemma 4.3
The proof of Lemma 4.3 applies a Cheeger-type argument to relate a function's gradient norm to weighted sets and graph cuts.
- Normalization: The argument normalizes the function by setting its maximum absolute value to one and uses the standard Cheeger-inequality technique.Under this normalization, f_i = 1 for vertices in Ω_1.
- Cheeger-type bounds: The proof bounds the relevant quotient through successive upper and lower estimates on its numerator and denominator.The displayed intermediate steps involve cut(S_z, V \ S_z) and level sets S_z.
- Minimizing level set: Choosing a minimizing level set S = S_z* completes the construction while preserving the weighted-size bounds required by the lemma.The level sets satisfy Ω_1 ⊆ S_z ⊆ Ω_0, yielding L_1 ≤ |S|_w ≤ L_2.
B Hitting times at low temperature: proof of Lemma 4.1
This proof analyzes low-temperature hitting times for reversible Markov chains by relating killed-chain spectral quantities to paths and boundary flows.
- Restricted chain: The argument considers a reversible discrete-time Markov chain and studies transitions restricted to states outside a target set A.The restricted transition kernel is used to analyze the time required to hit A.
- Spectral argument: The killed transition matrix has a leading eigenvalue whose spectral behavior determines the tail and hitting-time estimates.Perron-Frobenius theory supplies a nonnegative leading eigenvector for the lower-bound argument.
- Lower bound: A lower bound follows by comparing each state outside A with a path or allowed transition leading to A and controlling the resulting congestion.The bound uses the maximum congestion over allowed transitions.
- Upper bound: An upper bound is obtained from a boundary set B outside A and a characteristic-function test in the variational estimate.The boundary consists of transitions leaving B, and the proof chooses ϕ as B's characteristic function.
C Proof of Lemma 4.2
The proof establishes a structural dichotomy for optimal paths by partitioning vertices according to marginal potential changes and applying supermodularity.
- Partition construction: The vertices are partitioned into consecutive subsets so that marginal potential changes remain negative within each subset until a nonnegative threshold is reached.The partition is constructed iteratively by adding vertices and starting a new subset when the marginal becomes nonnegative.
- Supermodularity: Supermodularity shows that if the marginal change for the last subset is negative at the endpoint, it remains negative for all later positions.This yields the first structural alternative for the final subset.
- Second case: If the endpoint marginal is nonnegative, explicit inequalities over the partitioned subsets establish the second alternative.The proof combines inequalities across subsets and cancels contributions from internal edges.
D Proof of Theorem 3.4
The proof partitions the graph recursively into subsets, arranges each induced subgraph by cutwidth, and concatenates these arrangements to bound the tilted cutwidth.
- Recursive partition: The proof recursively partitions V into subsets R1, R2, ..., Rl, stopping when no qualifying set S remains and assigning the residual vertices to Rl.The qualifying sets satisfy L1 ≤ |S|h ≤ L2, while the residual set obeys |Rl|h < L1 because L2 ≥ hmax.
- Recursive partition: For each vertex j in Vt, the induced-subgraph quantity satisfies (hVt)j = hj + |∂j|V \ Vt.This accounts for the contribution from neighbors outside the current vertex set.
- Cut bound: Each partition set Rt satisfies cut(Rt, Vt \ Rt) ≤ |Rt|^2h + cut(Rt, V \ Vt).The bound follows by applying Eq. (9) to the induced subgraph G(Vt) and using L1 ≤ |Rt|h.
- Cut bound: The proof sums the cut relation across partition stages before constructing the global ordering.The cumulative relation is used for all 1 ≤ t < l.
- Global ordering: Concatenating cutwidth-optimal arrangements of R1 through Rl yields an ordering whose tilted cutwidth can be bounded.For an intermediate prefix S, the proof writes S as the earlier blocks together with a subset R ⊂ Rt and bounds its cut.
E Eigenvectors and barriers
This appendix studies a general Markov chain through the principal eigenvector of a restricted transition matrix and derives a threshold set for bounding its variational quantity.
- Setup: The appendix considers a general Markov chain with state space S and a subset A of configurations.The construction is explicitly framed for an arbitrary chain and configuration subset.
- Eigenvector threshold: The principal eigenvector ψ0 of PA has eigenvalue 1 − λ0,A and can be chosen nonnegative by Perron–Frobenius.A threshold b ≥ 0 defines B = {x ∈ S : ψ0(x) > b}.
- Variational bounds: Using the indicator of B in the variational principle gives the upper bound immediately.The proof substitutes ϕ(x) = I(x ∈ B).
- Variational bounds: The lower-bound argument orders the distinct values of ψ0 and compares squared differences across these levels.For i < j, the squared difference is bounded below by the sum of squared successive gaps between ψ(i) and ψ(j).
- Variational bounds: Level sets Bl = {x ∈ S : ψ0(x) ≥ ψ(l)} connect the ordered eigenvector values to the lower-bound proof.The resulting relation implies the lemma's claimed conclusion.