Should Decision-Makers Reveal Classifiers in Online Strategic Classification?

Thank you for your thoughtful comments. We address them below.

adversarial tie-breaking

We appreciate the reviewer’s concern and want to clarify that we do not intend to make adversarial tie-breaking a realistic behavioral assumption. Instead, we use it as a conceptual and technical intermediate step toward analyzing the more realistic setting (\gamma-Weighted) where agents cannot observe the currently implemented classifier and instead best respond to an estimate of it. As we discussed in Lines 235-251 of our manuscript, in such settings, estimation error can cause the agents to perceive one node as slightly better than the other node, even if the true classifier might assign them the same label. For example, if $\tilde h(v) = h(v)$ for all $v \in N_{out}(x)$, but $\tilde h(x) = h(x) - \epsilon$, the agent would not remain at $x$, behaving as if they are breaking ties adversarially. The purpose of Theorem 3 is precisely to highlight the mistake bound gap between the case where agents only perceive a perturbed version of the true hypothesis $h$ versus the case where they perceive $h$ perfectly. We treat adversarial tie-breaking as a proxy for incorporating such estimation errors into the mistake bound analysis, which serves as a building block towards the gamma-Weighted setting. Second, our upper bound in Theorem 4.1 holds for both tie-breaking ways. We note that our lower bound in Theorem 4.4 consists of two parts: $\min(d/\log(1/\gamma), |H|)$ and $d \cdot k_{\text{in}} \cdot k_{\text{out}}$* , where the first part still holds for the standard tie-breaking case with a slight refinement of the proof. The second part will be reduced to $d\cdot k_{\text{out}}$ in the standard tie-breaking case. The dependency on $k_{\text{in}}$ in unrevealed classifier + standard tie-breaking is left as an open problem.

*There is a typo in the original statement of Theorem 4.4, $k_{\text{in}}$ should be replaced by $k_{\text{in}} \cdot k_{\text{out}}$.

finite feature space

First, we would like to clarify that our model does not require the feature or action space to be finite: one can define a generic manipulation graph structure over any (potentially infinite or continuous) feature space by treating features as vertices and defining edges as possible manipulations. However, the learnability of an instance — in both our work and prior works [Ahmadi et al, 2023, 2024; Cohen et al, 2024] — relies on the finiteness of the maximum degree of the manipulation graph. Without the finite degree assumption, learning in infinite graphs is generally intractable. This has also been noticed by prior work eg [Shao et al, NeurIPS 2023, “Strategic Classification under Unknown Personalized Manipulation”], which shows that when the feature space is continuous and agents can manipulate to any point within a ball around the initial features, mistake bounds are usually $\Omega(|H|)$.

Second, we would like to remark that when the feature space is continuous but satisfies certain smoothness conditions, it is often possible to discretize the space and then construct a finite manipulation graph on a covering net. Our results then apply to this discretized finite graph.

realizable setting

Our goal is to study the gap between the setting where the currently implemented hypothesis is revealed and the setting where it is not. The agnostic case remains open in the literature even in the revealed classifiers setting —as also noted by reviewer MqF7. However, we believe that similar ideas as used in Algorithms 1 and 3 can be applied to the agnostic setting too.

We would like to thank the reviewer for the thoughtful comments. We address them below.

lower bound statement in Theorem 4.4

Thanks for catching the issue in the theorem statement. The lower bound in Theorem 4.4 consists of two parts: $\min( d/\log(1/\gamma), |H|)$ and $d \cdot k_{\text{in}} \cdot k_{\text{out}}$. The first bound holds for all $\gamma\in(0,1)$, and its proof is provided in Appendix B.3. The second bound emphasizes the dependency on maximum in-degree and is established only when $\gamma\to0$. Its proof follows from a modified version of that of Theorem 3.3.

We agree that the theorem statement should be more precise, and will update in revisions to clarify that the second bound is only established in the $\gamma\to0$ regime. In the following, we provide more details for this modified proof and will add them to future versions of this paper.

Consider the graph that is the same as that in Figure 2 but all nodes in the first layer (namely $x_1,x_2,\ldots,x_{k_1}$) are connected by a clique. This modification gives $k_{\text{out}}=k_1+k_2$ and $k_{\text{in}}=k_2$.

For $\gamma\to0$, best responding to $\tilde{h}^\gamma_t$ is equivalent to best responding to $h_{t-1}$. Now, we perform a case discussion of both $h_{t-1}$ — which the agent $x_t$ best responds to — and the current classifier $h_t$. We will construct an adversary that induces at least one mistake in every two rounds in the first $2k_1k_2$ rounds. Now we assume that the learner does not make a mistake at round $t-1$ and show how to induce a mistake in round $t$.

• Case 1: If $h_{t-1}$ labels $x_0$ by positive. Then if $h_t(x_0)=1$, the adversary picks $(x_t,y_t)=(x_0,0)$ and induces a false positive mistake. If $h_t(x_0)=0$, then the adversary picks $(x_t,y_t)=(x_{i^*},1)$, which manipulates to $x_0$ and induces a false negative mistake while revealing no information. These correspond to cases 1 and 2 of the proof of Theorem 3.3.

• Case 2: If $h_t$ labels any leaf node $x_{i,j}$ as positive, then the adversary picks $(x_t,y_t)=(x_{i,j},0)$. This induces a false positive mistake and removes one hypothesis. Since the learner made no mistake in round $t-1$, we can assume that $h_{t-1}$ labels all leaf nodes as negative. This case corresponds to case 4 of Theorem 3.3.

• Case 3: We are left with the case where $h_{t-1}$ labels $x_0$ and all leaf nodes as negative. Due to adversarial tie-breaking and the added clique, we can assume that all nodes in $\{x_0,x_1,\ldots,x_{k_1}\}$ manipulates to the same node $x_i$ in response to $h_{t-1}$. If $h_t(x_i)=1$, then the adversary can choose $(x_t,y_t)=(x_0,0)$ and induce a false positive mistake. If $h_t(x_i)=0$, then the adversary chooses $(x_t,y_t)=(x_{i^*},1)$ and induces a false negative mistake while revealing no information about $i^*$. This case is a modification of case 3 of Theorem 3.3 that accounts for historical best response.

We will correct this in the paper.

the phrase "With probability at least 1/3”

We allow agents to best respond to the weighted average classifier with adversarially tie-breaking in this setting and we focus on adversarially choosing the specific $x_t$ at each time. Instead of finding the worst instance among all possible cases, it is enough to show our desired instance can happen with $\Theta(1)$ probability.

agents arrive stochastically

Since we focus on mistake bounds in the realizable setting, they cannot be reduced to the VC dimension in the stochastic setting, even in standard online learning without strategic behavior. However, for regret bounds in the agnostic setting, such a reduction is possible. We believe it would be interesting to explore regret bounds in the agnostic setting, both when the classifier is revealed and when it is not.

application of Algorithm 1

Algorithm 1 has two main components: the weighted voting of experts and the choice of threshold/updating mechanism of experts. The high-level idea of weighted expert voting is fundamental and has been widely applied in many settings. Choosing a biased threshold that favors false positives is useful in scenarios where false positives and false negatives carry different amounts of information about the true hypothesis.

Novelty of our results

We would like to re-emphasize the technical novelty of our results. First, as discussed in our response to reviewers WPjm and T9UQ regarding adversarial tie-breaking, we show that when agents only observe a perturbed version of the current predictor $h_t$—rather than the exact $h_t$—the mistake bound increases by a factor of $k_\text{in}$ (see Corollary 3.2 and Theorem 3.3).

Second, in the weighted sum of history case, as the reviewer pointed out, $1/\log(1/\gamma)$ can be seen as the effective memory length of the agent. One interesting implication of this lower bound is that, in the worst case, the agent may need to “forget” its entire history—incurring $\Omega(1/\log(1/\gamma))$ mistakes—before it can make correct decisions again.

Thank you for the thoughtful comments and for examining our proofs. We address them below.

infinite/continuous feature space

First, we would like to clarify that our model does not require the feature or action space to be finite: one can define a generic manipulation graph structure over any (potentially infinite or continuous) feature space by treating features as vertices and defining edges as possible manipulations. However, the learnability of an instance — in both our work and prior works [Ahmadi et al, 2023, 2024; Cohen et al, 2024] — relies on the finiteness of the maximum degree of the manipulation graph. Without the finite degree assumption, learning in infinite graphs is generally intractable. This has also been noticed by prior work eg [Shao et al, NeurIPS 2023, “Strategic Classification under Unknown Personalized Manipulation”], which shows that when the feature space is continuous and agents can manipulate to any point within a ball around the initial features, mistake bounds are usually $\Omega(|H|)$.

Second, we would like to remark that when the feature space is continuous but satisfies certain smoothness conditions, it is often possible to discretize the space and then construct a finite manipulation graph on a covering net. Our results then apply to this discretized finite graph.

Thank you for the thoughtful comments. We address them below.

revealing the past deployed policies

We agree that the decision-maker might not want to reveal their past models explicitly. However, historical outcomes often reveal past classifiers implicitly. For example, we can observe which students were admitted by a college in previous years (based on SAT scores, GPA, extracurriculars) or which loan applicants were approved—and use this information to estimate the predictors that were likely implemented in the past. In some specific cases, the model is effectively made public: in college admissions in countries with unified entrance exams, universities often reveal the threshold classifier by publishing the minimum admission scores after each admissions cycle.

adversarial tie-breaking

We appreciate the reviewer’s concern and want to clarify that we do not intend to make adversarial tie-breaking a realistic behavioral assumption. Instead, we use it as a conceptual and technical intermediate step toward analyzing the more realistic setting (gamma-Weighted) where agents cannot observe the currently implemented classifier and instead best respond to an estimate of it. As we discussed in Lines 235-251 of our manuscript, in such settings, estimation error can cause the agents to perceive one node as slightly better than the other node, even if the true classifier might assign them the same label. For example, if $\tilde h(v) = h(v)$ for all $v \in N_{out}(x)$, but $\tilde h(x) = h(x) - \epsilon$, the agent would not remain at $x$, behaving as if they are breaking ties adversarially.

The purpose of Theorem 3 is precisely to highlight the mistake bound gap between the case where agents only perceive a perturbed version of the true hypothesis $h$ versus the case where they perceive $h$ perfectly. We treat adversarial tie-breaking as a proxy for incorporating such estimation errors into the mistake bound analysis, which serves as a building block towards the gamma-Weighted setting. Second, our upper bound in Theorem 4.1 holds for both tie-breaking ways. We note that our lower bound in Theorem 4.4 consists of two parts: $\min(d/\log(1/\gamma), |H|)$ and $d \cdot k_{in} \cdot k_{out}$* , where the first part still holds for the standard tie-breaking case with a slight refinement of the proof. The second part will be reduced to $d\cdot k_{out}$ in the standard tie-breaking case. The dependency on $k_{\text{in}}$ in unrevealed classifier + standard tie-breaking is left as an open problem.

*There is a typo in the original statement of Theorem 4.4, $k_{in}$ should be replaced by $k_{in} \cdot k_{out}$.

realizability assumption

Please see the response to reviewer T9UQ.

alternatives to revealing the model in inducing agent responses

We completely agree that there are interesting settings between the two extremes, and we see it as an exciting open direction to study the spectrum of information that may be revealed. We will add [Tsirtsis and Rodriguez 2020] to the related work section and include a discussion along these lines.

explanation for line 340

The complete proof for Lemma 4.2 is in Appendix B.2, and we’d like to provide more explanation here. At first sight, it seems that there won’t be false negative mistakes because our algorithm is very conservative. Every positive sample $x$ will always have a neighbor $u$ that is labeled as positive by $h^\star$ and $h_t$. Such $u$ is always in $BR_{\tilde{h}_t^\gamma}(x)$ and we won’t make a false negative mistake on $x$ if $x$ manipulates to this $u$. However, we argue there still can be false negative errors for one very specific scenario. That is, $x$ manipulates to another neighbor $v$ in $BR\_{\tilde{h}\_t^\gamma}(x)$ but $h\_t(v)=0$. For such a case to happen, $\tilde{h}\_t^\gamma(v)$ must be 1 to ensure that $x$ will choose to manipulate to it with non-negative probability. That means there is a $h’$ that is kept in $E$ until time $t-1$ such that $h’(v)=1$. However, $h_t(v)=0$ means that this $h’$ is not in $E$ at time $t$ so it must be removed at time $t-1$. Since we only remove a classifier when a false positive mistake occurs, the number of false negative errors is no larger than the number of false positive errors.

main idea of Algorithm 3

Algorithm 3 is a reduction to the Revealed-Adv setting, so its progress is tightly coupled with the progress of the algorithm used in the Revealed-Adv setting (Let A’ be such an algorithm, e.g., Algorithm 1). Specifically, Algorithm 3 calls A’ once every $\Phi$ mistakes it makes, so every $\Phi$ mistakes of Algorithm 3 corresponds to a single mistake made by A’. Therefore, if algorithm 3 makes recurring mistakes, then A’ must also be making recurring mistakes in the Revealed-Adv setting. However, this contradicts with the mistake bound for A’ (e.g., Corollary 3.2). Therefore, such “instability” cannot persist, and Algorithm 3 ends up having a finite mistake bound.