PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Incentive Design for Linear-Quadratic Dynamic Games: No-Regret Social Coordination

Lantian Zhang, Yibei Li, Georgios Vasileiou, Lihua Xie, Silun Zhang

arXiv:2610.13448v1eess.SYcs.SY

TL;DR

Unknown agent preferences make it difficult for planners to align private incentives with social goals, especially in dynamic games where actions shape future costs. The paper develops an adaptive incentive framework that learns preferences while steering equilibrium behavior toward the social optimum. Its analysis establishes consistent learning and sublinear regret and net-budget imbalance relative to the full-information oracle.

  • Problem

    Planners must coordinate agents whose private preferences are unknown, while dynamic actions affect future costs and strategic responses.

    Source: §I · p. 1

  • Method

    The framework estimates preferences online and combines certainty-equivalent incentives with decaying random probing to steer a multi-agent LQ game's equilibrium.

    Source: §I · p. 2

  • Results

    The adaptive scheme achieves vanishing average regret relative to the full-information oracle and vanishing average net budget.

    Source: §I · p. 2, §VIII · p. 11

  • Takeaways & Limitations

    Preference learning and incentive design can be combined in a closed loop without requiring persistent excitation or i.i.d. trajectory data.

    Source: §I · p. 2

Abstract

from arXiv · show

Incentives can align private interests with collective goals, but their design becomes intertwined with learning when agents' preferences are unknown. This paper develops an adaptive incentive-design framework for multi-agent linear-quadratic dynamic games, where a system planner can simultaneously learn agents' private preferences and steer their strategic behavior towards the social optimum. To this end, we first characterize the complete family of affine incentives that implement the social optimum as the unique open-loop Nash equilibrium while ensuring exact budget balance. When agents' preferences are unknown, we develop an online algorithm to estimate their preference parameters and establish strong consistency of the estimates under a weak trajectory-dependent excitation condition, without requiring persistent excitation or i.i.d. trajectories. We then integrate this estimator into an active-learning incentive mechanism that combines certainty-equivalent coordination with decaying random probing. We prove that the probing generates sufficient information through the agents' equilibrium responses and the system dynamics, ensuring consistent preference learning from the resulting closed-loop trajectories. We show that the induced trajectories converge almost surely to their socially optimal counterparts, while cumulative social-cost regret relative to the full-information oracle and cumulative net-budget imbalance grow sublinearly. Simulations of a transboundary pollution game demonstrate the effectiveness of the proposed framework.

I. INTRODUCTION

The paper studies adaptive incentives for multi-agent LQ dynamic games, where unknown private preferences and dynamic strategic responses complicate social coordination. It combines preference learning with incentive design to steer equilibrium behavior toward the social optimum.

A. Related Work

  • Prior work studies adaptive incentive design, inverse cost learning, and adaptive control, while this paper considers a closed loop where incentives shape the trajectories used for learning.The paper distinguishes its setting by learning private costs rather than unknown physical dynamics and by influencing agents through payments rather than directly choosing their actions.Source: §I · p. 1, A. Related Work · p. 2

I. INTRODUCTION

  • Dynamic games require coordination across state–action trajectories because current actions shape future costs and strategic responses.The paper uses LQ games, with linear dynamics and quadratic objectives, as a tractable setting for this problem.Source: §I · p. 1
  • The framework learns unknown agent preferences from noisy responses while steering the induced Nash equilibrium toward the social optimum.Its three contributions characterize full-information incentives, establish consistent preference estimation without persistent excitation or i.i.d. trajectories, and combine certainty-equivalent design with decaying probing.Source: §I · p. 2

II. PRELIMINARIES: INCENTIVIZED LQ DYNAMIC GAMES

  • The model has a planner announce affine payment laws based on shared states and agents’ actions, while agents play an incentivized open-loop Nash equilibrium.Positive payments are taxes and negative payments are subsidies; private quadratic costs encode preferences over states and control effort.Source: §II · p. 3

III. PROBLEM FORMULATION: ADAPTIVE INCENTIVE DESIGN

The planner repeatedly selects incentives from past observations as agents respond with open-loop Nash strategies and noisy trajectories. The problem is to approach social-optimal behavior while average regret and net budget converge to zero; a full-information characterization provides a benchmark.

III. PROBLEM FORMULATION: ADAPTIVE INCENTIVE DESIGN

  • Each season, the planner selects incentives using prior observations, agents play the induced open-loop Nash equilibrium, and the planner observes a noisy state-action trajectory.Incentives for the next season can use the current observation, making the incentive sequence adaptive.Source: §III · p. 4
  • The target is the unique strategy profile minimizing social cost, with its state trajectory generated by the system dynamics.Uniqueness follows from strict convexity of the social cost.Source: §III · p. 4

A. Problem Formulation

  • The planner does not know agents’ preference parameters and uses past observations to steer their induced strategies toward the social optimum.The stated problem requires average regret and average net budget to converge to zero almost surely.Source: A. Problem Formulation · p. 4
  • The net-budget metric tracks the average surplus or deficit from transfers among participants.The formulation treats budget balance as a separate performance objective alongside social-cost regret.Source: A. Problem Formulation · p. 4
  • The stated assumptions require controllability of each (A, B_i), nonsingular A, a sufficiently long horizon, martingale-difference noise, and bounded initial states.The initial-state condition accommodates episodic settings and rolling horizons when the corresponding closed-loop system is stable.Source: A. Problem Formulation · p. 4

B. Incentive Design under Full Information

  • In the full-information case, the paper characterizes incentive profiles that achieve zero regret and zero net budget for each season.Proposition 1 gives an if-and-only-if characterization for incentives implementing the socially optimal strategy, under Assumption 1.Source: B. Incentive Design under Full… · p. 5
  • The full-information incentive family serves as a benchmark and basis for adaptive design when preference parameters are unknown.The characterization is stated for each season given the private cost parameters and initial state.Source: B. Incentive Design under Full… · p. 5

IV. ADAPTIVE PREFERENCE LEARNING

The section develops preference estimation from noisy observations of agents’ strategic behavior, using a bias-corrected recursive estimator. Its estimates are strongly consistent under trajectory-dependent excitation, without requiring persistent excitation or i.i.d. trajectories.

IV. ADAPTIVE PREFERENCE LEARNING

  • Pontryagin’s maximum principle yields a linear regression in the unknown preferences, but noisy observations perturb the regression and can bias ordinary least squares.The regression relates the agents’ state and IONE trajectories to the preference parameter vector.Source: §IV · p. 5
  • The proposed recursive least-squares estimator uses a bias-corrected loss to address errors-in-variables bias caused by observation noise.Its regularization term compensates for bias in the regression vector; the update uses the observed regression quantities and a Moore–Penrose pseudoinverse.Source: §IV · p. 5
  • The estimator is strongly consistent under a trajectory-dependent excitation condition, which permits temporally dependent and nonstationary trajectories without requiring persistent excitation or i.i.d. data.The condition requires sufficient information to accumulate in all parameter directions and accommodates the learning-and-decision feedback loop.Source: §IV · p. 6
  • The consistency theorem specifies the excitation needed for learning, while the following section designs incentives to generate informative trajectories with sublinear social-cost regret.The theorem’s condition concerns the trajectory and allows temporal dependence and nonstationarity when sufficient information accumulates in all parameter directions.Source: §IV · p. 6

V. ADAPTIVE INCENTIVE DESIGN

The adaptive design combines certainty-equivalent incentives based on current preference estimates with decaying random probing. Under the stated assumptions, the probing supplies information for consistent learning, while average regret and net-budget imbalance converge almost surely to zero.

V. ADAPTIVE INCENTIVE DESIGN

  • The algorithm constructs certainty-equivalent incentives by substituting current estimates of the unknown cost parameters into the full-information incentive construction.The certainty-equivalent output is projected onto a ball of radius log(h + 1), which is described as controlling the effect of inaccurate early estimates while the design stabilizes.Source: §V · p. 6
  • Algorithm 1 combines certainty-equivalent coordination with a shrinking random probe, generating information indirectly through agents’ open-loop Nash responses and the system dynamics.The certainty-equivalent incentive uses the current preference estimate; the planner perturbs payments rather than directly choosing agents’ actions.Source: §V · p. 6
  • Algorithm 1 alternates incentive design, agents’ open-loop Nash play, noisy trajectory observation, and a preference-estimate update.The planner observes the initial state before designing each incentive and updates from the resulting noisy trajectory.Source: §V · p. 7
  • Under the stated assumptions, the smallest eigenvalue of the information matrix grows at least as c_Λ h^(1−2nγ) almost surely after an almost surely finite index.The result quantifies the information generated by active probing even though its perturbation amplitude vanishes.Source: §V · p. 7
  • For the proposed adaptive incentive algorithm, the paper presents sublinear growth of cumulative regret and budget; Theorem 3 gives results under Assumptions 1–4 for average regret R(H) and average net budget B(H).Source: §V · p. 7
  • The parameter-learning error and the exploration signal contribute separate terms to both regret and net-budget bounds.The stated analysis requires 0 < γ < 1/(4n) for sublinear regret; balancing the polynomial orders gives γ⋆ = 1/(4n + 2).Source: §V · p. 7

VI. PROOF OF MAIN RESULTS

The proof section establishes the main theorems through preliminary bounds and martingale arguments. In the proof of Theorem 1, the information matrix eventually becomes invertible almost surely.

A. Proof of Theorem 1

  • The proof of Theorem 1 begins by establishing preliminary bounds in a lemma before deriving its result.The section identifies a martingale convergence result as part of the argument when β > 4.Source: A. Proof of Theorem 1 · pp. 7–8
  • The proof of Theorem 1 establishes that the information matrix’s minimum eigenvalue diverges almost surely, so the matrix is eventually invertible.An almost surely finite index exists after which the stated invertibility holds.Source: A. Proof of Theorem 1 · p. 7
  • The proof bounds separate summation terms using martingale-difference properties and previously established bounds.The cross-term argument uses that the sequence is a martingale difference and that the associated predictable term is suitably bounded.Source: A. Proof of Theorem 1 · pp. 7–8

B. Proof of Theorem 2

The proof of Theorem 2 builds on excitation bounds to establish strong consistency and sharpen the information-matrix growth bound. It then applies the estimator’s error bound to prove Theorem 2.

B. Proof of Theorem 2

  • A structured block-matrix lower bound is established under bounds on its entries, with a positive constant independent of the season index.The stated entry bounds use a sequence C_h; the resulting lower-bound constant μ is independent of h.Source: B. Proof of Theorem 2 · p. 8
  • The excitation lemmas connect excitation of the specified vectors to excitation of the regression vectors and augmented action-state vectors.The augmented-vector bound is stated for Algorithm 1 under Assumptions 1–4 and a sequence C_h = O(log h).Source: B. Proof of Theorem 2 · p. 8
  • The proof first establishes strong consistency of the parameter estimates, then sharpens the lower bound on the information matrix’s minimum eigenvalue.Once the estimates converge, the proof uses boundedness of the estimated parameters and related quantities to remove a logarithmic loss in the excitation bound.Source: B. Proof of Theorem 2 · pp. 8–9
  • With the excitation condition verified, the proof applies Theorem 1’s estimation-error bound to establish Theorem 2.The preceding argument shows almost-sure strong consistency of the estimates.Source: B. Proof of Theorem 2 · p. 9

C. Proof of Theorem 3

The proof derives a net-budget bound by combining the incentive perturbation and estimator-rate bounds with bounded probing.

C. Proof of Theorem 3

  • The incentive is expressed as a certainty-equivalent term plus a decaying probing term for sufficiently large h.The relation is stated as P_h = P̄_h + h^-γv_h, with the probing sequence uniformly bounded.Source: C. Proof of Theorem 3 · p. 10
  • A second-order Taylor expansion is used with a uniformly bounded Hessian to control the relevant objective change.The proof invokes the bounded Hessian of Φ(ξ_h, ·) over the relevant bounded set.Source: C. Proof of Theorem 3 · p. 10
  • The proof establishes the desired net-budget bound.It combines the incentive perturbation relation, the estimator's convergence rate, and a uniform bound on the probing sequence.Source: C. Proof of Theorem 3 · p. 10

VII. SIMULATION

The simulations apply the adaptive incentive algorithm to a transboundary pollution game and compare its learning and coordination outcomes with a certainty-equivalence baseline. The conclusion states that the framework achieves strong consistency under non-persistent excitation and sublinear regret and net budget relative to the oracle policy.

VII. SIMULATION

  • The simulation models countries choosing pollution-abatement strategies and a planner using subsidies to align mitigation with a global pollution-reduction objective.The discrete dynamic game represents countries' cumulative effects on pollution sinks.Source: §VII · p. 10
  • Algorithm 1's parameter-estimation error decreases while IOC-CE's remains larger, and only Algorithm 1's information-matrix minimum eigenvalue grows steadily.The baseline omits exploratory probing; Figure 1 compares squared estimation error and the minimum eigenvalue of accumulated information.Source: §VII · p. 11, Figure 1 · p. 11
  • Both average social-cost regret R(h) and average net budget B(h) approach zero under the proposed Algorithm 1.Figure 2 plots both quantities over time; its shaded regions indicate one standard deviation.Source: §VII · p. 11, Figure 2 · p. 11

VIII. CONCLUDING REMARKS

  • The framework establishes strong preference-estimate consistency under a non-PE condition and achieves sublinear regret and net budget relative to the oracle policy.The conclusion identifies open-loop Nash strategies as the setting and lists closed-loop Nash strategies, partial observations, and nonlinear dynamics and incentives as future extensions.Source: §VIII · p. 11

APPENDIX I

The appendix specifies the backward recursion for the socially optimal solution and describes the resulting strategy and state trajectory for each season.

APPENDIX I

  • The backward recursion is initialized with V*(T) = 0 and r*(T) = 0.The definitions proceed for t = T − 1, ..., 0.Source: Appendix I · p. 12
  • At each time t, V*(t) is defined using Q*, A, V*(t + 1), and K*(t).The displayed update is V*(t) = Q* + AᵀV*(t + 1)A − K*(t)ᵀBᵀV*(t + 1)A.Source: Appendix I · p. 12
  • For a given initial state ξh, the appendix writes the socially optimal strategy as U*h.The corresponding optimal state trajectory is generated recursively.Source: Appendix I · p. 12

APPENDIX II

The appendix develops algebraic steps for characterizing the equilibrium and budget conditions, including a regression identity for the unknown preferences.

APPENDIX II

  • Strict convexity makes each agent's first-order condition sufficient for its unique best response, yielding the stacked equilibrium relation.The proof states that stacking the conditions gives MU = −η − HP.Source: APPENDIX II · p. 13
  • An incentive satisfies the stated implementation and budget conditions exactly when it meets both the displayed incentive relation and the net-transfer condition.The proof states this equivalence after deriving the expression for total net transfer.Source: APPENDIX II · p. 13
  • The proof notes that the columns for constant incentive coefficients are zero in H but equal one in 1ᵀ.This distinction is used alongside H's full row rank in the characterization argument.Source: APPENDIX II · p. 13
  • Stacking the agent-level identities yields the regression relation (ϕh − δh)θ = yh.The proof obtains this relation by expressing each agent's observations as linear functions of the unknown parameters.Source: APPENDIX II · p. 13

APPENDIX III

Appendix III presents two martingale convergence results used in the proposed algorithm’s convergence analysis.

APPENDIX III

  • The appendix presents two martingale convergence results used in the algorithm’s convergence analysis.Source: APPENDIX III · p. 16
  • Lemma 8 assumes a martingale difference sequence with uniformly bounded conditional moments of order α>2, alongside an adapted sequence.Source: APPENDIX III · p. 16
  • Lemma 9 gives an almost-sure little-o bound on ∥Sh−¯Sh∥ relative to (λmax(Sh)+h)^η.Source: APPENDIX III · p. 16
Loading 2610.13448v1…