Who leads and who follows in strategic classification?

Theorem (proactive decision-maker). Let the decision-maker run the one-point zeroth-order method of Flaxman et al., $\phi_{t+1}=\Pi_\Theta\big(\phi_t-\eta_t\tfrac d\delta L(\bar\mu_t,\phi_t+\delta u_t)u_t\big)$, deploying $\theta_t=\phi_t+\delta u_t$, where $\bar\mu_t$ is the agents' average action in epoch $t$. If $SR_L$ is convex and $\beta$-Lipschitz, $|L|\le B$, and $L$ is $\beta_\mu$-Lipschitz in $\mu$, then with $\eta_t\propto d^{-1/2}t^{-3/4}$ and $\delta\propto d^{1/2}T^{-1/4}$, $$\sum_{t\le T}\big(\mathbb E\,SR_L(\theta_t)-SR_L(\theta_{SE})\big)\le C\sqrt d\,T^{3/4}+\frac d\delta\,\beta_\mu D_\Theta\sum_{t\le T}\mathbb E\|\bar\mu_t-\mu_{BR}(\theta_t)\|,$$ and under (A1) with $\mathcal M$ compact the last sum vanishes as $\tau\to\infty$: the usual zeroth-order regret plus a bias from agents not yet at their best response, which long epochs remove. Constant epochs. If the agents instead run warm-started gradient descent on a smooth Polyak-Lojasiewicz objective and $\mu_{BR}$ is Lipschitz, a fixed epoch length biases the decision-maker's gradient estimate toward the stable-point condition and regret is linear; the epoch length has to grow with $T$ (logarithmically in $dT$ suffices) to reach the leader's optimum at the $O(\sqrt d\,T^{3/4})$ rate (Step 3).

The slower player faces a Stackelberg problem, because the faster one has already converged. Take $\tau\to\infty$ before $T\to\infty$. Against a proactive decision-maker the agents end each epoch at $\mu_{BR}(\theta_t)$, so the loss it observes for $\theta_t$ is $SR_L(\theta_t)$ up to the agents' lag. Against a reactive one the model ends each epoch at $\theta_{BR}(\mu_t)$, and by continuity $\lim_\tau\sum_t\mathbb E R(\mu_t,\theta_t)=\sum_t\mathbb E\,SR_R(\mu_t)$: the agents are scored on their Stackelberg risk whether they know it or not. Whoever is slow runs a learning rule on its own Stackelberg risk, and only the slow player's rationality decides which equilibrium is reached.

A proactive decision-maker reaches its equilibrium with a zeroth-order method, and the agents' lag enters as a bias. It cannot differentiate through $\mu_{BR}$, so it uses $\tfrac d\delta\,\mathrm{loss}(\phi+\delta u)\,u$, an unbiased gradient of the ball-smoothed $SR_L$; the standard online analysis gives $\sqrt d\,T^{3/4}$. The new piece is that the queried loss is $L(\bar\mu_t,\theta_t)$ in place of $L(\mu_{BR}(\theta_t),\theta_t)$, off by at most $\beta_\mu\|\bar\mu_t-\mu_{BR}(\theta_t)\|$; the one-point estimator scales any error in a function value by $d/\delta$, and in the descent inequality it multiplies $\|\phi_t-\hat\theta_{SE}\|\le D_\Theta$. Under (A1) and compactness, vanishing average regret against a unique minimizer forces the average lag to vanish.

With a constant epoch length the agents' lag biases the decision-maker toward the stable point, so epochs must grow with $T$. Gradient descent on a Polyak-Lojasiewicz objective contracts the distance to the minimizer by $\alpha(\tau)\lt1$ per epoch, so the warm-started lag $\epsilon_t=\|\mu_t-\mu_{BR}(\theta_t)\|$ satisfies $$\epsilon_t\le\alpha(\tau)\big(\epsilon_{t-1}+\beta_{BR}\|\theta_t-\theta_{t-1}\|\big),$$ forgetting its past at rate $\alpha$ and refreshed by however far the deployed model moved. The deployed model jumps by up to $2\delta$ each epoch through the fresh probe $u_t$, so the lag is of order $\delta$ every epoch, and the estimator multiplies it by $d/\delta$. The bias has a simple form: the probe moves the best response by about $\delta Ju_t$, with $J$ the Jacobian of $\mu_{BR}$, and if an epoch shrinks the lag by a factor $\rho$, only the fraction $1-\rho$ of that move has happened when the loss is read. To first order the expected estimate is $\nabla_\theta L+(1-\rho)J^\top\nabla_\mu L$ in place of $\nabla SR_L=\nabla_\theta L+J^\top\nabla_\mu L$, an interpolation between the stable-point condition ($\rho=1$) and the leader's ($\rho=0$). In an example meeting every assumption ($d=1$, $R=\tfrac12(\mu-\theta)^2$, $L=\tfrac12(\theta-1)^2+\mu\theta$, $\eta_\mu=\tfrac12$, $\tau=1$, so $\rho=\tfrac12$) the iterates settle at $1/(3-\rho)=0.4$ instead of $\theta_{SE}=1/3$, and regret grows linearly (my analysis, checked by simulation; not in the paper). Warm starts keep the lag at the probe scale, where reinitializing each epoch would leave a constant lag, but only epochs growing with $T$ (logarithmically in $dT$) recover the rate; the paper's experiments, with epochs of 100 to 200 steps, are long enough that the bias is negligible (my estimate).

A reactive decision-maker delivers the agents' equilibrium by a continuity argument, with no rates. Compare the real play with an ideal path $\mu^*_t$ that the agents' continuous update rule would produce if every model were exactly $\theta_{BR}(\mu)$. By induction on $t$, $\mu_t\to_p\mu^*_t$ as $\tau\to\infty$, since the decision-maker's iterates converge to $\theta_{BR}(\mu_t)$ and every map involved is continuous. On the ideal path (A2) is exactly vanishing regret on $SR_R$, and continuity carries it to the real path; uniqueness of $\mu_{SE}$ and compactness turn vanishing regret into vanishing average distance to $\mu_{SE}$, and a Lipschitz bound gives the decision-maker's loss. Both limits are needed: the agents must learn a bandit problem over epochs, and nothing says how long that takes.

In linear regression the leading agents stop at norm 1, which helps both sides. If the decision-maker leads, the agents push the full budget along the model, $\mu_{BR}(\theta)=B\theta/\|\theta\|$, and $$SR_L(\theta)=\tfrac{\sigma^2}2+\tfrac12\|\beta-\theta\|^2+\tfrac{B^2}2\|\theta\|^2,\qquad\theta_{SE}=\frac\beta{1+B^2}.$$ If the agents lead, the decision-maker answers a known shift with $\theta_{BR}(\mu)=(I+\mu\mu^\top)^{-1}\beta$, so $SR_R(\mu)=-\mu^\top\beta/(1+\|\mu\|^2)$, minimized along $\beta$ at $\|\mu\|=\min(1,B)$: past norm 1 the decision-maker discounts the manipulated direction faster than the push gains, and the milder shift also lowers the decision-maker's loss. Moreover the decision-maker-led outcome is a Nash equilibrium, a performatively stable point (my observation, checked numerically, not stated in the paper), because $\mu_{BR}$ moves orthogonally to $\theta$ while $L$ depends on $\mu$ only through $\mu^\top\theta$, so the indirect term in $\nabla SR_L$ vanishes. In this model the stable point and the decision-maker's optimum coincide, and the improvement comes only from letting the agents lead.

In logistic regression each inequality follows in one line. On the agents' side, the same orthogonality shows that $\nabla SR_L(\theta_{SE})=0$ implies $\nabla_\theta L(\mu_{BR}(\theta_{SE}),\theta_{SE})=0$, so $\theta_{SE}$ is a best response to $\mu_{BR}(\theta_{SE})$; leading agents can play $\mu_{BR}(\theta_{SE})$ and get the decision-maker-led outcome, and they can only do better. On the decision-maker's side, only label-0 points move and their loss increases in $\mu^\top\theta$, so the agents' best response is its worst case, $SR_L(\theta)=\max_{\mu\in\mathcal M}L(\mu,\theta)$, and for every $\theta$ $$L(\mu_{SE},\theta_{BR}(\mu_{SE}))\le L(\mu_{SE},\theta)\le\max_\mu L(\mu,\theta)=SR_L(\theta),$$ the min-max inequality of a game that is zero-sum along $\mu^\top\theta$. Strictness is numerical: the gap grows as fewer agents can manipulate a label and as $B$ grows.

In simulations both players do better when the agents lead. Wherever the two orders differ, both players do better when the agents lead, including in a setting the propositions do not cover. With budget-constrained agents, at $B=2$ both players' running risks settle at clearly better values when the agents lead, and at $B=1$ the equilibria coincide. With costly deviations, $R=\tfrac\lambda2\|\mu\|^2-\mu^\top\theta$, the response $\theta/\lambda$ is not orthogonal to $\theta$, so the decision-maker-led point is not a Nash point, and the ranking holds anyway, with a gap that shrinks as $\lambda$ grows. These are small, low-dimensional runs with step sizes tuned per setting.