PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing Stationary Equilibria in Measure-Dependent Markov Systems

Jing Dong, Bar Light, Xin Tong

arXiv:2609.17584v1cs.GTmath.PR

TL;DR

When a stochastic system’s transition law depends on its own long-run distribution, ordinary stationary analysis does not by itself solve the resulting equilibrium problem. The paper reduces the problem to a finite-dimensional self-consistency equation, matches algorithms to its structure, and develops finite-time IPA gradient estimators; queueing and opinion-model examples illustrate different computational approaches.

  • Problem

    When the transition law depends on the distribution being evolved, familiar convergence properties of ordinary Markov chains need not carry over, and direct iteration may be unreliable.

    Source: §1 · pp. 1–2

  • Method

    The paper reduces equilibrium computation to a finite-dimensional self-consistency equation and develops finite-time IPA estimators for its Jacobian to support residual-gradient methods.

    Source: §1 · pp. 3–4, §2 · p. 7

  • Results

    In the strategic G/G/c queue, relaxed iteration converges when an additional one-sided stability condition holds, while the opinion model’s order-preserving map supports convergent monotone iteration.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Different structural properties of the stationary response map lead naturally to different equilibrium-computation methods in the queueing and opinion-dynamics examples.

    Source: §1 · p. 4

    The paper uses a terminal-time estimator to separate Monte Carlo error from finite-time bias; time-average analogues require control of serial dependence, such as mixing or summable covariance bounds.

    Source: §4 · p. 13

Abstract

from arXiv · show

Many stochastic systems in operations and economics exhibit feedback between their long-run state distribution and the transition law governing their dynamics. In this paper, we develop a computational framework for stationary equilibria in such measure-dependent Markov systems when this feedback operates through a finite-dimensional aggregate. We show that the original stationary-equilibrium problem can be reduced to a finite-dimensional self-consistency equation, separating steady-state analysis of the underlying Markov system from equilibrium computation. We use properties of the resulting self-consistency map to guide the choice among fixed-point iteration, relaxed fixed-point iteration, and minimization of the fixed-point residual. The last approach requires derivatives of the self-consistency map, which are typically unavailable in closed form. We therefore develop finite-time infinitesimal perturbation analysis estimators for these derivatives, with error bounds that separate Monte Carlo error from finite-time bias. We illustrate the framework through a strategic $G/G/c$ queue and an opinion-dynamics model, showing how different structural properties lead naturally to different equilibrium-computation methods.

1 Introduction

Measure-dependent Markov systems require a distribution to be invariant under the transition law it induces, while that law must reflect the distribution it generates. The paper reduces this problem to a finite-dimensional self-consistency equation and uses the map’s structure to guide computation, including in queueing and opinion models.

1 Introduction

  • When behavior and population outcomes interact, stationary equilibrium requires their long-run distribution and transition law to be mutually consistent.This matters for evaluating congestion and social outcomes, and analytical solutions are often unavailable outside stylized models.Source: §1 · p. 2
  • A finite-dimensional aggregate lets the authors freeze the transition kernel, compute its stationary distribution, and solve for an aggregate that matches the one generated at stationarity.Under uniqueness of the frozen chain’s stationary distribution, the original equilibrium problem is equivalent to a fixed point of the stationary response map.Source: §1 · pp. 2–3
  • The response map’s structure guides method choice: contraction, order preservation, or one-sided stability can support different fixed-point schemes, while residual minimization is an alternative when iteration is unreliable.Residual minimization requires the Jacobian of the response map, which is typically unavailable in closed form.Source: §1 · p. 3
  • The paper develops finite-time IPA estimators for the response-map Jacobian, differentiating simulated paths and separating Monte Carlo error from finite-time bias.The analysis provides standard mean-squared-error bounds under Lyapunov moment control and a truncated estimator under weaker fractional stability.Source: §1 · pp. 3–4
  • In the strategic G/G/c queue, stationary perturbation bounds yield log-Lipschitz regularity, and relaxed iteration converges when an additional one-sided stability condition holds.For more complex queueing settings where structural conditions are difficult to verify, the finite-time IPA bound supports residual-gradient computation.Source: §1 · p. 4

1.1 Literature Review

  • The opinion model’s order-preserving response map supports monotone fixed-point iteration, while the paper’s broader approach extends beyond queueing to multidimensional aggregates.The literature review positions this as complementary to work on queue-specific behavioral equilibria and steady-state derivative estimation, with finite-time bounds derived from state-sensitivity stability.Source: §1 · p. 4, §1.1 · pp. 5–6

2 Problem Setup

When the transition law depends on the current distribution through a finite-dimensional aggregate, the nonlinear stationary-equilibrium problem can be reduced to a fixed point in that aggregate. Directly iterating the distribution can fail even when the reduced problem is well behaved.

2 Problem Setup

  • For each aggregate value, the setup freezes the transition kernel as an ordinary Markov chain; its stationary distribution determines the aggregate response.The aggregator can represent means, moments, type-specific averages, or congestion measures.Source: §2 · p. 6
  • Directly iterating the nonlinear Markov operator can fail to converge because each updated distribution changes the transition kernel, even when a stationary equilibrium exists.In a two-state example, the iterates alternate between a_0 and 1-a_0 unless a_0=1/2, although (1/2, 1/2) is stationary.Source: §2 · p. 7
  • When each frozen chain has a unique stationary distribution, its equilibrium aggregate is a fixed point of the stationary response map, and that distribution is an equilibrium of the original system.The correspondence works in both directions under the uniqueness condition.Source: §2 · p. 7
  • The examples show that relaxed iteration on the reduced map can converge when direct iteration does not, and direct iteration can fail even when the reduced map is a contraction.The reduced method updates using the frozen chain’s stationary response; direct iteration feeds transient distribution changes back into subsequent dynamics.Source: §2 · pp. 7–8

3 Fixed Point Problem

The section presents fixed-point algorithms selected according to the self-consistency map’s structure, alongside residual minimization when fixed-point iteration is unsuitable. Each method has different requirements, and derivative-based optimization adds a need to estimate the map’s Jacobian.

3 Fixed Point Problem

  • The algorithmic development assumes each frozen transition kernel has a unique stationary distribution, so the response map is well defined.The paper identifies this as a standard ergodicity condition and gives sufficient conditions including compactness with the Feller property plus a Doeblin condition, or positive Harris recurrence with aperiodicity and irreducibility.Source: §3 · pp. 8–9
  • Residual-gradient methods can be used when fixed-point iterations are unstable or ineffective, but computing their gradients requires the response-map Jacobian, which is rarely available in closed form.Gradient descent has less restrictive convergence requirements than Picard or relaxed iteration, but depends on the gradient-estimation methods developed in Section 4.Source: §3 · p. 9
  • Picard iteration is suited to a contractive map, while relaxed fixed-point iteration can converge under weaker incremental one-sided conditions with Lipschitz regularity.The table summarizes recommended outer algorithms by structural conditions; the precise guarantees are deferred to Appendix A.2.Source: §3 · pp. 9–10, Table 1 · p. 9
  • When the aggregate space has an order and the map preserves it, monotone Picard iteration offers an alternative, including when convex relaxation or derivatives are not defined.This is relevant for nonconvex or discrete aggregate spaces.Source: §3 · p. 10
  • In the AR(1) example, Picard iteration has one locally stable equilibrium and another unstable one, while residual minimization treats both equilibria as global minima.The second equilibrium remains a locally well-conditioned minimum of the residual objective.Source: §3 · pp. 10–11

4 Gradient Estimation

The section develops finite-time IPA estimators for the Jacobian needed by residual-gradient methods, then derives stability conditions that control estimator error. It distinguishes when raw IPA has standard Monte Carlo guarantees from regimes where clipping provides robust consistency.

4 Gradient Estimation

  • Assuming G is three-times continuously differentiable near a, the two function estimates have variance of order N^-1, and finite-horizon bias is ignored, central differences use h ≍ N^-1/6 for MSE order N^-2/3, versus the usual Monte Carlo rate N^-1.Source: §4 · p. 11
  • IPA differentiates a simulated sample path and avoids finite-difference bias and resimulating each coordinate perturbation.The section separates Monte Carlo error from finite-time bias; time-averaged IPA can use simulation output more efficiently but requires control of serial dependence.Source: §4 · pp. 11, 13
  • Finite-time control of IPA error requires stability of the sensitivity recursion, since occasional Jacobian factors with norm above one can amplify derivatives despite geometric ergodicity of the state.The analysis uses average contraction of random Jacobian products and a Lyapunov function based on a Poisson equation.Source: §4 · p. 13

4.1 Stability of the Sensitivity Process

  • The stability conditions separate coupling of the driving process from contraction of the differentiated recursion, avoiding a direct ergodicity analysis of the full augmented process.The modular sufficient conditions allow Jacobian factors to exceed one at some times when their cumulative products contract in a fractional moment.Source: §4.1 · p. 15
  • Fractional-moment contraction can control bounded and clipped IPA functionals even when the sensitivity process is heavy-tailed and lacks first or second moments.This weaker stability alone does not provide the moment bounds needed for the usual MSE analysis of raw IPA.Source: §4.1 · p. 16

4.2 IPA Gradient Estimation Analysis

  • With sufficiently strong moment control, raw IPA achieves the standard Monte Carlo rate; with only fractional stability and first-moment integrability, clipping yields robust consistency.The Lyapunov-controlled analysis imposes moment and coupling controls on the IPA summand that enters the finite-time bias.Source: §4.2 · p. 16, §4.2.1 · p. 16

4.2.1 The Lyapunov-Controlled Case

  • The additional estimator conditions separately provide augmented-process moment control, second-moment control of the IPA summand, and fractional coupling of that summand.The conditions are stated directly for the IPA summand, preserving generality when the objective gradient is unbounded or not globally Lipschitz.Source: §4.2.1 · p. 17

Appendix B.3.

The section develops finite-time IPA error controls, including clipping and sufficient conditions for stability of the sensitivity process. It also relates replication count to total simulation work.

Appendix B.3.

  • O(N^-1) error in independent replications can require O(N log N) simulated transitions when each trajectory runs for O(log N) steps.The resulting serial-work bound carries a logarithmic overhead; the replication-based rate is natural when trajectories run in parallel.Source: Appendix B.3 · pp. 17–18

4.2.2 The clipped IPA estimator

  • Clipping decomposes the estimator error into Monte Carlo error, finite-time truncated bias, and stationary truncation bias.The clipped summand is bounded by M, enabling a bounded-summand Monte Carlo estimate.Source: §4.2.2 · p. 18
  • The stationary truncation bias vanishes as M grows when the IPA summand has a finite first moment.An additional 1+δ moment condition yields an explicit clipping-bias bound.Source: §4.2.2 · p. 19
  • Radial clipping supports finite-time analysis through its Lipschitz property, whereas hard truncation generally needs an anti-concentration condition or carefully chosen cutoffs.Both methods have bounded-summand variance and similar stationary tail bias.Source: §4.2.2 · p. 19

4.3 Weak contraction on average

  • Recurrent resets can yield weak average contraction when sensitivity resets occur and the time to the next reset has a geometric tail.The paper identifies drift-and-small-set arguments as one way to obtain that tail bound.Source: §4.3 · pp. 19–20
  • Negative stationary mean-log growth is another sufficient route to sensitivity decay, but almost-sure decay alone does not ensure the needed fractional-moment bound.Rare episodes of large expansion can dominate positive moments; quantitative concentration conditions provide a sufficient route.Source: §4.3 · pp. 20–21

5 Application: Strategic G/G/c Queue

The queue application freezes the aggregate to analyze a standard workload chain, then imposes self-consistency on the aggregate and stationary workload distribution. It establishes equilibrium existence and develops relaxed fixed-point and IPA approaches for computing it.

5 Application: Strategic G/G/c Queue

  • The application models a first-come, first-served G/G/c queue whose interarrival-time law depends on an aggregate congestion statistic of the waiting-time distribution.Freezing the aggregate gives a Kiefer–Wolfowitz workload recursion; equilibrium requires the aggregate to match the stationary response.Source: §5 · p. 22
  • Under Assumption 5 and a nonempty, closed, convex aggregate set, the strategic queue has a stationary equilibrium.The equilibrium aggregate is a fixed point of G, and its corresponding frozen workload distribution is stationary.Source: §5 · pp. 22, 24

5.1 Relaxed Fixed Point Iterations for Strategic 𝐺/𝐺/𝑐Queue

  • For scalar congestion feedback, G is decreasing and has a unique fixed point; relaxed iteration with δ_k = δ_0(k + 1)^-2/3 converges for sufficiently small δ_0.The result assumes the conditions of Example 7 and Assumption 5, with H Lipschitz in W1.Source: §5.1 · p. 24
  • For the strategic M/M/1 mean–variance example, a verified one-sided condition and a Lipschitz map yield linear convergence of relaxed iteration for damping parameters satisfying the stated inequality.Figure 1 distinguishes parameter combinations where the one-sided condition is numerically verified from those where it is not; the latter does not imply divergence.Source: §5.1 · p. 25, Figure 1 · p. 25

5.2 IPA for the Strategic 𝐺/𝐺/𝑐Queue

  • The queue’s empty-state reset helps stabilize pathwise sensitivities, and the finite-time IPA result estimates G's derivative with error bounds uniform over a∈K.The theorem assumes light-tail and stability/reset conditions and IPA regularity; the paper notes bounded-gradient statistics such as mean waiting time.Source: §5.2 · pp. 26–27

6 Application: Opinion Dynamics

The opinion-dynamics application turns type-level belief feedback into a finite-dimensional self-consistency problem, while the conclusion emphasizes matching computational methods to the structure of the response map. In both settings, the stationary distribution of a frozen system supplies the response used to test equilibrium consistency.

6 Application: Opinion Dynamics

  • In the heterogeneous-agent model, fixed types update beliefs using their current belief, a social signal, and an idiosyncratic shock.The aggregate is the vector of type-level mean beliefs, and the population law evolves as a nonlinear Markov chain.Source: §6 · pp. 27–28
  • For the noisy mean-field DeGroot example, 0 ≤ α_τ < 1 and the stated shock moment condition ensure a unique stationary distribution for each frozen aggregate.The resulting map is affine and coordinatewise nondecreasing; with the additional stated condition, its fixed point is unique and standard iteration converges globally.Source: §6 · p. 28
  • For more general opinion dynamics, monotone updating, frozen-chain convergence, continuity, and uniform integrability conditions yield a continuous nondecreasing map whose iteration converges monotonically to a fixed point.The theorem applies on an invariant order interval K.Source: §6 · p. 29

7 Conclusion

  • The framework reduces measure-dependent equilibrium to a finite-dimensional equation and develops finite-time IPA derivative estimators with separate Monte Carlo and finite-time-bias bounds.Different structural properties of the stationary response map call for different equilibrium-computation methods.Source: §7 · pp. 29–30

A Algorithmic Summary for the Fixed Point Problem

The algorithmic summary selects a fixed-point method according to the geometry and regularity of the self-consistency map. Its conditions range from contraction and monotonicity to one-sided bounds and gradient-descent geometry.

1. Contraction

  • When G is a contraction, Picard iteration is the natural method, and constant-damping relaxed iteration also converges linearly.The stated factor for relaxed iteration is 1 − δ + δL.Source: A Algorithmic Summary for the Fixed… · p. 32

2. Monotone order interval

  • On an order interval, a continuous coordinatewise nondecreasing G and suitable lower and upper bounds ensure fixed-point iteration converges to a fixed point.The stated result also covers relaxed iteration with constant damping.Source: A Algorithmic Summary for the Fixed… · p. 32

3. Nonexpansive

  • For nonexpansive G, relaxed iteration with constant damping gives an ergodic O(1/k) decay rate for the fixed-point residual.The supplied result concerns the minimum squared residual among the first N iterates.Source: A Algorithmic Summary for the Fixed… · p. 32

4. Lipschitz with an incremental one-sided condition

  • For Lipschitz G satisfying the incremental one-sided condition, constant-damping relaxed iteration converges linearly when the stated q_δ is below one.The condition is implied by the stated Jacobian bound when G is continuously differentiable.Source: A Algorithmic Summary for the Fixed… · p. 32

5. Log-Lipschitz with an incremental one-sided condition

  • With the incremental one-sided and log-Lipschitz conditions, sufficiently small decreasing damping yields convergence to the unique fixed point.The result assumes a fixed point exists.Source: A Algorithmic Summary for the Fixed… · p. 32

6. Gradient descent under PL geometry

  • Under the stated smoothness and Polyak–Łojasiewicz conditions, gradient descent on the residual objective drives its value to zero, with accumulation points that are fixed points of G.The supplied summary also gives a sufficient Jacobian condition for the PL inequality.Source: A Algorithmic Summary for the Fixed… · p. 33

A.1 Primitive conditions for regularity of the self-consistency map

This section links properties of the frozen Markov kernels to regularity of the self-consistency map. Uniform contractivity supports Lipschitz continuity, while geometric convergence with nonexpansiveness supports a log-Lipschitz conclusion.

A.1 Primitive conditions for regularity of the self-consistency map

  • The section derives sufficient conditions on frozen kernels that connect model primitives to monotonicity or Lipschitz regularity of G.The results link outer-algorithm convergence criteria to properties of the kernels used in applications.Source: §A.1 · p. 33
  • Under Assumption 9, uniform contractivity of the frozen kernels yields Lipschitz continuity of G when the aggregator is Lipschitz.Theorem 8 gives a perturbation bound for the stationary response.Source: §A.1 · p. 34
  • When frozen kernels are nonexpansive but converge geometrically to stationarity, the stated conditions yield log-Lipschitz regularity of G.The conclusion also assumes a Lipschitz aggregator.Source: §A.1 · p. 34
  • The bounded metric assumption is for technical convenience; the result extends to an unbounded metric when the measures have finite d-moments and the assumptions hold on that class.The stated extension avoids requiring boundedness of the metric itself.Source: §A.1 · p. 35

A.2 Convergence Analyses for Fixed Point Algorithms

The convergence analyses give guarantees for fixed-point and relaxed iterations under monotonicity, nonexpansiveness, one-sided conditions, and log-Lipschitz regularity. They also analyze gradient descent on the fixed-point residual and clarify what its stationarity guarantee does not establish without a PL condition.

A.2 Convergence Analyses for Fixed Point Algorithms

  • On a coordinatewise order interval, continuity, monotonicity, and suitable lower and upper bounds ensure fixed-point and constant-damping relaxed iterations converge to a fixed point.The iterates converge monotonically within the interval.Source: §A.2 · pp. 35–36
  • For nonexpansive G with a fixed point, relaxed iteration with constant damping has an O(1/N) bound on the minimum squared residual over the first N iterates.The result notes that δ = 1/2 maximizes the decaying rate.Source: §A.2 · p. 36
  • For Lipschitz G satisfying the incremental one-sided condition, relaxed iteration converges to a unique fixed point when q_δ < 1.The proposition states q_δ = (1 − δ)^2 + 2cδ(1 − δ) + δ^2L^2.Source: §A.2 · p. 36
  • With an incremental one-sided condition and log-Lipschitz regularity, sufficiently small decreasing damping yields convergence to a unique fixed point.The proposition assumes a fixed point exists.Source: §A.2 · p. 37
  • Under the PL condition, gradient descent drives the residual objective to zero, and every accumulation point is a fixed point of G.The stated Jacobian condition gives the PL inequality and rules out spurious critical points of the residual objective.Source: §A.2 · pp. 39–40
  • Without a PL condition, gradient descent still has an O(1/k) stationarity bound, but this alone need not imply convergence to a fixed point.The stated reason is that I − ∇G(a) may be singular, so a small gradient need not force a small fixed-point residual.Source: §A.2 · pp. 40–41

A.3 Proof of Theorems 7 – 9

The appendix proves order and regularity properties used in the equilibrium analysis, then establishes conditions for sensitivity contraction and bounds the finite-time gradient estimator's error.

A.3 Proof of Theorems 7 – 9

  • Under the monotonicity assumptions, induction carries ordering of the frozen chains to their stationary distributions and coordinatewise ordering of f.The proof of the second part reverses an induction inequality under Assumption 8.Source: §A.3 · p. 41

B.1 Auxiliary Results

  • A centered Lipschitz function b yields a Lipschitz solution to the Poisson equation and a Lipschitz associated function under Assumption 2(1).The lemma also assumes E[b(Y∞)] = 0.Source: §B.1 · p. 43

B.2 Proof of Theorem 1

  • The proof of Theorem 1 bounds its terms using weak average contraction, coupling contraction, and a transient moment condition for ξ.It combines the resulting bounds over m = 0, …, T−1.Source: §B.2 · pp. 45, 47

B.3 From sensitivity contraction to summand contraction

  • With bounded, Lipschitz gradients, the sensitivity process satisfies Condition 3 of Assumption 3 with β = γ^s.The stated setup takes s in (0, min{q0/4, 1/4}).Source: §B.3 · p. 47

B.4 Proof of Theorem 2.

  • Theorem 2 combines a Monte Carlo variance bound with a squared finite-time bias bound to control estimator error.The bias argument uses a uniform second-moment bound and the sensitivity-contraction condition.Source: §B.4 · p. 48

C.1 Uniform ergodicity and stationary perturbation

This appendix establishes uniform stability and parameter sensitivity for frozen queue chains, then applies those properties to equilibrium maps and IPA derivatives.

C.1 Uniform ergodicity and stationary perturbation

  • Each frozen queue chain has a unique invariant distribution and uniform geometric convergence, with one-step parameter sensitivity bounded in W1.The convergence constants are independent of the parameter.Source: §C.1 · pp. 50–51

C.2 Scalar Strategic G/G/c Queue

  • The scalar strategic G/G/c equilibrium map is decreasing, so it has at most one fixed point; relaxed fixed-point iteration converges under the stated step-size schedule.The schedule is δ_k = δ_0(k + 1)^−2/3 for sufficiently small δ_0.Source: §C.2 · p. 52

C.3 Mean-Variance Feedback M/M/1 Queue

  • For the mean-variance feedback M/M/1 map, the sufficient one-sided condition bounds the symmetric Jacobian above by c_os < 1, and G is Lipschitz on K.The Lipschitz argument covers the boundary between active and inactive regions.Source: §C.3 · pp. 52–53

C.4 IPA for Strategic G/G/c queue

  • The queue workload has an almost-sure finite-horizon pathwise derivative, and the proof establishes the stationary IPA identity rather than assuming it.The finite-horizon derivative is stated under Assumption 6.Source: §C.4 · pp. 53, 57

D Opinion Dynamics Appendix

The appendix uses within-type stochastic order and continuity of frozen stationary distributions to establish order and continuity properties of the opinion-dynamics self-consistency map.

D Opinion Dynamics Appendix

  • States are compared only within type, while the type marginal remains fixed and the belief coordinate evolves.The within-type order compares beliefs for states sharing the same type.Source: D Opinion Dynamics Appendix · p. 57
  • Under weak kernel continuity, uniqueness of the invariant distribution, and tightness, the frozen stationary distribution varies weakly continuously with the parameter.The continuity result is stated for invariant distributions within a weakly closed set.Source: D Opinion Dynamics Appendix · pp. 58–59
  • The self-consistency map G is coordinatewise nondecreasing and continuous on K.The argument transfers within-type stochastic order to type-level means and uses uniform integrability for continuity.Source: D Opinion Dynamics Appendix · p. 60
  • The order, continuity, and boundary properties verify the conditions of Proposition 6 for G.The proof establishes that G(K) is contained in K.Source: D Opinion Dynamics Appendix · p. 60
Loading 2609.17584v1…