Bayesian Strategic Classification

Thank you for these questions, we will now respond in detail.

The model (while the model in the paper makes sense, I'm also curious about other natural ways to model the problem, e.g., the learner could commit to a (possibly restricted) distribution over classifiers and hide the realization from the agent(s). Is there anything interesting we can say about such alternative models? Is there a reason to focus on the particular model in this paper? In particular, I guess one potential criticism of the current model is that, given enough time, agents will eventually figure out the actual classifier being used (e.g., in the same way that they come up with the prior distribution).):

While working with randomized classifiers is an interesting direction for future work, it is still susceptible to the same criticism of the reviewer: over time the agents will be able to learn what distribution the learner is using and best respond according to that. Also, in practice, it may be undesirable for a learner to constantly change their deployed classifier, both because it is costly but also because it may be perceived as unreliable or unfair.

We believe our model is a natural and simple first attempt towards understanding incomplete information in strategic classification. Having said that, we completely agree with the reviewer that the use of randomized models is an interesting direction for future work, as we have mentioned it in the limitations section: “... However, we note that changing the screening algorithm requires significant resources, and the rate at which the classifier is updated is generally slower than the rate at which decisions are made. In practice, this means that strategic agents effectively face a fixed model in each “batch” between updates.”

Line 168, “truthfully” (I'm a bit unsure about the wording here. In particular, the posterior of the agents is generally misleading. More generally, there seems to be a mismatch between what the agents know about the learner and how they behave -- the agents have no reason to believe that the classifier being used is distributed according to the posterior. I wonder what the authors think about this.):

We call it truthful because we require that the learner includes its deployed classifier $h$ in the shortlist $H$. In other words, we don’t allow the learner to `lie’ to the agents. Moreover, after releasing $H$, regardless of what the common prior distribution $\pi$ is, the probability of $h$ in the posterior $\pi \vert_H$ can only increase.

We note that the behavior of our agents follow a traditional Bayes update, the natural model used for updating informational beliefs in the vast majority of related game theory and in particular Bayesian Persuasion [3] literature. Truthfulness and believing that the learner is truthful are also the standard assumption in settings involving information revelation [3], with the motivation that these games are played in a repeated context where lying is observable and punishable in the long-term.

Def 2.2 (this will probably become clear soon, but is h part of the learner's action? It sounds like it's not, but then why do you say this is a generalization of the full information release game?):

The reviewer is correct that if $h$ is not the strategic optimal classifier (i.e., one that maximizes the strategic accuracy in the full information release game), this will not be a generalization of the full information release game. We will clarify it in the final version of the paper.

We assume that $h$ is fixed and the learner is not willing to change it due to cost issues: as mentioned in the paper, “... However, we note that changing the screening algorithm requires significant resources, and the rate at which the classifier is updated is generally slower than the rate at which decisions are made”.

We further note that in the case where the fixed $h$ is the strategic optimal classifier in the full information release game (i.e. “standard” strategic classification), our game essentially becomes a generalization of the full information release game because the learner can always choose $H=\{h\}$.

Line 314, $h \ge f$: notation abused here. Remark 4.2 explains the notational abuse that we adopt for simplicity. We simply view $f$ (or $h$) both as a function and their corresponding real-valued threshold, so $h \ge f$ simply means that the threshold for $h$ is larger than or equal to the threshold for $f$.

Sec 4: why not publish $h = f + 1$ (in this setup, why shouldn't the learner simply publish the exact optimal classifier ($h = f + 1$, which is perfectly accurate after manipulation)? I guess this is also where fixing h as an input parameter makes less sense.):

Releasing $h=f+1$ is not necessarily an optimal or even a feasible solution because in general the space of thresholds is bounded (which is natural because test scores are normally bounded, and so must be the thresholds we work with on those test scores). Observe that this is shown in Example 2.4.

[3] Kamenica, Emir, and Matthew Gentzkow. "Bayesian persuasion." American Economic Review 101, no. 6 (2011): 2590-2615.

Thank you for these detailed comments which we shall now do our best to answer!

Part 1

Interaction model, true relation between features and labels is known to the learner:

This is an assumption made in prior work on strategic classification (e.g. see [2,4]). That being said, extending our results to a setting in which the learner only has access to labeled examples is an interesting future work.

Agents’ prior distribution is known to the learner: This is a common assumption in Bayesian Persuasion and in game-theoretic Bayesian settings, e.g., [1].

From a motivational point of view, for example, employers also have access to job interview questions dataset such as Glassdoor when hiring, and may have a good understanding of the information available to the agents. This prior can also encode agents having a very simple prior showing understanding top few features that are commonly known, which is reasonable in settings such as credit scoring (where everyone knows most agents understand that paying on time has a positive impact, for example). There are also natural cases where we can assume that the prior is uniform, corresponding to the agents having no prior information revelation in other Bayesian settings (e.g., active learning [5], the last section on pg. 2.).

Assuming that $\pi$ has finite support:

We will include this extension in the final version of the paper: note that one can often discretize the space of possible classifiers to reduce to a finite setting. We do note that only our results in Section 3 rely on finiteness, but small cardinality is not required, so discretization is sufficient for our purposes. We have complemented our results in Section 4 which primarily focuses on discrete uniform priors by considering the case of continuous uniform priors (which have infinitely many elements in their support); see Section D.2 in the Appendix for details.

Regarding the discretization approach for Section 3, note that if $\pi$ has infinite support size, we can ignore classifiers with sufficiently small probabilities (i.e., $poly(\epsilon)$), as they do not affect the manipulation strategy when searching for a $(1+\epsilon)$-approximate solution. The number of classifiers in the support with probability at least $poly(\epsilon)$ for a fixed $\epsilon>0$ is at most $1/poly(\epsilon)$ which is a finite number. Therefore, to obtain a nearly optimal solution, it suffices to only consider probability distributions $\pi$ with finite support size.

Also, observe that finite $\pi$ captures broad phenomena already, like job interview questions on sites like Glassdoor/Leetcode.

Common prior in practical setting (1. What could be reasonable assumptions for the functional form of the common prior $\pi$ in practical settings? 2. How can $\pi$ be estimated from data? 3. In which plausible practical scenarios does the size of $\pi$'s support induce a practically-significant discrepancy between efficient and inefficient algorithms?):

1. In Section 4.1, we think of the prior as uniform over a set; this can be seen as initially having no information about the classifier, thinking all classifiers are equally likely on the support (the support itself could encode information about what reasonable classifiers are). This can be easily estimated from data. If there is any prior knowledge (e.g., 0.1 fraction of technical interview questions involve dynamic programming questions), we assume the prior incorporates this knowledge.

2. Estimating $\pi$ from data is a good question. In some of the more specific settings that exist in practice, like humans adapting to high stakes test/interview questions, humans do maintain tables of counts over the discrete range of possible questions, and then create the prior by dividing the count for each question by the normalization term, e.g. summing over all counts. E.g. when people take a test they then share this information with their peers who also have access to the database.

3. It is an interesting question thinking about the impact of $\pi$ on efficient/inefficient algorithms in practice. This question will require further work.

Dishonest information disclosure How much power can the learner gain from acting in a non-truthful way?

We restrict to truthful information disclosure as in Bayesian Persuasion [3]. Relaxing this requirement obviously extends the action space of the learner and hence can only increase the learner’s utility. Here is an example in which lying to the agents can achieve optimal utility for the learner: consider a case in which $X = [0,1]$, $D$ is uniform over $X$, and $f(x)=1[x \geq 0.5]$ is the ground truth and $h=f$ is the deployed classifier. If the learner lies to the agents and tells them that the deployed classifier is $h’(x)=1$ (i.e. everyone is qualified), regardless of what the prior distribution of the agents is, no one will manipulate. The learner can then deploy $f$ for optimal accuracy.

Part 2:

Can truthful information sharing (by the learner) can be enforced or incentivized?:

Here, we highlight the typical argument in Bayesian Persuasion: if the learner is not truthful, over time, the learner will lose credibility and will not be trusted by the agents anymore. As a result the agents will simply ignore the information coming from the subset release and will base their response according to the prior, which could then become sub-optimal for the learner. We also emphasize that in the applications that we consider in our paper (such as hiring, loans, etc.), while the learner does not need to reveal their model fully, the learner could face legal and ethical challenges if they choose to misrepresent the model for their own favor.

Estimating the feature-label distribution from samples (instead of knowing the distribution) (What are the consequences of the learner not knowing the feature-label distribution $D$, and being required to estimate it from data?):

Given a data set sampled $i.i.d.$ from the distribution, the learner can find the optimal subset $H$ with respect to the data set and then appeal to standard generalization guarantees to argue that the same subset is (approximately) optimal with respect to the distribution, provided that the sample size is large enough. We note that while this gives only a sketch of the extension from knowing $D$ to having only a sample from $D$, the exact characterization of the sample complexity requires careful analysis and considerations.

What is the complexity of H, i.e., cardinality of H? (Can the analysis framework be used to estimate the typical cardinality/"complexity" of the optimal hypothesis sets $H$ reported by the learner? Is there intuition for practical scenarios where a non-trivial $H$ is expected to be "simple to describe" or particularly complex in some sense?):

Our analysis and examples show that the optimal partial information $H$ could in fact be any subset of the hypothesis class. It is not clear to us whether the size of the optimal $H$ can be estimated. Example 2.1 in the paper shows a set of examples in which a subset $H$ is “simple to describe” (like releasing the “relevant features” of the deployed classifier), but we note that such examples for partial information release are not necessarily optimal for the learner.

[1] Kremer, Ilan, Yishay Mansour, and Motty Perry. “Implementing the ‘Wisdom of the Crowd.’” Journal of Political Economy 122, no. 5 (2014): 988–1012. https://doi.org/10.1086/676597.

[2] Yahav Bechavod, Chara Podimata, Steven Wu, Juba Ziani. “Information Discrepancy in Strategic Learning”. Proceedings of the 39th International Conference on Machine Learning, PMLR 162:1691-1715, 2022.

[3] Kamenica, Emir, and Matthew Gentzkow. "Bayesian persuasion." American Economic Review 101, no. 6 (2011): 2590-2615.

[4] Mark Braverman and Sumegha Garg. 2020. The Role of Randomness and Noise in Strategic Classification. In Foundations of Responsible Computing (FORC) (LIPIcs, Vol. 156).

[5] Dasgupta, S. (2004). Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17.

Thank you for this review, we will now respond in detail.

Positive results seem to be under strong constraints. This may imply that the problem itself is very difficult:

A challenging aspect of work in strategic classification theory, along with other fields in ML is that with minimal assumptions, many problems are intractable.

For instance, we show that the learner’s optimal information release problem is NP-hard when the agents’ prior can be arbitrary, and a similar result is exhibited in the first strategic classification paper [Hardt et al. 2016].

That said, despite such hardness barriers, adding some assumptions to relax the problem is important so we can investigate specific challenges, craft initial algorithms that then can be used as a foundation for later empirically performant algorithms.

Role of the oracle: Description of the oracle: the oracle solves the following “projection” problem: given an agent $x$ with cost function $c$, a collection of classifiers $\{h_1, \ldots, h_n\}$, and a binary (0/1) vector $b=(b_1, \ldots, b_n)$, the oracle returns a point $z$ that minimizes the cost $c(x,z)$ for the agent such that for all $i$, $h_i (z) = b_i$. Instead of using the binary vector $b$, in our paper we adopt $R^+$ (classifiers whose corresponding $b_i$ is $1$) and $R^-$ (classifiers whose corresponding $b_i$ is $0$). Note that when $n=1$, this is simply projecting the point $x$ onto either $\{h_1(z) = 1\}$ or $\{h_1(z) = 0\}$, according to the cost function $c$. When $n>1$, this is the projection of $x$, according to the cost function $c$, onto one of the $2^n$ regions created by the $n$ classifiers (each classifier has a positive and a negative region) which we denote by $R^+ \cap R^-$. Informally, the oracle abstracts out the task of finding the closest point, w.r.t. a given cost function, to a given point (an agent), that passes only the classifiers in $R^+$ without passing the classifiers in $R^-$ (or equivalently a point in $R^+ \cap R^-$ because we require to pass exactly ones corresponding to $R^+$ and nothing more)..

Why we use an oracle: we need an oracle model because solving the best response problem in Equation 1 may span a large class of potential deployed classifiers, prior distribution $\pi$, and cost function $c$, and specialized optimization techniques are required for each problem class. In our setting, we want to focus on the details of information release so by assuming the oracle model we can isolate the impact of the information release, while abstracting away the agent’s ability to solve the best response problem which is tangential to our point. This allows our assumptions to model a range of agents using different optimization methods to solve Equation 1; further, we can plug in a large class of optimization methods in place of the oracle as needed for specific applications.

Re Question about Remark 4.3: By “harder”, we mean that the classifier $h$ is more stringent and harder to pass, in that it uses a higher threshold than the true classifier $f$. The reason we need to do so is because the agents’ ability to manipulate their features allows them to obtain a higher perceived score than their true score. The learner needs to make the classifier more difficult to pass to compensate for this strategic behavior and inflated scores. This is relatively standard in strategic classification, where the classifier is “pushed to the right” to be robust to manipulation.

We thank the reviewer for suggesting interesting questions that can be natural future directions of this work such as other utility functions and dynamic environments.

• Regarding the performance of partial information release versus full information release, while we have examples where one outperforms the other, the exact characterization of instances in which one outperforms the other is not known. This is indeed an interesting question.

• For any $n$ and $d$, the best response algorithm for linear classifiers (Algorithm 2) has oracle complexity of $\sum_{j=0}^d {n \choose j}$ which is $O(n^d)$ for $d \ll n$ and $O(2^n)$ for $d \approx n$. This is why we need that the dimension is relatively small compared to $n$.