Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
Authors: Han Shao
Shuo Xie
Kunhe Yang
Venue: ICML 2025 poster (2025)
Keywords: strategic classification
mistake bound
online learning
Primary area: theory->game_theory

Abstract: Strategic classification addresses a learning problem where a decision-maker implements a classifier over agents who may manipulate their features in order to receive favorable predictions. In the standard model of online strategic classification, in each round, the decision-maker implements and publicly reveals a classifier, after which agents perfectly best respond based on this knowledge. However, in practice, whether to disclose the classifier is often debated---some decision-makers believe that hiding the classifier can prevent misclassification errors caused by manipulation. In this paper, we formally examine how limiting the agents' access to the current classifier affects the decision-maker's performance. Specifically, we consider an extended online strategic classification setting where agents lack direct knowledge about the current classifier and instead manipulate based on a weighted average of historically implemented classifiers. Our main result shows that in this setting, the decision-maker incurs $(1-\gamma)^{-1}$ or $k_{\text{in}}$ times more mistakes compared to the full-knowledge setting, where $k_{\text{in}}$ is the maximum in-degree of the manipulation graph (representing how many distinct feature vectors can be manipulated to appear as a single one), and $\gamma$ is the discount factor indicating agents' memory of past classifiers. Our results demonstrate how withholding access to the classifier can backfire and degrade the decision-maker's performance in online strategic classification.

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
Han Shao'
Shuo Xie
Kunhe Yang?
Abstract
their features receive favorable outcomes (Brückner & Scheffer, 2011; Hardt et al., 2016; Ahmadi et al., 2023), For example, in college admissions, when decision-maker evaluates applicants, students may retake the SAT, switch schools, or enroll in easier classes to boost their GPAs in hopes of gaining admission. Similarly, in loan approval, where classifier assesses applicants based on their credit scores, individuals may open or close credit cards or bank accounts to improve their credit scores.
Strategic classification addresses learning prob- lem where decision-maker implements classi- fier over agents who may manipulate their features in order to receive favorable predictions. In the standard model of online strategic classification, in each round, the decision-maker implements and publicly reveals a classífier, after which agents perfectly best respond based on this knowledge. However, in practice, whether disclose the clas- sifier is often debated some saccisionmmaker be- lieve that hiding the classifier can prevent mis- classification errors caused by manipulation. In this paper, we formally examine how limiting the agents' access to the current classifier affects the decision-maker's performance. Specifically, we consider an extended online strategic classifica- tion setting where agents lack direct knowledge about the current classifier and instead manipulate based on weighted average of historically imple- mented classifiers. Our main result shows that in this setting, the decision-mate incurs (1 --)-
More formally, an agent (z, consists of a pre- manipulation feature vector and a ground-truth label y. When modeling strategic manipulation, we assume that each agent has limited manipulation power. We adopt manipu- lation graphs, initially introduced by Zhang & Conitzer (2021), represent feasible manipulations. In this graph, the nodes correspond all possible feature vectors. There is an edge from x to x' if and only if an agent with the feature vector x can manipulate their feature vector to x'. Additionally, there is always a self-loop at each node, as agents can choose to remain at x by doing nothing.
A sequence of agents (x1, 31), (222, 92).... ... arrives sequen- tially. In each round the decision-maker implements a classifier h,, and the agent (z,, y1) manipulates their feature vector from 2; to a neighbor i in an attempt to receive a positive prediction under ht- In prior work, it is usu- ally assumed that the preision-maker is transparent -hey reveal their current classifier to the agents before manip- ulation and that agents are rational-ther best respond by manipulating to a reachable feature that is labeled as positive (if one exists) in the most cost-efficient way. Specif- ically. if all their neighbors are labeled as negative, they remain at their current feature without making any changes, as manipulation would not help change the prediction from negative to positive. Many algorithms developed in prior work (e.g. Ahmadi et al., 2023; 2024; Cohen et al., 2024a) heavily rely this standard bie-breaking assumption.
or kin times more mistakes compared to the full- knowledge setting, where km is the maximum in-degree of the manipulation graph (representing how many distinct feature vectors can be manip- ulated to appear as single one), and y is the discount factor indicating agents' memory of past classifiers. Our results demonstrate how withhold- ing access to the classifier can backfire and de- grade the caaision-makerr performance in online strategic classification.
1. Introduction
In online strategic classification, a decision maker makes decisions over a sequence of agents who may manipulate
However, in real-world applications, the decision-maker may withhold their classifier to prevent agents from manipu- lating their features. Nevertheless, even without knowledge of the current classifier, agents will still attempt to optimize their outcomes through strategic manipulation. This raises a fundamental question:
'CMSA. Harvard University 'Toyota Technological Insti- tute at Chicago "University of California, Berkeley. Correspon- dence to: Han Shao <han @ cmsa. fas. harvard. Shuo Xie <shuox sauoxx@ttic.oom edu>, Kunhe Yang <kunhcyang @ berkeley.edur
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Can decision-makers benefit from hiding the classifiers?

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
More specifically, we assume that agents only have knowl- edge of previously implemented classifiers when they re- spond. For example, in centralized college admissions, uni- versities often publish past cutoff scores, revealing previous classifiers.
1.1. Related Work
The research on strategic machine learning-which focuses designing machine learning algorithms that remain robust in the presence of strategic behaviors-datte back to the works of Dalvi et al. (2004); Brückner & Scheffer (201 I); Dekel et al. (2010). Within this field, strategic classification was first studied by Hardt et al. (2016), who examines the accuracy of classification tasks when agents can modify their features to receive more favorable outcomes. Overall, our work contributes to the literature of strategic classification in the following three aspects.
In this setting, we consider natural models of agents' behav- ior that exhibit heuristic rationality, One natural approach is for agents to best respond to the classifier from the previous round. For example, student applicants may assume that the admission rule will closely resemble the one used last year. Another heuristic method is to best respond to the average of historically implemented classifiers. We unify these ap- proaches by considering a general framework where agents best respond to weighted average of historical classifiers.
(I) Learnability in the online setting. Our work focuses on the online setting where the decision-maker (also called the learner) aims to make irrevocable classification deci- sions to a sequence of agents arriving one by one. Among the prior works that analyze the mistake bound/Stackelberg regret in such settings (Dong al., 2018; Chen et al., 2020; Ahmadi et al., 2021; 2023; 2024; Shao et al., 2023; Cohen et al., 2024a), our work is most closely related to that of Ah- madi et al. (2023; 2024); Cohen et al. (2024a). These works model the agents' ground-trute labels as induced by graph- based manipulations (Zhang & Conitzer, 2021; Lechner Umner, 2022) toward an unknown hypothesis within a given hypothesis class with bounded complexity, an assumption analogous to realizability in classical online learning (Little- stone, 1988). Building on this framework, our work is the first to analyze how the mistake bound changes under alter- native models of agent behaviors, specifically when agents best respond to a weighted sum of historical classifiers rather than the current classifier.
Under this model, we answer our central question negatively. We show that when agents best respond to weighted aver- age of past classifiers, the decision-maker incurs (1 - ->)-1 or kin times more mistakes, where Kin is the maximum in- degree of the manipulation graph and y E (0, is the discount factor representing agents' memory of past classi- fiers. This implies that the decision-maker may not benefit from hiding the classifiers but incur a substantial increase in the mistake bound.
To better understand this problem, we first analyze a simple base case by removing the standard tie-breaking assump- agents remain at their original feature vector x when their entire neighborhood is labeled as negative. We show that removing this assumption can already hurt the decision-maker, increasing the mistake bound by factor of é (Kin). This not only serves a building block but also highlights that even small perturbation in agents' perceived classifiers can significantly impact the mistakes made by the decision-maker.
(II) Agent behavioral models beyond best response. There have also been recent works exploring alternative agent behaviors beyond the simple best-response model, including noisy response (Jagadeesan et al., 2021), gradient descent (Zrnic et al., 2021), and non-myopic agents optimiz- ing for discounted future rewards (Haghtalab et al., 2022). In contrast, our settings assume that agents cannot observe the current classifier but manipulate based historical observa- tions. Xic & Zhang (2024) also assumes agents best respond to previous decision policy but they focus on welfare and fairness. We compare the learner's 's optimal mistake bound both when the classifier is revealed and when is withheld. More broadly, these studies fit within the context of repeated Stackelberg (principal-ageee -agent) games with learning agents, (e.g. Haghtalab et al., 2022: 2024; Blum al., 2014), where recent work focuses on designing principal's 's algorithms to strategize against agents who employ specific online learn- ing algorithms such as no-regret algorithms (Braverman et al., 2018; Deng et al., 2019; Mansour et al., 2022; Fiez et al., 2020; Brown et al., 2024). While these works gener- ally assume known or fixed/stochastic games, part of our main challenge arises from the fact that agents' initial fea-
Contributions. We summarize our contributions as follows.
When agents best respond to the current classifier with ar- bitrary tie- die-breaking, we provide lower bound on the mis- take bound, showing that the decision-maker will make ((ka) times more mistakes. We also propose an algo- rithm that achieves a matching upper bound.
When agents best respond to the weighted average of history with arbitrary rie-breaking, we establish a lower bound on the mistake bound, showing that the decision- maker will make (1 --)-- or ki times more mistakes. Additionally, we propose an algorithm with mistake bound of O(11 - 7)- k.
We also explore the scenario where agents run online learning algorithms, and discuss the challenge of mod- eling learning agents through diminishing regret due to their nonstatic and large action space.
2

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
tures are unknown and chosen by an online adversary. Fur- thermore, as we will discuss in Section 5, defining learning agents in strategic classification presents unique challenges due to the dynamic and large action spaces.
for ( = 1,.... T) is described in Protocol 1.
Protocol 1 Decision-Maaker/Ageen Interaction
1: for t I...., T do
2:
The learner implements a classifier he E )
(III) Decision-maker's strategy beyond full transparency. Our study studies the decision-maker's choice between mak- ing the classifiers fully transparent or withholding infor- mation. Prior works have explored other forms of partial transparency mechanisms in the offline setting, such as re- leasing a subset of potential classifiers that includes the actual implemented classifier (Cohen et al., 2024b), incor- porating randomness and noise (Braverman & Garg, 2020), withholding the classifier so that agents employ imitation and social learning (Ghalme et al., 2021; Bechavod et al., 2022; Akyol al., 2016), providing feedback on the classi- fier with varying levels of accuracy (Barsotti et al., 2022), and revealing counterfactual explanations instead of the clas- sifier itself (Tsirtsis & Gomez Rodriguez, 2020). Our main contribution to this thread is studying the online interac- tion between the decision- maker and a stream of agents, and to quantitatively characterize the impact of information disclosure strategies on the pecision-maker"s performance.
3: The environment picks an agent (Iz, Wr).
4:
The agent manipulates from 2, to 2,--
5:
The learner observes the post-manipulation feature vector 0t and the true label ye, and makes a mistake if hi (1x) A 1/+-
6: end for
Manipulation Graph. Agents will try to maximize their chance of receiving a positive prediction by modifying their feature vector some reachable feature vectors. Following prior works (c.g. Zhang & Conitzer, 2021; Lechner & Urner, 2022; Ahmadi et al., 2023; Lechner et al., 2023), we model the set of reachable feature vectors through a manipulation graph G = (X, E), where the nodes are all feature vectors in X. For any two feature vectors I, x' E X. there is a directed edge from 2 to r'-ie.. x') E E-if and only if an agent with initial feature vector x can manipulate to x'. Additionally, there is always self-loop at each node x E X, i.e., V(z, x)) E E, as agents can choose to remain at x by doing nothing.
While our work also focuses on the accuracy perspective, many works have explored various other perspectives of strategic classification, such as encouraging genuine im- provements versus discouraging "gaming" (e.g. Ahmadi et al., 2022; Bechavod et al., 2021; Haghtalab et al., 2021; Liu et al., 2020), understanding the causal implications (e.g- Miller et al., 2020; Bechavod et al., 2021: Shavit et al., 2020; Perdomo et al., 2020), and fairness concerns (e.g. Hu al.,
For each node x E X, let Nom[x] = fa'l(z, x²) E E and [=] = {='[(x', x) E E} denote the out- and in- neighborhoods of x in the manipulation graph G. Let Kout = supxex [[Nou[z]]] and kn = supwex [NNin denote the maximum det-de and maximum in-degree of the manipulation graph, respectively.
2019; Liu et al., 2020; Milli et al., 2019).
Agent Behavior Models. At each round f, an agent ma- nipulates their feature vector from D4 to a reachable vector oe E Nom[sre] with the intent to maximize their probability of receiving a positive prediction. Concretely, the agent either observes h, or forms an estimate hy based on the in- formation available to them, and then chooses it E No [x:) among those that maximize hz(v) or (v). We formal- ize the set of such best response manipulations as the best response set:
2. Model
Throughout this work, we focus on the binary classification task in the online setting. Let X' denote the feature vector space and y {0, 1} denote the label space. A hypothesis h : X + y' (also called a classifier or predictor) is function that maps feature vectors to labels. We denote by H.C C yd the hypothesis class. A fractional predictor X [0, 1] is a function that maps feature vectors to the probability of being labeled as 1.
Definition 2.1 (Best Response Set). Given a (potentially fractional) predictor h E [0, 1|a,, the best response function BR, X' + 2x will map to the set of reachable neighbors with the highest predicted value, i.c.,
An example (x, y) E X x V, referred to as an agent in this context, consists of pre-manipulation feature vector x and ground-truth label y. We consider the task of sequential classification where the decision-maker (aka learner) aims to classify a sequence of agents (x1, (61,)),, ), (22,32), y2),... that arrives in an online manner. In each round t, the decision- maker implements a classifier fü, and the agent (Iz, 3r) ma- nipulates their feature vector from 2, to 2t with an attempt to receive a positive prediction under he. The interaction between the
(Rx == argmax.eN.IIab(())
We consider three models of agent behaviors based on (1) how they break ties when there are multiple options inside (x), and (2) how agents form their estimate h4.
and the agents (which repeats
(Revealed-Std) Revealed Classifier + Best-Response with Standard Tie-breaking. This is the standard setting
3

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
in the literature of strategic classification, e-g., Ahmadi al. (2023); Cohen et al. (2024a); Ahmadi et al. (2024). In this case, the decision-maker reveals the implemented 0-1 classifier h4 E {0, 1 to the agent in each round. The agent best responds to ht by choosing U/ E BR (x+)- Specifically, if every reachable feature vector in Now is labeled as under i.. when he (BRr, (x+)) = 0- the agent chooses f2 = 2t as they have no incentive to manipulate if manipulation does not yield positive clas- sification. Otherwise, if there are neighbors labeled as 1, ties among them are broken arbitrarily.
Learner's Objective. The learner's objective is minimize the total number of classification mistakes. For a sequence of agents S = (2i, Ue (t)ee the learner's mistake bound is
Ma(S) Σ 1 (be(vr)) # we).
y where & E (Revealed-Std, Arb )-eiighted) de- notes one of the three agent behavioral models described above, which determines how U, is chosen. We also use Ma S) to denote the mistake bound of a specific algo- rithm A. Following prior works (Ahmadi et al., 2021; 2023; Cohen al., 2024a), we focus on the strategic realizable setting, where there exists an optimal hypothesis h* H. that perfectly classifies the agent sequence S when each agent (zz, y1) best responds to h", Formally, this means V(I,, yo) E S, h² h' (xz)) = yt-
(Revealed-Arb) Revealed Classifier + Best- Rest-Response with Arbitrary Tie-breaking. As a variation of Revealed-Std, in Revealed-Arb, the agents still observe ht and best responds to but break ties arbitrarily among the vectors in BR,, (xz)². In particular, even if all neigh- bors in N [ are labeled negative, the agent may still choose to move rather than stay, due to the arbitrary nature of biebbreaking. We introduce this model as an interme- diary step toward our main setting, where agents do not observe ht directly, but instead best respond to an estimate Tr. Estimation errors can make some out out-neighbors ap- pear more favorable- - even when all are actually negative under h, - so agent's 's best response to ht may resemble a best response to h4 under arbitrary tie- breaking. This motivates us to consider the Revealed-Arb setting.
We focus on this realizable setting because, across all three agent behavior models that we consider, there exists learner strategy that achieves zero mistakes by using the -inndl-sg-- classifier h" across all rounds. Con- sequently, the mistake bound M(S) aligns with the notion of Stackelberg regret, which measures the learner's perfor- mance relative to the best fixed strategy in hindsight in this principal-agen framework. In either of the three settings & E (Revealed-Std, Revealed-Arb, >-eightedd,, we use
M²( 8 strategic realizahle under H
sup
Md(S)
(y-Weightedd) Unrevealed Classifier Estimated via Weighted Sum of History. This is the main setting of this paper. In each round f, the agent cannot observe the imple- mented classifier ht, but only has access to the historically implemented classifiers ..t...,,,..., As a natural heuris- tic, the agent estimates h4 by taking a weighted average of these historical classifiers,
to denote a learner's worst-case mistake bound across all strategic realizable sequences. Similar to (M, S), we sometimes use MM H) to emphasize the algorithm A. Following a common assumption in the literature (Cohen et al., 2024a; Ahmadi et al., 2024; 2023), we focus on deter- ministic algorithms.
1-7
t-2
In the standard setting, Ahmadi al. (2023); Cohen et al. (2024a) show that MRevealed (?)) = (kiut Ldim (H)), where Ldim(H) is the Littlestone dimension of H (Little- stone, 1988). They also establish that 22(kimu Ldim(H)) is a tight lower bound for all deterministic algorithms. In this paper, we characterize the optimal mistake bound in the other two settings of Revealed-Are and -eightee
?
h1-1-
1 - ---
7 E (0, 1) is discount factor that reflects how quickly the agent's 's memory of older classifiers diminishes. The agent then chooses v, E BR (x:) with arbitrary tie tie-breaking. By adjusting the values of 7, this model captures spec- trum of agent behaviors. When 7 + 1, N7 approaches the average of all historical classifiers, reminiscent of fictitious play in repeated games. When 7 -> 0, h. ap- proaches hy-1, meaning that the agent uses a one-step memory and best responds only to the most recent classi- fier.
2.1. Summary of Results
We show that in the Revealed-Arb setting, the learner suf- fers extra km multiplicative factor in the mistake bound than the Revealed-Std setting. More specifically, we show that there exists family of instances where 22 Amu Ldim(H)) is a lower bound for MRevealed-Arb (H) for de- terminisite algorithms (Thm 3.3). We also propose an al- gorithm that reduces our learning problem to classical on- line learning problem and prove that MRReealed-Arb (?))
'The breakink may be adversarially chosen to induce the maximum number of mistakes. However, this differs from adver- sarial perturbations studied in robustness literature (e.g., (Mon- tasser al., 2019)), since the agent only chooses from vectors that maximize he-
Ö Kom T.dim Tdiim?()), see Cor 3.2.
4

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
When agents lack information of the current classifier, and instead best respond to h2 with a discount factor Y E (0,1), we propose a reduction algorithm that trans- forms the 7-Weighted setting into the Revealed-Arb set- ting, achieving
We will present our upper bound in the Revealed-Arb setting in Section 3.1 and lower bound in Section 3.2.
3.1. Upper Bound
In this section, we provide an upper bound on Aee by establishing reduction to classical (non-strategic) online learning. While the main idea is similar to that of Cohen et al. (2024a), we need to address the challenge of no longer being able to observe the agent's true feature vector 2 under false negative mistake (i.e., when the agent's true label is yr = 1, but the classifier he incorrectly labels the agent as 0). We address this challenge via a more careful and conservative procedure of updating the expert class. We present the algorithm in Algorithm
Weightedd (70) = 0(11-))-)) MRRevaleed-Abb
=ō (11-7)-1 kin Ldlim(H))
This implies a Ō ([1-))-1 km)) multiplicative gap compared to the Revealed-Std deterministic lower bound of [2Kouu Addim(H)) (Ahmadi et al., 2023; Cohen al., 2024a). We also show in Theorem 4.4 that for determin- istic algorithms, both the (1 7)- and Ain factors are necessary in different regimes of the --eightted setting.
At high level, Algorithm maintains a set E' of weighted experts and predicts x as only when the total weight of experts predicting it as is sufficiently large. Each expert runs a classical non-strategic online learning algorithm, such as the SOA algorithm (Littlestone, 1988), with different inputs. Each time mistake is made, the algorithm penalizes the experts who made incorrect predictions. The challenge lies in identifying whether an expert has made a mistake, as we do not know the original feature vector I2 and thus cannot determine the post- mast-manipulation feature vector had we followed this expert. Additionally, we aim for at least one expert to perform nearly as well as the optimal classifier h*. To achieve this, we seek to feed the expert the post- manipulation feature vector that would have resulted had we implemented the optimal classifier ht*
3. Revealed Classifiers with Arbitrary Tie-breaking
In this section, we study Revealed-Arb setting, which serves as building block for our main setting where the classifiers are not revealed. In the Revealed-Ari setting, the decision- maker reveals the classifier h at each round, then the agent (a4, ye) manipulates their feature vector from 24 to v2 that is chosen arbitrarily from the best response set, i.e.,
E BR,, (zz).
In particular, this model allows agents to move arbitrarily to any out-neighbor, even when both i2 and v4 are labeled negative by hrs In contrast, prior works such as Ahmadi et al. (2023); Cohen et al. (2024a); Ahmadi et al. (2024) assumes that agents remain at when he labels all the out- meighbors Naw [ as negative. This assumption is critical to their results as it allows the decision-make to exactly infer an agent's true feature vector when it ends up labeled as negative by the classifier. Specifically, when by (v:) = 0, the decision-maker can deduce that 2; = v, and penalize all the hypotheses in H that misclassify this agent.
The algorithm uses the observed e E BRA, (wr) to enu- merate all possible manipulated feature vectors that would have allowed the agent to be correctly classified had they best responded to the optimal classifier h², Then, least one expert in F is fed with the same trajectory induced by best-responding to h²t
In particular, when Algorithm I incurs a false negative mis- take, the agent might have manipulated from an in-neighbor T4 E Mo as permitted by the adversarial tic- tie-breaking rule. To account for this, our algorithm first identifies all the in-neighbors of vn that cannot manipulate to re- ceive positive classification under hy-ie., those who has he be(M (Nou [x]) = 0-as possible candidates for xt. This forms the set X, as described in Line 9 of Algorithm 1. Our algorithm then considers all potential manipulations of a. under ht and forms the set V, in Line 10. These nodes are then used to update the experts as way of enumerating all possible trajectories consistent with h
Understanding arbitrary tie-breaking as an intermedi- ate step toward the --Weighted setting. Addressing the challenges arising from arbitrary tie-breaking is an impor- tant intermediate step towards our main 7- Weighted setting. In the --eeighted setting, agents lack access to the current classifier and instead use the weighted sum of historically implemented classifiers as an estimate. This estimation inevitably introduces small errors that cause the agents to perceive certain out-neighbors as more favorable than oth- ers, even when all are labeled as negative under h4. As a result, when the agent's estimate h, is close to hr their best response to ht can still be viewed as a best response to hrg but under arbitrary tie-breaking rules (which we will formalize in Section 4). Therefore, we first remove the stan- dard tie- brebbraking assumption, and study the Revealed-Art setting before analyzing the -eeihheedd setting.
We provide the guarantee for Algorithm I in Theorem 3.1 and defer its proof to Appendix A.I.
Theorem 3.1 (Upper Bound on MRevealed-Arb. Let M H) be the mistake bound of A in the standard (non-
5

---

16: end for Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
Algorithm 1 Reduction from Revealed-Arb to classical
kig in the strategic realizable setting, when the agents best- respond to h2 with adversarial tie-breaking, our Algorithm I with A = SOA can achieve mistake bound
(non-strategic) online learning
Input: standard online learning algorithm A, manip- ulation graph G, maximum out-degree Kout and maxi- mum in-degree km
M Revealed-Ard (H) = -Kimm kow lnnnKingiii Hour) d).
2: Initialization: Expert set E {A}. Initial weight
WA= = 1.
3.2. Lower Bound
3: for t 1,2....d do
In this section, we provide a lower bound of MRevealed-Ard that matches the upper bound up logarithm factors. We defer the proof of Theorem 3.3 to Appendix A.2.
4: Prediction: Vo E X, set (x) = 1 if and only
EAED WA
WA 2 2(Kivut + 1) +
Theorem 3.3 (Lower bound on -Revealed-Arb). For any d, kin Kont E N with Kow 2 kin. there exists hypothesis class H with Littlestone dimension d, and manipulation graph G with maximum in (resp. outr-e kin (resp. koua), such that in the strategic realizable setting, any deterministic learning algorithms must suffer
AEE:AG))=1
5: Update: //when be makes mistake at the observed
node
6: if (x())) = 1 and ye = 0 (false positive mistake)
then
7: for all A E satisfying A(v:) I, update A by feeding with (vr, 0). update weight WA t f 8: else if (12) and ye 1 (false negative mistake) then
MRevealed (H) S2(kinn Kow d).
Our construction is built upon the lower bounds in Ahmadi et al. (2023); Cohen et al. (2024a). We defer the formal construction to Appendix A.2. Here, we provide some intu- ition on why removing the standard tie-breaking assumption makes the problem harder.
9:
X, - fx E N h, (Naul(=)) = 0} //Possible candidates for 2t based on observed
10:
Ve + U,eX Noui(a] //Possible manipulations of 24 under the optimal classifier h*
for all A E E s.t. Vx' Vi, A(x') 0, do
Consider manipulation graph that has subgraph structure shown in Figure 1. Suppose we have a hypothesis class where each hypothesis h; labels agents with the original feature vector z, (Vi = 2, 3) as positive and all others as negative. Let the optimal hypothesis be hę*.
12:
feed (a', 1) to A for each x' E V/ to obtain a new expert A(x',))
13:
Replace A in E with {A(x'11) Lx E V.J. assign weights (A(x'1) (2/(2(V))) end for
14:
Consider the scenario where the decision-maker implements the all-negative function and the adversary selects agent Zz.. In the Revealed setting, if the tie- tie-breaking always favors zo, the decision-maker makes a mistake but observes the post-manipulation feature at To. thereby gaining no information about i*, This is in contrast to the Revealed-SS setting, where agent DG. cannot obtain a positive prediction through manipulation and thus remains at za,, enabling the learner to successfully identify the optimal hypothesis.
15: end if
strategic) online learning setting when the inputs are (non- strategic) realizable by H. online strategic classification where the agent sequence strategic realizable under 'H, and each agent best responds to ht with adversarial tie- breaking, Algorithm I achieves
20
MRevealed-Arb (H) =Oknnn Kout In In(Kin - 1 (A, H).
is well-known that the Standard Optimal Algo- rithm (SOA) (Littlestonee 1988) achieves mistake bound MSaa (H) Ldim(H) in the standard realizable online learning (where Ldim(H) is the Littlestone dimension of H). By plugging this non-strategic mistake bound into Theorem 3.1, we obtain an upper bound on MRevealed summarized in the following corollary.
D1
22
33
Figure subgraph of the lower bound construction.
4. Best Response to the Weighted-Sum of History
Corollary 3.2 (Upper bound on MReveated-Arb) For any hypothesis class H. with Littlestone dimension d, and any monipulation graph G with out-degree kiw and in in-degree
In this section, we study the -Wiihttedd setting. In round t, the agents cannot observe the current implemented classifier ht. They will only best respond to the weighted average
6

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
of historical classifiers i.z -يب Σr= - for some 7 E (0, 1) as defined in Section 2, i... 24 E RR (Tr) with adversarially tie-breaking. We show that the learner will suffer O((1 - -)--1 kim) times more mistakes.
To achieve the second mistake bound of O (d(1 - - hun In(Kin we design re- duction to Revealed-Arb as shown in Algorithm 3. Given any algorithm A with a mistake bound guarantee in the Revealed-Are setting, we update A and implement a new classifier only after a sufficiently large number of repeated mistakes, say & repeated mistakes. When the implemented classifier remains the same for at least repeated mistakes, the weighted average of historical classifiers will be close to h. Consequently, when agents best respond to R7. they are in fact best responding to h4- However, as mentioned at the beginning of Section 3, tie-breaking in this setting is adversarial.
4.1. Upper Bound
Theorem 4.1 (Upper bound on -e-Weiihted). For any hy- pothesis class H with Littlestone dimension d and any ma- nipulation graph G with dut-ee Kow and in-degree kim in the strategic realizable setting, when the agents best- respond the ---eighted sum of the history h2² there exists learning algorithm that achieves mistake bound of
0 (min { d(l1 - (d)1-))' Kon In (oinhoou): (711))
Algorithm 3 Reduction from 7-Weighted to Revealed-Arb
1: Input: Parameters Y an online learning algorithm
We design two separate algorithms the bounds of O(1Hl) (in Lemma
achieve 4.2) and O ((1 - -))-1 hour In(A our )d) (by combining Lemma 4.3 and Corollary 3.2) respectively.
A that achieves mistake bound MMReealed-Arb(() for Revealed-Arb agents.
2: Initialization: Update frequency:
+
[l(()) (n)](])(]] +
Number of mistakes since the most recent update: Φ +
While achieving O((7l) is usually trivial in most online learning problems (including our Revealed-Arb setting), it becomes subtle in the y- weigghted setting. Typically, this linear guarantee can be obtained by trying each hypothesis in H. and discarding it once it makes mistake. However, in the 7-Weighted setting, even if we have identified the optimal classifier h* and used it as the current classifier he, it may still make a mistake since the agent is not necessarily best responding to ht.
Clock (current time step) of algorithm i: 1.
for t 1,2,... do
Commitment: Commit to classifier he + h4 //Use A's i-th output.
5: Prediction: Agent (I2, arrives, manipulates to me
and receives label hx(w)).
6: Update: //when we make a mistake at the observed node 1y
To achieve this linear guarantee, we refine the approach of trying all hypotheses as shown in Algorithm 2. Specifically, we predict x positive if any existing hypothesis labels positive. If we make false positive mistake, we can climinate one hypothesis. A false negative mistake can occur only if a false positive mistake happened in the previous round. Thus, we obtain the following guarantee. The proof of Lemma 4.2 deferred to Appendix B.2.
if h4 (v:) # y then
8:
Φ Φ +1
if
$ then //ff the learner has made 4 mistakes since the last update of A
10:
11:
Update A: Feed A with observation (ve, yr); i i àb + 0. //Reset the mistake counter
12:
13: end if
Algorithm 2 Conservative algorithm for W-iigtteed 1: Initialization: expert set E H.
14:
end if
15:
end for
2: for t 11=1,,2 1, do
3: Prediction: at each point x, hxx)) 1 if and only if there exists h E E such that h(z) 1.
By running Algorithm 3, the total number of mistakes is bounded by the mistake bound of A multiplied by the num- ber of mistakes between each update of A. which is tb
4: Update: //when observe a mistake at Uz
5: if yt- = 0 then
Lemma 4.3 (Mistake bound of Algorithm 3). Let MRewealed-Ard (A, H) be an upper bound on the number of mistakes that A makes on any strategic realizable sequence of agents in the Revealed-Ard setting. Then the -eeehhtt setting, i.e., E BR (ax) for all 2 1, the mistake bound of Algorithm 3 satisfies
6: F. Fx(h: M(v+)) = =1}
7: end if
8:
end for
Lemma 4.2. For any hypothesis class H. in the strategic realizable setting, when the agents best-respond to the "y- weighted sum of the history h2, Algorithm 2 achieves a mistake bound of O(H)).
[n 1
My Weighted (H)
In(y) +1)
Arevealed-ArbAAA H).
7

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
We defer the proof of Lemma 4.3 to Appendix B.1. Combin- ing Lemma 4.3 and Corollary 3.2, we achieve the mistake bound of O ((1 - -))- 1 kintiou In (Kinhoon))
fact, the learner can guarantee only a single mistake: by initially predicting the left leaf of each star positive, the learner will eventually make a mistake sponding to the optimal hypothesis har, at which point the learner can then switch to implementing h4s and makes no further mistakes.
the star corre-
4.2. Lower Bound
In this subsection, we will provide the lower bound MM-Weighted. which shows that both the kip factor and the (1-7)-1 factor are unavoidable in certain regimes. We defer the proof to Appendix B.3.
However, the above approach incurs (1 11-7) -) mistakes in the ?-Weighted setting. The adversary can repeatedly present correctly labeled agents to build up weight on 2 , in the learner's 7-weighted classifier 47, before inducing a mistake in the i"-th star. Once the learner identifies i* through the mistake and attempts to switch to the correct prediction over the i*-th star by Lx,,, R² it must continue implementing this new hypothesis for (1 - -- rounds of repeated deployment of 1 R before the best response of agent _ switches from Ti+ ,I. to Ii. During this transition - which forces the agent to "forget" the influence of past classifiers - the learner continues to make mistakes.
Theorem 4,4 (Lower bound on Mn-Weighted) For any E N and discount factor 7 E 1), there exists a hy- pothesis class H. with Littlestone dimension d and a ma- nipulation graph G with kin = kiow = 2, such that in the strategic realizable setting, when agents best-respond to hū, any deterministic learning algorithm must suffer mistake bound of
My-Weightee S2 d(1--))+, (m) (P11))
In the full proof of Theorem 4.4 which we present in Ap- pendix B.3, we show that this (1-7)-1 blow-up in mistakes is inevitable for any learning algorithm, unless [7] is small and the learner adopts a more conservative algorithm (e.g.. Algorithm 2) to achieve mistake bound of [?(].
In the special case o + O, for any Rins Kime E N where Kont 2 (1 + ((1)) kim there exists an instance with max- imum in (resp. out)- kin (resp. kow), such that any deterministic learning algorithm must have
Weighteed Rid -ii Kowa)
5. Learning Agents
In Theorem 4.4's lower bound, the Am factor arises due to arbitrary tie-breaking, which is consistent with the lower bound in the Revealed-Arb setting. This component of the lower bound is established using a modified version of the instance used in the proof of Theorem 3.3.
In recent years, repeated Stackelberg games with learn- ing agents have become a rapidly growing area of study (see Brown et al. (2024); Haghtalab et al. (2024); Collina et al. (2024) for a non-exhaustive list). In such settings, in each round, the decision maker first selects a policy (cor- responding to the classifier in strategic classification), and the agents subsequently choose an action (corresponding to which neighbor to manipulate to) by running an online learning algorithm instead of directly best responding. How- ever, these results cannot be directly applied to strategic classification, as the agents' action sets, Noar [aa], vary over time. In contrast, the existing literature typically focuses on games such as auctions (Braverman et al., 2018; Cai et al., 2023) and contract design (Guruganesh et al., 2024), which assume a static action set for agents throughout the game.
On the other hand, the (1 - -) factor reflects the cost of having historically implemented incorrect hypotheses. In fact, this lower bound still holds even when agents adopt standard tie-breaking. The construction is based on repli- cating a simple star graph (with one center and two leaves) by [7] times, as illustrated in Figure 2. Each hypothesis h2 E H. labels the right Icaf of the i-th star as positive and the left leaves of all the other stars as positive, i.e.,
h4 A== n ( (.)
FL.L
LLR
L
DRR
H.L
THR
Defining learning agents in strategic classification presents unique challenges, since we need meaningful performance guarantees for their learning algorithms. While regret (or variations such as swap-regret) is a standard performance measure in many game-theoretic settings, it does not trans- late directly to strategic classification for two reasons.
F1
Bi.B
FHHB
Figure 2. The graph used to establish the lower bound on Meigtigteedd for general y E (0, 1).
1. The agents' action sets, Now[2z)), vary over time, making the standard regret notions inapplicable because they usually assume a static action set. Although adopting sleeping regret (where an action/feature vector is only feasible in rounds where it is reachable from the agent's
Note that if the agent best responds to the current classifier (as in the Revealed-Std or Revealed-Arb Arb setting), then this instance is easy to learn as d, kim, Koa are all constants. In
8

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
initial feature vector) as performance measure could address this issue, it remains an open direction due to the second challenge below.
The function of captures the bounded rationality of learn- ing agents: as the gap between the best and second-best manipulations shrink, they have higher probability of choos- ing the suboptimal action even when the learner is already implementing the optimal classifier. This leads us to the following observation. See Appendix C for a formal version and the proof.
2. Classical regret bounds often depend on the size of the action set. In graph-based strategic classification, actions correspond to nodes, and the total number of possible actions can be extremely large or even infinite, rendering traditional regret guarantees impractical or meaningless. Even in geometric setting (e.g. Dong et al., 2018; Shen et al., 2024) where features are d-dimensional vectors in a Euclidean space and can be grouped based on geomet- ric adjacency. Haghtalab et al. (2024) have highlighted a similar challenge of overcoming exponential dependency on the dimension d.
Observation 5.2 (informal). There exists a hypothesis class
H = (h) h22 } of size and a manipulation graph G with kin Kious I 3 such that when agents run Multiplicative Weights/e-Greedt with et set to be -/ or /i (which are the most common choices of parameters), the decision maker will suffer infinite mistakes as I goes to infinity.
6. Discussion and Future Directions
Though existing results cannot be directly applied to obtain performance guarantees for the agent's 's learning algorithm, we still aim to provide some insights into learning agents. A popular category of learning algorithms considered in this context is mean- based learning algorithms. Adapting the definition to the context of strategic classification, mean- based algorithms can be defined as follows.
In this paper, we investigate the question of whether decision-makers should make classifiers transparent in on- line strategic classification. We focus on a non-transparent setting in which agents do not observe the current classifier but manipulate their features based on a "-weighted average of historical classifiers. We show that compared with the fully transparent setting, hiding the classifiers leads to an additional multiplicative factor of (1 -1)- or kin in the decision-makes 's mistake bound. Notably, the km factor is unavoidable even in the transparent setting when the agent switch from standard to adversarial tie-breaking among mul- tiple best responses. We complement these lower bounds with algorithms whose mistake bounds grow by at most O(11 7)- kin) factor relative to the the transparent setting.
Definition 5.1 (Mean- Based Learning Algorithms (Braver- man et al., 2018)). Let Tu = T-1 Σ h be the empirical average of historical classifiers. An algorithm is me-n- based it is the case that whenever (o') < (v) - r for v, E Vomtee [2t], the probability that the algorithm chooses to manipulate node v' is at most 17. An algorithm is called mean-based if it is t-meen- for some 1) - o(1).
Mean-based algorithms encompass most standard online learning algorithms, such as the Multiplicative Weights al- gorithm, the e-Greedy algorithm, and so on (Braverman et al., 2018). Our main Weightee setting with 7 1, also falls in the mean-based class with 17 = 0. As shown in Section 4, the de- cision maker suffers )(?)) mistakes in this case. However, the situation can be worse for other mean-based algorithms. We observe that if 17 is non-zero, the decision maker could suffer an infinite number of mistakes even in the strategic realizable setting.
There remains several open directions for future work. An immediate question is to close the gap between upper and lower bounds. While our lower bound shows the hin and (1 - --) factors are individually unavoidable in differ- ent regimes, it remains to extent our construction in Theo- rem 4.4 to simultaneously deal with any combinations of kim and y. Another open problem is extending our analysis to randomized algorithms (where the adversary's 's choice of the agent sequence cannot depend on the realized classifiers) or the agnostic setting (where the optimal classifier makes nonzero mistakes). The characterizations for both setting are particularly challenging and has remained open even in the standard transparent setting (Ahmadi et al., 2023; 2024; Cohen et al., 2024a). Finally, as discussed in Section 5, it remains open to consider other models of learning agents with nontrivial performance guarantee for both the decision- maker and the agents. We believe that sleeping regret is a natural candidate for agent's performance measure, but deriving meaningful sleeping regret bounds is challenging due to the large action space.
algorithm, the
More specifically, given the average of historical classi- fiers, h, = - E' hr let v1 = arg Nalze) (v) and U2 = arg max.en..... (o..). (e((r) be the empirically best and second best neighbors. For a based al- gorithm A, we define a monotonically decreasing func- tion o,4 [0 + [0, 1] such that oz (T) he (x2)) is lower bound of the probability of choosing the sec- ond best neighbor U2. For example, for Multiplicative Weights where the probability of choosing a neighbor e is proportional to exp(EI (x) with learning rate Et, (2) 2 exp(- (xp(-cr(t-))=)) For e-Greedy with exploration rate Ct. (2) 2 E /ron-
9

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
Impact Statement
Braverman, M. and Garg. S. The role of randomness and noise in strategic classification. In Foundations of Re- sponsible Computing (FORC), volume 156 of LIPIcs, pp. 9:1-9:20, 2020.
This work purely theoretical. We do not foresee any immediate societal consequences.
Acknowledgments
Braverman, M., Mao, J., Schneider, J., and Weinberg, M. Selling a no-regret buyer. In Proceedings of the 2018 ACM Conference Economics and Computation, pp. 523-538, 2018.
We thank Avrim Blum for the helpful discussions. HS was supported by Harvard CMSA.
Brown, W., Schneider, J., and Vodrahalli, K. learning in games good for the learners? Advances in Neural Information Processing Systems, 36, 2024.
References
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 6-25, 2021.
Brückner, M. and Scheffer, T. Stackelberg games for adver- sarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 547-555, 2011.
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. On classification of strategic agents who can both game and improve. arXiv preprint arXiv:2203.0012
Cai, L.,, Weinberg, S. M., Wildenhain, E.,, and Zhang, S. Selling to multiple no-regret buyers. In International Conference on Web and Internet Economics, pp. 113-129. Springer, 2023.
2022.
Ahmadi, S., Blum, A., and Yang, K. Fundamental bounds online strategic classification. In Proceedings of the 24th ACM Conference Economics and Computation, pp. 22-58, 2023.
Chen, Y., Liu, Y., and Podimata, C. Learning strategy- aware linear classifiers. Advances in Neural Information Processing Systems, 33:15265 13:15255-15276, 2020.
Ahmadi, S., Yang, K., and Zhang, H. Strategic littlestone dimension: Improved bounds on online strategic clas- sification. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Cohen, L., Mansour, Y., Moran, S., and Shao, H. Learn- ability gaps of strategic classification. arXiv preprint arXiv: 1rx2v 2024a.
Cohen, L., Sharífi-Malvajerdi, S., Stangl, K., Vakilian, A., and Ziani, J. Bayesian strategic classification. arXiv preprint arXiv:2402.08758, 2024b.
Akyol, E., Langbort, C., and Basar, T. Price of trans- parency in strategic machine learning. arXiv preprint 1r0.v:1610.08210, 2016.
Collina, N., Roth, A., and Shao, H. Efficient prior-free mechanisms for no-regret agents. In Proceedings of the 25th ACM Conference on Economics and Computation, pp. 511-541, 2024.
Barsotti, F., Koçer, R. G., and Santos, F. Transparency, detection and imitation in strategic classification. In 31st International Joint Conference on Artificial Intelligence, IJCAI 2022, pp. 67-73. International Joint Conferences on Artificial Intelligence (UCAI), 2022.
Dalvi, N., Domingos, P., Sanghai, S., and Verma, D. Ad- versarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discov- ery and data mining, pp. 99-108, 2004.
Bechavod, Y., Ligett, K., Wu, S., and Ziani, J. Gaming helps! learning from strategic interactions in natural dy- namics. In International Conference Artificial Intell- gence and Statistics, pp. 12422. PMLR, 2021.
Dekel, O., Fischer, F., and Procaccia, A. D. Incentive com- patible regression learning. Journal of Computer and System Sciences, 2010.
Bechavod, Y., Podimata, C., Wu, S., and Ziani, J. In- formation discrepancy in strategic learning. Interna- tional Conference on Machine Learning, pp. 1691-1715. PMLR, 2022.
Deng, Y., Schneider, J., and Sivan, B. Strategizing against no-regret learners. Advances in neural information pro- cessing systems, 32, 2019.
Blum, A., Haghtalab, N., and Procaccia, A. Lazy defenders are almost optimal against diligent attackers. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
Dong, J., Roth, A., Schutzman, Z., Waggoner, B., and Wu, Z. S. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55-70, 2018.
10

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
Fiez, T., Chasnov, B., and Ratliff, L.. Implicit learning dy- namies in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In Interna- tional Conference on Machine Learning. pp. 3133-3144. PMLR, 2020.
Liu, L. T., Wilson, A., Haghtalab, N., Kalai, A. T., Borgs, C., and Chayes, J. The disparate equilibria of algorith- mic decision making when individuals invest rationally. In Proceedings of the 2020 Conference on Fairness, Ac- countability, and Transparency, pp. 381-391, 2020.
Ghalme, G., Nair, V., Eilat, I., Talaam-Cohen I., and Rosen- feld, N. Strategic classification in the dark. In Interna- tional Conference on Machine Learning, pp. 3672-3681.
Mansour, Y., Mohri, M., Schneider, J., and Sivan, B. Strate- gizing against learners in bayesian games. In Conference on Learning Theory, pp. 5221-5252. PMLR, 2022.
PMLR, 2021.
Miller, J., Milli, S., and Hardt, M. Strategic classification causal modeling in disguise. In International Conference on Machine Learning, pp. 6917-6926. PMLR, 2020.
Guruganesh, G., Kolumbus, Y., Schneider, J., Talgam- Cohen, I., Vlatakis GaaaakiisGKaar,,uumiis,, E.-V., Wang. J. R., and Weinberg, S. M. Contracting with learning agent. arXiv preprint arXiv:2401.16198, 2024.
Milli, S., Miller, J., Dragan, A. D., and Hardt, M. The social cost of strategic classification. In Proceedings of the Con- ference on Fairness, Accountability, and Transparency, pp. 230 239, 2019.
Haghtalab, N., Immorlica, N., Lucier, B., and Wang. J. 7. Maximizing welfare with incentive-aware evaluation mechanisms. In Proceedings of the Twenty-Ninth Ninth Inter- national Conference on International Joint Conferences on Artificial Intelligence, pp. 160-166, 2021.
Montasser, O., Hanneke, S., and Srebro, N. Ve classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pp. 2512-2530. PMLR, 2019.
Haghtalab, N., Lykouris, T., Nietert, S., and Wei, A. Learn- ing in stackelberg games with myn-my agents. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 117-918,22 2022.
Perdomo, J., Zrnie, T., Mendler-Dünner,, C., and Hardt, M. Performative prediction. In International Conference on Machine Learning. pp. 7599-7609, PMLR, 2020.
Haghtalab, N., Podimata, C., and Yang. K. Calibrated stack- elberg games: Learning optimal commitments against calibrated agents. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Shao, H., Blum, A., and Montasser, O. Strategic classifi- cation under unknown personalized manipulation. arXiv preprint arXiv:2305. 16500 2023.
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 11 1121 2016.
Shavit, Y., Edelman, B., and Axelrod, B. Causal strate- gic linear regression. In International Conference on Machine Learning (ICML), pp. (676-8686, 2020.
Shen, L., Ho-Nguyen, N., Giang-Tran, K.-H., and Kıling- Karzan, F. Mistake, manipulation and margin guaran- tees in online strategic classification. arXiv preprint arXiv:2403.18176 2024.
Hu, L., Immorlica, N., and Vaughan, J. W. The disparate ef- fects of strategic manipulation. In Proceedings of the Con- ference on Fairness, Accountability, and Transparency, pp. 2019.
Tsirtsis, S. and Gomez Rodriguez, M. Decisions, counter- factual explanations and strategic behavior. Advances in Neural Information Processing Systems, 33:16749- 16760, 2020.
Jagadeesan, M., Gendler-Dünner, C., and Hardt, M. Alter- native microfoundations for strategic classification. In International Conference on Machine Learning, pp. 4687- 4697. PMLR, 2021.
Xie, T. and Zhang, X. Automating data annotation under strategic human agents: Risks and potential solutions. arXiv preprint arXiv:2405.08027, 2024.
Lechner, T. and Urner, R. Learning losses for strategic classification. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 7337-7344, 2022.
Zhang, H. and Conitzer, V. Incentive-aware pac learning. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 35, pp. 5797-5804, 2021.
Lechner, T., Urner, R., and Ben-David, S. Strategic clas- sification with unknown user manipulations. In Inter- national Conference on Machine Learning, pp. 18714- 18732. PMLR, 2023.
Zrnic, T., Mazumdar, E., Sastry, S., and Jordan, M. Who leads and who follows in strategic classification? Ad- vances in Neural Information Processing Systems, 34: 15257-15269, 2021.
Littlestone, N. Learning quickly when irrelevant attributes abound: A new finear-threshll algorithm. Machine learning, 2(4):285-318, 1988.

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
A. Omitted Proofs from Section 3
A.1. Proof of Theorem 3.1
Theorem 3.1 (Upper Bound on MRevealed-Arbb. Let (A, H) be the mistake bound of A in the standard online learning setting when the inputs are inon-strategia realizable by In online strategic classification where the agent sequence stralegic realizable under H. and each agent best responds to with adversarial lie-breaking, Algorithm I achieves
MRevealed Arb (H) (Rin kout
(A,
M (A, H).
Proof of Theerrmm 3.1. Suppose the standard online learning algorithm that input to Algorithm 1, and let M be the number of mistakes that makes on any realizable sequence. To keep track of the algorithm's progress, we use W2 to denote the total weight of experts at the beginning of round i.e.,
We = Σ
AEE
We first show that whenever Algorithm makes a mistake at round f, the total weight satisfies
Wi+1 (1- (1-4(kome 4(Kout + 1) + 17) We.
We analyze the following cases.
Case 1: False positive mistake. In this case, the agent is labeled as (v())) 1 after manipulation, but the true label is
Y: 0. Since the true label is 0, the realizability of input sequence S implies that the optimal hypothesis h* should label the entire neighborhood Nowr [az]-incluuing t- O. Therefore, we proceed by updating all experts that predict A(v) = 1 by feeding them with the example (v,, 0), and halving their weights. Since (e(1)) = 1, according to the prediction rule in Line 4, we must have
Σ
1 WA
W,
Koou
1k + 1)
AEE:
Therefore, the updated total weight satisfies
W 121=Wi W1 Wi-
Σ
AEE:A(e)==1
1
5 4(kiuu + 1) + +1) W.
Case 2: False negative mistake. In this case, the agent is predicted as (2(v)) = O, but the true label is ys 1. This implies that our learner h, labeled the entire out neighborhood Noml with 0, otherwise, if there is an x' E Nou [z:]] with (x')) = 1, De would have manipulated to x' and received a positive label. In addition, since the sequence of agents is realizable, we know that h* (BRR, (zx)) = 1, i.c., h* must label some node in Nou [xz]] as 1.
However, the main challenge in this adversarial tie- bre-brek setting is that we do not observe the true label Øt. Instead, we know that &a can be any of the in-neighbors of v. that satisfies hy (Nom(z)) [x]) (which means ht labels all nodes in Nowr [x]] 0). Thus, construct set of candidates for z; as follows (as described in Line 9 of Algorithm 1):
X = {a E Nu[ev]] he (Nort( [x]) 0}
Since & contains all possible choices of 21, any expert that labels the union of their out nei-hhigbboroood (i.c., 1z == U UnS Nom (zr)) as all negative must be wrong. Based on our prediction rule, we can show that the total weight of such
12

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
experts should take up significant fraction of W
E
w
(8)
W E
Σ
w (
r'vV AE A
IV3
1
Wr
2(Kiau + (kin + 11
2 V
kin Kiout
Wr
2(hiou + ()in + +1)
W,.
In the above inequalities, step (a) is because all nodes in VE are labeled as 0 by ht which, according to the prediction rule in Line 4, implies that for any x' E Ve, we have EAEE:ACE)== A (t) most km Rout-
W. 2(h +1] Step (b) is because the size of V is at
According to the algorithm, we split each of such A into [V/] experts i.e, {A(r', 1) x' E V.J -ad split the weight I equally among them. Thus, have Wi+1 (1 W)W; < (1 I(kh [(A.+)))A W.
Deriving the final mistake bound. We have proved that whenever Algorithm I makes mistake, the total weight W; is reduced by multiplicative factor of 4(hut 1)) Let N denote the total number of mistakes that Algorithm 1 makes.
N
Then we have total weight in the final round is at most
4(Kom 1)(k++1)
On the other hand, note that there exists an expert A E that is execution of A with trajectory (v/ ys) during the mistake rounds, where uf BR, (Ir)). Since the agent sequence (æ,, Ve)121 is strategic realizable, have h (BR,, (xx,) Mt. which implies h" (xt)) Vt- In other words, the inputs of A are realizable under h" According to the mistake bound assumption of A, A makes at most M mistakes.
Now we analyze the weight of A At each mistake round 6, if the A makes a false positive mistake, its weight is reduced by half. If A" made a false negative mistake, it is split into a few experts, one of which fed by (2/ y1) where of E BR,, (zz). Thus, since A makes at most M mistakes, its
This specific new expert's weight reduced by most 2 2(k tkkkt))(
weight at the final round will be at least
2T 31
Combining these two observations, we have
N
2(Kour + +1) +1) ) M
(1- +1) +1)
>
which yields the mistake bound of Algorithm 1:
N S 4(kout + 1)( + 1) (2 + 1) + 1))
The proof is thus complete.
A.2. Proof of Theorem 3.3
Theorem 3.3 (Lower bound on -Reeealed-Arb)- For any d, kins kout E N with Rosi km there exists a hypothesis class H. with Littlestone dimension d, and manipulation graph G with maximum in (resp. out)-degree kin (resp. Roua). such that in the strategic realizable setting, any deterministic learning algorithms must suffer
M MRevealed Arb (H) = -2(ken . kiaut d).
13

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
00
22
21
J11
412
31ke
221
T/2
2222
11111
Tki.2
Fki k2
Figure 3. Example for lower bound construction for the Revealed-Arb setting.
Proof of Theorem 3.3. Consider graph with nodes Jo, .1,....: -.g .1....... 1 l.... F as shown in Fig 3 with 22 > k1. The maximum out-degree is 22 and the maximum in-degree is kj The hypothesis class contains all singletons over the leaves. Suppose the target hypothesis is h Then only agents with original feature vectors at 2z+ and Ter.j* are labeled as positive. For any deterministic algorithm, at time t, there are the following cases:
If h all-negative, the adversary can pick 2; z; and tie-breaking favors To. Then we only observe t Tos Yt and T h2 makes mistake but learn nothing.
If h; labels 2a as positive, the adversary can pick = To and tie- tie-breaking favors To- Then we observe To.
V/- = 0 and Dr- = 1. Again, h, makes a mistake but learn nothing.
If he labels any node x, in the second layer as positive, the adversary can pick æ; zo and tie-breaking favors x,,
Then we observe 1/ Tt. V/ 0 and T 1. Again, h2 makes mistake but learn nothing.
Hence, h, can only label some leaves as positive. When labels any leaf zij other than the target one as positive, the adversary picks Ie = Iij being that leaf and tie-breaking favors Zzz- he makes a mistake and learns that Taj is not the target leaf.
Therefore, the algorithm will make ky mistakes. The Littlestone dimension of this hypothesis class is We can extend the result Littlestone dimension being d by making d independent copies of this example.
B. Omitted Proofs from Section 4
B.1. Proof Lemma 4.3
Lemma 4.3 (Mistake bound of Algorithm 3). Let MRevested Arb (A, H) be an upper bound on the number of mistakes that A makes on any strategic realizable sequence of agents in the Revealed-Art setting. Then the y-Weighted setting, i.e., Ut E BR2 (Ix) for all 2 1, the mistake bound of Algorithm satisfies
In In(3) In(r))
My.Weighted (H)
+1) - MRevesledd-nbb H)..
Proof of Lemma 4.3. Let A' be the algorithm obtained by applying the reduction in Algorithm 3 to A. Let (4) be the time steps in which line 11 of Algorithm 3 is called. The key to establishing this lemma is to show that, for any t t,, the agent's 's response will best respond to the current h1 with arbitrary tie- beeakrkk by manipulating to BR (Ix).
To see this, note that the condition in Line ensures that A' has made at least &b = ( In(>)1 + mistakes in the time interval [4-1 1, t.), which implies that f, - (f,-1 + 1) 2 क Moreover, during this time interval, A' has been using
14

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
the same classifier l Therefore, time = 44 the 7-discounted average classifier can be written
h4- 1 7--1 rml
1 7p
1-1
hr +
Σ 7 ---1
he-r
(hr = h4 for r S $ 1)
g
x=
1 --1
10- gp
-t- h4 +
h
h== g- - 7 7
1 1-
-(1 - E4) h + Ex h.
(E. == 2 2
I-
In the above equation, we have
70-1 ---11 g0-1 Et 1 ge---1 S g00-1 S {n
1
3
This implies that Ni is already very close to the true h4 If (BRi, (s+)) = 1, then we claim BR (3x) C BRA, (2.) because for any xe's r''s neighbor & BRR, (Ire,, it holds that
(v) = (1 - -.)). + 6: T(() = T((w)
Sa < E max (v')
If 1,(BBR,, (1+)) O, then BRy (m)) being some e E Now can be viewed as breaking tie adversarially for best responding to hi--
Per guarantee of algorithm A. we conclude that the number of mistakes that A' makes on the subsequence S' = (IL, Mc2111 at most MRevealed-Arb (A, H).
Finally, it remains to bound the mistakes on the entire sequence S. Since A calls A' once per + mistakes, the total number of mistakes is at most
Meiwhigtted (A', T D MRReveleed (rb H)
= -(In(1/3)/ln(r)) + +1) MRReveled (r, H).
The proof is thus complete.
B.2. Proof of Lemma 4.2
Lemma 4.2. For any hypothesis class H. in the strategic realizable setting, when the agents best-respond the w-weighted sum of the history hi, Algorithm 2 achieves mistake bound of ((H)).
Proof of Lemma 4.2. First we show that h² is always in E. For any ye 0, 11" (vx) 0 because max,e Nar[z h²(v) 0. Then h* will never be removed from E.
Next we show the number of false negative error is no larger than the number of false positive error. Suppose we make a false negative mistake at time f, i.e., Yt = and hy (v.) = 0. For E BR, (zt), (x) = h4-1(1) = because he (v) 1 and h+ E E at time 1.... ,l- 1-11-1111 1. Then we have 7 (v) = 1 by the definition of 7.7 Moreover it holds that 62 (wx) 2 h (BR (u) 1. So (vt),.. "h.,.....,,,1 (1z) must all be positive. he(wr) 0 means that E is updated time t 1 otherwise h will be the same h4. So false negative mistake can only occur right after a false positive mistake.
Every time we make false positive mistake, at least one hypothesis will be removed from F. otherwise e won't be classified as positive. So the number of false positive mistakes is upper bounded by the number of candidate hypothesis | and the number of total mistakes is upper bounded by 7)).
15

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
B.3. Proof of Theorem 4.4
Theorem 4.4 (Lower bound on MMy.Weighted)- For any d and discount factor Y E (0, 1), there exists hypothesis class
H with Littlestone dimension d and manipulation graph G with kin Rout 2, such that in the strategic realizable setting. when agents best-respond to h any deterministic learning algorithm must suffer mistake bound of
My-Weighted S2 (min (011-))-11111
In the special case of + O, for any kins Kow E I4 where Kout 2 (1+ 22(1) Kin there exists an instance with maximum in (resp. out) degree kim (resp. kouth, such that any deterministic learning algorithm must have
My.Weightee 2d kin Konz)
Proof of Theorem 4.4. We prove this theorem by establishing the two lower bounds separately. First, adapting the construc- tion in Theorem 3.3, we show that 7 O, the freedom of arbitrary tie-breaking forces the decision-maker to suffer d- km how mistakes. Next, we use different instance that exploits the agent's 's effective memory length to show that MRevealed = Ω [minfd() -) [ Combining these bounds completes the proof.
F0
F1.1
21,2
11,ka
22,1
22,2
22
17 112k (2
3ki 82
Figure Lower bound construction when >
Part 1: MM.-Weighted 22(d kin Kout) as 7 + 0. For this lower bound, consider the graph that is the same that in Figure 3, but all nodes in the first layer (namely 21, .222...... Ikk) are connected by clique, as shown in Figure 4. This modification gives Kout k + 12 and kin = k2. As in Theorem 3.3, we let the hypothesis class consist of all singletons over the leaves, i.e., H = (hr, = Iz,,, | E [ka]. E [k2]]- Suppose the target hypothesis is some unknown hy E H. Under the strategic realizability assumption, only agents originally located at xg. or x.. have positive true labels.
For + 0, best responding to R. is equivalent to best responding to h We will construct an adversary that induces at least one mistake in every two rounds in the first 2k hi rounds. This will establish a lower bound of 2(kin (Kout kin))
O(km kom) under the assumption that A 2 (1 + ((1)) km
Consider two consecutive rounds 1 and (where 2, 4. ......... 22g If the learner already makes mistake at round I 1, then mistake have been induced across these rounds. Otherwise, show below how to force mistake in round by performing
discussion of both h which the agent s; best responds and the current classifier ht- We let the initial version space contain all hypotheses.
1. If 14-1 labels vn by positive, then consider two sub-cases. If he (2o) = 1, the adversary can pick (Ix, vi) = (IDs 0), and make the tie-breaking favor Zo. This forces h, to make false positive mistake but learns nothing.
On the other hand, if (2o) = 0, then the adversary picks some (i* )² consistent with the current version space,
Since the learner's algorithm is deterministic, the adversary can simulate the interaction between the algorithm and the adversary, and pick the hypothesis hy+ that the last be removed from the version space. This makes the realizable hypothesis consistent across rounds.
16

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
sets (1 M/) ( 1), and again makes the tie-breaking favor wo- As result, the I-th agent will manipulate to zig and induces false negative mistake while revealing no information.
2. If h4 labels any leaf node æij as positive, then the adversary picks (x1,, ve) = (z 0), and removes hypothesis ha.j from the version space if it has not been removed yet. This induces a false positive mistake. Since the learner made no mistake in round / 1, we can assume that -4-1 labels all leaf nodes as negative.
3. We are left with the case where h ( = 1 and h1 labels all leaf nodes as negative. In addition, from case 2, it is without loss of generality to assume that h4- ( have induced a false positive mistake in round ( - 1 already. Therefore, only the middle layer (xi,..., F } can be potentially labeled as positive by 14- Due to arbitrary tie-breaking and the added clique, we can assume that all nodes in {ro, 21,...,, 2Kk, } manipulates to the same node 2; where i E arg (aX) h in response to hy-1- Now consider the following two subcases:
-1 for all i E [Ka] and j E [K2], as otherwise the learner could
If he (z,) = 1, then the adversary can choose (2r4, = (In, 0), which will manipulate to x; and induce a false positive mistake. If (a;) = 0. then the adversary chooses (oz, Ha) = (aze, 1) from the version space* and induces a false negative mistake, while revealing no information about i*
Note that the proof of this case crucially relies on the additional clique structure. Without this clique, the learner can set h to predict all middle-layer nodes (Z1...., Tkk, as positive, and set hú to predict all nodes as negative. This would cause all leaf nodes Zt.j to manipulate to their parent T;, while the middle-layer nodes stay put. In this case, for the adversary to induce a mistake, would have to reveal information about i*, which would allow the learner to either eliminate up to l2 hypotheses in a single round.
Since the version space initially contains 41 h2 classifiers, the above construction can be used to induce at least k1 A22 1 mistakes before the version space becomes empty. This establishes the l2k - Agy) mistake bound when d = 1. For general d, we can create dl independent copies of the same instance to obtain a bound of (2k) k2 . d).
Part 2: For any 7 E (0,1), 1), Mei-Weighted = Ω (min ( d(1 - -,- (171)) For simplicity, we consider the agents best respond to unnormalized weighted sum of history
2-2
Σ
7 h1-
in this proof because the agents will make the same manipulation for hi and T.. We first provide an example for hypothesis
class with Littlestone dimension being 1. Consider the graph with F1,B, Fi, FI, R1 T H. HH,, as shown in
Fig 2. There are H classifier in the hypothesis class H with h, defined as h,(2),)) = 0 for all j; (z = 1, 1,,, = 0 for any j A i; and ha(aa,,)) O, ha (2(,,, R) = 1. Suppose the target hypothesis is har.
At each round t, there are three cases regarding the weighted sum of historical classifiers Ry:
1. If there exists i # it such that h, (ZI,B) = max ( F of h4
F (ZI,L), (, (I,,R)), we consider the following two cases
(a) If hy labels n as negative, the adversary can pick 24+ = Ni,B- The agent will always stay at zú,0 under standard tie-breaking rule. We will observe i2 = B, Vt+ 1 and De = 0. he makes a mistake but learns nothing. T. (z), the adversary can pick x, Is The agent will
(b) If h labels Ti as positive and TV (xx,B) manipulate to n. he makes a mistake but learns nothing.
(c) If T. (Zx,B) = F (z) 2 Ty (zx,L) and h4 labels both æ,, and zi, as positive, the adversary can pick x, Zi The agent will stay at ni hy makes a mistake and we can eliminate h;
(d) If Th (Z) = Th, (Z.RR) 2 T (I), and he labels F, as positive and æ as negative, we can't 't force a mistake this round. However, h/ (Zx.B) will be strictly larger than h/ (z,,n) because he (x( he (=(,))). Then we force mistake in round L. + 1 without revealing any information like we did in (a) and (b) above.
Again, assume that he+.p is the last hypothesis that remains in the version space.
17

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
but by (r.,B) by (F.,R) consider 2. If there exists o i* such that Ni (x,,,) max (24,)) (x..)) (L,,)); (x..)) the following two cases of h4-
(a) If he labels R as positive, the adversary can pick 2; = Ri,R. The agent will stay at R. We will observe yr = and Vo 1. h2 makes a mistake and we can eliminate h;.
(b) he labels R as negative, the adversary can pick 2; = Bt With probability over 1/2, the agent will
manipulate to R- We will observe yt and T 0. h2 makes mistake but we can't make any progress.
3. If F. (Ri,L) > F. (2),)) and Fyy (FI,L) > F. (I.,,) for all i o i", we consider the following cases of h2-
(a) If he labels T2 negative, the adversary can pick , B. The agent will manipulate to Ti,L. h makes mistake but learns nothing.
(b) If he labels L B,,B, all as positive, the adversary pick 2, R. If the agent stays at R, we make mistake and can eliminate h4. If the agent manipulates to B, we make a mistake but can't un'tt learn anything. (c) If h, labels Z and 2t positive and labels 7 negative, the adversary can pick x, Li The agent will manipulate to Fi,L. We don't I make mistake but we also learn nothing. The only benefit in this round is that weeighted-suu will receive more weight for R than 2 from h2- (d) If h labels Z,,L positive and R as negative, the adversary will pick 2, 21 Again we don't tt make mistakes and learn nothing. But >-weighted-sum will receive more weight for Zı,L than Fi, from h4-
Start from some time T. We hope to achieve one of the following goals at time T T where T is some number we will choose later:
There exists a feasible such that hor (1) > For (z.,)) + अा-
There exists a feasible i such that Tor (7),)) > TyT (x:,,)))
We make least one mistake and the hypotheses we can eliminate no more than the mistakes we make.
The third case will happen once one of ((a-d), 2(a), 2(b), 3(a), 3(b) happens. So we would assume only 3(c) and 3(d) occur between time T' and 7".
For any feasible i at time T. we define A, (T St Th (((h,,)),L) = 1, (x.,nn) = 0, he (xi,n) = 1} and C₁ (T < 1 (h( 1, h.(,,n) = 0, ( 0). We further define A EiEs, 2 - An Eien, -1 and Oo Erec; 7t Then can have that
1,,,(Z (,,,( B, (T <t<
hr (T)(())) = T' (1)()) - + DA + AB + Ac
= TTT 1 1-
1-7
(1)()))) = "TT + AAA
(1)(B))) = - AB.
If neither of the two goals is achieved for i, then it must hold that
3(1 7) 2 (T) (1)
= -T' (vr(7))aa.)) An De
> AB + Ao
and
A^ AB T -T (1))))
< 3(1 -7) - -A x -T (ur
1
$ 3(1 7)
Ac -
3(1 7)
18

---

1, it will always hold Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
Combining the two inequalities above, we have that
T"
AA A AB
Ac <
3(1 77)
This requires -T" 2 !. which won't be true for T' T +
In(1/>) So least one of the first goal achieved time T
3.
Next we claim we can achieve one of the following goals at time T" 2 T
(vT"())((111)) (T) + 3(->))
hTw (1) > hr" ()) and (T =.
We make least one mistake and the hypotheses we can eliminate no more than the mistakes we make.
From the derivation above, we can assume the third case never happens after T. If the first case also never happens after T', we know must hold that (2))) > (x,)) for any 2 T'. So there exists t 2 T" such that ht (x = 1, we can finish proving the claim. On the other hand, if (xi,)) = 0 for all the 2 T", for T + In(1/7]*
1.5. we have that
T
(T) - TTT (7)
2
T" -1 1- (helsta.)) (xi,n))
t=
-T
1-y
1
3(1 7)
This is because (+)),)) 2 (1)(,)) and he(2),)) for all the / 2 It means the first case will happen T" which causes contradiction.
If the second case happens,
choose rT" Ti We will make mistake and eliminate h;-
In(4/3) the first case happens, we will choose h, as the target classifier. For t = T" T"...., T" + mi(17) that Fy (#),L) > Tr, (2),)) because
(I,,L) Fy (F..n)
1-1 1
2 22'-T" (1) - TTT (7)(a.))))
==
1 --1--""
TT"
3(1 7)
1 1-7
4/2 1-1
3(1 - 7) 0.
We will diseuss all the cases during T ,.., T In(4/3) rounds.
in which we can force mistakes in at least half of the
(m177)
ifh h (#LB) > 17 L.), we consider the following two cases of ht-
(x(,B) = 1, the adversary will choose 2, = Tt,L- The agent will manipulate to B, hy will make a mistake but learn nothing.
If (,) = 0, the adversary will choose Ri,R. The agent will manipulate Zi B- by will make a mistake but learn nothing.
If F (Rx,B) = n. (#x,L) > Ti. (.) we consider the following four cases of ht.
19

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
If (T,,L)))) 1, the adversary will choose ze L.,L- The agent will stay X4,L. hy will make mistake.
If (1( 0, the adversary will choose Ri The agent will manipulate zi,B. hy will make mistake but learn nothing.
(T),)) = and ( 1, we won't force a mistake in this round. But ( and Ni (#r,L) won't be the same and we can definitely force a mistake in round
discussed above.
Based the analysis above, the learner will either make at least 4/33 mistakes to know the target functions make (m(l//>
least [H] mistakes eliminate all the alternative functions. is easy show that ln(1/3)
In(4/3) 7) for any
1m(1/73
0 <<> < 1. So the mistake bound is Q(min (1 -)- [7(]). , For Littlestone dimension d, we can create d independent
copies of the above instance. The mistake bound will be {2min d(1 - ->)- (H()).
C. Omitted Details and Proofs from Section 5
Observation C.1 (Formal version of Observation 5.2). There exists hypothesis class H. {h1,hh) h2) of size 2 and manipulation graph G with ki:: Kow S 2 such that for any mean-based learner A, the decision maker will suffer at least
Σ minfor (1=1-1112 ),Ct number of mistakes, where Ct SI(1) is the probability of choosing empirical best neighbor.
- in Multiplicative Weights/e-Greedy when the number of Note that learning/exploration rate is usually set to be é, VT rounds is T, then have El= o (--1-1/3) Q(VT) for both. This implies that Multiplicative Weights/e-Greeid will suffer infinite number of mistakes as T goes to infinity the strategic realizable setting.
Proof. Consider a manipulation graph shown in Fig 5, where there are three nodes and a hypothesis class H m=my l==rg)
LL
2 R
JB
Figure 5.
For any time horizon T, in the first 2/2 rounds, the adversary always picks agent (2., yr) = (x 1), which consistent with either hypothesis in H. After the first T/2 rounds, we compare (xT/2(1)) and (T)2((R)) We pick the target function to be h* = Ilymn / 2 ( and h* 1g=ar, otherwise. W.L.o.g. assume that ( 2 2 R)) and h" _=== Then at round = T/2 I,..., T, we have (t ()- (hry2(æR) brrz((1)) S T/22.
Then at round t T/2 1, T, we consider the following cases:
[x( > (x) and hy (x = 1. this case, the adversary will pick (æ,, ye) = (æz, 0). then with probability at least ct, the agent will manipulate the empirically best neighbor EB and the learner makes mistake.
Tr(#B) > Tx(xL) and he(x)) = 0. In this case, TT(2R) - Tr( < T(((R) T(( < -11-// Then the adversary will pick (z,, v1) (æR, 1). then with probability at least oA (AA(-1_T/2) T/22), the agent will manipulate to the empirically second best neighbor æ and the learner makes a mistake.
he(#n) < he(x)) and he (x1.) = O. In this case, the adversary will pick (I,, Wr = (æn, 1), then with probability at least of 0,A( 12-1////) the agent will manipulate to 2y and the learner makes mistake.
20

---

Should Decision-Makers Reveal Classifiers in Online Strategic Classification?
he(B)) S hx())) and (x(z) In this case, the adversary will pick (It, vc) (x 0), then with probability least Ct, the agent will manipulate zy and the learner makes mistake.
As result, in all cases, the learner makes a mistake in each round > I with probability Q2min ((minn(oA("=2 o=A("=1-1/2) ), Summing over 12 + 1, 7] completes the proof.
2
21


Reviews:
[{"review_id": "MRsHgsnMjD", "reviewer": "Reviewer_WPjm", "summary": "This work studies an online classification setting, where arriving points (agents) can manipulate their features according to a manipulation graph, where the rationale to to obtain more favorable predictions. Under a realizability assumption, the authors study a scenario where the decision maker does not reveal its currently deployed predictor to agents, who instead manipulate their features as a response to the weighted average of past predictors in the interaction. Under an additional assumption of adversarial manipulations by agents, the authors prove upper and lower mistake bounds for the problem, and show a gap for the full information analogue (though without allowing manipulations to be adversarial), studied in previous work. The paper concludes with examining situations where agents run no regret algorithms instead of best responding, and demonstrate the difficulty of learnability in their model.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for the thoughtful comments. We address them below.\n\n> revealing the past deployed policies\n\nWe agree that the decision-maker might not want to reveal their past models explicitly. However, historical outcomes often reveal past classifiers implicitly. For example, we can observe which students were admitted by a college in previous years (based on SAT scores, GPA, extracurriculars) or which loan applicants were approved—and use this information to estimate the predictors that were likely implemented in the past. In some specific cases, the model is effectively made public: in college admissions in countries with unified entrance exams, universities often reveal the threshold classifier by publishing the minimum admission scores after each admissions cycle.\n\n> adversarial tie-breaking\n\nWe appreciate the reviewer’s concern and want to clarify that we do *not* intend to make adversarial tie-breaking a realistic behavioral assumption. Instead, we use it as a conceptual and technical intermediate step toward analyzing the more realistic setting (gamma-Weighted) where agents *cannot* observe the currently implemented classifier and instead best respond to an *estimate* of it. As we discussed in Lines 235-251 of our manuscript, in such settings, estimation error can cause the agents to perceive one node as slightly better than the other node, even if the true classifier might assign them the same label. For example, if $\\tilde h(v) = h(v)$ for all $v \\in N_{out}(x)$, but $\\tilde h(x) = h(x) - \\epsilon$, the agent would not remain at $x$, behaving as if they are breaking ties adversarially.\n\nThe purpose of Theorem 3 is precisely to highlight the mistake bound gap between the case where agents only perceive a perturbed version of the true hypothesis $h$ versus the case where they perceive $h$ perfectly. We treat adversarial tie-breaking as a proxy for incorporating such estimation errors into the mistake bound analysis, which serves as a building block towards the gamma-Weighted setting. \nSecond, our upper bound in Theorem 4.1 holds for both tie-breaking ways. We note that our lower bound in Theorem 4.4 consists of two parts: $\\min(d/\\log(1/\\gamma), |H|)$ and $d \\cdot k_{in} \\cdot k_{out}$* , where the first part still holds for the standard tie-breaking case with a slight refinement of the proof. The second part will be reduced to $d\\cdot k_{out}$ in the standard tie-breaking case. The dependency on $k_{\\text{in}}$ in unrevealed classifier + standard tie-breaking is left as an open problem. \n\n*There is a typo in the original statement of Theorem 4.4, $ k_{in}$ should be replaced by $k_{in} \\cdot k_{out}$.\n\n> realizability assumption\n\nPlease see the response to reviewer T9UQ.\n\n> alternatives to revealing the model in inducing agent responses\n\nWe completely agree that there are interesting settings between the two extremes, and we see it as an exciting open direction to study the spectrum of information that may be revealed. We will add [Tsirtsis and Rodriguez 2020] to the related work section and include a discussion along these lines.\n\n> explanation for line 340\n\nThe complete proof for Lemma 4.2 is in Appendix B.2, and we’d like to provide more explanation here. At first sight, it seems that there won’t be false negative mistakes because our algorithm is very conservative. Every positive sample $x$ will always have a neighbor $u$ that is labeled as positive by $h^\\star$ and $h_t$. Such $u$ is always in $BR_{\\tilde{h}_t^\\gamma}(x)$ and we won’t make a false negative mistake on $x$ if $x$ manipulates to this $u$. However, we argue there still can be false negative errors for one very specific scenario. That is, $x$ manipulates to another neighbor $v$ in $BR\\_{\\tilde{h}\\_t^\\gamma}(x)$ but $h\\_t(v)=0$. For such a case to happen, $\\tilde{h}\\_t^\\gamma(v)$ must be 1 to ensure that $x$ will choose to manipulate to it with non-negative probability. That means there is a $h’$ that is kept in $E$ until time $t-1$ such that $h’(v)=1$. However, $h_t(v)=0$ means that this $h’$ is not in $E$ at time $t$ so it must be removed at time $t-1$. Since we only remove a classifier when a false positive mistake occurs, the number of false negative errors is no larger than the number of false positive errors. \n\n> main idea of Algorithm 3\n\nAlgorithm 3 is a reduction to the Revealed-Adv setting, so its progress is tightly coupled with the progress of the algorithm used in the Revealed-Adv setting (Let A’ be such an algorithm, e.g., Algorithm 1). Specifically, Algorithm 3 calls A’ once every $\\Phi$ mistakes it makes, so every $\\Phi$ mistakes of Algorithm 3 corresponds to a single mistake made by A’. Therefore, if algorithm 3 makes recurring mistakes, then A’ must also be making recurring mistakes in the Revealed-Adv setting. However, this contradicts with the mistake bound for A’ (e.g., Corollary 3.2). Therefore, such “instability” cannot persist, and Algorithm 3 ends up having a finite mistake bound.", "claims_and_evidence": "The paper is fully theoretical. I did not read the appendix with the proofs, but from glancing, it seems like the resulted are well established.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I did not.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "The paper contributes to the line of work on strategic classification, and particularly to studying the question regarding the implications of not revealing the deployed predictors to agents. The paper follows a line of work modelling possible manipulations as graphs.", "essential_references_not_discussed": "In the context of revealing predictors to agents, one line of work that I think is relevant to mention is on providing explanations to agents instead of revealing the predictor (e.g. Counterfactual Explanations, Tsirtsis and Rodriguez 2020), where the agents are given a suggested point to manipulate to, and the prediction at that new point. It is important to point out that there are alternative actionable signals that can be provided to agents to induce strategic modification, and the choice is not only between revealing a predictor or obscuring it (and even if a predictor is revealed and is of high complexity, a common agent may find it difficult to even calculate their best response). I believe the authors should include such a discussion in relevant previous work.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is very well written, I enjoyed reading it.\n\n2. The approaches for solving the main problem in this work are original, creative, and I found the reduction approach in the paper interesting.\n\n3. The problem of whether classifiers should be revealed in strategic settings is central, and clearly motivated.\n\n\n\nWeakness:\nI am slightly concerned regarding the significance of obtained results, due to the following points:\n\n1. In the scenario of the paper, there is strong reason to believe that a decision maker who does not want to reveal their current model, would not want to reveal past deployed policies (e.g. there might be many similarities, and the developed predictors may be proprietary and allow the decision maker to maintain competitive edge).\n\n2. The scenario of adversarial manipulation, in which agents may still manipulate to different points even if they do not benefit from such action seems to be rather unnatural (especially that usually such manipulations have cost/effort for agents). To my understanding, the lower bounds in Theorems 3.3, 4.4 strongly rely on this assumption.\n\n3. The realizability assumption in the basis of this work (while maybe necessary to allow for the analysis) is rather restrictive.\n\n4. There are alternatives to revealing the model in inducing agent responses, which may aid to circumvent the tensions between the two extremes (see more in essential references section).", "other_comments_or_suggestions": "Algorithm 3 should appear in the main text. I understand that there are space limitations, however it is central to this work and should be included.", "questions_for_authors": "1. Why did you opt to study the problem under the additional (and largely unnatural in a strategic agents context) assumption of adversarial manipulations? Have you considered the non-adversarial + unrevealed classifier case?\n\n2. In line 340, you state \"a false negative mistake can occur only if a false positive mistake happened in the previous round\". Can you explain why this is the case?\n\n3. Regarding Algorithm 3 (described in the paragraph starting in line 361) --- why can't there be instability in the classification where there are recurring mistakes but still inability to make progress according to the described scheme? The argument is probably formalized in the appendix, but I am wondering about the main ideas in the proof.", "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": "", "extra_scores": {}}, {"review_id": "BKGhGDmxun", "reviewer": "Reviewer_q9sy", "summary": "This paper studies how hiding the classifier from the agents affects the performance of strategic classification. The result shows that hiding the classifier from the agents significantly increase the number of mistakes the decision maker would make, in proportion to the maximum in-degree of the manipulation graph. The paper proposed two algorithms for strategic learning with adversarial and $\\gamma$-weighted agents and calculated the upper bound on the number of mistakes each algorithm makes. The authors also provided special examples where the upper bound is attained.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for the thoughtful comments and for examining our proofs. We address them below.\n\n> infinite/continuous feature space\n\nFirst, we would like to clarify that our model does not require the feature or action space to be finite: one can define a generic manipulation graph structure over any (potentially infinite or continuous) feature space by treating features as vertices and defining edges as possible manipulations. However, the *learnability* of an instance — in both our work and prior works [Ahmadi et al, 2023, 2024; Cohen et al, 2024] — relies on the finiteness of the *maximum degree* of the manipulation graph.  Without the finite degree assumption, learning in infinite graphs is generally intractable. This has also been noticed by prior work eg [Shao et al, NeurIPS 2023, “Strategic Classification under Unknown Personalized Manipulation”], which shows that when the feature space is continuous and agents can manipulate to any point within a ball around the initial features, mistake bounds are usually $\\Omega(|H|)$.\n\nSecond, we would like to remark that when the feature space is continuous but satisfies certain smoothness conditions, it is often possible to discretize the space and then construct a finite manipulation graph on a covering net. Our results then apply to this discretized finite graph.", "claims_and_evidence": "The central claim is hiding classifiers would increase the number of mistakes of the decision maker. This is well supported by the reduction from the $\\gamma$-weighted version to the adversarial agents. Every claims are soundly supported by theoretical construction and proofs.", "methods_and_evaluation_criteria": "The key methodology is to reduce the target situation ($\\gamma$-weighted case) to the adversarial setting and derived bounds of the latter based on Littlestone dimensions. The method is innovative and appropriate. The evaluatoin metric is the number of mistakes the decision maker made throughout the interaction process. The evaluatoin metrics is reasonable and has well-documented benchmarks.", "theoretical_claims": "I checked all theorems and lemma except Observation 5.2. The theoretical results are correct as far as I can tell.", "experimental_designs_or_analyses": "The paper is purely theoretical, relying on algorithms and constructed examples (e.g., Figure 1 and 2).", "relation_to_broader_scientific_literature": "The work extends the strategic classification framework to non-transparent settings. While it’s commonly assumed and argued that revealing classifiers to agents is reasonable and practical, rigorous theoretical studies on its benefits are scarce. This work fills this gap in the literature.\n\nThe model introduced in this work, which incorporates discounted agent memory and adversarial tie-breaking, is novel in my understanding.\n\nSection 5 connects the work to repeated Stackelberg games with learning agents. The authors thoroughly discuss the challenges of adapting the current model to the learning agent problem and provide insights into the implications of the findings in this context.", "essential_references_not_discussed": "Not recognized.", "other_strengths_and_weaknesses": "The most important innovation of this paper lies in the idea of connecting the target setting ($\\gamma$-weighted) agents to the adversarial agents. The paper contributes to the strategic classification community by theoretically supporting the commonly adopted assumption that hiding classifiers to the agents does not benefits the decision maker.\n\nThe weakness could be in the limitations of the action space where in usual cases agents may have access to an infinite or even continuous action space.", "other_comments_or_suggestions": "No.", "questions_for_authors": "No.", "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": "", "extra_scores": {}}, {"review_id": "HWiUMtq3oV", "reviewer": "Reviewer_MqF7", "summary": "This work considers a strategic online classification setting. At each round $t$, the learner selects classifier $h_t : \\mathcal{X} \\in \\{0,1\\}$ and an agent with true feature $x_t \\in \\mathcal{X}$ and label $y_t \\in \\{0,1\\}$ selects a manipulated feature $v_t \\in \\mathcal{X}$. After the round, $v_t$ and $y_t$ are revealed to the learner. This work supposes that the agent selects $v_t$ among the out-neighbors of $x_t$ in a directed graph, in order to maximize $\\tilde{h}_t(v_t)$, where $\\tilde{h}_t : \\mathcal{X} \\to [0,1]$ is a guess for $h_t$. Previous work examined this problem thoroughly when $\\tilde{h}_t = h_t$ and the agent breaks ties favorably. This work considers the setting where $h_t$ is not revealed until after round $t$, and the learner uses a weighted sum of previous classifiers, according to a discount factor $\\gamma$. Under a standard realizability assumption, they design new algorithms and upper bound the number of mistakes made by the learner, accompanied with constructions lower bounding the number of mistakes by any learning algorithm. When $\\tilde{h}_t = h_t$ but tie-breaking is adversarial, they show that their is already a significant overhead in the mistake bound based on the in-degree of the manipulation graph. In the weighted sum case, there is further overhead according to the agents' time horizon $1/\\log(1/\\gamma)$. This provides a simple strategic learning setting where withholding access to the classifier degrades performance.\n\n## Update after Rebuttal\nI have increased my score to accept based on their clarifications and promised corrections.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We would like to thank the reviewer for the thoughtful comments. We address them below.\n> lower bound statement in Theorem 4.4\n\nThanks for catching the issue in the theorem statement. The lower bound in Theorem 4.4 consists of two parts: $\\min( d/\\log(1/\\gamma), |H|)$ and $d \\cdot k_{\\text{in}} \\cdot k_{\\text{out}}$. The first bound holds for all $\\gamma\\in(0,1)$, and its proof is provided in Appendix B.3. The second bound emphasizes the dependency on maximum in-degree and is established only when $\\gamma\\to0$. Its proof follows from a modified version of that of Theorem 3.3. \n\nWe agree that the theorem statement should be more precise, and will update in revisions to clarify that the second bound is only established in the $\\gamma\\to0$ regime. In the following, we provide more details for this modified proof and will add them to future versions of this paper.\n\nConsider the graph that is the same as that in Figure 2 but all nodes in the first layer (namely $x_1,x_2,\\ldots,x_{k_1}$) are connected by a clique. This modification gives $k_{\\text{out}}=k_1+k_2$ and $k_{\\text{in}}=k_2$. \n\nFor $\\gamma\\to0$, best responding to $\\tilde{h}^\\gamma_t$ is equivalent to best responding to $h_{t-1}$. Now, we perform a case discussion of both $h_{t-1}$ — which the agent $x_t$ best responds to — and the current classifier $h_t$. We will construct an adversary that induces at least one mistake in every two rounds in the first $2k_1k_2$ rounds. Now we assume that the learner does not make a mistake at round $t-1$ and show how to induce a mistake in round $t$.\n\n* Case 1: If $h_{t-1}$ labels $x_0$ by positive. Then if $h_t(x_0)=1$, the adversary picks $(x_t,y_t)=(x_0,0)$ and induces a false positive mistake. If $h_t(x_0)=0$, then the adversary picks $(x_t,y_t)=(x_{i^*},1)$, which manipulates to $x_0$ and induces a false negative mistake while revealing no information. These correspond to cases 1 and 2 of the proof of Theorem 3.3.\n\n* Case 2: If $h_t$ labels any leaf node $x_{i,j}$ as positive, then the adversary picks $(x_t,y_t)=(x_{i,j},0)$. This induces a false positive mistake and removes one hypothesis. Since the learner made no mistake in round $t-1$, we can assume that $h_{t-1}$ labels all leaf nodes as negative. This case corresponds to case 4 of Theorem 3.3.\n\n* Case 3: We are left with the case where $h_{t-1}$ labels $x_0$ and all leaf nodes as negative. Due to adversarial tie-breaking and the added clique, we can assume that all nodes in $\\{x_0,x_1,\\ldots,x_{k_1}\\}$ manipulates to the same node $x_i$ in response to $h_{t-1}$. If $h_t(x_i)=1$, then the adversary can choose $(x_t,y_t)=(x_0,0)$ and induce a false positive mistake. If $h_t(x_i)=0$, then the adversary chooses $(x_t,y_t)=(x_{i^*},1)$ and induces a false negative mistake while revealing no information about $i^*$. This case is a modification of case 3 of Theorem 3.3 that accounts for historical best response.\n\nWe will correct this in the paper.\n\n> the phrase \"With probability at least 1/3”\n\nWe allow agents to best respond to the weighted average classifier with adversarially tie-breaking in this setting and we focus on adversarially choosing the specific $x_t$ at each time. Instead of finding the worst instance among all possible cases, it is enough to show our desired instance can happen with $\\Theta(1)$ probability.\n\n> agents arrive stochastically\n\nSince we focus on mistake bounds in the realizable setting, they cannot be reduced to the VC dimension in the stochastic setting, even in standard online learning without strategic behavior. However, for regret bounds in the agnostic setting, such a reduction is possible. We believe it would be interesting to explore regret bounds in the agnostic setting, both when the classifier is revealed and when it is not. \n\n> application of Algorithm 1\n\nAlgorithm 1 has two main components: the weighted voting of experts and the choice of threshold/updating mechanism of experts. The high-level idea of weighted expert voting is fundamental and has been widely applied in many settings. Choosing a biased threshold that favors false positives is useful in scenarios where false positives and false negatives carry different amounts of information about the true hypothesis.\n\n> Novelty of our results\n\nWe would like to re-emphasize the technical novelty of our results.\nFirst, as discussed in our response to reviewers WPjm and T9UQ regarding adversarial tie-breaking, we show that when agents only observe a perturbed version of the current predictor $h_t$—rather than the exact $h_t$—the mistake bound increases by a factor of $k_\\text{in}$ (see Corollary 3.2 and Theorem 3.3).\n\nSecond, in the weighted sum of history case, as the reviewer pointed out, $1/\\log(1/\\gamma)$ can be seen as the effective memory length of the agent. One interesting implication of this lower bound is that, in the worst case, the agent may need to “forget” its entire history—incurring $\\Omega(1/\\log(1/\\gamma))$ mistakes—before it can make correct decisions again.", "claims_and_evidence": "Yes, this is a theoretical paper and (almost) all of the results have proofs which appear sound. The only piece I slightly struggled with was the proof of Theorem 4.4. There is one piece of their claim which I don't think is properly treated by the proof and one typo in the statement (I think). For the rest of the proof, I can follow the line-by-line arguments but I think a better proof overview would be helpful, since this result is key to the paper's thesis. The bound is somewhat natural, since $1/\\log(1/\\gamma)$ is roughly the effective memory length of the agents, so I would be surprised if there was any major issue.\n\nI feel confident vouching for correctness of the other results, whose proofs I found pretty clear.\n\nI am willing to raise my score if the authors address my concerns with Theorem 4.4.", "methods_and_evaluation_criteria": "n/a", "theoretical_claims": "Yes, I read through all of the proofs, as mentioned above. For Theorem 4.4, I had two comments. First, shouldn't $k_\\mathrm{out}$ appear in the LB? I think this is just a typo. Second, I don't see why taking $\\gamma \\to 0$ is okay for the first part of the proof. The theorem was claimed to hold for each fixed $\\gamma$ and it seems non-trivial to extend the LB in Theorem 3.3 when $\\gamma$ is bounded away from 0.", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "There is a fair amount of literature on strategic classification, which is discussed in the related work. Their results shine some light on the importance of tie-breaking assumptions made in previous works for the online setting where $\\tilde{h}_t = h_t$. The extension they consider to the weighted average case is a pretty natural one. I don't think it is that surprising that their agents with memory are harder to learn against, but it is good to establish.", "essential_references_not_discussed": "Nothing comes to mind.", "other_strengths_and_weaknesses": "I actually think the technical contributions with respect to tie-breaking are more interesting than that of revealing the classifier, which the paper is framed around. In particular, the $k_\\mathrm{in}$ dependence seems to be due to the tie-breaking choice rather than not revealing the classifier. The dependence on $1/\\log(1/\\gamma)$ is much less surprising to me.\n\nThe realizability assumption is rather strong, and these results would definitely be more compelling without it. This is an open problem even when classifiers are revealed immediately though, so I don't hold that against the authors.", "other_comments_or_suggestions": "For me, it feels a bit more intuitive to imagine the agent maintaining a distribution over classifiers and manipulating their feature to maximize the probability of a positive label. This of course coincides with taking a weighted sum over classifiers though, so there is no issue.\n\nI didn't understand the phrase \"With probability at least 1/3, the agent will stay at xi,B because it is one of the best candidates.\" on page 15. Isn't the agent's choice up to us in this LB construction? I.e. we can have this occur all of the time. In any case, I don't think this point affects the result, but I want to make sure I'm not misunderstanding something.\n\nThis is a small nit, but I prefer using $(1-\\gamma)^{-1}$ instead of $1 + 1/\\log(1/\\gamma)$. These are equivalent up to constant factors and the former is commonly used for effective time horizons in RL. I think it's worth noting somewhere.\n\nDouble parentheses in last citation on page 2", "questions_for_authors": "What does this setting look like if the agents arrive stochastically? Can the Littlestone dimension can be reduced to a VC dimension?\n\nAlgorithm 1 seems pretty generic and I could imagine the same idea being useful in other settings. Have you thought about any other applications / has any similar idea appeared in the literature?", "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": "", "extra_scores": {}}, {"review_id": "nWyliSCVF9", "reviewer": "Reviewer_T9UQ", "summary": "This paper mainly proposes regret bounds for online strategic classification under two novel settings: (i) Revealed-Adv where the agents can still manipulate their feature arbitrarily even when the feature vector after manipulation is still negative. In this case the decision-maker makes $\\Omega(k_{in})$ times more mistakes; (ii) agents do not know current policy $h_t$. Instead, they best respond to an exponential average of previous classifiers. In this case, an additional $\\frac{1}{log(1/\\gamma)}$ portion of mistakes are expected.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your thoughtful comments. We address them below.\n\n> adversarial tie-breaking\n\nWe appreciate the reviewer’s concern and want to clarify that we do *not* intend to make adversarial tie-breaking a realistic behavioral assumption. Instead, we use it as a conceptual and technical intermediate step toward analyzing the more realistic setting (\\gamma-Weighted) where agents *cannot* observe the currently implemented classifier and instead best respond to an *estimate* of it. As we discussed in Lines 235-251 of our manuscript, in such settings, estimation error can cause the agents to perceive one node as slightly better than the other node, even if the true classifier might assign them the same label. For example, if $\\tilde h(v) = h(v)$ for all $v \\in N_{out}(x)$, but $\\tilde h(x) = h(x) - \\epsilon$, the agent would not remain at $x$, behaving as if they are breaking ties adversarially.\nThe purpose of Theorem 3 is precisely to highlight the mistake bound gap between the case where agents only perceive a perturbed version of the true hypothesis $h$ versus the case where they perceive $h$ perfectly. We treat adversarial tie-breaking as a proxy for incorporating such estimation errors into the mistake bound analysis, which serves as a building block towards the gamma-Weighted setting. \nSecond, our upper bound in Theorem 4.1 holds for both tie-breaking ways. We note that our lower bound in Theorem 4.4 consists of two parts: $\\min(d/\\log(1/\\gamma), |H|)$ and $d \\cdot k_{\\text{in}} \\cdot k_{\\text{out}}$* , where the first part still holds for the standard tie-breaking case with a slight refinement of the proof. The second part will be reduced to $d\\cdot k_{\\text{out}}$ in the standard tie-breaking case. The dependency on $k_{\\text{in}}$ in unrevealed classifier + standard tie-breaking is left as an open problem. \n\n*There is a typo in the original statement of Theorem 4.4, $ k_{\\text{in}}$ should be replaced by $k_{\\text{in}} \\cdot k_{\\text{out}}$.\n\n> finite feature space\n\nFirst, we would like to clarify that our model does not require the feature or action space to be finite: one can define a generic manipulation graph structure over any (potentially infinite or continuous) feature space by treating features as vertices and defining edges as possible manipulations. However, the *learnability* of an instance — in both our work and prior works [Ahmadi et al, 2023, 2024; Cohen et al, 2024] — relies on the finiteness of the *maximum degree* of the manipulation graph.  Without the finite degree assumption, learning in infinite graphs is generally intractable. This has also been noticed by prior work eg [Shao et al, NeurIPS 2023, “Strategic Classification under Unknown Personalized Manipulation”], which shows that when the feature space is continuous and agents can manipulate to any point within a ball around the initial features, mistake bounds are usually $\\Omega(|H|)$.\n\nSecond, we would like to remark that when the feature space is continuous but satisfies certain smoothness conditions, it is often possible to discretize the space and then construct a finite manipulation graph on a covering net. Our results then apply to this discretized finite graph.\n\n\n> realizable setting\n\nOur goal is to study the gap between the setting where the currently implemented hypothesis is revealed and the setting where it is not. The agnostic case remains open in the literature even in the revealed classifiers setting —as also noted by reviewer MqF7. However, we believe that similar ideas as used in Algorithms 1 and 3 can be applied to the agnostic setting too.", "claims_and_evidence": "1. The contribution is very clear and the proposed settings mostly make sense in strategic classification settings;\n2. The theorems are clear, and the explanations linking setting (ii) and (iii) are helpful. The intuitions introduced in Figure 1 is clear;\n3. The theoretical results seem to be intuitively correct.", "methods_and_evaluation_criteria": "This is a purely theoretical work, so there are no evaluations. For methods, Algorithm 1-2 are plausible.", "theoretical_claims": "I only read through proof of Theorem 3.1 - 3.3 which mostly make sense.", "experimental_designs_or_analyses": "There is no experiment.", "relation_to_broader_scientific_literature": "This paper can make a meaningful contribution to the learning bounds of online strategic classification. Specifically, the idea that decision-maker does not reveal classifier and the agents respond to the previous classifiers was proposed recently and the learning bounds are worthwhile researching.", "essential_references_not_discussed": "The paper already discussed related work. In (II) of Section 1.1, there are other literature quite related but not mentioned. For example, [1] studies a setting where agents arrive sequentially and also best respond to previous decision policy instead of the current one, although the authors mainly focused on welfare and fairness; [2] focused on online strategic classification in a continuous setting where the feature can be in $R^d$. \n\n[1] Xie, T., & Zhang, X. (2024). Automating data annotation under strategic human agents: Risks and potential solutions. arXiv preprint arXiv:2405.08027.\n\n[2] Shen, L., Ho-Nguyen, N., Giang-Tran, K. H., & Kılınç-Karzan, F. (2024). Mistake, Manipulation and Margin Guarantees in Online Strategic Classification. arXiv preprint arXiv:2403.18176.", "other_strengths_and_weaknesses": "1. I am unsure about whether the \"adversarial tie-breaking\" is actually practical. In your setting, each feature vector has an $N_{out}$ and there seems to be no cost. However, in classic SC setting, manipulating the feature should incur a cost. This is to say, if there is no utility gain, the agents will never move and this makes sense.\n\n2. The paper assumes a finite and realizable setting. Specifically, it seems that the feature vectors are countable. This may limit practical usage.", "other_comments_or_suggestions": "I think overall the paper is well-written, and my questions are listed above.", "questions_for_authors": "N/A", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies online strategic classification where the learned model is not always revealed to users. The paper establishes interesting theoretical claims regarding outcomes for the decision-maker in terms of the benefits and losses of a transparent policy. Reviewers found the writing to be clear, the contributions clearly stated, and the results to be sound and easy to follow. They also believe that the paper fills a gap in the online setting of strategic classification, and does this well. Some reviewers pointed out the strong assumptions made (e.g., realizability, action space). Several reviewers thought that the paper would benefit from better explaining the rationale for tie-breaking, and even making this point more emphasized in the paper. The authors are encouraged to take these and all other questions and concerns raised by the reviewers and implement them in the next revision.
Decision: Accept (poster)