Incentive design constitutes a foundational paradigm for influencing the behavior of strategic agents, wherein a system planner (principal) publicly commits to an incentive mechanism designed to align individual objectives with collective social welfare. This paper introduces the Regret-Minimizing Adaptive Incentive Design (RAID) problem, which aims to synthesize incentive laws under information asymmetry and achieve asymptotically minimal regret compared to an oracle with full information. To this end, we develop the RAID algorithm, which employs a switching policy alternating between probing (exploration) and estimate-based incentivization (exploitation). The associated type estimator relies only on a weaker excitation condition required for strong consistency in least squares estimation, substantially relaxing the persistence-of-excitation assumptions previously used in adaptive incentive design. In addition, we establish the strong consistency of the proposed type estimator and prove that the incentive obtained asymptotically minimizes the planner's average regret almost surely. Numerical experiments illustrate the convergence rate of the proposed methodology.
Figures & tables
Fig. 1: Mean (solid) and ±1 standard deviation (shaded) of ∥θ^i(t)−θi∗∥2 and t−1Rt over 100 independent realizations of Algorithm 1 . Dashed lines indicate the a.s. convergence rates predicted in Theorem 3 .
Fig. 2: Estimation error ∥θ^i(t)−θi∗∥2 over a single realization of Algorithm 1 for a single agent. Dashed lines indicate the rate O(t−γ/2) , γ=2/3 . Columns vary the probing parameter σ2 . (Top row) ei(t)∼Unif[−0.5,0.5] . (Bottom row) ei(t) is a Rademacher-distributed random variable on {±0.1} .
Fig. 3: Average regret t−1Rt over a single realization of Algorithm 1 for a single agent. Model noise is ei(t)∼N(0,0.1) . Dashed lines indicate the rate O(tγ−1logt) . Columns vary the probing parameter σ2 and rows vary the switching parameter γ .