Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification
Authors: Saba Ahmadi
Kunhe Yang
Hanrui Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: online strategic classification
Littlestone dimension
manipulation graph
Primary area: online_learning

Abstract: We study the problem of online binary classification in settings where strategic agents can modify their observable features to receive a positive classification. We model the set of feasible manipulations by a directed graph over the feature space, and assume the learner only observes the manipulated features instead of the original ones. We introduce the Strategic Littlestone Dimension, a new combinatorial measure that captures the joint complexity of the hypothesis class and the manipulation graph. We demonstrate that it characterizes the instance-optimal mistake bounds for deterministic learning algorithms in the realizable setting. We also achieve improved regret in the agnostic setting by a refined agnostic-to-realizable reduction that accounts for the additional challenge of not observing agents' original features. Finally, we relax the assumption that the learner knows the manipulation graph, instead assuming their knowledge is captured by a family of graphs. We derive regret bounds in both the realizable setting where all agents manipulate according to the same graph within the graph family, and the agnostic setting where the manipulation graphs are chosen adversarially and not consistently modeled by a single graph in the family.

Strategic Littlestone Dimension:
Improved Bounds on Online Strategic Classification"
Saba Ahmadit.", Kunhe Yang*', and Hanrui Zhang
Toyota Technological Institute at Chicago, sabaêttic. edu University of California, Berkeley, kunheyang@berkeley edu Chinese University of Hong Kong, hanrui@cse cuhk. edu. hk
Abstract
We study the problem online binary classification settings where strategic agents modify their observable features to receive positive classification. We model the set of feasible manipulations by a directed graph over the feature space, and assume the learner only observes the manipulated features instead the original ones. We introduce the Strategic Littlstonee Dimension, a new combinatorial measure that captures the joint complexity of the hypothesis class and the manipulation graph. We demonstrate that characterizes the instance- optimal mistake bounds for deterministic learning algorithms the realizable setting. We also achieve improved regret in the agnostic setting by a refined agnostic-to-realizabee reduction that accounts for the additional challenge of not observing agents' original features. Finally, we relax the assumption that the learner knows the manipulation graph, instead assuming their knowledge captured by a family of graphs. We derive regret bounds in both the realizable setting where all agents manipulate according to the same graph within the graph family, and the agnostic setting where the manipulation graphs are chosen adversarially and not consistently modeled by a single graph in the family.
Introduction
Strategic considerations in machine learning have gained significant attention during the past decades. When MI. algorithms are used to assist decisions that affect a strategic entity (e.g., a person, a company, or an LLM agent), this entity henceforth the agent naturally attempts game the ML algorithms into making decisions that better serve the agent's 's goals, which in many cases differ from the decision maker's. s. Examples include loan applicants optimizing their credit score without actually improving their financial situation It is therefore desirable, if not imperative, that the MI. algorithms used for decision-making be robust against such strategic manipulation.
Indeed, extensive effort has been made towards designing ML algorithms the presence of strategic behavior, shaping the research area of strategic machine learning [Brückner and Scheffer 201 Hardt et al. 2016). In particular, powerful frameworks have been proposed for offline environments, where the decision maker has access to historical data, which they train model that is subsequently used to make decisions about (i.c., to classify) members of a static population. These frameworks provide almost optimal Icarnability results and sample complexity bounds for strategic machine learning in offline environments, which gracefully generalize their non-strategic counterparts (see, e.g., (Zhang
and Conitzer 2021 Sundaram al. 2023
"Authors are ordered alphabetically.
"The following article (among others) discusses some well-known tricks for this: https://wwi
nerdwallet. wwt.///attttee/attttooteteceeeee weweceeerrreeeeeeeee credit- prreditssooree score- fast
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

However, the situation becomes subtler in online environments, where the decision maker has little or no prior knowledge about the population being classified, and must constantly adjust the decision-making policy (i.e., the classifier) through trial and error. This is particularly challenging in the presence of strategic behavior, because often the decision maker can only observe the agent's features after manipulation. In such online environments, the performance of a learning algorithm is often measured by its regret, i.c., how many more mistakes it makes compared to the best classifier within certain family in hindsight. For online strategic classification, while progress has been made in understanding the optimal regret in several important special cases, a full instance-wise characterization has been missing, even in the seemingly basic realizable setting (meaning that there always exists a perfect classifier in hindsight). This salient gap is the starting point of our investigation in this paper which turns out to reach quite a bit beyond the gap itself.
Following prior work (Ahmadi et al. 2023 Cohen et al. 2024 we study the following standard and general model of online strategic classification: we have (possibly infinite) feature space, equipped with a manipulation graph deñned over it. An edge between two feature vectors æ1 and 222 means that agent whose true features are Iı can pretend to have features 22, and in fact, the agent would have incentives to do so if the label assigned to 22 by the classifier is better than that assigned to the true features TT. At each time step, the decision maker commits to a classifier (which may depend on observations from previous interactions), and an agent arrives and observes the classifier. The agent then responds to the classifier by reporting (possibly nontruthfully) a feature vector that leads to the most desirable label subject to the manipulation graph, i.c., the reported feature vector must be a neighbor of the agent's 's true feature vector. The decision maker then observes the reported feature vector, as well as whether the label assigned to that feature vector matches the agent's 'ss true label.
1.1 Our Results and Techniques
An instance-optimal regret bound through the strategic Littlestone dimension. Our first main finding is an instance-optimal regret bound for online strategic classification in the realizable setting, when randomization is not allowed (we will discuss the role of randomization in Section In this setting, there is a predefined hypothesis class of classifiers, in which there must exist one classifier that assigns all agents their true labels under manipulation. The decision maker, knowing that a perfect classifier exists in this class, tries to learn it on the fly while making as few mistakes as possible in the process. Naturally, the richer this hypothesis class is, the harder the decision maker's 's task will be (e.g., one extreme is when the hypothesis class contains only one classifier, and the decision maker knows a priori that that classifier must be perfectly correct, and the optimal regret is 0). Thus, the optimal regret must depend on the richness of the hypothesis class. Similarly, one can imagine that the optimal regret must also depend on the mani graph.
Previous work (Ahmadi et al. 2023, Cohen et al. 2024 has established regret bounds for this setting based on various complexity measures of the hypothesis class and the manipulation graph, including the size and the (classical) Littlestone dimension [Littlstonne 1988) of the hypothesis class, as well as the maximum out-degree of the manipulation graph. However, the optimality (when applicable) of these bounds only holds under the assumption that the mistake bound must be parametrized as function on the classical Littlestone dimension and/or the graph's 's out-degree. However, these bounds are not tight for all instances, as there exist problem instances that are learnable where all these parameters are infinite.
To address the above issue, we introduce a new combinatorial complexity measure that generalizes the classical Littlestone dimension into strategic settings. Conceptually, the new notion also builds on the idea of "shattered trees", which has proved extremely useful in classical settings. However, the asymmetry introduced by strategic behavior demands a much more delicate construction of shattered trees (among other intriguing implications to be discussed in Section B) We show that the generalized Littlestone dimension captures precisely the optimal regret of any deterministic learning algorithm given a particular hypothesis class and manipulation graph, thereby providing complete characterization of learnability in this setting. Being instance-optimal, our bound strengthens and unifies all previous bounds for online strategic classification in the realizable setting.
Eggg, unlike in classical (non -ton-strategic) settings, true positive does not carry the same information as a false negative in our setting.
2

---

An improved regret bound for the agnostic case. We then proceed to the agnostic setting, where no hypothesis necessarily assigns correct labels all agents. The regret is defined with respect the best hypothesis in hindsight. Compared to the classical (i.e., non-strategic) setting, the main challenge incomplete information: since the learner cannot observe original features, upon observing the behavior of an agent under one classifier, it is not always possible to counterfactually infer what would have been observed if the learner used another classifier.
To understand why this can be a major obstacle, recall some high-level ideas behind the algorithms for classical agnostic online classification (see, e.g., (Ben-David et al., 2009]). The key is to construct a finite set of "representative" experts out of the potentially infinite set of hypotheses, such that the best expert performs almost as well as the best hypothesis in hindsight. An agnostic learner then runs a no-regret learning algorithm (such as multiplicative weights) on the expert set, which in the long run matches the performance of the best expert, and in turn of the best hypothesis.
The partial information challenge appears in both steps of the above approach. First, to construct the set of representative experts, the learner needs to simulate the observation received by each hypothesis, had that hypothesis been used to label the strategic agents. Second, the no-regret algorithm on the expert set also needs to counterfacurally infer the agent's response to each expert. To circumvent both issues, we design a nuanced construction of the representative set of experts that effectively "guesses" each potential direction of the agent's 's manipulation. We then run the biased voting approach introduced in [Ahmadi et al.) [023] on the finite set of experts, which enjoys regret guarantees in the strategic setting even with partial information. Combined with our regret bound for the realizable setting, this approach yields an improved bound for the agnostic setting.
Learning with unknown manipulation graphs. Our last result focuses on relaxing the assumption that the learner has perfect knowledge about the manipulation graph structure. Instead, following previous works (Lechner et al. 2023 Cohen et al. 2024], we model their knowledge about the manipulation graph using a pre- rre-nee graph class, which to some degree reflects the true set of feasible manipulations. In this setting, our work is the first that provides positive results when the learner only observes features after manipulation. We start with the realizable setting where the manipulation graphs are consistently modeled by the same (unknown) graph in the class. In this setting, we provide more careful construction of the representative experts to account for the additional challenge of unknown graphs. Combing this construction with re-examining the effectiveness of the biased voting approach [Ahmaadi et al. 2023] when the input graph a overly- conservative estimate of the true graph, we obtain the first regret bound in this setting that is approximately optimal (up to logarithmic factors) in certain instances. We also extend our results to fully agnostic settings where the agents in each round manipulates according to a potentially different graph, and the best graph in the class has nonzero error in modeling all the manipulations.
1.2 Further Related Work
There a growing line of research that studies learning from data provided by strategic agents (Dalvi ct al. 2004 Dekel et al. 2008 Brückner and Schetfer 201T). The seminal work of Hardt et al. [2016] introduced the problem of strategic classification as a repeated game between a mechanism designer that deploys a classifier and an agent that best responds to the classifier by modifying their features at cost. Follow-up work studied different variations of this model, an online learning setting (Dong et al.) 2018 Chen et al.] 2020 Ahmadi et al., [021]. incentivizing agents to take improvement actions rather than gaming actions [Kleinberg and Raghavan 2020 Haghtalab et al.
2020
Alon et al. 2020 Ahmadi et al., 2022], causal learning [Bechavod et al. 202 Perdomo et al.
2020
screening processes [Cohen et al. 2023), fairness
[Hu ct al. 2019), etc.
Two different models for capturing the set of plausible manipulations have been considered in the literature. The first one a geometric model, where the agent's best-response to the mechanism designer's deployed classifier is a state within a bounded distance (with respect to some E, norm) from the original state, i.e. feature set (Dong et al.) 2018 Chen et al., 20200 [Shao et af.) [204 Sundaram et al., 2023 Ghalme et al.) 2021 Haghtalab et al.) 2020]. In the second model, introduced by Zhhan and Conitzer [002]] there combinatorial structure, i.e. manipulation graph, that captures the agent's ss set of plausible manipulations. This model has been studied in both offline PAC
learning [Lechner and Urner 2022 Zhang and Conitzer 2021 Lechner et al. 2023] and online
settings (Ahmadi et al. 2023 In recent work, Lechner et al. 2023 consider this problem in an
3

---

offline setting where the underlying manipulation is unknown and belongs to known family of graphs. Our work improves the results given by [Ahmadi et al. 2023] the online setting and also extends their results to the setting where the underlying manipulation is unknown and belongs to known family of graphs.
Our work is also closely related to that of Cohen et al. [2024), with two main points of distinction. First, in the realizable setting, their bound shown be optimal for a specific instance, whereas our bound is instance-wise optimal. Second, in both the agnostic and the unknown graph settings, they assume that agents' original features are observable before the learner makes decisions, whereas our algorithm only requires access to post-manipulation features.
Finally, our work is also tangentially connected to several recent advances in understanding multi- class classification under bandit feedback, e.g., [Raman et al. 2024 Filmus et al. 2024). as the false-positive mistake types can be treated as mulriple labels at very abstract level. However, an additional challenge in the strategic setting is that the learner needs to choose a classifier without observing the original instance to be labeled.
2 Model and Preliminaries
2.1 Strategic classification.
Let X' be a space of feature vectors, y' (-1,1) be the binary label space, and H X' - > be hypothesis class that is known to the learner (also referred to as "decision-makers", X. In the strategic classification setting, agents prefer positive labels over negative labels, and they may manipulate their features within a predefined range to receive a positive label. We use the manipulation graphs introduced by [Zhang and Conitzer 2021] Lechner and Urner 2022] model the set of feasible manipulations. The manipulation graph G(X,&) E) is a directed graph in which each node corresponds to a feature vector in X, and each edge (11, E & C X2 represents that an agent with initial feature vector æ1 can modify their feature vector 222 For each E X, use N (I:) denote the set of out-neighbors of x in G, excluding x itself, and N [x] denote the out-neighbors including x. Formally, N (1r) {a' E X {a) (xr,z')= E E) and N [x] [=) N (ar). Similarly, we use No and N [a] to denote respectively the exclusive and inclusive in in-neigbborhood of x.
Agents' utility and the manipulation rule. fier h E y², an agent with initial features E X aims to maximize their utility by potentially manipulating their features to a different x'. The agent's 's utility function utila, (2, x') is defined as
Given a manipulation graph G(X, E) and a classi-
uti (x,, x²) M(x') 0o 1 ( E E)
where the agent's utility the classification outcome (xx') minus the manipulation cost associated with changing features from x to x'. For the classification outcome, agents receive utility +1 if the classifier h labels x' as positive and -I otherwise. For the manipulation cost, moving from to x' incurs no cost if the two features are connected by an edge in G, but when x and x' are not connected (i.e., (x. x²) & E), the manipulation incurs an infinite cost, effectively making such a manipulation infeasible. As result, an agent with initial features x would move to some x' in the inclusive neighborhood N [x] that labeled as positive by h, if such a node exists.
Formally, the set of best response features from x, denoted by BRG. (x), ), is defined as
BRG,(()) A {a' (till,, = +1) = [x] n {a M(x)) = +1}.
If, however, the set (z) is empty - indicating that the entire out-neigbborhood N [a] is labeled as negative by h - then the agent is assumed to not manipulate their features and remain at x. In addition, when there are multiple nodes in BRG (I), the agent may select any node arbitrarily. We do not require the selection be consistent across rounds results specifically focus on the learner's 's mistakes against worst-case (adversarial) selections by the agent Finally, the manipulated feature vector is denoted by br (2x)
follow pre-specified rule. Our
*Some previous works, such as AAhmddi et al. 2023 Cohen et al. 2024], assume that agents will not manipulate their features if & E (z). While this assumption enforces consistency in the special case of h(2))= = 1, we remark that most algorithms proposed by both papers remain effective even without this assumption.

---

The labels induced by the manipulated feature vectors (x) are captured by effective classifiers hi, formally defined
+1, 3f NG s.t. h(v) +1;
(x) A h(bra,
11-11,1 -1, otherwise.
Online learning. We consider an online strategic classification setting modeled as repeated game between the learner (aka the decision maker) and an adversary over T rounds, where the learner make decisions according to an online learning algorithm A. At each round t E [T]. the learner first commits the classifier h4 y (not necessarily restricted H) that is generated by .4 The adversary then selects an agent (ate, Ut) where I22 E X' is the original feature vector and ye E ) is the true label. response to hę, the agent manipulates their features from 2t to 04- bra, (2+)). Consequently, the learner observes the manipulated features 2 (instead of zz), and incurs a mistake y/ + 11 (we). We use = (I,, 3/ Me)ee to denote the sequence of agents.
The learner aims to minimize the Stackelberg regret on S with respect to the optimal hypothesis h" E H. had the agents responded to h*:
R H. G) A EiT, ( (Ix)) + yo3 mink EH Et=1 ( (zz)) + yr
We call a sequence realizable with respect to H the optimal-in-hindsight hypothesis h H achieves zero mistakes on S. Specifically, this means that for all (I,, ) in the sequence S, we have y/ ht (bro, (z.)) (2.). In such cases, the learner's regret coincides with the number of mis- takes made. We use Mistake (H. G) to denote the maximal number of mistakes that A makes against any realizable sequence with respect class H. and graph G. A deterministic algorithm is called min- max optimal or instance-optime if achieves the minimal Mistake, (7H, G) across all deterministic algorithms
We denote this optimal mistake bound by M(H, G) & inf A deterministic Mistake G).
2.2 Classical Littlestone Dimension
In this section, we revisit the classical online binary classification setting where the agents are unable to strategically manipulate their features. This setting can be viewed as special case of strategic classification where the manipulation graph G consists solely of isolated nodes. We will introduce the characterization of the optimal mistake in this classical setting - known as the Litrlestone Dimension which inspires our analysis in the strategic setting.
Definition 2.1 (H-Shattered Littlestone Tree). A Littlestone tree shuftered by hypothesis class H of depth d is a binary tree where:
(Structure) Nodes are labeled by X' and each non-leaf node has exactly two outgoing edges that are labeled by +1 and 11, respectively.
(Consistency) For every root-to-leat toll-fo path x1 Vi, 22 wi, ..... .. yd node and each yt is the edge connecting It and I1+1. there exists hypothesis h E H. that is consistent with the entire path, i.e., Vt S d, h(æ;) yb-
xs+1 where æ1 is the root
The above tree structure intuitively models adversary's 's strategy to maximize the learner's mistakes, where each node 2₁ represents the unlabeled instance to be presented to the learner, and y/ represents the type of mistake (cither false positive or a false negative) that the adversary aims to induce. For example, if the learner predicts the label of Ie to be Di = +1, then the adversary will declare Vi 1, enforce false positive mistake, and choose the next instance Fı-1 the children of the current node along the -1 edge. In addition, the consistency requirement guarantees that the resulting input sequence is realizable by some classifier in H.
Definition 2.2 (Littlestone Dimension). The Littlestone dimension of class H. denoted as Ldim(H), the maximum integer d such that there exists an H-shattered Littlestone of depth d.
The interpretation of the true structure immediately implies that the mistake of any algorithm should be lower bounded by Ldim(H). Moreover, seminal result by Littlestone [1988] also showed that an online learning algorithm known as the Standard Optimal Algorithm (SOA, see Algorithm 2
In this paper, we mainly consider deterministic algorithms. We will discuss the role of randomness in Section Gand Appendix E
5

---

Appendix A) can achieve this lower bound. Together, they form a complete characterization of the optimal mistake bound in the classical setting, which we summarize in the following proposition.
Proposition 2.1 (Optimal Mistake Bound [Littlestone, 1988). ) Let MMH) be the optimal mistake in the classical online learning setting, then M(H) Ldim(H) (-).
In the next section, we will discuss the challenges of extending Littlestone's characterization the strategic setting, and present our solution.
3 The Strategic Littlestone Dimension
In this section, we will introduce combinatorial dimension called the Strategic Littlestone Di- mension, and show that it characterizes the minmax optimal mistake bound for strategic classification.
Inspired by the classical Littlestone dimension, we hope to use a tree structure to model an ad adversary's s strategy for selecting agents (z,, where nodes serve as (proxies of) the initial feature vector of each agent, and edges represent the types of mistakes that the adversary can induce. However, since agents can strategically manipulate their features, the potential mistakes associated with the same initial feature vector could manifest in many more types depending on the learner's s choice of classifiers. Specifically, let x be the initial feature vector. Then a mistake associated with x might be observed as a false negative mistake at node x (denoted as (ar, +1) where is the observable node and +1 is the true label), or as a false positive mistake at any outgoing neighbor u of æ (denoted as (1) accordingly). Therefore, adversary's 's strategy should accommodate all such possibilities, which necessitates the strategic Littlestone tree to contain branches representing all potential mistake types.
Another challenge is caused by the mismatch of the information available to the learner and the adversary. Since the learner only observes manipulated features instead of the true ones, the amounts of information carried by false positive and false negative mistakes are inherently asymmetric. False negatives provide full-information feedback as the manipulated and original features are identical. However, false positives introduce uncertainty about the original features, which could potentially be any in-neighbor of the observed one. As result, a hypothesis is deemed "consistent" with false positive observation as long as can correctly label any one of the potential original nodes.
Now we formally introduce the strategic Littlestone tree with adapted branching and consistency rules tailored for strategic classification. See Figure for pictorial illustration.
Definition 3.1 (H-Shattered Strategic Littlestone Tree). A Strategic Littlestone tree for hypothesis class H under graph G with depth is a tree where:
(Structure) Nodes are labeled by X. The set of outgoing edges from each non-leaf node x are: one false negative edge (x, +1), and a set of false positive edges {(v. -1) E [z]]]
(Consistency) For every root-to-leaf path x (ur,en), z/1 (122292) ...I'' [va.wa),, 2'st1 where x¹ is the root node and (t) E X x {+1} is the edge that connects I' and T there exists a hypothesis h E H. that is consistent with the entire path. Specifically, Vt < d. Ex, s.t. hz(z,)) = Vt. where I; satisfies I, = e if yr = +1, and z, E NN, if = -1.
Definition 3.2 (Strategic Littlestone Dimension). The Strategic Littlestone Dimension of hypothesis class H under graph G, denoted with SLdim H. G), is defined as the largest nonnegative integer d for which there exists Strategic Littlestone tree of depth d shattered by H under graph G.
Theorem 3.1 (Minmax optimal mistake for strategic classification). For any hypotheses class H and manipulation graph G. the minmax optimal mistake in the realizable setting is captured by the strategic Littlesoone dimension, i.e,, M(H G) SLdim G).
We divide the proof of Theorem 3.1 into two parts: the lower bound direction is established in Theorem 3.2, and the upper bound direction is established in Theorem 3.3
Theorem 3.2 (Lower bound part of T..1rem(3.]]. For any pair of hypothesis class H and manipula- tion graph G, any deterministic online learning algorithm A must suffer mistake lower bound of Mistake (H, G) Z SP, G).
Let be a strategic Littlesoone tree for (H, G) with depth d. We will show that for any deterministic algorithm A, there exists an adversarial sequence of agents
Proof sketch of Theorem 3.2

---

(1t 30
A Strategic Littlestone Tree with depth 2. False negative edges are marked red, whereas false positive edges are marked blue. The highlighted path zí [u1-91),, 2/2 (u2.w2), z' an example root-to-lcaf path. this path, the first observation (v1, Vi is a false positive, which satisfies 21 E N [z]] and y11 = 1; the second observation (12, ya) is false negative, which satisfies = 2//2 and y2 +1.
Figure I:
S = (Ze, Ve) such that A is forced to make mistake at every round. We construct the sequence
by first finding path 21 (m1-ar)) 2/2 (12-wa),, ...2% (96.80) d'a+1 in tree T which specifies the types of mistakes that the adversary wishes to induce, then reverse-engineeringg this path to obtain the sequence of initial feature vectors before manipulation that is realizable under H. We remark that the need for reverse-engineering is unique to the strategic setting, which is essential in resolving the information asymmetry between the learner and the adversary regarding the true features. We formally prove this theorem in Appendix B.1
In the remainder of this section, we present an algorithm called the Strategic Standard Optimal Algorithm (SSOA) that achieves the instance-optimal mistake bound of (H, G). We first define some notations. For any hypothesis sub-class FF C H and an observable labeled instance (v, E X x y, we use F( to denote the subset of F that is consistent with (v, y) under manipulation graph G. We refer to the consistency rule defined in Definition 3.1 i.e., for all X, F ((,+11) and ((.-1) are defined respectively as:
G
FG (1,+1) (h E F (T(()) +1};
A (1 ( -
3x E N [u] s.t. (x(()) -1}.
We present SSOA Algorithm [ and prove its optimality Theorem 3.3 The high-level idea of SSOA is similar to the classical SOA algorithm (Algorithm 2) it maintains version space of classifiers consistent with the history, and chooses a classifier he in a way that guarantees the "progress on mistakes" property. This means that the (strategic) Littlestone dimension of the version space should decrease whenever a mistake is made.
However, designing h, to satisfy this property in strategic setting is more challenging because the potential types of mistakes depend on h 's labeling in the neighborhood N [ay], where x; is unobservable. we directly optimize the labelings on N [x]] for each independently, the resulting classifier may suggest self-contradictrry labelings to the nodes the overlapping parts of N [x] and N [x') for different and x'. Instead, the learner needs to choose a single h, that simultaneously guarantecs the "progress mistakes" property for all possible x; and their neighborhoods.
In the following, we will show that this challenge can be resolved by choosing classifier he that labels each node only based on whether a false positive observation (x, -1) can decrease the strategic Littlestone dimension, as described Line 3 of Algorithm
Theorem 3.3 (Upper bound part of Theorem 3.1 The SSOA algorithm (Algorithm 7 achieves a maximal mistake bound of Mistakessoa (H, GJ SLdim(H, G).
Remark 3.4 (Comparison with previous results). Since the mistake bound of SSOA shown to be instance-optimal across all deterministic algorithms, it improves upon the bounds established by Ahmadi et al.) (2023), [ooen el al.) (2024), which both depend on the maximun out-degree of the graph G. Furthermore, we show in Appendix B.2 that the gap between their bounds and ours could be arbitrarily large. An extreme example is the complete graph G supported on an unbounded domain, where SLdim G) = but both previous bounds are oc.
suffices to prove that if SSOA makes a mistake at round I, then the strategic Littlestone dimension of version space H. (maintained by the SSOA algorithm in Line 5) must
Proof of Theorem 3.3
7

---

Algorithm 1: The Strategic Standard Optimal Algorithm (SSOA)
Input: Hypothesis class H. manipulation graph G. Initialization Version space Ho < H.
for & [2'] do
Commit to the classifier hs X' + { defined as follows:
+1, if SLdim (H4--1) (z,-1) G) SLdim((H4-1,
Var E (x))
-1, otherwise.
Observe the manipulated feature vector is and the true label yr; If a mistake occurs (tr) + yr), update He - (He-1)a (1 Otherwise He & He-1-
end
decrease by at least 1, namely SLdim(H,, G) < SLdim(H4:-1, G) 1. For notational convenience, let SLdim(H4-1,G)
False positives. We start with the case where SSOA makes a false positive mistake, i.e., (tx( +1 but y/ 1. According the definition of classifier he and the update rule of version space H4, we immediately obtain
SLdim(H,, G) SLdim ((H4-1) (1) .)) SLdim(H4.1,,) G) = SL,,m(H,, G) S 1
False negatives. Then we consider the case where 5SOA makes a false negative mistake, i.e., (v())) - but V/ +1. For the sake of contradiction, assume that the strategic Littlestone di- mension does not decrease, i.e., SLdim G) SLdim (Ho-))( (ee,+1) G) = d. This assumption implies that there exists a strategic Littlestone tree T that is shattered by (Hz-1)6 (1e,+1) and of depth SLdim(H4-1: G).
Since the agent is classified as negative, it must be the case that the agent has not manipulated (i.e., I, vt), and the entire outgoing neighborhood N is labeled as negative by h4. Therefore, according to the definition of h,, for all [x),, have SLdim (HH-1) which implies that there also exists a strategic Littlestone tree Ty of depth d that is shattered by (H4-1)(
d,
Now consider the tree T' with root 2t, subtree on the false negative edge (z,, +1), and subtree To on each false positive edge (u. 11) for all N [xy]. Since we have argued that each subtree has depth d, the overall depth of T' is d + 1. We claim that T' is shattered by H4-1. In fact, for all root-to-leaf paths in T'. the first observation is guaranteed be consistent with all hypotheses in the subclass for the subtree, and the consistency of each subtree ensures the existence of hypothesis that makes all subsequent observations realizable.
We have thus constructed a strategic Littlestone tree T that is shattered by H4-1 and of depth d + However, this contradicts with the assumption that SLdim (H--1, G) d. Therefore, must follow that SLdim He, G) < SLdim(H, G).
SLdim G) - 1, which in turn proves Mistake5soa G) <
4 Agnostic Setting
In this section, we study the regret bound in the agnostic setting. Recall that benchmark is de- fined as the minimum number of mistakes that the best hypothesis in H makes, i.e., OPT A min+-gx Everyy [b (x;)) # y.). We will present an algorithm that has vanishing regret compared to & OPT whenever the strategic Littlestone dimension is bounded, where A is the maximum out-degree of G. Inspired by the classical reduction framework proposed by (Ben-Davie et al. 2009], our algorithm aims to reduce the agnostic problem to that of strategic online learning with expert advice by constructing finite number of representative experts that performs almost as well as the potentially unbounded hypothesis class. The problem with finite expert set then

---

be solved using the biased weighted voting algorithm proposed by Ahmadi et al. [2023]. However, establishing the reduction turns out be more challenging the strategic setting. as the learner can only observe manipulated features instead of the original ones. We address this problem by designing the experts to "guess" every possibile direction the original node could have come. We present our algorithms (Algorithms and in Appendix and analyze their regret in Theorem 4.1
Theorem 4.1. For any adaptive adversarial sequence S of length T, the Agnostic Online Strategic Classification algorithm (Algorithm 3 has regret bound
Regret(S, H. G) S S OPT + A SLdim(H, G) (log T log Ag))
where Dg (resp. A denotes the maximum out- out-degree (resp. in-degree) of graph G.
Remark 4.2. Ahmadi et al. [2023] showed that there exists instances in which all deterministic algorithmss must suffer regret St ( which means the first term in the above bound is necessary.
The second term connects to our instance-wise lower bound of SLiim G) in Theorem 3.2
Proof sketch of Theorem 4.1 We use to denote the set of experts constructed in Algorithm and define OPT as the minimum number of mistakes made by the best expert ex E C, had the agents responded to e*. Then the Biased Weighted Majority Vote algorithm from Ahmadi al. 2023 guarantees that the number of mistakes made by Algorithm is at most A OPT + A log According to our construction of experts, the total number of experts satisfies log | S log (Emsd (M) (AG) S O(d- (log T + log AG), where d = SLdim(H, G) is the strategic Littlestone dimension. Therefore, suffices to show that OPT is not too much larger than OPT-in other words, the set of experts é are representative enough of the original hypothesis class H in their ability of performing strategic classification. We use the following lemma, which we prove in Appendix by establishing the equivalence between the SSOA instance running on the sequence labeled by the effective classifier and the SSOA instance simulated by a specific expert.
Lemma 4.3 (Experts are representative). For any hypothesis h E H and any sequence of agents S, there exists expert en. E E that makes at most SLdim (H, G) more mistakes than h.
5 Unknown Manipulation Graph
In this section, we generalize the main settings to relax the assumption that the learner has full knowledge about the underlying manipulation graph G. Instead, we use graph class G to capture the learner's knowledge about the manipulation graph. In Section we begin with the realizable graph class setting, where the true manipulation graph remains the same across rounds and belongs to the family G. We then study the agnostic graph class setting in Section [.2] where we drop both assumptions and allow our regret bound to depend on the "imperfectness" of G. In both cases, we assume the hypothesis class H is also agnostic, which encompasses the setting where H is realizable.
5.1 Realizable graph classes
In this section, we assume that there exists a perfect (but unknown) graph G* E G, such that each agent (It, y1) E S manipulates according to G*. We define the benchmark OPT h to be the optimal number of mistakes made by the best h* E H assuming that each agent best responds to h+ according to G*. Formally, OPT
ming-cH 1 (h* (bro* _ (2x)) * ). Same to our main setting, we assume that the learner only observes the post-manipulation features v. bro. ,r (11) after they commit to classifier h4, but cannot observe the original features 2t.
Our algorithm (Algorithm 6) for this setting leverages two main ideas. First, to overcome the challenge that G* is unknown to the experts, we blow up the number of experts by a factor of [g] and let each expert simulate their own SSOA instance according to some internal belief of G*. Since the regret bound depends logarithmic on the number of experts, this only introduces an extra log [g] term, which has been shown by Cohen et al. (2044 to be unavoidable even when the learner has access to the original features.
Our second idea involves re-examining the correctness of Algorithm 5 for bounded expert class to the scenario where the input G is a pessimistic estimate of the true graph G+ i.e., G contains all the edges in G* but potentially some extra edges. This allows us to use Gunion whose edge set is taken to

---

be the union of all egdes in G. Combining these two ideas, we present our algorithm and establish its regret bound (Theorem 5.I) in Appendix
Theorem 5.1. For any realizable graph class 9 and any adaptive adversarial sequence S of length has regret bound
T, Algorithm 6
Regret(S, H. G) S SO S (OPT + dg (log T' + log AG) log (91))
where dg A maxxeg SLdim(H. G) is the maximum strategic Littlestone dimension for all graphs in G, Ag
g A is the maximum out-degree of Gunion (i.e., the union of graphs in 9), and Ag A maxGeg Ag is the maximum max in-degree over graphs in G.
Remark 5.2 (Implications in the realizable setting). In the realizable setting where OPT = O, Theorem 5.7 implies a mistake bound of Ó(A A -dg + log G)). This bound is optimal up to logarithmic factors due to a lower bound proved by Cohen al.) [2024] Proposition 14J. They constructed an instance with [9] = H = (n) in which any deterministic algorithm makes Q(n) mistakes. In this instance, our bound evaluates to be Ónn) since D = (()) and dg =.
5.2 Agnostic graph classes
In this section, consider a fully agnostic setting where each agent (Iz, Mr) may behave according to different manipulation graph G2 C Gunion- We define the benchmark OPT to count the number of times that the best graph G* fails to model the local manipulation structure under Gz, and OPTH is defined as in Section 5.1 using the graph G that achieves OPTg.
T
T
OPTg A min G'
[
[nd] + N [md) OPT
min bRCR
Σ t=1
1 (bra" (2x) (ar)) # 90)
t=1
Assuming access to an upper bound N of OPTg, we present Algorithm 7 that achieves a regret bound of Ô (N + OPT + de)). as shown in Theorem D.2 We additionally apply the standard doubling trick remove the requirement of knowing N. More details can be found in Appendix D.2
6 Discussion and Future Research
Improved bounds for the agnostic setting, An immediate direction for future research is tightening our bounds in the agnostic setting under known manipulation graph. Note that our upper bound is Ô ( (OPT + SLdim(H, H., G)) whereas the lower bounds are 52 A OPT) from Ahmadi al. 2023 and 2(SLdim(H4 G)) from Theorem 3.2 The extra A factor is introduced by the strategic learning-wiit with---xperrt---vice algorithm, for which all known results have the dependency on Ag.
Randomized learners. Our results mainly focus deterministic learners. It is an important open problem find the corresponding characterizations for randomized learners. In Appendix E. we provided family of realizable instances that witnesses super-constant gap between the optimal mistake deterministic and randomized algorithms. This contrast their classical counterparts which are always factor of 2 within each other. One challenge (among others) of proving tight lower bound the randomized setting is controlling the learner's information about the agents' original features, as the adversary can no longer "look-ahead" at algorithm's 'ss future classifiers.
"We can also derive regret bounds when OPT is defined based on the agents' best responses according to their own manipulation graph G; instead of G", In this case, the regret bound would be the same up to constant factors.
10

---

Acknowledgments. We thank Avrim Blum for the helpful comments and discussions. This work was done while Hanrui Zhang was in residence at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley, California, during the Fall 2023 semester. This work was supported part by the National Science Foundation under grants DMS-1928930, CCF-2212968, and ECCS- 2216899, by the Alfred P. Sloan Foundation under grant G-2021-16778, by the Simons Foundation under the Simons Collaboration on the Theory of Algorithmic Fairness, and by the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003, The views expressed in this work do not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred. Approved for public release; distribution is unlimited.
References
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 6-25, 2021.
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On classification of strategic agents who can both game and improve. arXiv preprint arXiv:2203.00/24, 2022.
Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds online strategic classification. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), pages 22-58, 2023.
Tal Alon, Magdalen Dobson, Ariel Procaccia, Inbal Talgam-Cohen and Jamie Tucker-Foltz. Mul- tiagent evaluation mechanisms. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 34(02):1774-77811 2020.
Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234-1242. PMLR, 2021.
Shai Ben- David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In Conference on Learning Theory (COLT), volume page 2009.
Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547-555, 2011.
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy- linear classifiers. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 15265-15276, 2020.
Lee Cohen, Saced Sharifi Malvii-iaalajjrrdi, Kevin Stangl, Ali Vakilian, and Juba Ziani. Sequential strategic screening. In International Conference Machine Learning, pages 6279-6299 6295. PMLR, 2023.
Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao. Learnability gaps of strategic classification. arXiv preprint arXiv:2402. 19303, 2024.
Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial classifica- tion. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 108, 2004.
Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 884-893, 2008
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 55-70, 2018.
Yuval Filmus, Steve Hanneke, Idan Mchalel, and Shay Moran. Bandit-feedback online multiclass classification: Variants and tradeoffs. arXiv preprint arXiv:2402.07453 2024.
Alan M Frieze. On the independence number of random graphs. Discrete Mathematics, 81(2): 17 171-175, 1990.
11

---

Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, Cohen, and Nir Rosenfeld. Strategic classifi- cation the dark. International Conference on Machine Learning, pages 3672-3681. PMLR, 2021.
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. International Joint Conference on Artificial Intelligence (IJCAI), pages 160-166, 2020.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Innovations in Theoretical Computer Science Conference (ITCS), pages 111-122, 2016
Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 19, page 259-268, 2019.
Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
Tosca Lechner and Ruth Umnr. Learning losses for strategic classification. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), volume 36, pages 7337-7344, 2022.
Tosca Lechner, Ruth Urner, and Shai Ben-David. Strategic classification with unknown user ma- nipulations. In International Conference on Machine Learning, pages 18714-18732. PMLR, 2023.
Nick Littlestone. Learning quickly when irrelevant attributes abound: new tinear-threshold algorithm. Machine learning, 2:285-313 1988.
Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünnee and Moritz Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119, pages 7599-7609, PMLR, 2020.
Ananth Raman, Vinod Raman, Unique Subedi, Idan Mchalel, and Ambuj Tewari. Multiclass online learnability under bandit feedback. In International Conference on Algorithmic Learning Theory, pages 9012 PMLR, 2024.
Han Shao, Avrim Blum, and Omar Montasser. Strategic classification under unknown personalized manipulation. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2024.
Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. PAC-learning for strategic classification. Journal of Machine Learning Research. 24(192):1-38, 2023.
Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI), volume 35, pages 5797-5804, 2021.
12

---

A Supplementary Materials for Section 2
We present the SOA algorithm in Algorithm 2
Algorithm 2: The Classical Standard Optimal Algorithm (SOA)
Input: Hypothesis class H. Initialization Version space Ho H.
for t E [T] do
Observe 24; For y {+1), let (( + (h H4-1 h(x)) 0):
Predict Ut t arg max,, Ldim(H(
Observe yr and update version space H, t H (1(2))))
6 end
B Supplementary Materials for Section 3
B.1
Proof of Theorem 3.2
Theorem 3.2 (Restated). For any pair of hypothesis class H. and manipulation graph G, any deterministic online learning algorithm A must suffer a mistake lower bound of M G) 2 SLdim(H, G).
Proof of Theorem 3.2 Recall that to construct an adversarial sequence of agents S = (x,, Be)
such that is forced make mistake at every round, we will first find a path x²} (er.21), x/ (02.22),
.... (va.84) s'441 in tree T which specifies the types of mistakes that the adversary wishes to induce, then reverse-engineenee manipulation that is realizable under H.
this path to obtain the sequence of initial feature vectors before
Constructing the path. We initialize x¹1 to be the root of the tree T. For all / S d and given the history (partial path) æ (v1.81), ... -.--111 (v1-1.Bi-1), 2/, we find the edge (Ve, ye and the next node T as follows: run the online learning algorithm A for t - rounds with inputs (vy. ye )es--- and let h, be the outputted classifier at round t. We examine the labels of he in the out-neighborhood N [xr]] under graph G and consider the following two cases.
Case 1: False negatives. If all the feature vectors in [='] is labeled as negative by he, then the adversary will induce false negative mistake by letting the post-manipulation feature vector be a/ (which is same as the original feature vector 21) and the true label be positive, i.e. (Vt, Br) 2 (x + +1). We then choose the next node 2/41 to be the child of x along the false negative edge (2/ +1) in T.
Case 2: False positives. If there exists E N [=/]] such that (v) = +1, then the adversary will induce false positive mistake that is observed at o with true label 11, i.e., (V,, Vt) & (v. -1). However, we remark that the true features may be chosen as different node in N [vg] to ensure realizability,, which we will discuss the eevrss--nginneriin part. We choose 2/41 to be the child of i along the false positive edge (u, 11) in T.
(01.81)
Reverse-engineering Repeating the above procedure for all f < d gives us the path x
....'' (va.gu) 2'441 where each y already specifies the true labels of each agent. It remains to select the initial features (zx). Since T is shattered by H. the consistency part of Definition 3. guarantees the existence of E such that Vt < d, there exists 2, that satisfies ha = Vr, where I, = V x/ y: -1 and x, No [vr] if y, +1. We let those (Ir))etd be agents' true feature vectors. It then follows that the sequence of agents S = (æ,, ye) is realizable under (H, G) and indeed induces mistake observed as (v,, y1) at every round E [d].
13

---

Finally, if SLd G) < oo, then the above argument with d = (H, G) proves the theorem. When SLdim (H, G) oo, the above argument shows Mistake (H. G) for all d E N, which implies that M (H, G) xc by driving d - xo. The proof is thus complete.
B.2 Comparison with max-degree based bounds
In this section, we consider two families of instances (H, G) in which our mistake bound SLdim(H, G) from Theorem 3.3 significantly improves the previous bounds. We compare with upper bounds ( log [ from [Ahmadi et al. 2023] and 0(4) Ldim(?() from [Cohen et al. 2024), where Ldim(H) denotes the classical Littlstone dimension of hypothesis class H. We focuses on comparing with the latter bound, since it can be shown that Ldim (H) s log [H] for all H.
Graphs with a large clique. Our first example involves graphs with a very large clique. The main idea is that the densest part of graph may turn out be very easy to learn since there are only a few effective hypotheses supported on it. On the other hand, the harder-to-learn part of the hypothesis class may be supported on a subgraph with much smaller maximum degree. For this reason, the previous bounds that directly multiply the complexity of the entire graph (e.g., 4g) with the complexity of the entire hypothesis class would be suboptimal.
Let (G', be a pair of manipulation graph and hypothesis class, for which we have SLdim (H. G*) I O LLdimH"') since the strategic Littlestone dimension is a lower bound of all valid mistake bounds (Theorem Let N > max [7'1) be very large integer, and KN be a clique of size N. We assume that the vertex set of K is disjoint from that of G'. We take the hypothesis class on KN to be the set of all functions, i... [=1]KN Let G G' U KN and H = H' x {+1]%.
Previous bound: Since A N and Ldim(H) 2 Ldim(H'). Therefore, the bound in Cohen et al. 2024 is of order (ignoring logarithmic factors)
(H)) S(N Ldim(?")).
Our bound based on the strategic Littlestone dimension: bounds the mistake bound achievable by any deterministic algorithm. Consider the following deterministic algorithm that uses two independent algorithms Ag and A to learn on each of the disjoint subgraphs g' and Kv, We will choose A₁ to be the proposed by Cohen et [2024). and Ag be the algorithm that predicts all nodes negative until a mistake happens, at which point flips the prediction to positive on all nodes. Since the effective classifiers on KN is either all positive or all negative, A2 makes at most mistake. We have
By Theorem 3.2 SLdim(H. G) lower
algorithm
SLdim(H. G) < Mistake (H', "') + Mistake ({#1) KN) = Ô -LdimH")).
Improvement. As a result, for this instance, the gap between these two algorithms is lower bounded by N/ A G", which can be arbitrarily large by taking N + x0.
Random graphs in G(n,p), H = (+1)". Our second example considers random graphs G ~ G(n, p), in which every (undirected) edge realized independently with probability p. We will show that when p= (1/n)) (when the random graph is "effectively" dense), with high probability over G (), the strategic Littlestone dimension significantly improves previous bounds.
Since H is extremely expressive (contains all functions), we have log | Ldim(H) - n. However, we will show that even after strengthening the previous bounds by applying it on the reduced-size hypothesis class HG C which contains only one hypothesis in each equivalence class that induces the same effective hypothesis h the strategic Littlestone dimension SLdim G) still offers significant improvement over A Adim(Hcc)
By concentration, A 2 ((mp) with high probability. Moreover, with high probability, the independence number (G) satisfies (<G)= Z ((log(pp)/p) [Frieze] 1990). Let T(G) be the independent set with size (G) and consider the projection of Ha onto (G)). Since there are edges inside, the effective hypothesis coincides with the original hypothesis, therefore
Previous bound:
14

---

(Ha)na) contains all functions that maps from I(G to {+1}, which has classical Littlestone dimension [I(G) = =aGG). As result, we have that with high probability,
a (dim (mmp) (llo((pp)pp) 2 log(n)))
Our bound based the strategic Littlestone dimension: Again, SLdim(H, G) lower bounds the mistake bound of all deterministic algorithms. Consider the following algorithm: start with predicting all nodes positive. Whenever false positive is observed at some node u, flip the sign of u to negative. Such an algorithm achieves a mistake bound of n. Therefore,
SLdim H. G) S n.
Improvement When p = ( with high probability, the gap between these two bounds are (mmp) (1),,,
which can be made to approach oo as n oc.
C Supplementary Materials for Section
C.1 Algorithms for the agnostic setting
In this section, we present algorithms for the agnostic setting and prove their regret guarantees. As discussed in Section 4 the main idea behind the strategic version of agmostic-to-realize lies in our "guess" of the possible direction the original node would have come from. To do this systematicallyy,
reduction
first need to specify indexing system the in-neighborhoods of every node in the graph. For each node v E X, we assign unique index to each in-neighbor in NG [u] from the range (0, 1, ................................ } where Aø being the max in-degree of G. This indexing is specific to each u and does not require consistency when indexing common in-neighbor of different nodes. We
now ready to formally introduce our algorithms in Algorithms Band
Algorithm 3: Agnostic Online Strategic Classification Algorithm
Input: Hypothesis class H. manipulation graph G. Let < (H, G);
2 foreach m S d, f1:m, Fiam where S i1 .....
.....t. <i S T, 0 ri, mm I Ag do
Construct Expert(iimm T1:m) as in Algorithm
end
Run Biased Weighted Majority Vote (Algorithm) the set of experts.
Algorithm 4: Expert(i1, ... 2m 71, .m: G)
Input: Hypothesis class H., manipulation graph G, indices for mistakes 1 < i < im S T,
indices for manipulation directions 0 S Ti,". .' S Ag.
the sequence of post-manipulation agents (we, (te,))) received sequentially.
Output: Classifiers (he))etz outputted sequentially.
Initialization :imuulate an instance of the SSOA algorithm with parameters (H, G).
for t [T]do do
he + classifier outputted by the SSOA algorithm;
Observe the manipulated feature vector o, and the true label yr:
fi.....,4, (suppose ig) then
St <- the in-neighbor in N [v:] with index ru/l/ guess of the original feature vector t.bbr,,.ce ( simulate the post- post-manipulation feature vector response h,
Update the 5SOA algorithm with instance (0t. (f,())).
end
end
15

---

C.2 Proof of Lemma 4.3
4.3 (Restated), For any hypothesis h E H and any sequence of agents S, there exists expert ch E that makes at most SLdim (H, G) more mistakes than h.
Lemma
Proof of Lemma 4.3 Let us define the hypothetical sequence S A (1 )ee[T) where we keep
the same sequence of initial feature vectors (x4) in S, but adjust their labels to be y & ha())) i.e., the label that the effective classifier he assigns to 2t.- Note that this sequence is defined only for analytical purpose and not required to be known by either the agnostic algorithm or the experts.
By definition, ((h) is realizable by the hypothesis guarantees that runnning SSOA ( gives most SLdim G) mistakes. Let S SLdim (H, G) be the number mistakes made, and 61, i2, ... im be the time steps at which the mistakes occur. In addition, every mistake i t E [T], let vi be the post-manipulation node observed by the SSOA algorithm running on sequence 8th), On the other hand, let be the observation received by each expert. Although i2 may different from vi (h) because 12 the best response to the agnostic algorithm while ui is the best response to S50A, we know that 2 must be an out-neighbor of zt. Therefore, there must exist an index r (where 0 I r I AG) such that is the ry-th in-neighbor of et. We argue that Expert(i1:m: fl:m) the expert ед that we want.
H under graph G. Therefore, Theorem 3.3
We first establish the equivalence of the two following instances of SSOA:
SSOA denotes the algorithm instance simulated by expert en:5
SSOA h denotes the algorithm instance running on sequence s(h)
We will show by induction that both instances SSOA" and SSOA A have the same version space- aad and result, output the same classifier for the next round at all time steps. This is clearly true the base case / = 1, as the version spaces of both instances are initialized to be H. Now we assume the two instances
equivalent up to 1 and prove that they are still equivalent time t. Since they have the same version spaces H4-1, they output the same classifiers for time step t. We denote this classifier by h, as in line 2 of Algorithm 4
If /. & (i,,-.. (im) ), then the version space Hs are still the same because neither instances update. Otherwise, there exists E [m]] such that ig. Since SSOA* makes a mistake at ig. will update the version space with observation (v, (h) y1 (v, (h) (v, (o( On the other hand, according to line 7 of Algorithm 4 the instance SSOA* is updated using observation (0,, (..)))). Therefore, it suffices to show that u/ Gr Since our choice of r& guarantees x, to be the rh-th in-neighbor of Ut.
we have +; xt. based on line 5 of Algorithm 4. Therefore, both (h) and ên are equal to br,, (11e.
so they are the same. As result, both SSOA th and SSOA " updates their version space using the same observation, their H4 remains the same. By induction, these two instances are equivalent for all time steps.
Finally, we use the equivalence established above to prove the lemma. Using (he)eerzy to denote the sequence of classifiers outputted by ex. we have
T
T
Mistake,, (S) - Mistake =
Σ
1 (br (orr,, # 31
1 1(h(brr,c(z)) # ve
1=1
T
Roelbrr, h(bra,(xx)))
I (fee(bra., # vi (M)
(uf (h) = ho(()) in S(A)
= Mistakessoa (s(h))
(Equivalence of SSOA and SSOA" (S(N) is realizable under 7L and G)
< SLdim(H. G).
16

---

The proof of the lemma is thus complete.
C.3 The Biased Weighted Majority Vote Algorithm
We present the algorithm in Algorithm 5
Algorithm 5: Biased Weighted Majority Vote (Ahmadi et al. 2023)
Input: Expert class C, manipulation graph G(X, E) that is supergraph of the true (unknown) manipulation graph G
Initialization For all experts e E, set weight wb(e) 1.
for t E [T] do
1* the learner commits to classifier iú that constructed follows:
for v E X do
Let W (v) = (0) we(e). (T(w) (w) Eeee (c), and
W, = (w) + W. (u) E.ee we(e), e, is the prediction of expert round
if W (v) 2 W + 2) then
(v) - +1;
else
(1(v) f- -1;
end end
10
Observe manipulated node or and output prediction h2(v)); if (w4) # z/ then
10 If there was mistake:
if 11- = -1 then
10 False positive mistake.
13
E' + {e E E ce(v)) +1}: 1/:// // penalize the experts that label i positive.
14
else
1a False negative mistake.
15
[|r - N [o]] \ for E e - f é Vx E [ex), ex(x)= - -
=
16
// penalize the experts that label all nodes in Ñ [ux] negative. end
17
18
if C,, then (e) + 7 we)c); otherwise, wc+1(c) & we(e);
end
end
C.4 Proof of Theorem 4.1
Theorem 4.1 (eestaedd) For any adaptive adversarial sequence S of length T, the Agnostic Online Strategic Classification algorithum (Algorithm 3 has regret bound
RSgret(S, H., G) o ( OPT + A SLdim(H, G) (log T + log Ag))
where DT (resp. Ag) denotes the maximum out-degree (resp, in-degree) of graph G.
Proof of Theorem 4.1 As showed in the proof sketch, combing the guarantee Algorithm 5 and
bound on gives
Mistake(S, H. G) < A O + A log |el x OPT + A d(log T + log Ag),
where OPT denotes the optimal number of mistakes made by the best expert in
Applying Lemma 4.3 to the best hypothesis hindsight h² E H. shows that there exists en E C that makes no more than OPT + mistakes, which further implies OPT < OPT + d. Hence, we have
Mistake H) & A (OPT + dloo + dl log A
17

---

D Supplementary Materials for Section 5
D.1 Realizable graph classes
Algorithm Online Strategic Classification For Relizable Graph Class
Input: Hypothesis class H. graph class G.
foreach G E G
Let da f (H, G);
foreach da; $1mm Flom where 1 I i1 <....
ST,0sm," ",..,, A do
Construct Expert(limm Piom; G) as in Algorithm end end
7 Let Gunion +- (X, Egeg Eg) be the union of graphs in G;
8 Run Biased Weighted Majority Vote (Algorithm on the set of experts under graph Gunion-
Theorem (Restated), For any realizable graph class 9 and any adaptive adversarial sequence of lenghh T, Algorithmm O has regret bound
Regret(S, S, H. G) - O (At (OPTH + dg (log T + log Ag) log log]gl)),
maXGeg SLdim (.. G) is the maximum strategic Littlestone dimension for all graphs g, A D is the maximum out-degree of Gunion (i.e., the union of graphs in G), and A maxGeg Ag is the maximum max in-degree over graphs in G.
where dg
Proof of Theorem 5.7 For each G 9, we use EG to denote the subset of experts constructed in Algorithm for graph G. We also use C a Ugegeg denote the of all experts.
To prove this theorem, we first revisit the regret guarantee for Algorithm 5 in Lemma D.1 especially
when the input graph G does match the actual graph G*. The proof of Lemma D. largely follows from [Ahmadi et al., 2023), but we include in the end of this section for completeness.
Lemma D.1 (Regret of Algorithm Ahhaadi et al. 2023)). ). Algorithm S is called manipulation graph G that includes all the edges in the actual manipulation graph G*, then the number of mistakes upper bounded as follows:
Mistake(H, G") so) 5o OPT + log (
where AT is the maximum out-degree of graph G, and OPT is the minimum number of mistakes made by the optimal expert under graph G
Since Gunion contains all edges any G 9 and thus the unknown G*, Lemma D.I that the number of mistakes made by Algorithm is is most
A OPT - log je| A OPT + A (dg log(T + log [9])
where the second step the following upper bound the number of experts:
c <
Σ
Σ
T m)
(A
GEg
< | Σ
(m
(VG E g, SLdim(HL, s A5 Ag)
Sgdg
S | (T A do+1
Therefore, it remains show that OPT OPT dg. To this end, apply Lemma 4.3 the expert class Eg,, in which all experts have the correct belief about the manipulation graph G* For the hypothesis ht E H that achieves OPTx under G* there must exist G. E Cg. C é such that Gn makes at most SLdim(H, G*) S dg more mistakes than h under G*. We have thus proved that OPTC OPT h. + dg. which in turn establishes the theorem.
18

---

Proof of Lemma D.1 Suppose a mistake is made in round t, we show the following claims hold:
The total weights decrease by least constant fraction: W4+1 S <Wi(1 - + 2)) where G is the input graph.
The algorithm penalizes experts only if it makes mistake G To prove these claims, we consider the following two types of mistakes.
False positive. Suppose (v(()) is positive but the true label Yt is negative. According to the algorithm, h2 labels e positive only when the total weight of experts predicting positive 82 is at least ( + 2). Moreover, each of their weights is decreased by a factor of y. As a result, we have W++1 & Wi(1 - 7/(27 + 2)) and the first claim holds.
For the second claim, note that the algorithm only penalize experts where (e = +1. Since ee N [dtr], this implies e (b (xx)) +1, whereas y/- -1. In other words, the experts penalized must have made a mistake under G
False negative. In the case of a false negative, the agent has not moved from different location to e to get classified as negative, so U, It. Since the agent did not move, none of the vertices in G+ [ex] was labeled positive by the algorithm. However, there might exist some vertices in N [v]] Not [oy] that are labeled as positive by the algorithm. Let [e, denote the set that includes all vertices N [ue] that are labeled as negative by he, we have
No. [vx] S [[o]] S [ur]
According to the algorithm, for each æ E [or]. the total weight of experts predicting as positive is less than W + 2) where A is the maximum out-degree G. Therefore, taking the union over all x E N [u)) it implies that the total weight of experts predicting negative on all x E Mua is least
W, (1 Mollll(A + 2)) Z Wi(1 (At 1)/(4//// + 2)) W./(A + 2).
where the inequality comes from [ua] S [ Reducing their weights by a factor of y results in We+1 I W. (>W,)/(At + 2). The first claim holds true.
As for the second claim, if an expert is penalized, then cx(x) = 1 for all æ E [ Since Not [ara] C [are) e, must label all nodes in Not [ate] as negative. In other words, e, (br (Ix))
11 which means that e must have made a mistake under G*. The second claim holds.
Regret analysis. Let M Mistake HH, G*) denote the number of mistakes made by the algorithm. Since the initial weights are all set to 1, we have Wo |E]. The first claim implies that W++1 S
W. (1- 7 2
Therefore, Wr < [ (1- +2
M
On the other hand, we use the second claim to show that Wf 7 OPT:. We have proved that whenever the algorithm decreases the weight of an expert, they must have made mistake on G
Let E E denote the best expert that achieves the minimum number of mistakes OPT G. under G*. From argument above, the weight of is penalized by no more than OPT times. Therefore, after rounds, WT 2 wT(C*) 2 -PPTS where the second inequality holds since < 7 < Finally, we have:
M
7 OPTS. WT < |E|
7
A +2
OPT
In < In E
+ M
1 (1-
7
< In
M
Y At +
A +
A G
+ 2
In
A + 22)
M
In E
OPTE
7
By setting y 1/e, we bound the total number of mistakes M S +e(A)+2)(L) +OPT). 0
19

---

D.2 Agnostic graph classes
Before presenting the algorithm the setting agnostic graph classes, we first introduce an indexing system to the in-neighborhoods of union which is constructed in the same way as described in Section These indices whill be in the range {0, 1.... Ag} where Ag is the maximum in-degree of graph Gunion- We now present the algorithm in Algorithms and g and prove its regret bound in Theorem D.2
Algorithm 7: Online Strategic Classification For Agnostic Graph Class
Input: Hypothesis class H. graph class G, an upper bound N that satisfies OPT, S N. Let Gunion +- (X, EGeg Eg) be the union of graphs in g, Ag + AG...
foreach G' E G do
Let de + SLdim(H, G);
foreach m S da. 11mm E (n) E [Aq]", n S N, 2 E Construct Expert(iims Timm 1m Tixi G) as in Algorithm g
M E
m [4g]" do
end
end
Run Biased Weighted Majority Vote (Algorithm on the set of experts under graph G Gunion-
Algorithm 8: Expert(i1mn F1:m: im Ti G)
Input: Hypothesis class H. manipulation graph G, indices for mistakes 1 < i1 < .... < im < T,
indices for manipulation directions 0 I r1. .' I Ag. indices for imperfect graphs 1 1 1/ < < i I T, and manipulation directions
ry, .ry s Ag.
the sequence of post masippanipultiion agents (Vt, (e)) received sequentially. Output: Classifiers (he) outputted sequentially.
Initialization : :Simulate an instance of the SSOA algorithm with parameters (H, G).
for / [T] do
he f- classifier outputted by the SSOA algorithm; Observe the manipulated feature vector e and the true label yr:
t (fi.,...,,m (suppose
ig) then 10t Guess where the original node z; comes from
if 1 E (i/,-.. , } (suppose i = (.)) then
2, t the in neincighbor in N G...a [1:] with index rill when G, o G. have G2 Gunion
else
8, + the in-neighbor in NO [tx] with index ra/l when G2 G
end
10
0. + b (#:) simulate the post-manipulation feature vector in response to hgg
Update the SSOA algorithm with instance (be. (f.))
11
12
end
end
Theorem D.2. For any graph class G and hypothesis class H. any adaptive adversarial sequence S of length T, and any integer N that is valid upper bound on OPT Algorithm 7 regret bound
Regret(S, S, H. H. s 0 (OPTx + (dg -log log A5) log [9]))
where dg & maXGeş SL, G) the maximum strategic Littlestone dimension for all graphs in G. and A (resp. AG) the maximum out-degree (resp. in-degree) of Gunion where Gunion the union of & that contains edges from all graphs in G.
Proof of Theorem D.2 Similar to the proof of Theorem we use EG to denote the subset of
experts constructed Algorithm 7 for graph G. and use UGeg EG to denote the set of all experts. Since we have G, C Gunion at all time steps, Lemma D.I on the expert set e gives upper bound
20

---

on the number of mistakes made by Algorithm 7 as follows:
Mistake(S, H, GI:T) X A OPT G + A log El
(I)
We establish the following lemma, which is strengthened version of Lemma 4.3 that accounts for the possibility of G + G.
Lemma D.3. For any hypothesis h H. any sequence of agents S, and any sequence of graphs G where T 1 [ [xe] * No [21] < N, there exists an expert en E Eg (which are constructed in Algorithm such that
Mistake,, (S, G1.T) s Mistake G) + N SLdim(H, G).
Applying the above lemma Eg. and using the upper bound OPTg 1[G, + G*] N, we conclude that for the optimal hypothesis h", there must exist expert e/*,G* E EG. C E, such that the number of mistakes e/2 G- makes under G1.7 at most SLdim G*) + N I dg + N more than that made by h under G". This implies
OPT Gur S OPTH + dg + N.
As for the number of experts, we have
e =
Σ
Σ
T
(4
Σ
T (4g)"
m
n2
GEG
(nnSLdim(H.G))
ASN
$ |g|
T
(m
Σ MSN
T (A
m
12
mSde
(VG E G, SLdim G) S dg. Ao S AAg)
S 191. (T- (T.
Finally, plugging both 2. (3) into the bound Equation [I gives us
Regret(S,, H. G) s O (4 (OPT + (dg + N) (log T + log AT) + log (g1))
as desired. The proof is thus complete.
Proof of Lemma D.3] We use a similar approach to that of proving Lemma sequence g(h) and the indices 11mm 7imm in the same way as Lemma 4.3 In addition, we set ii to be the time steps where G. * G, which clearly satisfies n < N. At time step t = i' (s E [k]), since it is the best response according to graph G, S Gunion there exists an index rg {0...... A such that H, is the -'hth in-neighbor under graph Gunion. We will show that expert ea Expert(i (i iam, Fl (imm rm G) the one want.
4.3 We define the
Again, we prove this by showing the equivalence of the following two SSOA instances:
SSOAA* is the algorithm instance simulated by expert cy:
SSOA h is the algorithm instance running on sequence 5(h).
Repeating the induction approach in Lemma 4.3 it suffices to show that the estimate a, correctly matches the true H, during the rounds iim When & .i'.... ,,,), this is guaranteed by the way indices F1:m are constructed. When there exists E [ra] such that = E. this also holds based on the definition of v/... Therefore, the above two SSOA instances are equivalent.
Finally, we have Mistake,, GL.) Mistake;(S,C. (S,
hee (2+)) # vo Σ ((((br,,((z)) 4 vc
T
T
5
Σ
I ( [or]] # [ +
Σ 1 ha ( # h(br).((a)))
[=1
(break [T] into two parts on whether N [Ma] * N (xx) (Combining Σ. 1(G, + G} s N and the bound from Lemma 4.3)
< N + SLdim(H, G).
21

---

We have thus established the lemma.
Doubling trick removing the assumption of knowing OPT; We end this section with an algorithm for agnostic graph classes that does not require any prior knowledge on OPTg. We present Algorithm which uses Algorithm as subrountine and performs the doubling technique on the parameter N.
This algorithm is based the important observation that, if N > OPT + OPT dg + log []
(in particular this implies 2 OPTg), then Theorem D.2 guarantees that running A Algorithm 7 with parameter N achieves the mistake upper bound of O (2N) (log T - log Ag )), where the leading constant of the mistake bound can be estimated to be S by more careful analysis. Therefore, if denote define the problem-dependent parameter C? to be
C 8 (log T + log Ag),
then as long as N reaches value least
N & OPT + g - dg + log [g],
(4)
running Algorithm 7 makes no more than C- N mistakes. Therefore, the learner just needs to estimate N through the doubling trick and terminate when the observed mistake does not exceed C times the estimate of N.
Algorithm 9: Online Strategic Classification For Agnostic Graph Class
Input: Hypothesis class H. graph class G.
Let C' + 8Δ8 (log T + log Ag Initialization iindex of the current epoch f-
while total number of steps T do f Epoch
A < a new instance of Algorithm with parameters (H, N₁ = 2*); while As has made no more than C- 2 mistakes
Run A& for another round
end
1* Exiting the while loop indicates that No. < N should double estimate and enter the next epoch */
+ 1 +1
8 end
Proposition D.4. For any graph class G, any hypothesis class H. and any sequences S (1),,)) (G.)ce]T). Algorithm 9 enjoys regret bound
Regret(S, H. < (A) (OPT* + OPTs + dg + log [G]) log(TA,))
Proof of Proposition D.4
Since the above argument has shown that epoch with N₂. 2 N will
never terminate, algorithm will have most k-* log N = log(OPT + OPT + dg + log (
epochs. Moreover, since the number of mistakes made in any epoch & cannot exceed C 2 the total number of mistakes (thus the regret) is upper bounded by
C. 2 CC-2* 2** <O(CN*) 5 (OPT OPTg + dg + +og log(T
This completes the proof.
E Randomization Gap
In this section, we present a an instance (H, G) which there exists an exponential gap between the optimal mistake bound of deterministic and randomized algorithms.
Let G be the star graph with center xo and A leaves {- .z).. H. {hi.-... ha} where (z) = L(z = J.J. An adaptive adversary picks a realizable sequence S = (2x, te where each agent (ær, 31) satisfies yt T (ax)) for a fixed h+ h;- H. This means all the realizable choices for (Iz, Vr) are restricted to the subset {(z,, +1), (zo. +1)} U ((x,, -1) i i*}.
22

---

Deterministic algorithms If the learner is restricted to using deterministic algorithms, then Ahmadi
al. 2023 Theorem 4.6] showed that the optimal mistake is lower bounded by A This implies M
( 2
Randomized algorithms If the learner is allowed to use randommess, we will construct an randomized algorithm A that enjoys an expected mistake bound of log A. This would imply M (H, G) log A, which in turn witnesses a super-constant gap between the minmax opti- mal mistake bounds for deterministic and randomized learners, i.e.,
M (H, G) Mrund (H, G) 2 (1).
The algorithm maintains version space H4 that consists of all the hypotheses consistent with the history up to time t. This version space is initialized to be Hi <- H. At every round, the learner commits to distribution over classifiers that randomly pick classifier from the version space, i.e., he Unif He). Let M be the expected of mistakes by A in the future starting from time step t where H.l = k. Consider the following cases:
If the adversary chooses (æt, ye) (z.,, +1), then the learner makes mistake with probability 1 1 k but gets to know afterwards and will make no more mistakes in the future. In this case, we have M (A) = +.-
If the adversary chooses (Ir, y/)) = (oo. +1). then the learner never makes mistakes, but also gains no information. The version space remains the same (H4+1 He). The expected mistakes in the future is still (l)).
If the adversary chooses (Ire, 34) (x;, 1) for some * i* then the learner makes mistake only when h; h4, which happens with probability E. On the other hand, no matter which h, gets realized, the learner can always observe (0,, yt) = (Iz -1) and update the version space to be He+1 Hi \ {h:). By symmetry of the star graph, the expected mistakes for future rounds is M(k 1). We thus have M(k) + M 1).
Overall, have
M(k) & max { 1
-1- M(k), + +MK 11}
(1-1
k.'
Solving the above recurrence relation gives us M(k) s log k. which implies Mrrand G) < Mistake G) = (A) S log A.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction (especially section 1.1) discuss technical results.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations and future directions are discussed in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

All theorems and claims are formally proved, either in the main paper or in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer:
[NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuii wwwtii/gguie///eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
26

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpp:////aarrps..ccccaaaa/aaaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This paper is theoretical work without any direct societal impact the best of our knowledge.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
27

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
28

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "PFqUxWT2bO", "reviewer": "Reviewer_wZa2", "summary": "This paper considers the problem of online binary classification when each data point can strategically manipulate its features in a discrete way which is captured by a manipulation graph. \n\nProtocol and regret: In each round, the learner picks a deterministic classifier $h_t$, and then the data point $(x_t,y_t)$ arrives, and manipulates its feature according to graph $G$ from $x_t$ to $v_t$. The learner receives only $v_t$ and incurs loss $\\mathbb{1}[h_t(v_t) \\neq y_t]$. The regret is measured with respect to the best fixed $h \\in \\mathcal{H}$.\n\n**contributions**\n\n\n1. They introduced an elegant notion of Strategic Littlestone Dimension $\\mathrm{SLdim}(\\mathcal{H}, G)$, which is based on hypothesis class $\\mathcal{H}$ and manipulation graph $G$\n\n2. They showed that $\\mathrm{SLdim}(\\mathcal{H}, G)$ fully characterizes the optimal mistake bound for a realizable case, by showing a lower bound on the mistake using a strategic counterpart of shattering tree and an upper bound using a strategic version of SOA.  (Note: The realizable case here means there exists some $h \\in \\mathcal{H}$ with no mistakes on the manipulated data. so $h$ does not necessarily need to correctly classify the actual data.)\n3. They extended their results for the agnostic case and showed an improved upper bound compared to previous works. They used the idea of approximating the whole class $\\mathcal{H}$ using a finite set of representative experts. (Their benchmark is $\\Delta_G^+ \\cdot OPT$, where $OPT$ is the error of the best hypothesis and $\\Delta_G^+$ is maximum out-degree of graph $G$)\n4. Finally, they designed algorithms with regret upper bound for the setting where the manipulation graph is unknown to the learner. They consider two cases: (i) all data points use the same unknown manipulation graph from a set of graphs, (ii) each data point uses a separate manipulation graph (case (ii) better captures those real-world applications in which different data points might have different capabilities for manipulation.)", "questions": "1. In line 101, you mentioned that, your approach yields an improved bound for the agnostic setting. Can you please provide more details about this improvement? I believe you are comparing the upper bound in Theorem 4.1. with an upper bound from previous work.\n2. In your setting, you assumed that each strategic data point only gets manipulated for a positive classification and if no manipulation leads to a positive classification, then the data point remains unchanged. Is this a necessary assumption for your results? In other words, I was wondering, do you anticipate that your result can be easily extended to the setting where all data points (even those without a chance of getting positive classification)  have the potential to be manipulated?", "limitations": "As mentioned by the authors in the checklist, this paper is theoretical with no direct implications. I completely agree with this.\n\nHowever, I want to note that the motivation for strategic classification comes from real-world problems. I think the progress toward this direction by theoretical researchers and practitioners can only be beneficial for society. This paper improves our theoretical understanding of the complexity of this problem in a somewhat stylized case.\n\nI can think of only one possible potential limitation (in a very high-level sense). Suppose a practitioner decided to use manipulation robust learning algorithms in their specific application. They need to model a set of manipulation graphs $\\mathcal{G}$. If due to inaccuracy in the modelling by the practitioner, $\\mathcal{G}$ only captures the certain type of manipulations done by group $A$ and does not capture the type of manipulations done by group $B$, then the resulting learning algorithm will be only robust with respect to a certain type of manipulation from group $A$. Therefore, group $B$ **might** have gained some unfair advantages. Hence, it is important to model the manipulation graph set $\\mathcal{G}$ accurately.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very strong paper\n\n- Wring is clear easy to follow and well cited. Math notations and technical proofs are also clean and clear. \n- Significance: the notion of strategic Littlestone dimension: This is a very valuable extension of the Littlestone dimension which characterizes the optimal mistake-bound --> it improves our understanding of the complexity of online binary classification with the presence of strategic behavior\n- Extension for unknown manipulation graph is valuable and I suspect further research by a broad range of researchers in that line\n- Some of the previous results relied on knowledge about both pre-manipulation data and post-manipulation data (e.g. [Cohen et al. 2024]) but this paper uses only post-manipulation data\n- A detailed comparison with previous works in the appendix for the realizable case (I didn't closely check all the details)", "weaknesses": "I don't find any major weakness at all.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback on our work. We are happy to see that you find our notion of Strategic Littlestone Dimension elegant and valuable. \n\n> Question 1: Improved bound for the agnostic setting\n\nThis improvement results from the comparison between Theorem 4.1 in our paper and the agnostic mistake bound in [Theorem 4.5, Ahmadi et al., 2023]. Both papers study the same setting of agnostic online strategic classification and design deterministic algorithms that achieve mistake bounds in terms of $\\Delta\\cdot$OPT. However, their result requires the hypothesis class $\\mathcal{H}$ to be finite, whereas we only require finiteness of the strategic Littlestone dimension, which is a strictly weaker condition. We will add clarifications to revisions of our paper.\n\n> Question 2: Data points with no feasible manipulation that receives positive label would stay unmanipulated\n\nYes, we do assume that data points that cannot manipulate to get a positive label would choose not to manipulate, and this is a necessary assumption for establishing our upper bound (whereas the lower bound would still hold if we remove this assumption). On the technical side, when false negative mistakes are made, this assumption enables us to identify the pre-manipulation features as the root of the strategic Littlestone subtree, and is crucial for establishing the “progress on mistakes” property. This assumption is also crucial for the previous upper bounds in [Ahmadi et al, Cohen et al.]. We believe that extending the results to the setting where all data points could manipulate is an interesting question for future research.\n\n> The importance of modeling the manipulation graph G accurately\n\nWe completely agree that accurate modeling of the manipulation graph is crucial and that inaccurate estimations for certain graphs could lead to fairness issues. As a preliminary effort towards addressing unknown manipulation graphs, we allow the learner to run the strategic classification algorithm using knowledge about a potentially larger graph class that contains the true graph. The learner incurs only a logarithmic cost in the size of the graph class (assuming that taking union of the graphs does not significantly increase maximum in/out degree). Since this extra cost is only logarithmic, this (to some extent) allows the learner to adopt more conservative estimations of the manipulation that captures the types of manipulations from both groups. However, this approach focuses on the objective of minimizing the total number of mistakes rather than ensuring fairness among different groups. We believe the fairness implications that you described can be an interesting direction for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7N900fadZb", "reviewer": "Reviewer_fR1n", "summary": "The paper tackles online binary classification where agents manipulate observable features for positive outcomes. It introduces the Strategic Littlestone Dimension (SLD), a new measure capturing the complexity of the hypothesis class and manipulation graph, demonstrating its role in achieving optimal mistake bounds for deterministic algorithms in the realizable setting. It also improves regret bounds in the agnostic setting by refining agnostic-to-realizable reductions and addressing unobserved original features. Additionally, it relaxes the assumption of a known manipulation graph, deriving regret bounds for scenarios with imperfect graph knowledge in both realizable and agnostic settings.", "questions": "See weaknesses.", "limitations": "The authors did discuss the limitations of their work.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The problem is well-motivated and interesting. The paper is also well-structured. The result based on the notion of the Strategic Littlestone Dimension is tight, with matched lower and upper bounds. Although I did not check the proof, the results of this paper appear to be correct.", "weaknesses": "My main concern is twofold:\n\n1. The paper primarily concerns deterministic learning algorithms, while most robust algorithms dealing with adversaries are stochastic, which greatly limits the practical relevance of the paper.\n\n2. The computational complexity of Algorithm 1 is not clear. Line 3 of Algorithm 1 looks computationally expensive. Can authors comment on the computational complexity of the algorithm?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions and comments.\n\n> Weakness 1: deterministic learning algorithms\n\nWhile we agree that many robust algorithms rely on randomization to deal with adversaries, we want to highlight that in the context of strategic classification, there are important scenarios where the learner must use deterministic algorithms due to legal or regulatory requirements. An example is college admissions, where institutions are required to publish clear and transparent decision criteria (aka classifiers), as randomization could be perceived as arbitrary or unfair, weakening the trustworthiness of the admissions process. This motivates our study of deterministic algorithms and highlights its practical relevance. We will add this note to the revised paper.\n\nIn addition, characterizing the minmax rates for randomized algorithms is highly nontrivial. In Appendix E, we have constructed instances for all $\\Delta$ where the deterministic minmax bound is $\\Omega(\\Delta)$ but the randomized minmax bound is $O(\\log\\Delta)$. This reveals a super constant gap that did not exist in the non-strategic setting. \n\nOn the technical front, one of the many challenges of establishing a lower bound for randomized algorithms is that the adversary's ability to reverse-engineer the post-manipulation features to obtain pre-manipulation ones relies on “looking ahead” at the learner’s algorithm. However, if the learner uses randomness, the adversary cannot fully control which mistakes will occur or what information they provide to the learner. This challenge is deeply rooted in the information asymmetry inherent in the strategic setting.\n\n> Weakness 2: computational complexity of Algorithm 1\n\nWhile we acknowledge that Algorithm 1 can be computationally expensive to implement, we want to remark that our primary focus is on the *statistical complexity* of learning in the presence of strategic manipulations, rather than the computational complexity. It is often the case that statistically optimal algorithms become computationally intensive — this is also true in the traditional (non-strategic) setting, where the SOA algorithm that enjoys minimax optimal mistake bound is also computationally expensive, and there are even computational hardness results for learning certain classes [Hazan and Koren, STOC’16]. We believe that exploring the tradeoff between computational and statistical complexity is an interesting direction for future research.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lgmF4mxfhX", "reviewer": "Reviewer_Mb38", "summary": "The authors continue the study of strategic classification in the online setting, where an agent can manipulate the instance features to potentially force a positive prediction (governed by a manipulation graph). In the *realizable* case, the authors provide a strategic variant of the Littlestone dimension and the SOA algorithm yielding the exact instance-dependent mistake rate. This improves upon degree-dependent mistake bounds of previous work. They also consider two individual additional directions: the agnostic case and the case when the manipulation graph is unknown. In the first they improve upon existing regret bounds, while in the latter they state novel upper bounds almost matching existing lower bounds.", "questions": "How does Thm 4.1. (the agnostic regret bound) relate to Prop. 30 in Cohen et al. [2024]? Moreover, are there somewhat tight (say up to log factors) lower bounds on the agnostic regret bound? In particular is the $\\mathcal{O}(\\Delta\\cdot\\mathrm{SLdim})$ term necessary in the upper bound (Thm 4.1)? (From your remark I understood that only $\\Delta\\cdot\\mathrm{OPT}$ and $\\mathrm{SLdim}$ are known lower bounds).\n\nIs the assumption that $X$ is discrete a strong one/necessary? We can just model the \"manipulation graph\" on an arbitrary domain $X$ as a function $f:X\\to P(X)$, where $f(x)$ is the set of allowed manipulations of $x$. Are there any difficulties generalizing here?\n\nIs a \"symmetric\" setting possible where the agent can (adversarially) modify $x$ to $v\\in N[x]$ no matter the label $h(x)$?. The motivation could be that some agents want to be strategically classified as $-1$ while others as $1$.", "limitations": "The achieved agnostic regret bound is not compared to the agnostic one in Cohen et al. [2024, Prop 30], or perhaps I missed it, see question above. Please clarify as this would help to judge the novelty and strength of the result.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Well written, interesting setting, and natural continuation ob previous work. \nTight characterization of the realizable setting.\n\n--- rebuttal ---\nupdated from 6 to 7", "weaknesses": "Strength of the agnostic result is a bit unclear / open (see questions / limitations below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and the insightful comments.\n\n> Comparison of our agnostic regret bound (Thm 4.1) to that of Cohen et al. (Prop 30), and whether there are tight lower bounds\n\nThank you for your question. Our agnostic algorithm that achieves the mistake bound in Thm 4.1 only requires observing post-manipulation features after committing to a classifier at each round. In contrast, Prop 30 of Cohen et al. requires the learner to observe pre-manipulation data before choosing a classifier and then observe post-manipulation data afterwards. This makes their setting strictly easier than ours. We will add a remark about this comparison to revised versions of our paper.\n\nAbout lower bounds in the agnostic setting, we agree that both $\\Delta\\cdot\\text{OPT}$ and $\\text{SLDim}$ are valid lower bounds but it’s unclear whether the $\\Delta\\cdot\\text{SLDim}$ term is necessary. It remains an important open question to derive lower bounds for this agnostic setting.\n\n> Does the domain $\\mathcal{X}$ need to be discrete?\n\nNo, the assumption on the discrete domain $\\mathcal{X}$ is not necessary. We totally agree that our results can be immediately extended to any domain with arbitrary predefined manipulations characterized by some abstract function $f$. We will clarify this in revisions.\n\n> Symmetric setting where agents can adversarially modify their features to the neighboring features\n\nWe agree that your proposed setting is also well-motivated, though it takes a different approach compared to our work. Our focus is on strategic modifications, which can be viewed as a special case of the fully adversarial setting that you mentioned. The setting you described–where each $x$ can adversarially move to any neighbor in $N(x)$ regardless of the label–has also been explored in the adversarial robustness literature, particularly in the context of offline learning where dat appoints are sampled from a fixed distribution (see, eg, [Montasser et al., NeurIPS’22]). Another related model (also in the offline setting) that reflects your motivation is proposed by [Sundaram et al., ICML’21] which introduces another parameter $r\\in\\mathbb{R}$ that indicates how much a data point prefers label $+1$ over $-1$. In this model, a negative $r$ implies that some agent wants to be classified as $-1$ rather than $+1$. Although our current approach does not generalize immediately, we believe that it is an interesting direction to bring either model to the online learning setting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sB9bHRvqEm", "reviewer": "Reviewer_ZNn3", "summary": "This paper studies an adversarial online setting where the agents can manipulate their feature vector $x_t$ to some feature vector $x'_t$ given a graph of manipulation rules $G$. The learner observes only $x'_t$ and knows in advance $G$. \nThe usual goal is to obtain sublinear regret, with respect to some hypothesis class. In the realizable setting, this is equivalent to minimizing the number of mistakes, also known as the \"mistake bound model\". \nWhen $G$ is \"empty\", meaning there are no edges, we get the standard online model. \n\nThe main contributions are as follows: \n\nIn the realizable setting, the authors define a Littlestone tree that incorporates the manipulations and defines a notion of the Littlestone dimension for these trees. Extending to the agnostic setting, the authors use a known technique for constructing a finite \"online cover\" of the hypothesis class, and then apply an algorithm for the finite case (version of multiplicative weights update). \n\nMoreover, an extended model is introduced, where there is a finite set of manipulation graphs from which a graph is chosen. When all agents use the same graph from this set this is called the realizable case otherwise it is an agnostic setting.", "questions": "There are many parts of the paper where the writing/definitions are confusing.\n\nParagraph on the manipulation rule: $h$ denotes the classifier or the loss function? Why does it make sense to define the best response on points where $h$ returns $1$? I don't see how it compiles if it's not the loss function. \nIt's not clear if it is consistent with lines 230-235: how do you define false positive and false negative? with respect to $h$ or the loss of $h$? \n\nLine 71 ״under the respective particular parametrization״ what does it mean?\nI understand what the line afterward means, but line 71 is not clear to me.\n\nLines 94-95: \"First, to construct the set of representative challenges\". Is it a typo?\n\nMinor: \n\nLine 34: \"decision maker has little or no prior knowledge about the population being classified\", this is also the case where the learner has no prior knowledge of the distribution. \n\nSometimes the learner is also referred to as the decision maker (mostly in the intro), it's worth making it clear.", "limitations": "The limitations are addressed properly.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The results in this paper improve upon previous papers that study this question.\n\nThe techniques are clear, and the proofs are correct (as far as I checked).", "weaknesses": "My main concern about the paper is the lack of technical novelty, ideas from standard online learning translate pretty smoothly to the strategic online learning setting.\n\nThe definition of the Littlestone tree is straightforward, taking the \"strategic loss\" into account. Indeed, the upper and lower bound proofs are very similar to those of the standard Littlestone dimension and the SOA algorithm.\n\nThe ideas in the agnostic setting are also quite standard: the agnostic online learning technique of constructing a finite \"online cover\" for the class (by Ben-David et al.) and using a version of multiplicative weights on the finite class (by Ahmadi et al.).\n\nWhat is the technical contribution of this paper?\n\nThe writing of the paper could be improved. I understand why the proofs should go through, but some definitions are really confusing. \nSee the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your the detailed review and valuable feedback.\n\n> Technical contribution\n\nWe respectfully disagree that our paper lacks technical novelty because it applies ideas from standard online learning. While we build on established methodologies such as the Littlestone tree, SOA learning rules, and the agnostic-to-realizable reduction via experts, these are foundational philosophies in learning theory literature that require different technical insights when applied to different settings. An active and expanding line of work have also been applying these methodologies to understand the learnability and optimal rates in various contexts, such as the multiclass Littlestone dimension [Daniely et al., COLT’11], Natarajan-Littlestone dimension [Kalavasis et al., NeurIPS’22], the randomized Littlestone dimension [Filmus et al., COLT’23], the VC-Littlestone tree [Bousquet et al., STOC’21], to name a few. While these results share common philosophies, each presents unique technical challenges and requires new insights.\n\nIn the strategic classification context, one significant challenge for us is the information asymmetry between the learner and adversary regarding the true features before manipulation. This challenge is not addressed by previous works on non-strategic learning where the true features are always observable. Below we outline our main technical contributions in addressing these challenges:\n\n- **Structural insights.** As discussed in Lines 225-242 of Section 3, our construction of the strategic Littlestone tree accounts for the asymmetric information carried by false positives and false negatives by creating an asymmetric number of branches. We also introduce a carefully designed consistency rule to ensure realizability of the adversary’s choices.\n\n- **Lower bounds:** While constructing a sequence of post-manipulation observations that the adversary wishes to induce to the learner is straightforward, a critical challenge is in finding a realizable sequence of initial features before manipulation. We address this by combining our new consistency rule with a novel reverse-engineering technique.\n\n- **Upper bounds:** As discussed in Lines 285-290, the main challenge in proving the upper bound is to construct a classification rule that simultaneously satisfies the “progress on mistakes” property for all features in the space. Since each layer of the SL tree inspects the entire neighborhood of a certain node, one cannot optimize each node independently as in non-strategic settings. We resolve this by favoring positive labels whenever false positives decrease the SLDim, a technique also rooted in the asymmetric information carried by false positives vs negatives.\n\n- **Agnostic reduction:** As discussed in Lines 88-93, our expert set needs to effectively guess the direction from which each agent moves from. We also extend this technique to the unknown graph setting.\nWe will add a more detailed discussion about these technical challenges and contributions in the revisions of our paper.\n\n> Manipulation rule, false positives and false negatives\n\nImplicit in our model is that all agents prefer positive labels over negative labels. While we use $h$ to denote the learner’s choice of classifier, you’re correct that agents’ loss function can also be written in terms of $h$. Specifically, under classifier $h$, an agent with true features $x$ and post-manipulation features $v$ incurs a loss of $-h(v)-\\infty\\cdot\\mathbf{1}\\{(x,v)\\not\\in E\\}$, where the second term is to ensure feasibility of manipulation from $x$ to $v$. To minimize this loss, agents will choose $v$ such that $h(v)=+1$ if possible. That’s why we define the best response on nodes where $h$ return $1$. We will clarify this assumption explicitly in future versions.\n\nIf an agent $(x,y)$’s true label $y$ is negative but she manipulates her features to receive a positive classification $h(v)=+1$, the learner has made a “false-positive mistake”. In this case, the observation available to the learner is represented as the pair (agent’s observable features, agent’s true label)$=(v,-1)$. Conversely, if $y=+1$ but no neighbor of $x$ is classified as positive by $h$, the agent will not manipulate and will receive a negative label $h(x)=-1$, resulting in a “false-negative mistake”. The learner’s observations are denoted by the pair  (agent’s observable features, agent’s true label)$=(x,+1)$.\n\n> Line 71 ״under the respective particular parametrization״\n\nThank you for pointing this out, we are sorry for the confusion. What we meant is that the (near)-optimality of the mistake bounds in previous work [Cohen et al., Ahmadi et al.] are established under the assumption that the mistake bound must be parametrized as a function on the Littlestone dimension and/or the graph’s out-degree. These works show optimality in a specific instance in which the bounds cannot be improved when parameterized in these particular ways. However, these bounds are not tight for all instances, especially when the parameters such as LDim or out-degree are infinite. We will clarify this in more detail.\n\n> Typo in Lines 94-95\n\nYes, this is a typo. We meant to write “to construct the set of representative experts”.\n\n> Learner’s prior knowledge\n\nWhile it is true that in the stochastic/offline setting with an unknown distribution, the learner has no prior knowledge about the population being classified, we want to emphasize that this is still easier than our online setting because even though the distribution is unknown, the learner knows that that there exists an underlying distribution, allowing her to learn a good classifier by estimating the distribution. In contrast, in the online setting, agents are adversarially chosen on-the-fly and do not come from any prespecified distribution.\n\n> Learner vs decision maker\n\nYes, we will make it clear in future versions of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6bYHsAsvPc", "reviewer": "Reviewer_6Ry7", "summary": "This paper studies online strategic classification from a combinatorial perspective. The paper defines a new combinatorial dimension called the Strategic Littlestone dimension that jointly captures the complexity of the hypothesis class and the manipulation graph. They show that the Strategic Littlestone dimension exactly quantifies the minimax number of mistakes made by deterministic learners in the realize setting. The paper also provides improved upper bounds in the agnostic setting by modifying the classic agnostic-to-realizable reduction to handle the fact that the learner does not observe true features. Finally, the paper considers the case where the manipulation graph is not known to the learner but belongs to a family of graphs which is known to the learner. They provide bounds on the minimax value in both the realizable and agnostic settings in this case.", "questions": "-  In the case of unknown manipulations graphs, is the finiteness of the graph class necessary? Is there a joint dimension of the graph class and the hypothesis class that captures learnability and the minimax rates in this setting?\n\n- Your definition of realizability states that if $(x_1, y_1), ..., (x_T, y_T)$ is the sequence of agents chosen by the adversary, there is a hypothesis $h \\in H$ such that $h(br_{G, h}(x_t)) = y_t$. That is, the label $y_t$ agrees with the value of $h$ on the agents best-response to $x_t$ w.r.t $h$. Is this the most natural definition of realizability? What about simply requiring that $h(x_t) = y_t$ for all $t \\in [T]$. Then, perhaps the fact that the learner observes $v_t$ instead of $x_t$ but still needs to correctly predict $y_t$ can be viewed as the learner observing noisy features? It would be nice if you can comment about why you choose this particular notion of regret and realizability. \n\n- Can you comment about any known separations between deterministic and randomized learnability for strategic online classification in the realizable setting?", "limitations": "No limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow\n- The problem setting is well-motivated\n- The technical contributions are novel and improve upon existing results. In particular, I found the proof of the lowerbound in terms of the strategic Littlestone dimension to be nice.", "weaknesses": "- Lack of lower bounds. Apart from the known manipulation graph, realizable setting (Theorem 3.2), lower bounds on the minimax regret in terms of the strategic Littlestone dimension are not provided. \n\n- Lack of results for randomized learners in the realizable setting. While the authors do discuss randomized learnability, and its difficulty in the discussion section, I find it a bit unsatisfying. Without lower bounds for randomized learners, it is not clear whether the strategic Littlestone dimension characterizes realizable strategic online learnability in full generality. Meaning,  as far as I can tell, there could be a separation between deterministic and randomized realizable learnability for strategic online classification (correct me if I'm wrong here). \n\n- Deterministic learners in the agnostic setting. It is well known that in order to achieve sub linear regret in the traditional online classification setting, one needs randomization in the agnostic setting. Thus, it is a bit strange to me that the authors study/construct deterministic learners for strategic online classification in the agnostic setting. This also leaves open the question of whether the strategic Littlestone dimension characterizes agnostic online learnability. \n\n- The two points above bring into question the utility/usefulness of the strategic Littlestone dimension. Compared to say the Littlestone dimension, which not only qualitatively characterizes online learnability in the realizable and agnostic settings but also exactly quantifies the minimax rates, the same (at least as of right now), cannot be said of the strategic Littlestone dimension. As far as I can tell, the strategic Littletone dimension only characterizes deterministic realizable learnability. \n\n- Lack of intuition behind the dimension. In traditional online classification, the intuition behind needing shattered Littlestone trees is very easy from a lower bound perspective  - we just need to tell the adversary what to play for every move of the learner. However, this sort of logic does not seem to work for strategic Littlestone trees due to the need for reverse engineering. Unfortunately, I did not fully understand the intuition behind the strategic Littlestone tree from the proof sketch of the lower bound in the main text.  I had to read the full proof in the Appendix to fully understanding the structure of the strategic Littlestone tree. I think the paper can benefit from a more detailed discussion about the differences between shattered Littlestone trees and shattered strategic Littlestone trees and how the adversary should use strategic Littlestone trees to construct hard streams. In addition, I think to improve intuition, it would be nice to buff up the proof sketch of Theorem 3.2, and even better to include the full proof in the main text. \n\n- Minor: there is a typo in the second bullet point in Def. 3.1. I think it should be $N_G^{-}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed and insightful comments.\n\n> Deterministic learners in the agnostic setting\n\nOur focus on deterministic algorithms is motivated by real-world applications of strategic classification where legal or regulatory requirements often demand the learner to use deterministic algorithms. For example, in college admissions, institutions are required or expected to publish clear and transparent decision criteria, as randomization could be seen as arbitrary or unfair, weakening the trustworthiness of the admissions process.\n\nAt the technical level, our construction of representative experts (Lemma 4.3) relies on a careful coupling analysis that applies to any trajectory of classifiers chosen by the learner, regardless of whether randomness is used or not. However, for the strategic variant of the learning from expert advice algorithm, the only known agnostic algorithm (from [Ahmadi et al., EC’23]) is also deterministic, which accounts for the deterministic nature of our agnostic algorithm. Therefore, to extend this technique to randomized algorithms, one key challenge is to design randomized agnostic algorithms in the finite expert setting with at most logarithmic dependence on the size of the experts. We believe this is an interesting and non-trivial question for future research.\n\n> Finiteness of the graph class in the unknown manipulation graph setting, and joint dimension of the graph class and the hypothesis class\n\nThank you for the insightful question. While the finiteness of the graph class is necessary in the worst case scenario (see [Prop 14, Cohen et al, 2024] for a lower bound in terms of $\\log|\\mathcal{G}|$), it is not necessary for every instance. We agree that introducing a joint complexity measure for the graph class and the hypothesis class to characterize minmax rates is a valuable open question. Some technical challenges we encountered in extending our single-graph SLDim to the multi-graph setting include:\n\n- In the structure of the strategic Littlestone tree (see Lines 247-248), the set of outgoing edges from a node depends on its out-neighborhood under the manipulation graph. When dealing with a family of graphs, one might attempt to use the union of the out-neighborhood for each graph in the class. However, that causes the tree to be too wide and shallow, resulting in a dimension that is smaller than the actual minmax mistake bound. In particular, it cannot become a valid upper bound because the branches no longer reflect the true types of mistakes that the learner can possibly make.\n\n- If one keeps track of a “graph version space” and to determine the structure of the Littlestone tree, there may be a monotonicity issue. As graphs are eliminated from the graph version space, the set of feasible manipulations shrinks, which may potentially cause the tree to become thinner and deeper, thus increasing the dimension of the subgraph! This is in contrast to the monotonicity in terms of the hypothesis class which is less subtle and almost immediate from definition. \n\n> Definition of realizability and regret\n\nThanks for the question. We believe this is an important point and we will add a remark to future versions of our paper. Unlike the traditional notion of realizability that simply assumes $h(x_t)=y_t$ some $h\\in H$ across all $t\\in[T]$, we use the strategic notion of realizability that requires $h(BR_{G,h}(x_t))=y_t$. In other words, we require that a hypothesis $h\\in H$ classifies each agent correctly if the agents also best respond to $h$. We adopt this notion for several reasons:\n\n- This notion is rooted in the concepts of Stackelberg value and Stackelberg regret in game theory, which account for agents’ best responses and serve as a natural benchmark in strategic settings.\n\n- It places the learner and the optimal hypothesis on equal footing when evaluating the number of mistakes they make, unlike the standard notion of realizability which implicitly assumes that agents manipulate against the learner but not against the optimal hypothesis. \n\n- Under this strategic notion of realizability, there always exists a learning algorithm in hindsight that can achieve zero mistakes against a realizable sequence, such as when the algorithm implements the optimal hypothesis throughout. This aligns with the purpose of introducing realizability in the first place. In contrast, it is unclear that any algorithm would be able to achieve zero mistakes against a standard realizable sequence. Previous work has shown strong incompatibility between these two notions in the context of linear strategic classification setting [Chen, Liu & Podimata, NeurIPS’20].\n\n> Separations between deterministic and randomized learnability\n\nYes, we showed a separation between deterministic and randomized mistake bounds in Appendix E. Specifically, we constructed a family of instances where for each value of $\\Delta$, there exists an instance where the minmax bound for deterministic algorithms is at least $\\Delta-1$, but the minmax bound for randomized algorithms is at most $\\log\\Delta$. This class witnesses a super-constant gap between deterministic and randomized bounds, unlike their non-strategic counterparts which only differ by a factor of 2. This implies that the proposed SLDim does not characterize randomized learnability and that characterizing learnability in the randomized setting is highly nontrivial.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers are in agreement that this paper studies a well-motivated problem, and proposed a novel instance-dependent complexity notion (strategic Littlestone's dimension that depends on the hypothesis class and manipulation graph). Extensions to the agnostic setting and the unknown manipulation graph setting are deemed interesting. The rebuttal addressed many concerns of the reviewers (mainly from a clarity perspective). They are happy to recommend acceptance.
Decision: Accept (poster)