Who Leads and Who Follows in Strategic Classification?

Abstract:
As predictive models are deployed into the real world, they must increasingly contend with strategic behavior. A growing body of work on strategic classification treats this problem as a Stackelberg game: the decision-maker “leads” in the game by deploying a model, and the strategic agents “follow” by playing their best response to the deployed model. Importantly, in this framing, the burden of learning is placed solely on the decision-maker, while the agents’ best responses are implicitly treated as instantaneous. In this work, we argue that the order of play in strategic classification is fundamentally determined by the relative frequencies at which the decision-maker and the agents adapt to each other’s actions. In particular, by generalizing the standard model to allow both players to learn over time, we show that a decision-maker that makes updates faster than the agents can reverse the order of play, meaning that the agents lead and the decision-maker follows. We observe in standard learning settings that such a role reversal can be desirable for both the decision-maker and the strategic agents. Finally, we show that a decision-maker with the freedom to choose their update frequency can induce learning dynamics that converge to Stackelberg equilibria with either order of play.

heading: 1 Introduction
text: Individuals interacting with a decision-making algorithm often adapt strategically to the decision rule in order to achieve a desirable outcome. While such strategic adaptation might increase the individuals’ utility, it also breaks the statistical patterns that justify the decision rule’s deployment. This widespread phenomenon, often known as Goodhart’s law, can be summarized as: “When a measure becomes a target, it ceases to be a good measure” [49].
A growing body of work known as strategic classification [14, 19, 28] models this phenomenon as a two-player game in which a decision-maker “leads” and strategic agents subsequently “follow.” Specifically, the decision-maker first deploys a decision rule, and the agents then take a strategic action so as to optimize their outcome according to the deployed rule, subject to natural manipulation costs. For example, a bank might make lending decisions using applicants’ credit scores. Knowing this mechanism, loan applicants might sign up for a large number of credit cards in an effort to strategically increase their credit score at little effort.
One of the main goals in the literature is to develop strategy-robust decision rules; that is, rules that remain meaningful even after the agents have adapted to them. Recent work has studied strategies for
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
finding such rules through repeated interactions between the decision-maker and the agents [6, 20, 46]. In particular, the decision-maker sequentially deploys different rules, and for each they observe the population’s response. Under certain regularity conditions, over time the decision-maker can find the optimal solution, defined as the rule that minimizes the decision-maker’s loss after the agents have responded to the rule.
With the emergence of online platforms such as social media and e-commerce sites, repeated interactions between decision-makers and the population have become ever more prevalent. Online platforms continuously monitor user behavior and update pricing algorithms, recommendation systems, and popularity rankings accordingly. Users, on the other hand, take actions to ensure favorable outcomes in the face of these updates.
A distinctive feature of online platforms is the decision-maker’s dominant computational power and abundant data resources, allowing the platform to react to any change in the agents’ behavior virtually instantaneously. For example, if fake news content changes over time, automated algorithms can quickly detect this and retrain the classifier to incorporate the shift. It has been observed [see, e.g., 16, 18, 45] that, when faced with such “reactive” algorithms, strategic agents tend to take actions that anticipate the algorithm’s response. That is, through repeated interactions, agents aim to find actions that maximize the agents’ utility after the decision-maker has responded to these actions. This suggests that the order of play in strategic interactions can in fact be reversed, such that the agents “lead” while the decision-maker “follows.”
To give an example of such a reversed strategic interaction, consider ride-sharing platforms that deploy algorithms for determining travel fare as a function of trip length and relevant traffic conditions. These pricing mechanisms are frequently updated based on the current supply and demand, and in particular a dip in the supply of drivers triggers a surge pricing algorithm. Möhlmann and Zalmanson [45] observed that drivers occasionally coordinate a massive deactivation of drivers from the system, artificially lowering driver supply, only to get back on the platform after some time has passed and the prices have surged. In this interaction, the drivers essentially make the first move, while the platform’s pricing algorithm reacts to their action. Other examples of users aiming to exert control over algorithms can be found in the context of social network analyses [16, 18].
In this work, we argue that the order of play in strategic classification is fundamentally tied to the relative update frequencies at which the decision-maker and the strategic agents adapt to each other’s actions. In particular, we show that, by tuning their update frequency appropriately, the decision-maker can select the order of play in the underlying game. Furthermore, in natural settings we show that allowing the strategic agents to play first in the game can actually be preferable for both the decision-maker and the agents. This is contrary to the order of play previously studied in the literature, whereby the decision-maker is always assumed to make the first move.

heading: 1.1 Our contribution
text: To give an overview of our results, we recall some relevant game-theoretic concepts. In the existing literature strategic classification is modeled as a Stackelberg game. A Stackelberg game is a twoperson game where one player, called the leader, moves first, and the other player, called the follower, moves second, with the possibility of adapting to the move of the leader. Previous work assumes that the decision-maker acts as the leader and the agents act as the follower. This means that the decision-maker first deploys a model, and the agents then modify their features at some cost in order to obtain a favorable outcome according to the model. The decision-maker’s goal is to find the Stackelberg equilibrium—the model that minimizes the decision-maker’s loss after the agents have optimally adapted to it. This optimal reaction by the agents is called the best response to the model.
An important parameter that has been largely overlooked in existing work is the rate at which the agents re-evaluate and potentially modify their features. Most works studying the interaction between a decision-maker and strategic agents implicitly assume that, as soon as the model is updated, the data collected from strategic agents follows the best response to the currently deployed model. In the current work we do not assume that the agents react instantaneously to model updates. Instead, we assume that there is a natural timescale according to which the agents adapt their features to models.
Allowing agents to adapt gradually to deployed models gives the decision-maker a new dimension upon which to act strategically. Faced with agents that adapt gradually, the decision-maker can choose the timescale at which they update the deployed model. In particular, they can choose a rate
of updates that is faster than the agents’ rate, or they can choose a rate that is slower than the agents’ rate. We call decision-makers that follow a faster clock than the agents reactive, and if they follow a slower clock we call them proactive. Given that existing work on strategic classification relies on instantaneous agent responses, the previously studied decision-makers are all implicitly proactive.
Our first main result states that the decision-maker’s choice of whether to be proactive or reactive fundamentally determines the order of play in strategic classification. Perhaps counterintuitively, by choosing to be reactive it is possible for the decision-maker to let the agents become the leader in the underlying Stackelberg game. Since changing the order of play changes the game’s natural equilibrium concept, this choice can have a potentially important impact on the solution that the decision-maker and agents find. Throughout, we refer to the Stackelberg equilibrium when the decision-maker leads as the decision-maker’s equilibrium and the Stackelberg equilibrium when the agents lead as the strategic agents’ equilibrium.
Theorem 1.1 (Informal). If the decision-maker is proactive, the natural dynamics of strategic classification converge to the decision-maker’s equilibrium. If the decision-maker is reactive, the natural dynamics of strategic classification converge to the strategic agents’ equilibrium.
To provide some intuition for Theorem 1.1, imagine that one player makes updates with far greater frequency than the other player. This allows the faster player to essentially converge to their best response between any two updates of the slower player. The slower player is then faced with a Stackelberg problem: they have to choose an action, expecting that the faster player will react optimally after their update. As a result, the optimal choice for the slower player is to drive the dynamics toward the Stackelberg equilibrium where they act as the leader.
It is well known (see, e.g., Section 4.5 in [5]) that under general losses, either player can prefer to lead or follow in a Stackelberg game, meaning that a player achieves lower loss at the corresponding equilibrium. Our second main takeaway is that in classic learning problems it can be preferable for both the decision-maker and the agents if the agents lead in the game and the decision-maker follows. One setting where this phenomenon arises is logistic regression with static labels and manipulable features.
Theorem 1.2 (Informal). Suppose that the decision-maker implements a logistic regression model and the strategic agents aim to maximize their predicted outcome. Then, both the decision-maker and the strategic agents prefer the strategic agents’ equilibrium to the decision-maker’s equilibrium.
Theorem 1.2 suggests that there are other meaningful equilibria than those previously studied in the literature. Moreover, Theorem 1.1 proves that such equilibria can naturally be achieved if the decision-maker is reactive and agents are no-regret. Seeing that the decision-maker’s equilibrium has also been shown to imply a cost to social welfare [30, 44], our results pave the way for studying new, potentially more desirable solutions in strategic settings.

heading: 1.2 Related work
text: Our work builds on the growing literature on strategic classification [see, e.g., 2, 11, 14, 19, 20, 25, 26, 28, 30, 35, 38, 42, 44, 51, and the references therein]. In these works, a decision-maker seeks to deploy a predictive model in an environment where strategic agents attempt to respond in a post hoc manner to maximize their utility given the model. Given this framework, a number of recent works have studied natural learning dynamics for learning models that are robust to strategic manipulation of the data [6, 17, 20, 30, 38, 48]. Such problems have also been studied in the more general setting of performative prediction [13, 31, 41, 43, 46]. Notably, all of these works model the interaction between the decision-maker and the agents as a repeated Stackelberg game [50] in which the decision-maker leads and the agents follow, and these roles are immutable. This follows in a long and continuing line of work in game theory on playing in games with hierarchies of play [3–5].
Learning in Stackelberg games is itself a growing area in game-theoretic machine learning. Recent work has analyzed the asymptotic convergence of gradient-based learning algorithms to local notions of Stackelberg equilibria [20–22] assuming a fixed order of play. The emphasis has largely been on zero-sum Stackelberg games, due to their structure and relevance for min-max optimization and adversarial learning [21, 33]. Such results often build upon work on two-timescale stochastic approximations [10, 36] in which tools from dynamical systems theory are used to analyze the limiting behavior of coupled stochastically perturbed dynamical systems evolving on different timescales.
In this paper we depart from this prior work in both our problem formulation and our analysis of learning algorithms. To begin, the problem we consider is asymmetric: one player, namely the strategic agents, makes updates at a fixed frequency, while the opposing player, the decision-maker, can strategically choose their update frequency as a function of the equilibrium to which they wish to converge. Thus, unlike prior work, the choice of timescale becomes a strategic choice on the part of the decision-maker and consequently the order of play in the Stackelberg game is not predetermined.
Our analysis of learning algorithms is also more involved than previous works since both the leader and follower make use of learning algorithms. Indeed, throughout our paper we assume that the population of agents is using no-regret learning algorithms, common in economics and decision theory [8, 9, 24, 27, 29, 39, 47]. This captures the reality that agents gradually adapt to the decisionmaker’s actions on some natural timescale. In contrast, existing literature on strategic classification and learning in Stackelberg games assume that the strategic agents or followers are always playing their best response to the leader’s action. One exception is recent work [32] that replaces agents’ best responses with noisy responses, which are best responses to a perturbed version of the deployed model. While this model does capture imperfect agent behavior, it does not address the effect of learning dynamics and relative update frequencies on the agents’ actions.
Given this assumption on the agents’ learning rules, we then show how decision-makers who reason strategically about their relative update frequency can use simple learning algorithms and still be guaranteed to converge to game-theoretically meaningful equilibria. Our analysis complements a line of recent work on understanding gradient-based learning in continuous games, but crucially does not assume that the two players play simultaneously [see, e.g., 12, 40]. Instead, we analyze cases where both the agents and decision-maker learn over time, and play asynchronously.
This represents a departure from work in economics on understanding equilibrium strategies in games and the benefits of different orders of play [see, e.g., 3, 4] in Stackelberg games. In our problem formulation, players do not have fixed strategies but must learn a strategy by learning about both their loss and their opponent’s through repeated interaction.
Some of our analyses touch on ideas from online convex optimization [52], specifically derivative-free optimization [1, 15, 23, 37]. Several works [20, 43] within strategic classification and performative prediction apply similar zeroth-order tools to find the decision-maker’s equilibrium, but once again assuming immediate best responses to deployed models. We show that such algorithms are versatile enough to be used without such strong assumptions while still having strong convergence guarantees.

heading: 1.3 Organization
text: This paper is organized as follows. In Section 2 we introduce our model for studying the interaction between a decision-maker and strategic agents that adapt gradually to deployed decision rules, and formalize the concept of reactive and proactive decision-makers. In Section 3 we show that under natural assumptions, a proactive or reactive decision-maker can drive the game towards the decisionmaker’s or agents’ equilibrium, respectively, by using simple learning rules. We follow this in Section 4 by showing how in simple learning problems inducing a certain order of play can benefit both the decision-maker and the agents. We conclude in Section 5 with a brief discussion of the questions our proposed model raises and some directions for future work.

heading: 2 Model
text: We start with an overview of the basic concepts and notation, and then discuss the main conceptual novelty of our work—implications of the decision-maker’s and strategic agents’ update frequencies.

heading: 2.1 Basic concepts and notation
text: Throughout we denote by z = (x, y) the (feature, label) pairs corresponding to the strategic agents’ data. We assume that the decision-maker chooses a model parameterized by θ ∈ Θ ⊆ Rd, where Θ is convex and closed, and that their loss is measured via a convex loss function `(z; θ). The strategic agents measure loss via a function r(z; θ) and, collectively, they form a distribution in the family {P(µ) : µ ∈M ⊆ Rm}, whereM is convex and closed. Here, µ denotes the aggregate summary of
all agents’ actions. The data observed by the decision-maker is P(µ) and as such varies depending on the agents’ aggregate action µ.
We denote L(µ, θ) = Ez∼P(µ)`(z; θ), and R(µ, θ) = Ez∼P(µ)r(z; θ). With this, the agents’ best response is given by µBR(θ) = arg minµR(µ, θ) and the decision-maker’s best response is given by θBR(µ) = arg minθ L(µ, θ). We assume that the best responses for both players are always unique.
If the decision-maker acts as the leader in the game, their incurred Stackelberg risk is equal to SRL(θ) = L(µBR(θ), θ). Similarly, we let SRR(µ) = R(µ, θBR(µ)) denote the Stackelberg risk of the agents when they lead in the game. We let θSE and µSE denote the decision-maker’s and strategic agents’ equilibrium, respectively: θSE = arg minθ SRL(θ) and µSE = arg minµ SRR(µ). We assume that each equilibrium is unique. Note that the two players cannot compute their respective equilibrium “offline”, as we do not assume they have access to the other player’s loss function.
As discussed earlier, we assume that there is an underlying timescale according to which the agents re-evaluate their features. Specifically, after each time interval of fixed length, the agents observe the currently deployed model, as well as their loss according to that model, and possibly modify their features accordingly. The decision-maker, aware of the agents’ timescale, can choose to be proactive, meaning they choose an update frequency slower than that of the agents, or reactive, meaning they choose a higher update frequency. This power asymmetry that allows the decision-maker to choose a timescale is characteristic of online platforms with abundant resources. Implicit in our setup in an assumption that the decision-maker can evaluate the agents’ update frequency and adapt to it. Big IT companies generally employ monitoring systems that detect distribution shift; at a high level, the rate of distribution shift can be thought of as the rate of agents’ adaptation.
We use the term epoch to refer to a period between two updates of the slower player (which player is the slower one is up to the decision-maker). In particular, the t-th epoch starts with a single update of the slower player, followed by τ ∈ N updates of the faster player. The rate τ is fixed. We use θt and µt to denote the iterate of the decision-maker and the strategic agents, respectively, at the end of epoch t. Furthermore, for the faster player, we use double-indexing to denote the within-epoch iterates. For example, if the decision-maker is the faster player, we use {θt,j}τj=1 to denote their iterates within epoch t. Note that θt,τ ≡ θt. We also let θ̄t = 1τ ∑τ j=1 θt,j . We adopt similar notation when the agents have a higher update frequency.

heading: 2.2 Rational agents in the face of varying update frequencies
text: Adopting the distinction between reactive and proactive decision-makers, it is crucial to re-evaluate what it means for the strategic agents to behave rationally. We argue that rational behavior must depend on the relative update frequencies of the decision-maker and the agents.
As a running toy example, consider a decision-maker building a model with the goal of distinguishing between spam and legitimate emails. The population of strategic agents aims to craft emails that bypass the decision-maker’s spam filter. Here, µ could determine the number of words in an email, types of words used, etc. The loss R(µ, θ) could be some decreasing function of the number of daily clicks on email content, given spam filter θ and emails crafted according to µ. In the following discussion assume that the timescales of the decision-maker and the agents have a significant separation: the decision-maker is either “significantly faster” or “significantly slower.” As we will make more formal later on, our results will generally assume a sufficiently large separation between the timescales. In the following paragraphs we informally describe rational agent behavior in the context of update frequencies.
Proactive decision-maker. First, assume that the decision-maker is proactive, and suppose they deploy model θ. By definition, this model remains in place for a relatively long time, as observed by the agents. Then, by choosing features µ, the agents experience loss R(µ, θ) during that period, and as a result the most rational decision is to choose features µBR(θ). In the running example, if θ is a spam filter that is in place for many months, it is rational for spammers to craft emails that are most likely to bypass filter θ. This is just the usual best response—as we alluded to earlier, when the decision-maker is proactive, our setup is similar to that of previous work.
Reactive decision-maker. Now assume that the decision-maker is reactive, and suppose the agents observe θ as the current model. Then, by setting µ, the agents do not experience loss R(µ, θ). Rather,
their loss is R(µ, θR(µ)), where θR(µ) denotes the decision-maker’s reaction to the agents’ choice µ. In the spam example, suppose that the decision-maker can aggregate and process data quickly, and retrains the spam filter every couple of hours. Moreover, suppose that the spammers adapt their emails only once per week. Then, the agents’ loss after choosing µ (evaluated weekly) is determined by the number of clicks allowed by the updated filter θR(µ), not the old filter θ. Therefore, if the agents could predict θR(µ), the agents’ optimal decision would be to choose arg minµR(µ, θR(µ)). In other words, rather than choose the best response to θ, rational agents interacting with a reactive decision-maker would choose µ so that it triggers the best possible reaction from θ.
We formalize this intuitive behavior by assuming that the agents are no-regret learners [47]. This essentially means that their average regret vanishes as the number of actions grows. More formally, we assume the following behavior depending on the relative update frequencies:
• If the decision-maker is proactive, then for any θt, the agents’ strategy ensures:
1
τ τ∑ j=1 ER(µt,j , θt)−min µ R(µ, θt)→ 0 as τ →∞. (A1)
• If the decision-maker is reactive, then for any response function θR(µ), the agents’ strategy ensures:
1
T T∑ t=1 ER(µt, θR(µt))−min µ R(µ, θR(µ))→ 0 as T →∞, (A2)
whenever such a strategy exists. If the agents’ loss is convex, the first condition can be satisfied by simple gradient descent. In fact, gradient descent would typically imply an even stronger guarantee, namely the convergence of the iterates, µt,τ → µBR(θt). The second condition can be satisfied by various bandit strategies if R(µ, θR(µ)) is Lipschitz andM is bounded (and we will impose these conditions explicitly in the following section). That said, it seems hardly suitable to assume that the agents run a well-specified optimization procedure. For this reason, we will for the most part avoid making explicit algorithmic assumptions on the agents’ strategy and our main takeaways will only rely on rational agent behavior in the limit, as in equations (A1) and (A2).

heading: 3 Learning dynamics
text: In this section, we study the limiting behavior of the interaction between the decision-maker and the strategic agents. We show that, by running classical optimization algorithms, the decision-maker can drive the interaction to a Stackelberg equilibrium with either player acting as the leader.

heading: 3.1 Convergence to decision-maker’s equilibrium
text: In general, we do not expect the decision-maker to be able to compute derivatives of the function SRL. For this reason, to achieve convergence to the decision-maker’s equilibrium, we consider running a derivative-free method. One such solution is the “gradient descent without a gradient” algorithm of Flaxman et al. [23]. Past work [20, 43] also considers this algorithm with the goal of optimizing SRL, but it assumes instantaneous agent responses. In other words, it assumes query access to SRL directly, while we consider perturbations due to imperfect agent responses. It is worth noting that, under further assumptions, one could apply more efficient two-stage approaches [31, 43] that approximate the gradients of SRL by first estimating the best-response map µBR.
Specifically, we let the decision-maker run the following update:
φt+1 = ΠΘ(φt − ηt d
δ L(µ̄t, φt + δut)ut), where ut ∼ Unif
( Sd−1 ) . (1)
Here, ΠΘ denotes the Euclidean projection, Unif ( Sd−1 ) denotes the uniform distribution on the unit sphere in Rd, ηt is a non-increasing step size sequence, and δ > 0 is a fixed hyperparameter. The deployed model in the t-th epoch is set as θt = φt + δut.2
2Technically, this assumes that we can deploy a model in a δ-ball around Θ. Another solution would be to use a projection onto a small contraction of Θ in equation (1). This is a minor technical hurdle common in the literature. The rate in Theorem 3.1 is unaffected by the choice of solution to this technical point.
We provide convergence guarantees assuming that the decision-maker’s Stackelberg risk SRL is convex. While this condition doesn’t follow from convexity of the loss `(z; θ) alone, previous work has established conditions for convexity of this objective for different learning problems and agent utilities [20, 43]. For example, in the linear and logistic regression examples discussed in the following section, the decision-maker’s Stackelberg risk will be convex.
Theorem 3.1. Denote by DΘ the diameter of Θ, and suppose that |L(µ, θ)| ≤ B for all µ, θ. Furthermore, suppose that SRL is convex and β-Lipschitz and L(µ, θ) is βµ-Lipschitz in the first entry for all θ. Then, if the decision-maker runs update (1) with ηt = η0d− 1 2 t− 3 4 and δ = δ0d 1 2T−1/4, it holds that
T∑ t=1 (E[SRL(θt)]− SRL(θSE)) ≤ ( D2Θ 2η0 + 2B2 δ20 )√ dT 3/4 + βµDΘ T∑ t=1 E‖µ̄t − µBR(θt)‖2.
Moreover, assuming that the agents are rational (A1) andM is compact, we have
lim τ→∞ T∑ t=1 (E[SRL(θt)]− SRL(θSE)) ≤ ( D2Θ 2η0 + 2B2 δ20 )√ dT 3/4. (2)
Remark 3.2. For Theorem 3.1, we assume that the agents are rational in a relatively weak sense, by assuming no-regret behavior. Often, however, we expect the agents’ strategy to achieve iterate convergence, and not just vanishing regret. More precisely, it makes sense to expect µt,τ → µBR(θt) as τ →∞. For example, this guarantee is achieved by gradient descent in a variety of settings. In that case, the decision-maker can simply use the last iterate instead of the average one:
φt+1 = ΠΘ(φt − ηt d
δ L(µt, φt + δut)ut), where ut ∼ Unif
( Sd−1 ) . (3)
Similarly, E‖µ̄t − µBR(θt)‖2 would be replaced by E‖µt − µBR(θt)‖2 in the bound of Theorem 3.1. Remark 3.3. The rateO( √ dT 3/4) is characteristic of the Flaxman et al. [23] zeroth-order algorithm. Subsequent work on bandit convex optimization has improved upon this rate in terms of T at the cost of worse dependence on d [1, 15, 37]. In this work we opt to analyze the Flaxman et al. method given its simplicity and the fact that its rate has not been uniformly improved upon. That said, we do not anticipate any difficulties in proving a result analogous to Theorem 3.1 in the context of a different bandit convex optimization algorithm. Specifically, we only require that the error ‖µ̄t − µBR(θt)‖2 propagates “smoothly” to the decision-maker’s regret.
In some cases, the additional regret due to imperfect agent responses does not alter the asymptotic rate at which the decision-maker accumulates regret even if the epoch length τ is constant and does not grow with T . To illustrate this point, we consider strategic agents that follow the gradient-descent direction on a possibly nonconvex objective with enough curvature. More precisely, we assume that for all θ, R(µ, θ) satisfies the Polyak-Łojasiewicz (PL) condition:
γ(R(µ, θ)− min µ∈M R(µ, θ)) ≤ 1 2 ‖∇µR(µ, θ)‖22,
for some parameter γ > 0. Suppose that the agents’ update is computed as:
µt,j+1 = µt,j − ηµ∇µR(µt,j , θt), (4)
where ηµ > 0 is a constant step size and µt,0 = µt−1,τ . In this case, gradient descent achieves last-iterate convergence and hence we assume that the decision-maker uses the update in equation (3).
Theorem 3.4. Assume the conditions of Theorem 3.1. In addition, suppose thatR(µ, θ) is βRµ -smooth in µ for all θ and satisfies the PL condition with parameter γ, and µBR(θ) is βBR-Lipschitz in θ. Assume that the strategic agents run update (4) with ηµ < 1βRµ . Further, suppose the epoch length is chosen so that τ > log(βRµ /γ)/ log (1/(1− γηµ)). Then, for some constant α(τ) ∈ (0, 1), we have
T∑ t=1 E‖µt − µBR(θt)‖2 ≤ ‖µ0 − µBR(θ0)‖2 + 4βBRBη0δ0 √ T 1− α(τ) .
Therefore, the decision-maker’s regret is O( √ dT 3/4) even with a constant epoch length. This result crucially depends on the fact that the optimization problems that the agents solve in neighboring epochs are coupled through µt,0 = µt−1,τ . If µt,0 were reinitialized arbitrarily in each epoch, the extra regret would be linear in T given constant epoch length.
By using standard tools from the stochastic approximation literature [10], in the Appendix we additionally provide convergence to local optima for the update (3) when SRL is possibly nonconvex.

heading: 3.2 Convergence to strategic agents’ equilibrium
text: Now we analyze the case when the decision-maker is reactive. Given a large enough gap in update frequencies—that is, a large enough epoch length τ—the decision-maker can converge to their best response to the current iterate µt between any two actions of the agents. The most natural choice for achieving this is to run standard gradient descent, θt,k+1 = θt,k − ηk∇θL(µt, θt,k). In what follows we provide asymptotic guarantees assuming that the decision-maker runs any algorithm that achieves iterate convergence. This condition can be satisfied by gradient descent in a variety of settings. Formally, we assume that for any fixed µt, the decision-maker’s strategy ensures
‖θt,τ − θBR(µt)‖2 →p 0, (5) as τ →∞. Here,→p denotes convergence in probability. We first observe that, in the limit as τ grows, the agents’ accumulated risk is equal to their accumulated Stackelberg risk at all the actions played so far. This simply follows by continuity. Lemma 3.5. Suppose that the decision-maker achieves iterate convergence (5) and R is continuous in the second argument. Then, for all T ∈ N, limτ→∞ ∑T t=1 ER(µt, θt) = ∑T t=1 ESRR(µt).
In other words, in every epoch the agents essentially play a Stackelberg game in which they lead and the decision-maker follows. This holds regardless of whether the agents behave rationally. If they do behave rationally (condition (A2)), we show that both the agents’ and the decision-maker’s average regret with respect to (µSE, θBR(µSE)) vanishes if the agents’ updates are continuous. To formalize this, suppose that for all t ∈ N, the agents set µt+1 = Dt+1(µ1, θ1, . . . , µt, θt, ξt+1), where Dt+1 is some fixed map and ξt+1 is a random variable independent of {(µi, θi)}i≤t. We include ξt+1 as an input to allow randomized strategies. Then, we will say that the agents’ updates are continuous if Dt+1 is continuous in the first 2t coordinates for all t ∈ N. Theorem 3.6. Suppose that the agents’ updates are continuous and rational (A2), and thatM is compact. Further, suppose that the decision-maker achieves iterate convergence (5) and SRR and SRL are Lipschitz. Then, it holds that
lim T→∞ lim τ→∞
1
T T∑ t=1 ESRR(µt)− SRR(µSE) = 0,
lim T→∞ lim τ→∞
1
T T∑ t=1 EL(µt, θt)− L(µSE, θBR(µSE)) = 0.

heading: 4 Preferred order of play
text: While we have shown that the decision-maker can tune their update frequency to achieve either order of play in the Stackelberg game, it remains to understand which order of play is preferable for the decision-maker and the strategic agents. In the following examples, we illustrate that in classic learning settings both players can prefer the order when the agents lead. This suggests that the natural and overall more desirable order of play is sometimes reversed compared to the order usually studied.
At first, it might seem counterintuitive that the decision-maker could prefer to follow. To get some intuition for why following might be preferred to leading, recall that in zero-sum games following is never worse. In particular, suppose R(µ, θ) = −L(µ, θ). Then, the basic min-max inequality says
L(µSE, θBR(µSE)) = max µ min θ L(µ, θ) ≤ min θ max µ L(µ, θ) = L(µBR(θSE), θSE),
with equality if and only if a Nash equilibrium exists. Therefore, if a Nash equilibrium does not exist, following is strictly preferred.
Since strategic classification is typically not a zero-sum game, we look at two common learning problems and analyze the preferred order of play.

heading: 4.1 Linear regression
text: Suppose that the agents’ non-strategic data, (x0, y), where x0 is a feature vector and y the outcome, is generated according to x0 ∼ P0, y = x>0 β + ξ, where P0 is a zero-mean distribution such that Ex0∼P0x0x>0 = I , β ∈ Rd is an arbitrary fixed vector, and ξ has mean zero and finite variance σ2. We denote the joint distribution of (x0, y) by P(0). Recall that we use z to denote the pair (x, y). Suppose that the decision-maker runs standard linear regression with the squared loss:
`(z; θ) = 1
2 (y − x>θ)2.
The agents aim to maximize their predicted outcome, r(z; θ) = −θ>x, subject to a fixed budget on feature manipulation—they can move to any x at distance at most B from their original features x0: ‖x − x0‖2 ≤ B. A similar model is considered by Kleinberg and Raghavan [35] and Chen et al. [17]. More precisely, we letM = {µ ∈ Rd : ‖µ‖2 ≤ B} and define P(µ) to be the distribution of (x, y), where (x0, y) ∼ P(0) and x = x0 + µ. Then, R(µ, θ) = Ez∼P(µ)r(z; θ) = −µ>θ and L(µ, θ) = Ez∼P(µ)`(z; θ). We prove that both the decision-maker and the agents prefer the agents’ equilibrium. Proposition 4.1. Assume the linear regression setup described above. Then, we have
σ2 2 + ‖β‖22 min(1, B)2 2(1 + min(1, B)2) = L(µSE, θBR(µSE)) ≤ SRL(θSE) = σ2 2 + ‖β‖22B2 2(1 +B2) ,
−‖β‖2 min(1, B) 1 + min(1, B)2 = SRR(µSE) ≤ R(µBR(θSE), θSE) = − ‖β‖2B 1 +B2 .
When B ≤ 1, the losses implied by the two scenarios are the same, while when B > 1, having the agents lead is strictly better for both players. Moreover, the strategic agents’ manipulation cost is no higher when they lead: ‖µSE‖2 ≤ ‖µBR(θSE)‖2.

heading: 4.2 Logistic regression
text: Next we consider a classification example. Suppose that the non-strategic data (x0, y) is sampled according to a base joint distribution P(0) supported on Rd × {0, 1}. Unlike in the linear regression example, we place no further constraint on P(0). We assume that the decision-maker trains a logistic regression classifier:
`(z; θ) = −yx>θ + log(1 + ex >θ).
The agents with y = 0 can manipulate their features to increase the probability of being positively labeled. A similar setup is considered by Dong et al. [20]. As in the previous example, the agents have a limited budget to change their features: if their non-strategic features are x0, they can move to any x which is at distance at most B from x0, ‖x− x0‖2 ≤ B. Thus, we setM = {µ ∈ Rd : ‖µ‖2 ≤ B} and denote by P(µ) the joint distribution of (x, y) where (x0, y) ∼ P(0) and x = x0 + µ1{y = 0}. We let R(µ, θ) = −µ>θ and L(µ, θ) = Ez∼P(µ)`(z; θ). Proposition 4.2. Assume the logistic regression setup described above. Then, we have
L(µSE, θBR(µSE)) ≤ SRL(θSE) and SRR(µSE) ≤ R(µBR(θSE), θSE).
There exist configurations of parameters such that the inequalities in Proposition 4.2 are strict, meaning that both players strictly prefer the agents to lead. We illustrate this empirically. In Figure 1 we generate non-strategic data according to y ∼ Bern (p) and x0|y ∼ N(4y − 2, 1) and plot the difference in risk between the two equilibria for the decision-maker and the agents, for varying B and p. For large p and small B, we see no difference between the equilibria. However, as p decreases and B increases, it becomes suboptimal for both players if the decision-maker leads.

heading: 5 Discussion
text: We have shown how the consideration of update frequencies allows natural learning dynamics to converge to Stackelberg equilibria where either player can act as the leader. Moreover, we observed that the previously unexplored order of play in which the agents lead can result in lower risk for both players. We have only begun to understand the implications of reversing the order of play in strategic classification, and update frequencies in general, and many questions remain open for future work.
In social settings, there are many considerations and concerns beyond minimizing risk. While our preliminary observations suggest that reversing the order of play might have benefits, we have yet to fully understand the impact of this reversed order on the population interacting with the model. That said, we do not propose a new type of interaction; real-world decision-making algorithms already possess, and employ, the power to be reactive. Our new framework is simply flexible enough to capture the difference between proactive and reactive decision-makers.
Furthermore, we assume that the agents act on a fixed timescale. Sometimes it is possible for the agents to choose their timescale strategically. In that case, there is first a “meta-game” between the decision-maker and the agents, as they might compete for the leader/follower role. For example, if both prefer to lead, then both might aim to make slow updates to reach the leader position; perhaps surprisingly, this incentive might prevent any interaction at all.
Finally, we study order-of-play preferences only in linear/logistic regression with linear agent utilities. There are many other learning settings and classes of agents’ utilities and costs in the literature, and going forward it is important to obtain general conditions when leading (or following) is preferable.

heading: Acknowledgements
text: We thank Moritz Hardt for an inspiring discussion and helpful feedback on this project. We wish to acknowledge support from the Office of Naval Research under the Vannevar Bush Fellowship program and support from HICON-LEARN (Design of HIgh CONfidence LEARNing-Enabled Systems), Defense Advanced Research Projects Agency award number FA8750-18-C-0101.

Review summaries:
This paper studies a variant of strategic classification where there is not instantaneous interaction between the learner and the agents, but rather, there is a “slower” and a “faster” player (i.e., the whole interaction is governed by the frequencies according to which the learner and the agents update their decisions). This variant is closer to real-life settings, where for example the learner may have much more computational power compared to the agents. In their model, the agents are assumed to update their decisions at a fixed rate, and the learner gets to decide whether to be proactive (i.e., update his decisions slower than the agents) or reactive (i.e., update his decisions faster). After the learner announces the deployed model, the agents are broadly “rational”; to be more specific, they decide their reports based on no-regret algorithms (rather than the standard instantaneous best-response in prior work). The difference in timescales results in fact in a change of who the “leader” and who the “follower” is in the setting. The question that the paper addresses is what changes in terms of loss for the learner and the agents if there exists this timescale difference and whether there are settings where it is best for both the agents and the learner to always have one of the two.  The paper has two main results. First, it shows that if the learner is proactive (resp. reactive), then the learning dynamics of the system converge to the learner’s equilibrium (resp. agents’ equilibrium). Second, it shows that if the learner runs linear or logistic regression and the agents aim to maximize their predicted score, it is preferred by both the learner and the agents that the agents “lead” (i.e., that the learner is reactive). In terms of techniques, the paper uses variants of standard tools in Bandit Convex Optimization (BCO), assuming that everything is smooth enough (i.e., convex, smooth, Lipschitz).

The paper argues for a more general view on strategic classification of objects modified by adversaries. In the standard view, the designer of the classifier is assumed to be the leader and the classifier is optimized with respect to a best response form the data generator to its parameters. This paper argues that in some situations, it may be possible and desirable to reverse the roles and force the rational attacker to create objects first and optimize them with respect to the expected best response classifier. The paper shows how different update frequencies of individual players using no regret and gradient descent learning can lead to convergence to the equilibria in either assignment of the roles. Furthermore, the paper shows that for linear and logistic regression, each of the role assignments can be desirable for each of the players depending on parameters, such as the magnitude of the allowed perturbation by the attacker. 

Almost all of the literature on strategic classification is situated in a Stackelberg game setting in which the decision-maker leads, committing to a model, after which agents follow, best-responding to the model. The core insight of this work is that in some real life situations, the decision-maker is able to adjust their model more rapidly than agents are able to adjust their strategic adaptation, leading to a reversal of the traditional order of play: the agents become the leader, and the decision-maker becomes the follower. The authors compare the dynamics of these "proactive" and "reactive" regimes, which differ in the comparative frequency of the two parties' updates, under the weak assumption that agents are no-regret learners. In particular they give conditions under which the learning dynamics converge to Stackelberg equilibria. Finally, they show that in two simple examples (linear regression and logistic regression with bounded actions of linear cost), the equilibrium in which the agents lead is at least as preferable (and sometimes more preferable) for _both_ agents.

The authors study an extension of strategic classification in which they consider how the time it takes the model designer and agents to react to one another effects the dynamics of strategic classification. Differences in the updating frequencies of the two parties can essentially switch which party is the leader (typically the model designer is the leader).  Different equilibria can arise depending on which party has the faster update frequency. Convergence to these equilibria is characterized in the case of agents leading and also the model designer leading. Additionally, cases in which having the agents be the leaders is desirable for both parties are outlined.