Strategic Classification under Unknown Personalized Manipulation

Summary

- This paper studies strategic classification with unknown and personalized manipulation in an online/distributional setting, i.e. different agents can manipulate their features to a different degree, and the learner does not know the extent to which agents can manipulate their features. - The paper assumes realizability, i.e. the existence of a correct classifier in the hypothesis class, that remains correct under strategic manipulation. Both bounds on PAC sample complexity and mistake bounds are provided for a variety of assumptions about the possible manipulations (metric ball vs nonball) and the feedback provided to the learner (original features observed before deploying classifier or not; original/manipulate/no features observed along the true label after classification). **While I remain unsure about the realistic applicability of the most interesting results, the rebuttal and others' reviews have not uncovered any new crucial weaknesses, so I am keeping my score.**

Strengths

- The paper is well written, and good intuition is provided for some of the technical theorems. - The setting of varying and unknown manipulations strength in strategic classification is relevant. - Both lower bounds and upper bounds based on concrete algorithms are provided

Weaknesses

- The motivation for the easier cases is not entirely clear. For example, in which setting is it realistic for the learner to see the *original* features of the next agent before choosing which hypothesis to deploy? - This is particularly relevant, as the more interesting results that seem clearly distinct from the previous literatur are on these easier cases. - Minor comments: - The Formatting of table 1 could be improved. In particular, some tildes are intersecting the table lines. Additionally, the third row with multiple results for slightly different settings could be further split up to avoid confusion. - If I understand correctly, it is possible for the strategic setting to be realizable for a class of hypotheses, while the non-strategic setting is not. Highlighting this might make some of the proofs (like for theorem 9) easier to parse. - I guess the tie-breaking procedure is slightly underspecified when there are multiple points at the decision boundary with the same distance from x?

Questions

- Do you expect (versions of) the proposed algorithms to still work if different players use different metrics rather than just differently sized balls for the same metric?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- The main limitations that are not discussed in the weaknesses were highlighted and discussed by the authors in the discussion/open problems section.

Summary

The paper studies strategic classification in the setting where agents generally have different power of manipulation, which is unknown to the classifier. The authors consider both the online model and the PAC model, and investigate 4 increasingly difficult settings in which the classifier observes different information about each agent. They show nontrivial regret / sample complexity upper and lower bounds for all these settings.

Strengths

The paper explores a meaningful and challenging new direction in strategic classification. The models and settings are natural and rich, and the results are fairly comprehensive (and in some cases surprising). Technically, there seem to be several interesting ideas behind the bounds.

Weaknesses

I'd be more excited to see results for infinite hypothesis classes and agonostic settings (both of which the authors discuss as future directions).

Questions

(also including detailed comments here) Footnote 1, "agents break ties randomly": do you really mean "arbitrarily"? Line 112, remark on randomized classifiers: the alternative model where agents don't observe the internal randomness of the classifier makes sense too. Any reason for choosing this particular model? Overview of results: while these results are certainly nice and important, I wonder if anything can be said in the case where $|\mathcal{H}| = \infty$. Can you comment on this (e.g., conjectures, difficulties)? (Later I see you mention this as a future direction, which sounds fair since the paper already has quite a number of results.) Line 240: why is "GALLANT" all capitalized? General technical question: how crucial is the metric space assumption? In other words, what if the triangle inequality doesn't hold? I guess at least some of your positive results still hold?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

n/a

Summary

The paper studies strategic classification where a sequence of agents, given information about decision rule, may manipulate their features strategically to receive favorable decisions. The goal of the learner is to find a hypothesis that minimizes the number of mistakes through sequential interaction with agents. In addition to conventional strategic classification where agents manipulate their features within a bounded radius ball, this paper also considers personalized manipulation where agents can only manipulate the features belonging to a manipulation set that is unknown to the learner. For both scenarios, it provides the mistake bounds and PAC sample complexity under several settings: 1) when original features are revealed to the learner before choosing the hypothesis and manipulated features after, 2) when both original and manipulated features are revealed after choosing the hypothesis, 3) when only manipulated features are revealed after choosing hypothesis, 4) neither original nor manipulated features are revealed.

Strengths

1. Establishing mistake bounds and sample complexity is an important topic in strategic classification, this can be challenging especially when agent features before/after manipulation are unknown to the learner. 2. The paper considered many settings comprehensively, from a simpler setting when both original and manipulated features are revealed to the learner, to a more complex setting when neither is known to the learner. 3. Section 3 (Overview of the results) is very helpful

Weaknesses

1. The presentation and some statements can be misleading and confusing. The authors emphasized in the abstract/introduction that one prime difference between the present paper and the prior works is that this paper considers personalized manipulation with non-ball manipulations. However, the majority of the paper still focuses on conventional settings with ball manipulations. It can be misleading as I expect more results on non-ball manipulations after reading the abstract. 2. The paper needs more literature review and discuss the differences with prior works to show the novelty. The paper introduced the existing works on regret bound in strategic learning very briefly, e.g., (Ahmadi et al., 2021), (Ahmadi et al., 2021). It seems they also considered mistake bound under uniform, unknown manipulations. Moreover, there are many other works studying PAC learning for strategic classification and conducting sample complexity analysis, e.g., [1,2,3]. I think a large body of related works is missing and authors should elaborate more on these works and discuss differences with the present paper. [1] Sundaram, R., Vullikanti, A., Xu, H., & Yao, F. (2021, July). Pac-learning for strategic classification. In International Conference on Machine Learning (pp. 9978-9988). PMLR. [2] Zhang, H., & Conitzer, V. (2021, May). Incentive-aware PAC learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 6, pp. 5797-5804). [3] Lechner, T., & Urner, R. (2022, June). Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 7, pp. 7337-7344).

Questions

It is not clear to me how the present model captures the personalized manipulations (i.e., different manipulation abilities across agents). Based on my understanding, the authors assume there exists a pre-defined manipulation set $u$ that constrains agents' ability to manipulate. Agents choose to manipulate only if such a manipulation set overlaps the positive region of the predictor, and they would break ties randomly. By personalization, do you mean the manipulation set differs across agents? It seems that the manipulation set $u$ is the same and fixed over time. Should not this manipulation set depends on the predictor? Why break ties randomly? It is very hard for me to interpret this model. It would be helpful if authors can link the model to a real example.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors discussed the limitations, but the potential negative societal impact is not discussed.

Summary

The paper explores a setting of strategic classification - where agents respond to deployed predictive policies by potentially manipulating their feature vector so as to achieve positive predictions. The authors explore this setting while allowing agent manipulations to be personalized (no assumptions regarding same manipulation budget across agents, etc.), and also do not assume that the learner knows the manipulation power of the agent ahead of time. The authors assume realizability - that the incoming agents and their labels are consistent with some "true" underlying concept h* in the concept class. They consider different variants of an online classification problem - based on whether the original/manipulated feature vector of the agent is revealed, and when are they revealed - before/after the learner selects its predictor. In these four settings, the authors give upper and lower bounds for mistakes (in a potentially adversarial setting), as well as sample complexity for PAC learning (In a stochastic data generation setting).

Strengths

The paper offers a "complete story" in the context of an interesting sub-problem in strategic manipulation (where the true label cannot change) in realizable, online settings. I liked the framework the authors present to capture the feasible manipulation region for each agent, which abstracts away the cost function/budget in an elegant manner. I also like that the authors operate under the fact that the learner does not know how agents would manipulate. The division to revealing the original/manipulated features before/after the classification also makes a lot of sense and is a nice way of thinking about manipulation settings (where the true label is unaffected by such changes). In terms of results/techniques - the idea of leveraging the ball structure of feasible manipulation area to order concepts by distances and allow for bisecting the version space is pretty neat. The results for the setting where both the original and manipulated features are revealed after the predictor is picked are even more interesting (especially the algorithm and sample complexity for improper learning). The paper is overall very well-written, and seems sound (although I have just looked, and not carefully read the appendix).

Weaknesses

I find the realizability assumption rather strong, in the following sense - as it is written in line 139, realizability in this paper is defined with respect to the manipulated features, i.e. there exists a concept h* which is the one giving the "true" labels for all of the manipulated features. But this, in turn, depends on the manipulations, which are personalized. This degree of circularity makes it a bit hard to think of how can we pick H ahead of time such that h* is present, without potentially having H to be of very large complexity, or otherwise restricting the personalized nature of the manipulations to some degree. But maybe this is inevitable for such general model of manipulation. I think it is implicitly assumed that given agent x, the personalized manipulation is fixed (there can't be another agent with the same features, and different manipulation profile). If so, maybe it is worth noting in the main text. Across the main text, the authors claim that prior work in strategic classification has not entailed personalized manipulation power for agents (e.g. line 375). This is inaccurate - see e.g. Bechavod et al. 2021.

Questions

I found it a bit difficult to follow example 1 in the main text. For example, if H is singletons over [n], how can f_t be all-negative? Also, could you clarify the definition of the metric - is it that distances from 0 to other nodes are 1, and all other distances are 2? Regardless, could you provide a more detailed explanation of the dynamics presented in this example?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors properly discuss limitations in the main text.

Summary

This paper studies an online learning problem where the learner interacts with a strategic agent in the following way: the learner chooses a hypothesis from a hypothesis class; the agent, after observing the chosen hypothesis, can manipulate its feature vector to be within some ball of unknown and personalized radius to obtain a positive prediction. The paper considers various settings (adversarial online and distributional online) and various feedback models (what feedback does the learner observe before and after its decision). The paper provides mistake bounds (upper and lower) (for the adversarial online setting) and sample complexity bounds (for the distributional online setting) for all feedback models.

Strengths

* The paper is well-written - it is clear and easy to follow. It also includes proof sketches and intuitions behind the results and proofs. * The paper studies an interesting online learning model and does a comprehensive job of modelling various types of feedback. * Algorithms 1 and 2 build on classic ideas but are cleverly modified for the problem being studied. * Theorem 7 about conservative algorithms is very interesting.

Weaknesses

* This paper studies the setting of a finite hypothesis class and in the realizable setting. Extensions to a general hypothesis class (with an appropriate combinatorial measure) and the agnostic case would really enhance the value of the paper. (Note - the authors point out these avenues for future work in the conclusion.)

Questions

* Is the definition of "conservative algorithms" (in section 4.3) a well-known concept? It certainly makes a lot of sense. I am wondering whether that formalism already exists or not. If not, do you have thoughts on how this could be used elsewhere in online learning for lower bounds?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Limitations: adequately addressed. Negative societal impact: this is theoretical paper and I don't see any direct negative impacts arising from this work.

Response to authors

I wish to thank the authors for their response. After reading the response, I tend to leave my original score unchanged.