Who Leads and Who Follows in Strategic Classification?
Authors: Tijana Zrnic
Eric Mazumdar
Shankar Sastry
Michael Jordan
Venue: NeurIPS 2021 Poster (2021)
Keywords: strategic classification
strategic agents
learning dynamics
Stackelberg game
Stackelberg equilibrium

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.

Who Leads and Who Follows in Strategic Classificatton?
Tijana Zrnic
Eric Mazumdar" California Institute of Technology mazumdar@caltech edu
University of California, Berkeley tij anj 2rmicoberkeley edu
S. Shankar Sastry University of California, Berkeley sastry@eecs. berkeley. edu
Michael Jordan
University of California, Berkeley jordan@cs berkeley edu
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 model, and the strategic agents "follow" by playing their best response the deployed model. Importantly, in this framing, the burden of learning is placed solely on the decision-maket while the agents" best responses are implicitly treated as instantaneous. this work, we argue that the order 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. particular, by generalizing the standard model to allow both players to learn over time, show that a decision maaker that makes updates faster than the agents can reverse follows. the order of play, meaning that the agents lead and the decision-make We observe in standard learning settings that such a role reversal can be desirable for both the decision-maie makerr and the strategic agents. Finally, show that prcision-maker with the freedom to choose their update frequency can induce learning dynamics that converge Stackelberg equilibria with either order of play.
Introduction
Individuals interacting with decision-making algorithm often adapt strategically 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 's law, can be summarized as: "When measure becomes target, it ceases to be good measure"
49
growing body of work known as strategic classification two-player game in which decision-maker "leads" and strategic agents subsequently "follow." first deploys decision rule, and the agents then take a strategic
28 models this phenomenon as
Specifically, the decision-make action so as to optimize their outcome according the deployed rule, subject natural manipulation costs. For example, a bank might make lending decisions using applicants' credit scores. Knowing this mechanism, loan applicants might sign up for 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 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
"quual contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

finding such rules through repeated interactions between the decision- makerr and the agents (6 20 46] In particular, the decision-make sequentially deploys different rules, and for each they observe the population's '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 '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.
distinctive feature of online platforms is the decision-maker's dominant computational power and abundant data resources, allowing the platform react 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 '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 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 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 '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 mecision-maker and the strategic agents adapt 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 the order of play previously studied in the literature, whereby the decision-maker is always assumed to make the first move.
1.1 Our contribution
To give an overview of our results, we recall some relevant cheorthcoretic concepts. In the existing literature strategic classification is modeled as a Stackelberg game. A Stackelberg game is two- person 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-
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 decision-makes and strategic agents implicitly assume that, 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, 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 prcision-makers that follow 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 Recision-makers are all implicitly proactive.
Our first main result states that the decision-maker 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 's natural equilibrium concept, this choice can have potentially important impact on the solution that the decision-maker maker and agents find. Throughout, we refer to the Stackelberg equilibrium when the decision-mate 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 '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.I 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 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 cquilibrium. Our second main takeaway is that in classic learning problems it can be preferable for both the decision-make and the agents if the agents lead in the game and the decision-maker follows. One setting where this phenomenon arises 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-madd 's equilibrium.
Theorem 1.2 suggests that there are other meaningful equilibria than those previously studied in the literature. Moreover, Theorem L.1 proves that such equilibria can naturally be achieved if the decision-maie is reactive and agents are no-regret. Seeing that the decision maker's is equilibrium has also been shown imply cost to social welfare [30 44), our results pave the way for studying new, potentially more desirable solutions in strategic settings.
1.2
Related work
Our work builds on the growing literature on strategic classification [see, e.g., 2
99 20
25
and the references therein]. In these works, decision 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
26
28
30
35
manipulation of the data 6., 17 20
30
38
48). Such problems have also been studied in the more
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 long and continuing line of work in game theory on playing in games with hicrarchies of play 3
general setting of performative prediction [13 31
Learning in Stackelberg games is itself growing area in game- tthe-tthe machine learning. Recent work has analyzed the asymptotic convergence of gradient- bassed learning algorithms to local notions of Stackelberg equilibria [20) assuming 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 [T0 36 which tools from dynamical systems theory are used to analyze the limiting behavior of coupled stochastically perturbed dynamical systems evolving on different timescales.
3

---

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 fixed frequency, while the opposing player, the decision-maker can strategically choose their update frequency as a function of the equilibrium which they wish to converge. Thus, unlike prior work, the choice of timescale becomes a strategic choice on the part of the recision-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-regrer learning algorithms, common in economics and decision This captures the reality that agents gradually adapt to the decision- maker's 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 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.
theory [8] [ 24 27 29 39 47
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 meme--hheretticlly meaningfuul equilibria. Our analysis complements a line of recent work on understanding gradient- bbseed learning 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-maie 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 [ 23 37. Several works 220 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.
1.3 Organization
This paper is organized as follows. In Section we introduce our model for studying the interaction between a decision-maker and strategic agents that adapt gradually 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 decision- maker's s or agents" equilibrium, respectively, by using simple learning rules. We follow this in Section 4 by showing how in simple learning problems inducing certain order of play can benefit both the docision-make 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.
2 Model
We start with an overview of the basic concepts and notation, and then discuss the main conceptual novelty of our work-inplications of the deciisio-maker"" and strategic agents' update frequencies.
2.1 Basic concepts and notation
Throughout we denote by z = (x, y) the (feature, label) pairs corresponding to the strategic agents' data. We assume that the decision chooses a model parameterized by E θ C Rd, where O is convex and closed, and that their loss is measured via convex loss function E(2; 0). The strategic agents measure loss via a function r(2; 0) and, collectively, they form a distribution in the family (P(N): a E M C 12m) where M is convex and closed. Here, μ denotes the aggregate summary of

---

all agents' actions. The data observed by the decision-mann is P(u) and as such varies depending on the agents' aggregate action j..
We denote [(,, 0) = BempP())((2 0), and R(u,0) 0) = (=)-(()))();))) With this, the agents' best response is given by MBB (0) = arg min, R(,,0) 0) and the decision-maker's best response is given by OBR (1) arg ming [(u, 0). We assume that the best responses for both players are always unique. If the decision-matee SR₂ (0) = [pBB(()), (0), 0). Similarly, we let SRR(H) of the agents when they lead in the game. We let ASE and μSE denote the decision-maker's s and strategic agents' equilibrium, respectively: ASE = arg ming (0) and uSE = arg min, y ((1) 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.
acts as the leader in the game, their incurred Stackelberg risk is equal to
R(H, (B)) denote the Stackelberg risk
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-man maker, aware of the agents' timescale, can choose 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-male timescale is characteristic of online platforms with abundant resources. Implicit in our setup in an assumption that the decision-me -aaker can evaluate the agents' update frequency and adapt to it. Big IT companies generally employ monitoring systems that detect distribution shift; at high level, the rate of distribution shift can be thought of as the rate of agents' adaptation.
to choose a
We use the term epoch to refer to a period between two updates of the slower player (which player is In particular, the t-th epoch starts with a single update of
the slower one up to the decision-makern the slower player, followed by T E N updates of the faster player. The rate T is fixed.
We use 0, and μ4 to denote the iterate of the decision- 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 {0t5)]=1 to denote their iterates within epoch f. Note that or,- =\t O,. We also let 0g = = Ej Ozg- We adopt similar notation when the agents have higher update frequency.
2.2 Rational agents in the face of varying update frequencies
Adopting the distinction between reactive and proactive Dacision-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 running toy example, consider 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, i could determine the number of words in email, types of words used, etc. The loss R(,, 0) could be some decreasing function of the number of daily clicks email content, given spam filter O 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-make is either "significantly faster" or "significantly slower." As will make more formal later on, our results will generally assume a sufficiently large separation between the timescales. In the following paragraphs informally describe rational agent behavior in the context of update frequencies.
Proactive decision-maker First, assume that the decision-male maker is proactive, and suppose they deploy model 0. By definition, this model remains in place for a relatively long time, as observed by the agents. Then, by choosing features μt, the agents experience loss R(u, 0) during that period, and as a result the most rational decision is to choose features μBR (0). In the running example, if e is spam filter that is in place for many months, it is rational for spammers craft emails that are most likely to bypass filter 6. 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 decesion-maker. Now assume that the decision-maker is reactive, and suppose the agents observe 0 as the current model. Then, by setting μ. the agents do not experience loss R(μ, 0). Rather,
5

---

their loss is R(H, PR (R())), where OR (1) denotes the decision-maker's maker's reaction to the agents' choice can aggregate and process data quickly.
j.. In the spam example, suppose that the 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 0g (J)), not the old filter 6. Therefore, if the agents could predict OR (1)), the agents' optimal decision would be to choose arg min, R(u, (R( (u)). In other words, rather than choose the best response to 0, rational agents interacting with a reactive decision-make would choose ya so that triggers the best possible reaction from
We formalize this intuitive behavior by assuming that the agents are no-regrer learners 47 This essentially means that their average regret vanishes the number of actions grows. More formally, we ussume the following behavior depending on the relative update frequencies:
If the decision-maker is proactive, then for any 0,, the agents' strategy ensures:
ER(M,,,0)) 0.) - min R(y, 02) - 0 as oo.
(A1)
If the decision-mane maker is reactive, then for any response function (z), the agents' strategy ensures:
T
Σ ER(,,, - min R(p, (R(()) - 0 as T 00;
(A2)
T
whenever such 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, Pt,r + pBR (0,). The second condition can be satisfied by various bandit strategies if R(j,, (n(()) is Lipschitz and M is bounded (and we will impose these conditions explicitly in the following section). That said, it seems hardly suitable assume that the agents run 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 (Al) and A2
3 Learning dynamics
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-make can drive the interaction to a Stackelberg equilibrium with either player acting as the leader.
3.1 Convergence decision-maker" equilibrium
In general, we do not expect the decision mecksi to be able to compute derivatives of the function SR,. For this reason, achieve convergence the decision-maker' equilibrium, consider running derivative-free method. One such solution is the "gradient descent without a gradient" algorithm Flaxman et 23 Past work 20 also considers this algorithm with the goal of optimizing SR,, but it assumes instantaneous agent responses. In other words, it assumes query access to SR, directly, while we consider perturbations due to imperfect agent responses. is worth noting that, under further assumptions, one could apply more efficient two-stage approaches [31 43 that approximate the gradients of SR, by first estimating the best-response map JBR-
Specifically, we let the decision- maker run the following update:
d L Φ: + 8uz)ue), where i, Unif (S+-1). Φ++1 lo 17t 8
Here, II denotes the Euclidean projection, Unif (8--1) denotes the uniform distribution on the unit sphere in d 7) is non-increasing step size sequence, and 8 > is a fixed hyperparameter. The deployed model in the 1-th epoch is set as 0, = Φt + du:
Technically, this assumes that we can deploy model in 5-ball around @. Another solution would be to use projection onto a small contraction of θ in equation (I] This is minor technical hurdle common in the literature. The rate in Theorem 3.I unaffected by the choice of solution this technical point.

---

We provide convergence guarantees assuming that the decision-makee maker's Stackelberg risk SR, is convex. While this condition doesn't follow from convexity of the loss {(2; alone, previous work has established conditions for convexity of this objective for different learning problems and agent utilities 22) 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 De the diameter of @ and suppose that [T 0)1 S B for all p., O. Furthermore, suppose that SR2 is convex and 3-Lipschitz and L(u, By-Lipschitz in the first entry for all 0. Then, if the ceaision-maker runs update with = "oo at= and i = Sod T 1/4 it holds that
D3
2B o8
(6.) -SR
VdT
B De
Σ Elie (0:)l2.
2nju
Moreover, assuming that the agents are rational
A1 and M is compact, we have
T
D8 2/jo
2B² 80
lim Σ
(EESR,
(0s()))) S
+
Vdr3/4
(2)
1=1
Remark 3.2. For Theorem 3.1 assume that the agents are rational in 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 expect pe,r PBR (0.) as t + oo. For example, this guarantee is achieved by gradient descent in a variety of settings. In that case, the recision-maker can simply use the last iterate instead of the average one:
Φet1 = (o: Th d Lig d, + Suu)u,), where u, Unif (Su-1).
(3)
Similarly, Elpa- - PBR (B)) 1|2 would be replaced by Ellme (BB((e))l in the bound of Theorem 3.1
Remark 3.3. The rate Ol (T3/4) is characteristic the Flaxman 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 [ 15 37J. In this work we opt to analyze the Flaxman 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.7 in the context of a different bandit convex optimization algorithm. Specifically, we only require that the error 11 HBR (9e) 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 maker accumulates regret even if the epoch length T 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 (PL.) condition:
for all 0, R(,, 0) satisfies the
1 1 V 1(,,
7R(,,, min R(e, 0)) S #EM
for some parameter 7 > 0. Suppose that the agents' update is computed
Pr.j+ = Pt.j - mh
(4)
where n, > constant step size and f4,0 = 11-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 1.11 In addition, suppose that R(μ, 0) is 8 smooth in μ. for all 0 and satisfies the PL condition with parameter 7, and (BR(() is Bpn-Lipschitz in B.
Assume that the strategic agents run update (4) with пμ < 6B.- Further, suppose the epoch length is
chosen so that t > log(3ft /////////)///))) 12/100 log (1/(1 (1111-1mm)) mm))) Then, for some constant a(7) E (0, 1), we have
T
E Bllee - MBR (0,)ll2 < ||po (BBR(00)1) + 48pg Bro /T
8n
1 - a(T)
7

---

Therefore, the decision-makee regret is O(vdT even with constant epoch length. This result crucially depends on the fact that the optimization problems that the agents solve neighboring epochs are coupled through 14.0 = 14-1, If 14,0 were reinitialized arbitrarily in each epoch, the extra regret would be linear in 7 given constant epoch length.
By using standard tools from the stochastic approximation literature [0], in the Appendix we additionally provide convergence local optima for the update (3) when SR₁ possibly nonconvex.
3.2 Convergence to strategic agents' equilibrium
Now we analyze the case when the decision-maker reactive. Given a large enough gap update frequencies- that is, large enough epoch length h-the response to the current iterate (4: between any two actions of the agents. The most natural choice for achieving this is to run standard gradient descent, 0t, 0r, mh VoL(ue, 0t,x). . In what follows we provide asymptotic guarantees assuming that the decision-make runs any algorithm that achieves iterate convergence. This condition can be satisfied by gradient descent in variety of settings. Formally, we assume that for any fixed pe, the srcision-maker 's strategy ensures
maker can converge to their best
||+,r BBR ll2 +tp 0,
(5)
as + 0o. 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 ilerate convergence ( and continuous in the second argument. Then, for all T E N, lim, (ii,,, 0,) = -i= ESRR((t).
In other words, in every epoch the agents essentially play a Stackelberg game in which they lead and the decision-man 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 decision-maker's maker's average regret with respect to (ASE, OBR (ASE) vanishes if the agents' updates are continuous. To formalize this, suppose that for all E N, the agents set 14+1 Dr+1 (M) .i,........ "i.....,Me.., Me, Oz, Ee+1), where D++1 is some fixed map and 1 is a random variable independent of ((u,, Ji)ses.. We include Eo+1 as an input to allow randomized strategies. Then, will say that the agents' updates are continuous if Di+1 is continuous in the first 2t coordinates for all E N.
Theorem 3.6. Suppose that the agents' updates continuous and rational A2 and that M is compact. Further, suppose that the decision-maker achieves iterate convergence and SR and SR, are Lipschitz. Then, it holds that
T
lim lim
ESR - SRR(USE) = 0,
T-000 70000
lim lim
EL(u,, 0.) L(USE, OnR (bR()))) 0.
T 7-000
Preferred order of play
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(y, 0) - L(,, 0). Then, the basic min-max inequality says
L(UsE, 4ER (pSE)) = max min (1,, 0) < min max L(H, A) = L(PER (fsE), (ss))
8
"
with equality if and only if a Nash equilibrium exists. Therefore, if Nash equilibrium does not exist, following is strictly preferred.
8

---

Since strategic classification is typically not zero-sum game, we look at two common learning problems and analyze the preferred order of play.
4.1 Linear regression
Suppose that the agents' non-strategic data, (mr. y), where zy is a feature vector and the outcome, generated according
To Po. y y= x + &,
where Po is a zero-mean distribution such that Eag-Po To = B. E R is an arbitrary fixed vector, and ş has mean zero and finite variance o², We denote the joint distribution of (z y) by P(O).
Recall that we use 2 to denote the pair (x,y), y). Suppose that the decision- maker runs standard linear regression with the squared loss:
1 {12 0) 2 (y x TO)..
The agents aim to maximize their predicted outcome, r(z; 0) = - x. subject to a fixed budget on feature manipulation- they can move to any distance most B from their original features zo. || - zolla I B. A similar model is considered by Kleinberg and Raghavan (35] and Chen et al. [7]. More precisely, we let M = {u E R ||a||22 I B} and define P(4) to be the distribution of (ze, y), where (rrg y) P(0) and x = xo + μ.. Then, R(p, 0) E. Pw) = -n² 0 and L(u, 0) E 0).
We prove that both the decision-make and the agents prefer the agents' equilibrium. Proposition 4.1. Assume the linear regression setup described above. Then, we have
0²
+ || min(1, B)²
a² ||
2 2(1 + min(1,B)3 L(uSE, (BR(USE)) S (RsB)
2
2(1 + B²)
|| min(1, (R&(uSE) S ((sE)( 0SE)
|| 1 + 132
1 B)
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: || I ||/B (fse)l12.
4.2 Logistic regression
Next we consider a classification example. Suppose that the non-strategic data (zo. y) sampled according to a base joint distribution P(0) supported on IRd {0, 13. Unlike the linear regression example, we place no further constraint on P(0).
We assume that the decision- maker trains logistic regression classifier:
E(2; 0) yrr 0 log(1 + + ").
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 limited budget to change their features: if their non-strategic features are zg. they
move to any
which is at distance at most B from To. ||x - zollz 2 I B. Thus, we set M = {os E Idd ||llz I B) and denote by P(μ) the joint distribution of (I., y) where (Fo, v) P(0) and I za fI 0). We let R(u, 0) - 0 and L(u, 0) Ex~p(u) ((z; O).
Proposition 4.2. Assume the logistic regression setup described above. Then, we have L'use, (pa(Use)) < (OSE) and SRæ(usE) S R(JER (0sg), 0sg).
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 we generate non-strategic data according to y ~ Bern (p) and zoly ~ 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-mann maker leads.

---

0.2 0.2
= 0.5
0.10
=
0.8
difference
0.6
0.7
((crn((ee)) (ep) SRa(pss)
(R((6))) Llube Benllee)
0.12
R(psa(8sg), Beg) (sse))
(6,( Littes (MAs3)
0.08
R(bbn(8gg) Byz) (use)
(R,(0;;) Littes 9px((M)))
0.06
0.3
0.
0.00
0.00
0.6
1.0
1.4
0.6
0.5
1.0
1.2
1.4
1.6
1.8
0.8
1.0
12
1.5
12
20
Figure I: Difference in secision-maker" and agents' risk implied by the two Stackelberg equilibria, for different values of B and p.
5 Discussion
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 this reversed order on the population interacting with the model. That type of interaction; real-world decision-making algorithms already
said, do not propose possess, and employ, the power to be reactive. Our new framework simply flexible enough to capture the difference between proactive and reactive decision-make
Furthermore, we assume that the agents act on fixed timescale. Sometimes is possible for agents to choose their timescale s/rategically. In that case, there is first "meta-game" between the aecision-maker and the agents, as they might compete for the leader/follower role. For example, 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, 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.
Acknowledgements
We thank Moritz Hardt for an inspiring discussion and helpful feedback this project. We wish to acknowledge support from the Office of Naval Research under the Vannevar Bush Fellowship program and support from HICON-LEAAR (Design of High CONfidence JEARNing--nnablee Systems), Defense Advanced Research Projects Agency award number FA8750-18-C-0101.
References
[1] Alekh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. SIAM Journal on Optimization, 23(1):213 2013.
[2] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6-25, 2021.
[3] Masaki Aoyagi. Reputation and dynamic Stackelberg leadership in infinitely repeated games. Journal of Economic Theory, 71:378-393, 1996.
[4] Ian Ball. Scoring strategic agents. arXiv preprint arXiv:1909.01888.
10

---

[5] Tamer Başar and Geert Jan Olsder. Dynamic Noncooperative Game Theory. SIAM, 1998.
[6] Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! Leamnngg from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234-1242, 2021.
[7] Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probubilites XXXIII, pages 1-68. Springer, 1999.
[8] Avrim Blum, Eyal Even-Dar, and Katrina Ligett. Routing without regret: On convergence to Nash equilibria twenty-fifth annual ACM symposium Principles of distributed computing, pages 45-52, 2006.
meiiitiminiiizing algorithms in routing games. In Proceedings of the
[9] Avrim Blum, Taghammaaaaahhh Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimiza- tion and the price of total anarchy. In Proceedings of the Fortieth Annual ACM Symposium Theory of Computing, pages 373-382, 2008
[10] Vivek S. Borkar. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, 2008
[11] Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. In Ist Symposium on Foundations of Responsible Computing, 2020.
[12] Mario Bravo, David Leslie, and Panayotis Mertikopoulos. Bandit learning in concave n-person games. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, page 5666-5676, 2018.
[13] Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. arXiv preprint trXiv:20/1.03880 2020.
[14] Michael Brückner, Christian Kanzow, and Tobias Scheffer. Static prediction games for ad- versarial learning problems. Journal of Machine Learning Research, 13(Sep):2617-2653 2012.
[15] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, pages 72-85, 2017.
[16] Jenna Burrell, Zoe Kahn, Anne Jonas, and Daniel Griffin. When users control the algorithms: Values expressed in practices on Twitter. Proceedings of the ACM on Human- Computrr Interaction, 3:19, 2019.
[17] Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy- aware linear classifiers. In Advances in Neural Information Processing Systems, volume 33, pages 55265-15276 2020.
[18) Kelley Cotter. Playing the visibility game: How digital influencers and algorithms negotiate influence Instagram. New Media & Society, 21(4):895-113, 2019.
[19] Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, and Deepak Verma. Adversarial classification. In Proceedings of the 10th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 99-108, 2004.
[20] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 55-70. ACM, 2018.
[21] Tanner Fiez and Lillian J Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference on Learning Representations, 2021.
[22] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in Stackelberg games: Equilibria characterization, convergence analysis, and empirical study. International Conference Machine Learning, pages 3133-3144, 2020.

---

[23] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without gradient. In Symposium on Discrete Algorithms, pages 385-394, 2005.
[24] Dean P Foster and Rakesh V Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1-2):40, 1997.
[25] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, Cohen, and Nir Rosenfeld. Strategic classification in the dark. In International Conference on Machine Learning, pages 3672-3681, 2021.
[26] Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 160-166, 2020.
[27] James Hannan. Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, (39)))977 1957.
[28] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifi- cation. In Proceedings of the ACM Conference on Innovations in Theoretical Computer Science, pages 111-122 2016.
[29] Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading correlated equilib- rium. Econometrica, 127-1115, 2000.
[30] Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency, pages 259-268. 2019.
[31] Zachary Izzo, Lexing Ying, and James Zou. How learn when data reacts your model: Performative gradient descent. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pages 4641-4650, 2021.
[32] Meena Jagadeesan, Celestine Mendler-Dünnner and Moritz Hardt. Alternative microfoundations for strategic classification. In Proceedings of the 38th International Conference Machine Learning, pages 4687 4687-4697, 4697, 2021.
[33] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In Proceedings of the 37th International Conference on Machine Learning, pages 4880-4889, 2020.
[34] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Lojase-Lo condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-8 881, 2016.
[35] Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategi- cally? In Proceedings of the ACM Conference on Economics and Computation (EC), pages 825-844, 2019.
[36] Vijay R. Konda and John N. Tsitsiklis. Convergence rate of linear two-time-scale stochastic approximation. The Annals of Applied Probability, 14(2):796 - 819, 2004.
[37] Tor Lattimore and Andras Gyorgy. Improved regret for zeroth-order stochastic convex bandits. In Conference on Learning Theory, pages 2938-2964, 2021.
[38] Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In Proceedings of the 38th International Conference on Machine Learning, pages 6243-6253, 2021.
[39] Nick Liulestone and Manfred K Warmuth. The weighted majority algorithm. Information and Computation, (08(2):212-2)) 261, 1994.
[40] Eric Mazumdar, Lillian Ratliff, and S. Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-131 2020.
12

---

[41] Celestine Mendler-Dtinner. Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic opti- mization for performative prediction. In Advances Neural Information Processing Systems, volume 33, pages
2020.
[42] John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pages 6917-6926, 2020.
[43] John Miller, Juan Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk. In Proceedings of the 38th International Conference Machine Learning. pages 7710-7720, 2021.
[44] Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency, pages 230-239 2019.
[45] Marieke Möhlmann and Lior Zalmanson. Hands on the wheel: Navigating algorithmic manage- ment and Uber drivers' autonomy. In Proceedings the international conference on information systems (ICIS), pages 10-13, 2017.
[46] Juan Perdomo, Tijana Zmic, Celestine Mendler-Dünnee. and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599-7609, 2020.
[47] Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78-86, 2010.
[48] Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In International Conference on Machine Learning, pages
2020.
[49] Marilyn Strathern. Improving ratings: Audit the British university system. European Review, 5(3):305-321, 1997.
[50] Heinrich Stackelberg. Market Structure and Equilibrium. Springer Berlin Heidelberg, 2010.
[51] Hanrui Zhang and Vincent Conitzer. Incentive-aware PAC learning. Proceedings the AAAI Conference Artificial Intelligence, 35:5797-5804, 2021.
[52] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In International Conference on Machine Learning, pages 928-936, 2003.
13


Reviews:
[{"review_id": "bQ6Dys0O5m", "reviewer": "Reviewer_Ddzr", "summary": "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.\n\nThe 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).", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "=====  Post Rebuttal  =====\n\nI would like to thank the authors for addressing my comments and participating in the discussion. Please include the BCO discussion in a revision of the paper, together with the other comments you acknowledged. I'm increasing my score to a \"weak accept\" after our discussion where you stated that the surprising result on the order of play seems to also hold for more \"adversarially\" produced datapoints.\n\n======================\n\nEvaluation.\nI think the paper’s strong trait is the observation of the different timescales, which is definitely novel and closer to reality than the prior models. The technical part of the paper is similar to prior work and in and of itself makes some assumptions on the form of the losses, the risks and the behavior of the agents (I do understand that the paper of [Dong et al., EC18] makes the same assumptions and proves the conditions under which they hold). The reason for my weak reject is that I think that the bound that you should have used for BCO part is the bound of [Bubeck et al., STOC17] and that the paper will benefit from a more clear writeup (I have included extended comments below).\n\nWeaknesses. \n\n-- The technical part of the paper is similar to prior work. And there is a second layer to that. The paper of [Dong et al., EC18] adapts the algorithm of [Flaxman et al., SODA05], which was indeed the first to achieve no regret in BCO, but ever since there have been much better algorithms. This is also acknowledged by [Dong et al., EC18]. I think that the paper should try to adapt the algorithm of [Bubeck et al., STOC17] which achieves O(poly(d) \\sqrt{T}) regret, instead of the O(T^{¾}) one. By the way, I do understand the higher dependence in the dimension, I am just focused on dropping the dependence in T. If this is not possible, is there a fundamental barrier?\n\n-- The two examples showcasing the counterintuitive preferred order of play are nice, but I think it would be more meaningful to consider more “adversarial” settings similar to prior work. Or, what happens if you have separable data (see the paper by [Ahmadi et al., EC21])? Are there any minimal conditions for the data generating process and the risk functions in order to get to the same conclusion that the agents’ leading is preferable for both?\n\n-- I think that the paper could use some clarifications in the write-up. Examples: (and please correct me if I’m wrong in any of the following)\n\n* I believe that you need to assume that the learner knows the agents’ frequencies in order to decide to be proactive/reactive. Why is it OK to assume such knowledge in real-life settings? \n* You assume that the label/score y remains the same even after manipulation. Please state that clearly, since there are a lot of works recently where this is not the case. \n* In 2.2 some details are loosely defined; for example, the “most rational decision” in Line 220 assumes a risk-averse, expected utility maximizer agent, right? Also, the no-regret behavior is not identical to the \\mu_{BR}. This is indeed clarified in the first paragraph of page 6, but I was confused reading lines 217 -- 233 and then the definition of the no-regret behavior. \n* What if for the faster player there is an “idle” round? In general, do the rounds for the updates need to “align”? I.e., the slow player plays once every 3 plays for the fast player. \n* It is said early in the paper that the agents’ leading is a “preferred” order of play; please specify earlier that this preference is defined wrt to the accuracy loss for the learner, the loss of the agents, and their manipulation cost. Alternatively, you can formally define welfare in the beginning and argue wrt to it.\n\nStrengths. \n\n-- The model is very interesting, novel, and indeed it models much better the interactions in strategic classification settings. Frankly, the idea of studying different timescales for the learner and the agents is one of the missing pieces in the strategic classification literature and the main selling point of the paper. \n\n-- The observation that there are settings where *both* the agents and the learner prefer that the agents’ lead is indeed surprising and counterintuitive. The paper does a good job of explaining also the relationship with zero-sum games.\n\nAdditional comments.\n\n-- Missing related works: [Braverman & Garg, FORC20], [Ghalme et al., ICML21], [Levanon & Rosenfeld, ICML21], [Jagadeesan et al., ICML21], [Ahmadi et al., EC21], [Bechavod et al., arXiv21]\n\n-- Line 180: what is m? Why is this not equal to d?\n\n-- Line 315: what is D_{t+1}? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the work are adequately addressed in Section 5. I also particularly enjoyed their observation about the meta-game that might be induced.\n\nI think the potentially negative impact of the work should have been addressed, too. For example, you could include a paragraph citing some of the papers that have proved how strategic classification makes the disadvantaged groups worse off. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns in my view.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6-7 hrs"}, "extra_text": {}}, {"review_id": "V5kMo0TxKxZ", "reviewer": "Reviewer_6sCC", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper makes several contributions:\n1) Pointing out that the order of play in strategic classification can be reversed\n2) ...and that differences of frequency of updates can determine the order of play\n3) Showing that both players might prefer the order in which the agents lead\n4) Performing analyses that merely assume agents achieve vanishing regret in comparison to best-response, rather than the traditional stronger assumption that agents instantly play the optimal move\n\nA very relevant recent paper seems to have been missed by the authors: [\"Scoring Strategic Agents\"](https://arxiv.org/abs/1909.01888) by Ian Ball. In this work, Ball studies strategic regression under both orders of play: decision-maker first, and agents first. These correspond to the classic economic settings of _screening_ and _signaling_ respectively. Thus, the current paper is not in fact the first to vary the order of play in the literature on strategic classification, so contribution #1 is not wholly novel.\n\nThat notwithstanding, I am recommending acceptance because contributions #2,3,4 are novel as far as I know, and are substantive and interesting. #2 and #3 are neat observations that are presented convincingly. The authors make a good case that the agents-first model is a better fit for many real-life settings than the decision-maker-first model. (The main body of the paper as a whole is admirably well-written). Regarding #4, I appreciate the no-regret model of agent behavior; I would like to see more strategic classification works use this rather than assume agents can instantly best-respond. Moreover, order of play is acutely underdiscussed in the literature even if it has already been brought up once before, and the Ball paper is framed as a work of economics rather than computer science.\n\nOne thing that confused me: the authors use a parameter $\\mu$ to denote \"the agents' action.\" But of course in many cases different agents take different actions. In the logistic regression example, $\\mu$ refers to the one action all the true-negative agents take (the true-positives don't take any action). So I gather that $\\mu$ is meant to parameterize the actions collectively taken by the full distribution of agents? It would be nice to have clarity about this from the authors.\n\nI have only given the proofs a cursory skim, not checked them for correctness.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One unaddressed limitation of the work is the assumption that agents act as a unit, maximizing their aggregate utility as a group. I think this is an understandable assumption for reasons of tractability and space. Indeed, when the decision-maker moves first, there is no difference between agents acting in their own self-interest versus in their collective self-interest, since each agent's utility is unaffected by the actions of others. But when the agents move first, the action of one agent can affect the model deployed by the decision-maker and thus the utility of another agent, and so the assumption matters and is in my opinion unrealistic (hence the common use of perfect Bayesian equilibria in the signaling literature).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "KboFRZ3o8iT", "reviewer": "Reviewer_nkip", "summary": "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: I agree with the first parts of the paper that claim that most existing work considers the classifier to be the leader in a Stackelberg game and I am not aware of any work that would reverse the roles. The idea to reverse the roles is not entirely intuitive and therefore sufficiently novel. Also, showing (in highly idealized setting) that the equilibria corresponding to the different orders can be induced by the speed of updating is interesting and novel.\n\nTechnical Quality: The main statements of the paper intuitively make sense. I did not carefully check the detailed proofs that are provided in a lengthy appendix. The main text is rather formal and reasonably clear, but some things are missing. For example, it makes an assumption that all best responses and equilibria are unique without any justification. Some of the notation is not properly introduced. For example, a crucial parameter “diam()” used in Theorem 3.1 is undefined, I / I_d in section 4 is undefined, ->_p for “convergence in probability” should also be defined more exactly.\n\nClarity: The main idea of the role reversal is clear. However, it is not enough on its own for a neurips publication and it is not very clear how some parts of the paper support it. The paper would, in my opinion, be substantially clearer if it introduced a comprehensive detailed description of a realistic problem, that would require the kind of analysis the paper promotes.  In the presented formal model, there is no change of data and the only thing evolving in time are the player’s strategies. Assuming rational players, I do not see much reason for having gradual updating on different time scales. In the given example with spam, the spammer would just craft the hardest to detect template and start using it, while the classifier would create the best classifier for it. If the equilibrium is unique as assumed, the spammers would not have any incentive to change their strategies anymore. Since the data do not change and the equilibria are unique, it is not clear why it is useful to analyze the process of adaptation of the classifier on the level of gradient descent. \nIf the gradual updating is somehow justified, the deeper, less trivial analysis in the paper is on the more standard form of the classifier in the role of the leader, which is unexpected after the introduction. There, the result in Theorem 3.1. is interesting and non-trivial. On the other hand, the analysis of the equilibrium for the reversed roles basically assumes that the classifier is trained to full convergence, which is much less interesting and novel.\n\nSignificance: The paper presents an interesting theoretical idea. However, it does not sufficiently argue for its practical impact. The paper shows some parameter settings, where the players’ payoffs in the different equilibria differ. However, the ability of the attacker needs to be quite extreme (over 1.5 change in data with unit variance (if I interpret the undefined I correctly). A more compelling discussion of practical impact would be necessary to consider the paper significant practically. If we focus on the theory, the paper may inspire future work that will consider the agent modifying the data as the leader.  It sufficiently shows that the case exists, and could potentially have some implications on players strategies, depending on parameters. However, I am not convinced that the paper provides sufficiently novel and interesting tools for deeper analysis of this problem to warrant a publication at NeurIPS.\n\nSummary: This paper presents a very interesting idea of role reversal and argues well for the need to analyse different adaptation speed of the players in adversarial classification. However, I do not think it provides sufficient evidence for its practical impact or sufficiently general, deep and reusable theoretical framework that would make its future analysis substantially simpler.\n\n\nAfter the discussion with the authors, they managed to resolve some of my confusions and I was happy to increase my score. While uniqueness would be a problem in non-linear classification or when assuming mixed strategies, I am ok with it in case of linear classifiers and pure strategies. We have also resolved the problem of changing data. I hope a future version of the paper will be much clearer about which agent has access to which information, but I think my main concern is resolved by the realisation that z is likely only a sample of the data that can be different in each round, even though it comes form the same static distribution, generally unknown to the players.\n\nThe concern that was not fully resolved is that the more interesting results with regret minimisation are for the more standard setup of the classifier as the leader and the reversed theorem essentially assumes a best-responding opponent, which is much less novel.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should analyse more carefully the limitations of their formal model (i.e., the data not changing) and the empirical results achieved (i.e., how realistic the parameters that lead to the difference are). For societal impact, the authors do not discuss it, however, I do not consider the potential negative impact of this work to be substantially larger than in case of any other work on adversarial classification. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JS-cS7d_2De", "reviewer": "Reviewer_1kNE", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n— The paper examines an important extension of the traditional strategic classification model. Namely consideration of response times, for both the model designer and the agents, adds a number of interesting insights.\n\n— Significant contributions are made in the from of results pertaining to this model extension. Specifically, the authors quantify convergence of strategies for the case of both a reactive and proactive model designer, as well as providing examples in which the latter is preferable to both parties.\n\n— The authors’ assumptions allow their results to be applicable in a wide range of settings.\n\n— It is both counter intuitive and interesting that situations can arise in which both the model designer and the agents prefer the agents to lead. Aside from being generally interesting, this result implies that the strand strategic classification model (model designer leading) can lead to less desirable outcomes and thus motivates the need to consider reactive model design and potential tool for robustness. \n\n— The paper is well written, the contributions are clearly outlined, and helpful intuition regarding results is provided.\n\n\nWeaknesses:\n\n— The informal presentation of Theorem 1.2 seems to overstate the actual result (which I believe is Proposition 4.1 and 4.2, although there appears to be no explicit mention of the formal version of 1.2), in that the theorem insinuates both parties prefer agents to lead when linear or logistic regression models are deployed. However, Section 4 appears to only provide sufficient conditions on the distribution of true features for this result to hold, rather than showing that it holds In general. \n\n— When looking at agents as potentially spending large periods of time to manipulate their features, it could be the case that this process also manipulates their true label, e.g. spending a year doing actions to increase one’s credit score may inadvertently increase one’s true credit-worthiness. Without accounting for this potential shift in labels, the the utility of the model designer may be incorrectly modeled. \n\n— Additionally if the update frequencies are low enough, such as some type of annual application system, we may be more interested in considering utility within some small number of iterations, rather than quantifying convergence as the number of iterations approach infinity. This is somewhat handled with several of the inequalities presented in section 3, but having a better characterization of utility with respect to each iteration would be helpful since the setting this paper studies is motivated by slow reacting agents.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the scores appear marginal, I still recommend this paper for acceptance.  The authors responded well to some points and some issues raised were found not to be much of a problem.  It is clear that some work is needed on the writeup in line with the reviewers' comments (e.g., contrasting with the Ball paper), but it is very reasonable to assume this can be done before the camera ready.

While we certainly can't fault the authors for not having a high enough reference count, there are a few other things that could be expanded.  For example, there is a paragraph on learning in Stackelberg games, but that literature (not necessarily restricted to the classification context) goes back to 2009 if not further, and not just for zero-sum games.  This seems worth discussing.  There is quite a bit of additional recent work on learning in non-zero-sum strategic classification settings, including relationships to mechanism design (which is itself a Stackelberg model), as well; see e.g. "Incentive-Aware PAC Learning" and other work cited therein.  To my knowledge, none of this makes the authors' work less valuable -- if anything, it makes it more so.  Finally, there is work in the economics literature on justifying Stackelberg models/outcomes through different degrees of patience between the players, e.g., "Reputation and Dynamic Stackelberg Leadership in Infinitely Repeated Games" -- it is not quite clear to me what the relationship is to update frequencies, but perhaps something interesting can be said.
Decision: Accept (Poster)