Bayesian Strategic Classification

Authors: lee  cohen
saeed  sharifi-malvajerdi
kevin  stangl
ali  vakilian
juba  ziani
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 00:27:58

Abstract: In strategic classification, agents modify their features, at a cost, to obtain a positive classification outcome from the learner’s classifier, 
typically assuming agents have full knowledge of the deployed classifier. In contrast, we consider a Bayesian setting where agents have a common distributional prior on the classifier being used and agents manipulate their features to maximize their expected utility according to this prior.
The learner can reveal truthful, yet not necessarily complete, information about the classifier to the agents, aiming to release just enough information to shape the agents' behavior and thus maximize accuracy. We show that partial information release can counter-intuitively benefit the learner’s accuracy, allowing qualified agents to pass the classifier while preventing unqualified agents from doing so. Despite the intractability of computing the best response of an agent in the general case, we provide oracle-efficient algorithms for scenarios where the learner’s hypothesis class consists of low-dimensional linear classifiers or when the agents’ cost function satisfies a sub-modularity condition. 
Additionally, we address the learner’s optimization problem, offering both positive and negative results on determining the optimal information release to maximize expected accuracy, particularly in settings where an agent’s qualification can be represented by a real-valued number.

Main paper: 
 introduction: 
 Machine Learning critically relies on the assumption that the training data is representative of the unseen instances a learner faces at test time. Yet, in many real-life situations, this assumption fails when individuals (agents) manipulate decision-making algorithms for personal advantage, by modifying their features at a cost. A typical example of such manipulations or strategic behavior is seen in loan applications or credit scoring: for example, an individual may open new credit card accounts to lower their credit utilization and increase their credit score artificially. In the context of job interviews, a candidate can spend time and effort to memorize solutions to common interview questions and potentially look more qualified than they are at the time of an interview. A student might cram to pass an exam this way without actually understanding or improving their knowledge of the subject.The prevalence of such behaviors has led to the rise of an area of research known as strategic classification. Strategic classification, introduced by Hardt et al. [2016] , aims to understand how a learner can optimally modify decision making algorithms to be robust to such strategic manipulations of agents, if and when possible.Most of the strategic classification literature makes the assumption that the model deployed by the learner is fully observable by the agents, granting them the ability to optimally best respond to the learner using resources such as effort, time, and money. Yet, this full information assumption can be unrealistic in practice. There are several reasons for this: some machine learning models are proprietary and hide the details of the model to avoid leaking "trade secrets": e.g., this is the case for the credit scoring algorithms used by FICO, Experian, and Equifax. 1 Some classifiers are simply too complex in the first place to be understood and interpreted completely by a human being with limited computational power, such as deep learning models. Other classifiers and models may be obfuscated for data privacy reasons, which are becoming an increasingly major concern with new European consumer protection laws such as GDPR [Regulation, 2018] and with the October 2023 Executive Order on responsible AI [Biden, 2023] . In turn, there is a need to study strategic classification when agents only have partial knowledge of the learner's model.There has been a relatively short line of work trying to understand the impact of incomplete information on strategic classification. Jagadeesan et al. [2021] and Bechavod et al. [2021] study the optimal classifiers in settings where agents can only gain partial or noisy information about the deployed model. Haghtalab et al. [2023] study calibrated Stackelberg games, a more general form of strategic classification; in their framework, the learner engages in repeated interactions with agents who base their actions on calibrated forecasts about the learner's classifier. They characterize the optimal utility of the learner for such games under some regularity assumptions. While we also model agents with prior knowledge of the learner's actions, Haghtalab et al. [2023] focus on an online learning setting and the selection of a strategy for the learner without incorporating any form of voluntary information release by the learner.In contrast, we focus on this additional critical aspect of voluntary information release by the learner that these works do not study. Namely, we ask:How to release partial and truthful information about the classifier to maximize accuracy?This should give the reader pause: why should a learner release information about their deployed classifier since presumably such information only makes it easier for agents to manipulate their features and "trick" the learner. In fact, Ghalme et al. [2021] showed that information revelation can help-a learner may prefer to fully reveal their classifier as opposed to hiding it. While they consider either fully revealing the classifier or completely hiding it, our model considers a wider spectrum of information revelation that includes both "full-information-release" and "no-information-release". We show that there exist instances where it is optimal to reveal only partial information about the classifier, in a model where a learner is allowed to reveal a subset of the classifiers containing the true deployed classifier. For example, a tech firm might reveal to candidates that they will ask them about a new type of data structure during their job interviews. Lenders might reveal to clients that they do not consider factors like credit score [Lake, 2024] . This selective disclosure can discourage unfit individuals, ultimately saving time and energy for both sides. In the following, we summarize our contributions.• In Section 2, we propose a new model of interactions between strategic agents and a learner, under partial information. The two novel modeling elements compared to the standard strategic classification literature are: i) agents have partial knowledge about the learner's classifier in the form of a distributional prior over the hypothesis class, and ii) the learner can release partial information about their deployed classifier. Specifically, our model allows the learner to release a subset of the hypothesis class to narrow down the agents' priors. Given our model, we consider a (Stackelberg) game between agents with partial knowledge and a learner that can release partial information about its deployed model. On the one hand, the agents aim to manipulate their features, at a cost, to increase their likelihood of receiving a positive classification outcome. On the other hand, the learner can release partial information to maximize the expected accuracy of its model, after agent manipulations. • In Section 3, we study the agent's best response in our game. We show that while in general, it is intractable to compute the best response of the agents in our model, there exist oracle-efficient algorithms 2 that can exactly solve the best response when the hypothesis class is the class of low-dimensional linear classifiers. We then move away from the linearity assumption and consider a natural condition on the agents' cost function for which we give an oracle-efficient approximation algorithm for the best response of the agents for any hypothesis class.• In Section 4, we study the learner's optimal information release problem. We consider screening/classification settings where agents are represented to the learner by a real-valued number that measures their qualification level for a certain task. Prior work has focused on similar onedimensional settings in the context of strategic classification; see, e.g., [Beyhaghi et al., 2023, Braverman and Garg, 2020] . We first show that the learner's optimal information release problem is NP-hard when the agents' prior can be arbitrary. In light of this hardness result, we focus on uniform prior distributions and provide closed-form solutions for the case of continuous uniform priors, and an efficient algorithm to compute the optimal information release for discrete uniform priors.• We finally consider alternative utility functions that are based on false positive (or negative) rates for the learner and provide insights as to what optimal information release should look under these utility functions, without restricting ourselves to uniform priors.Related Work. Strategic classification was first formalized by Brückner and Scheffer [2011] , Hardt et al. [2016] . Hardt et al. [2016] is perhaps the most seminal work in the area of strategic classification: they provide the first computationally efficient algorithms (under assumptions on the agents' cost function) to efficiently learn a near-optimal classifier in strategic settings. Importantly, this work makes the assumption that the agents fully know the exact parameters of the classifier due to existing "information leakage", even when the firm is obscuring their model. Hardt et al. [2016] also do not consider a learner that can release partial information about their model.Closest to our work, Jagadeesan et al. [2021] , Ghalme et al. [2021] , Bechavod et al. [2022] , and Haghtalab et al. [2023] relax the full information assumption and characterize the impact of opacity on the utility of the learner and agents. Jagadeesan et al. [2021] are the first to introduce a model of "biased" information about the learner's classifier: instead of observing the learner's deployed classifier exactly, agents observe and best respond to a noisy version of this classifier; one that is randomly shifted (by an additive amount) from the true deployed classifier.In contrast, Ghalme et al. [2021] and Bechavod et al. [2022] consider models of partial information on the classifiers, where agents can access samples in the form of historical (feature vector, learner's prediction) pairs. More precisely, Ghalme et al. [2021] study what they coin the "price of opacity" in strategic classification, defined as the difference in prediction error when not releasing vs fully releasing the classifier. They are the first to show that this price can be positive (in the context of strategic classification), meaning that a learner can reduce their prediction error by fully releasing their classifier in strategic settings. Our work considers more general, intermediate forms of information release, instead of the all-or-nothing, binary approach of Ghalme et al. [2021] . Bechavod et al. [2022] consider a strategic regression setting in which the learner does not release their regression rule, but agents have access to (feature, score) samples as described above. They study how disparity in sample access (e.g., agents may only access samples from people similar to them) about the classifier across different groups induce unfairness in classification outcomes across these groups. Haghtalab et al. [2023] consider agents with (calibrated) forecasts over the actions of the learner, but do not consider the learner's information release which is our focus. Additionally, in our model, we do not constrain the agent's prior distribution to be calibrated.Beyond strategic classification, there are a few related lines of work where such partial information is considered. One is Bayesian Persuasion [Kamenica and Gentzkow, 2011] : in Bayesian persuasion, the state of the world is randomly drawn from the prior, and there is a mapping from the state of the world to signal distributions. This mapping, i.e. the "signaling scheme", must be revealed to the agents in addition to the signal. In our setting, there is a fixed state of the world (the learner's classifier), and there is no need for the signaling scheme to be known, since the signal itself (the subset) reveals all the information needed for the agents. The agents only need to know that the learner is truthful, which is an assumption made in Bayesian persuasion too.Relatedly, algorithmic recourse studies an "intermediate" information release problem where the learner publishes a recommended action or recourse for each agent to take, rather than a set of potential classifiers used by the learner; e.g., Harris et al. [2022] . In our model, we release the same signal or information to all agents based on the underlying distribution over these agents' features.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Our introduction provides a summary of contributions that accurately reflect the new model and the results of this paper, with pointers to specific sections. Our model is introduced in Section 2, and Sections 3, 4 contain all formal statements and their proofs.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
model: 
 Our model consists of a population of agents and a learner. Each agent in our model is represented by a pair (x, y) where x ∈ X is a feature vector, and y ∈ {0, 1} is a binary label. Throughout, we call an agent with y = 0 a "negative", and an agent with y = 1 a "positive". We assume there exists a mapping f : X → {0, 1} that governs the relationship between x and y; i.e., y = f (x) for every agent (x, y). We will therefore use x to denote agents from now on. We denote by D the distribution over the space of agents X . Agent manipulations are characterized by a cost function c : X × X → [0, ∞) where c(x, x ′ ) denotes the cost that an agent incurs when changing their features from x to x ′ . We assume, similar to standard strategic classification settings, that manipulation does not change one's true label: manipulation is seen purely as "gaming"; it does not change the qualification of an agent. Let H ⊆ {0, 1} X denote our hypothesis class, and let h ∈ H be the fixed classifier that the learner is using for classification.A Partial Knowledge Model for the Agents. We move away from the standard assumption that agents fully know h and model agents as having a common (shared by all agents) prior distribution π over H. This distribution captures their initial belief about which classifier is deployed by the learner. Formally, for every h ′ ∈ H, π(h ′ ) is the probability that the learner is going to deploy h ′ for classification from the agents' perspective. We emphasize that the learner is committed to using a fixed classifier h. The prior π captures the agents' belief about the deployed classifier and is known to the learner.For example, job seekers may use Glassdoor to prepare for interviews. They may not know the exact hiring algorithm (h) of a specific company but can observe patterns from other companies for similar roles. This forms their initial belief, represented by π, about the classifier a company might use. Thus, π captures the agents' probabilistic beliefs rather than assuming full knowledge of h.3 A Partial Information Release Model for the Learner. The learner has the ability to influence the agents' prior belief π about the deployed classifier h by releasing partial information about h. We model information release by releasing a subset H ⊆ H such that h ∈ H. We note that we reveal information truthfully, meaning that the deployed classifier is required to be in H.Note that this is a general form of information release because it allows the learner to release any subset of the hypothesis class, so long as it includes the deployed classifier h. H = {h w,b : w = [w 1 , w 2 , . . . , w d ] ⊤ ∈ R d + , b ∈ R} where h w,b (x) ≜ 1[w ⊤ x + b ≥ 0]and x ∈ X = R d is the feature vector. Let h = h w0,b0 be the classifier deployed by the learner for some w 0 , b 0 . Under this setting, revealing the corresponding parameter of a feature, say x j , in h corresponds to releasing H 1 = {h w,b ∈ H : w j = w j 0 } (e.g., 'minimal GPA of 3.8 for grad school'). Revealing the top k features of h (e.g., the most significant class grades are algorithms and calculus) corresponds to releasing H 2 = {h w,b ∈ H : w i1 , w i2 . . . , w i k are the k largest coordinates of w}. Let I 0 be such that w i 0 ̸ = 0 iff i ∈ I 0 . Revealing the relevant features of h, i.e. features with nonzero coefficients (e.g., sensitive attributes like race or gender will not be used in the decision) corresponds to releasing H 3 = {h w,b ∈ H : w i ̸ = 0, ∀i ∈ I 0 }. This is a common form of information release in the real world4 .The Strategic Game with Partial Information Release. Once the partial information H is released by the learner, agents best respond as follows: each agent first computes their posterior belief about the deployed classifier by projecting their prior π onto H, which we denote by π| H , and is formally defined by: ∀h′ ∈ H, π| H (h ′ ) ≜ π(h ′ ) π(H) 1[h ′ ∈ H].Given this posterior distribution, the agent then moves to a new point that maximizes their utility. The utility is quasi-linear and measured by theh 1 (= f ) h 2 h 3 x 1 1 0 0 x 2 0 1 0 Table 1: Hypothesis class H in Example 2.3probability (according to π| H ) of receiving a positive outcome minus the manipulation cost. Formally, the utility of agent x that manipulates to x ′ , under the partial information H released by the learner is given by uEQUATIONWe let BR(x, H) denote the best response of agent x, i.e. a point x ′ that maximizes u x (x ′ , H). 5 The goal of the learner is to release H that includes its deployed classifier h so as to maximize its utility which is measured by its expected strategic accuracy.EQUATIONDefinition 2.2 (Strategic Game with Partial Information Release). The game, between the learner who is using h ∈ H for classification, and the agents who have a prior π over H, proceeds as follows:1. The learner (knowing f , D, c, π) publishes a subset of hypotheses H ⊆ H such that h ∈ H.x best responds by moving to a point BR(x, H) that maximizes their utility:BR(x, H) ∈ argmax x ′ ∈X u x (x ′ , H).The learner's goal is to find a subset H ⋆ ⊆ H with h ∈ H ⋆ , that maximizes its utility6 :H ⋆ ∈ argmax H⊆H, h∈H U (H)We note that similar to standard strategic classification, the game defined in Definition 2.2 can be seen as a Stackelberg game in which the learner, as the "leader", commits to her strategy first and then the agents, as the "followers", respond. The optimal strategy of the learner, H ⋆ , corresponds to the Stackelberg equilibrium of the game, assuming best response of the agents.Contrasting with the Standard Setting of Strategic Classification. The game defined in Definition 2.2 not only captures both the partial knowledge of the agents and the leaner's partial information release, but can also be viewed as a generalization of the standard strategic classification game where the agents fully observe the classifier h, which we refer to as the full information release game (e.g., see [Hardt et al., 2016] ). This is because the learner can always choose H = {h}. Next, we ask:Can partial information release increase the learner's utility compared to full information release?Observe that by definition, U (H ⋆ ) ≥ U ({h}), i.e., the learner can only gain utility when they optimally release partial information instead of fully revealing the classifier. In the following examples, we show that there exist instantiations of the problem where U (H ⋆ ) > U ({h}), even when h is picked to be the optimal classifier in the full information release game, i.e., one that maximizes U ({h}). In other words, we show that the learner can gain nonzero utility by releasing a subset that is not {h}, even if the choice of h is optimized for the full information release game.Example 2.3 (Partial vs. Full Information Release). Suppose X = {x 1 , x 2 }, and that their probability weights under the distribution7 are given by D(x 1 ) = 2/3, D(x 2 ) = 1/3, and their true labels are given by f (x 1 ) = 1, f (x 2 ) = 0. Suppose the cost function is given as follows: c(x 1 , x 2 ) = 2, c(x 2 , x 1 ) = 3/4. Let H = {h 1 , h 2 , h 3 } be given by table 1 . One can show that under this setting, h = h 1 is the optimal classifier under full information release, i.e., it optimizes U ({h}), and that for such h, U ({h}) = 2/3. However, suppose the prior distribution over H is uniform. One can show that under this setting, and when h = h 1 is the deployed classifier, releasingH ⋆ = {h 1 , h 2 } implies U (H ⋆ ) = 1 > U ({h}) = 2/3.In other words, the learner can exploit the agent's prior by releasing information in a way that increases its own utility by a significant amount.Algorithm 1: Oracle(c, H)Input: agent x, region R = R + ∩ R -specified as, R + = ∩ i∈I + {z : hi(z) = 1} and R -= ∩ i∈I -{z : hi(z) = 0}for some I + and I -. Output: argmin z∈R c(x, z)In the next example, we consider the more natural setting of single-sided threshold functions in one dimension and show that the same phenomenon occurs: the optimal utility achieved by partial information release is strictly larger than the utility achieved by the full information release of h, even after the choice of h is optimized for full information release. Example 2.4 (Partial vs. Full Information Release). Suppose X = [0, 2], D is the uniform distribution over[0, 2], f (x) = 1 [x ≥ 1.9], H = {h t : t ∈ [0, 2]} where h t (x) ≜ 1 [x ≥ t].Suppose the cost function is given by the distance c(x, x ′ ) = |x -x ′ |. We have that under this setting, the optimal classifier in H under full information release is h = h 2 , and that its corresponding utility is U ({h}) = 1 -Pr x∼U nif [0,2] [1 ≤ x < 1.9] = 0.55. Now suppose the agents have the following prior over H:π(h ′ ) = 0.1 • 1[h ′ = h 2 ] + 0.9 • 1[h ′ = h 1.8 ].Under this setting, and when h = h 2 is deployed for classification, one can see that releasing H ⋆ = {h 2 , h 1.8 } leads to perfect utility for the learner. We therefore have U (H ⋆ ) = 1 > U ({h}) = 0.55.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: See Section A.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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
the agents' best response problem: 
 In this section we focus on the best response problem faced by the agents in our model, as described in Definition 2.2. We consider a natural optimization oracle for the cost function of the agents that can solve simple projections. We will formally define this oracle later on. Given access to such an oracle, we then study the oracle complexity8 of the agent's best response problem. First, we show that the best response problem is computationally hard even for a common family of ℓ p -norm cost functions. Next, we provide an oracle-efficient algorithm9 for solving the best response problem when the hypothesis class is the class of low-dimensional linear classifiers. In Appendix B, we consider submodular cost functions and show that for any hypothesis class, there exists an oracle-efficient algorithm that approximately solves the best response problem in this setting.Recall that the agents' best response problem can be cast as the following: given an agent x ∈ X , and a distribution P (e.g., P = π| H where π is the prior and H is the released information) over a set {h 1 , . . . , h n } ⊆ H, we want to solve argmax z∈X {Pr h ′ ∼P [h ′ (z) = 1] -c(x, z)}. We consider an oracle that given any region R ⊆ X , specified by the intersection of positive (or negative) regions of h i 's, returns the projection of the agent x onto R according to the cost function c: argmin z∈R c(x, z). For example, when H is the class of linear classifiers and c(x, z) = ∥x -z∥ 2 , the oracle can compute the ℓ 2 -projection of the agent x onto the intersection of any subset of the linear halfspaces in {h 1 , . . . , h n }. We denote this oracle by Oracle(c, H) and formally define it in Algorithm 1.Having access to such an oracle, and without further assumptions, the best response problem can be solved by exhaustively searching over all subsets of {h 1 , . . . , h n } because:EQUATIONThis algorithm is inefficient because it makes exponentially many oracle calls. In what follows, we consider natural instantiations of our model and examine if we can get algorithms that make only poly(n) oracle calls. All missing proof of this sections are provided in Appendix C.p-Norm Cost Functions. First, we consider Euclidean spaces and the common family of p-norm functions for p ≥ 1 and show that even under the assumption that the cost function of the agent belongs to this family, the problem of finding the best response is computationally hard. Formally, a p-norm cost function is defined by: for everyx, x ′ ∈ R d , c p (x, x ′ ) = ∥x -x ′ ∥ p where p ≥ 1. Theorem 3.1. Ω(2 n / √ n)calls to the oracle (Algorithm 1) are required to compute the best response of an agent with 2/3 probability of success, even when X = R 2 and the cost function is c p for p ≥ 1.Algorithm 2: Best Response of Agents in the Linear Case Input: agent x, cost function c, arbitrary distribution P over linear classifiers {h1, . . . , hn}Step 1. Compute the partitioning (Rn) of the space given by {h1, . . . , hn};Initialize R1 ← {{z : h1(z) = 1}, {z : h1(z) = 0}}; for i = 2, . . . , n do Ri ← Ri-1; for R ∈ Ri-1 do if {z : hi(z) = 0} ∩ R ̸ = ∅ then Ri ← Ri \ R ; // Remove R Ri ← Ri ∪ {{z : hi(z) = 1} ∩ R, {z : hi(z) = 0} ∩ R} ; // Split R Step 2. Given Rn, compute the best response; for R ∈ Rn do Let R = R + ∩ R -where R + = ∩ i∈I + {z : hi(z) = 1} and R -= ∩ i∈I -{z : hi(z) = 0};Call the oracle (Algorithm 1) to solve zR ∈ argmin z∈R c(x, z); Compute the utility of zR: utility(zR) = i∈I + P (hi) -c(x, zR); Output: argmax z∈Z utility(z) where Z = {zR : R ∈ Rn} Low-Dimensional Linear Classifiers. Next, we show that when X = R d for some d, and when H contains only linear classifiers, i.e., every h ∈ H can be written as h(x) = 1 w ⊤ x + b ≥ 0 for some w ∈ R d and b ∈ R, then the best response of the agents can be computed with O(n d ) oracle calls when d ≪ n.The algorithm, which is described in Algorithm 2, first computes the partitioning (R n ) of the space X given by the n linear classifiers. For any element of the partition in R n , it then solves the best response when we restrict the agent to select its best response from that particular element. This gives us a set of points, one for each element of the partition. The algorithm finally outputs the point that has maximum utility for the agent. This point, by construction, is the best response of the agent. The oracle-efficiency of the algorithm follows from the observation that n linear halfspaces in d dimensions partition the space into at most O(n d ) elements when d ≪ n. Formally, Theorem 3.2. Suppose X = R d for some d ≪ n, and H contains only linear classifiers. Then for any agent x, any cost function c, and any distribution P over {h 1 , . . . , h n } ⊆ H, Algorithm 2 returns the best response of the agent in time O(n d+1 ), while making O(n d ) calls to the oracle (Algorithm 1).In Theorem 3.2 we require the distribution P be over {h 1 , . . . h n } ⊆ H, e.g. to have finite support.When this does not hold, ie. P has infinite support size, we can ignore classifiers with sufficiently small probabilities (i.e., poly(ϵ)), as they do not affect the manipulation strategy when searching for an (1 + ϵ)-approximate solution. The number of classifiers in the support with probability at poly(ϵ) for a fixed ϵ > 0 is at most 1/poly(ϵ) which is a finite number. Therefore, to obtain a nearly optimal solution, it suffices to only consider probability distributions with finite support size.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [NA] .Justification: This is a theoretical paper. All results are carefully proven, and do not require experiments to establish correctness.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
the learner's optimal information release problem: 
 In this section we focus on the learner's optimization problem as described in Definition 2.2. The learner is facing a population of agents with prior π and wants to release partial information H ⊆ H so as to maximize its utility U (H). We note that the learner's strategy space can be restricted to the support of the agents' prior π because including anything in H that is outside of π's support does not impact U (H). Therefore, one naive algorithm to compute the utility maximizing solution for the learner is to evaluate the utility on all subsets H ⊆ support(π) and output the one that maximizes the utility. However, this solution is inefficient; instead, can we have computationally efficient algorithms? We provide both positive and negative results for a natural instantiation of our model which is introduced below.The Setup: Classification Based on Test Scores. We adopt the following setup for the learner's information release problem. We are motivated by screening problems such as school admissions and hiring where an individual's qualification level can be captured via a real-valued number, say, a test score. We therefore consider agents that live in the one dimensional Euclidean space: X = [0, B] ⊆ R for some B. One can think of each x as the corresponding qualification level or test score of an agent where larger values of x correspond to higher qualification levels or higher test scores. As we are in a strategic setting, agents can modify their true feature x and "game" the learner by appearing more qualified than they actually are.We let f (x) = 1 [x ≥ t] for some t: there exists some threshold t that separates qualified and unqualified agents. We take the hypothesis class H to be the class of all single-sided threshold classifiers: every h ′ ∈ H can be written as h ′ (x) ≜ 1 [x ≥ t ′ ] for some t ′ . We further take the cost function of the agents to be the standard distance metric in R: c(x, x ′ ) = |x ′ -x|. 10 Remark 4.1. We emphasize that considering agents in the one-dimensional Euclidean space is only for simplicity of exposition. We basically assume, for an arbitrary space of agents X , there exists a function g :X → [0, B] such that f (x) = 1[g(x)≥ t] for some t, and that the cost function is given by c(x, z) = |g(z) -g(x)|. Here, g(x) captures the qualification level or test score of an agent x. Now observe that we can reduce this setting to the introduced setup of this section: takeX ′ = {g(x) : x ∈ X } ⊆ [0, B], f : X ′ → {0, 1} is given by f (x ′ ) = 1[x ′ ≥ t],and that the cost function c :X ′ × X ′ → [0, ∞) is given by c(x ′ , z ′ ) = |z ′ -x ′ |.Remark 4.2. Note that because every classifier h ′ ∈ H is uniquely specified by a real-valued threshold, for simplicity of our notations, we abuse notation and use h ′ interchangeably as both a mapping (the classifier) and a real-valued number (the corresponding threshold) throughout this section. The same abuse of notation applies to f as well.The classifier deployed by the learner is some h ≥ f . We note that it is natural to assume h ≥ f because in our setup, higher values of x are considered "better". So given the strategic behavior of the agents, the learner only wants to make the classification task "harder" compared to the ground truth f -choosing h < f will only hurt the learner's utility. Because we will extensively make use of the fact that h ≥ f , we state it as a remark below. Remark 4.3. The learner's adopted classifier is some h ∈ H such that h ≥ f . First, we show that under the introduced setup, the learner's optimization problem is NP-hard if the prior can be chosen arbitrarily. This is shown by a reduction from the NP-hard subset sum problem. The formal NP-hardness statement and its proof, as well as further useful facts about the agents' best response under this setup are in Appendix D.Given the hardness of the learner's problem for arbitrary prior distributions, we focus on a specific family of priors, namely, uniform priors over a given set, and examine the existence of efficient algorithms for such priors. In Appendix D.2, we consider continuous uniform priors and provide closed form solutions for the learner's optimal partial information release problem.In this section, we provide an efficient algorithm for computing the learner's optimal information release when the prior π is a discrete uniform distribution over a set {h 1 , h 2 , . . . , h n } ⊆ H that includes the adopted classifier h. Here, the objective of the learner is to release a subset H ⊆ {h 1 , h 2 , . . . , h n } such that h ∈ H. Throughout, we take h = h k where 1 ≤ k ≤ n, and assume h 1 ≤ h 2 ≤ . . . ≤ h n . The complete exposition of this section, including all details, proofs, necessary lemmas, and the description of the proposed algorithm, can be found in Appendix E.We first characterize the utility of any subset H released by the learner using a real-valued function of H. Define, for anyH ⊆ {h 1 , . . . , h n } such that h ∈ H, R H ≜ inf {x : BR(x, H) ≥ h}(4) Note that BR(x = h, H) ≥ h for any H such that h ∈ H. Therefore, {x : BR(x, H) ≥ h} is nonempty, and that R H ≤ h for any H such that h ∈ H. In the following lemma, we show that R H characterizes the utility of H for the learner, for any prior π over {h 1 , . . . , h n }. Lemma 4.4. Fix any prior π over {h 1 , . . . , h n }. We have that for any H ⊆ {h 1 , . . . , h n } such that h ∈ H, the utility of the learner, given by Equation 2, can be written asU (H) = 1 -Pr x∼D [R H < x < f ] R H < f 1 -Pr x∼D [f ≤ x ≤ R H ] R H ≥ f (5)10 Our results can be extended to the case where c(x, x ′ ) = k|x ′ -x| for some constant k.Given such characterization of the learner's utility by R H , we show that when the agents' prior is uniform over {h 1 , . . . , h n }, there are only polynomially many possible values that R H can take, even though there are exponentially many H's. We characterize the set of possible values for R H as well.For any possible value R of R H , our algorithm efficiently finds a subset H such that R H = R, if such H exists, and finally outputs the one with maximal utility.More formally, we consider the following partitioning of the space of subsets of {h 1 , . . . , h n }. For any ℓ ∈ {1, 2, . . . , n}, and for any i ∈ {k, k + 1, . . . , n}, define S i,ℓ ≜ {H ⊆ {h 1 , . . . , h n } : h ∈ H, |H| = ℓ, BR(h, H) = h i } Note that BR(h ≡ h k , H) ∈ {h i : i ≥ k}U (H) = max i,ℓ max H∈S i,ℓ U (H)Given this partitioning of the space, we show that R H can be characterized as follows.Lemma 4.5. If the prior π is uniform over {h 1 , . . . , h n }, then for anyH ∈ S i,l , R H = h i -j/ℓ where j = |{h ′ ∈ H : h ′ ∈ (R H , h i ]}|.Given such characterization, our proposed algorithm (Algorithm 3), for any i, ℓ, enumerates over all possible j ∈ {1, . . . , ℓ} and returns a H such that H ∈ S i,ℓ and R H = h i -j/ℓ, if such H exists. The algorithm then outputs the subset H with maximal utility according to Equation 5. Theorem 4.6. There exists an algorithm (Algorithm 3) that for any n, any uniform prior over {h 1 , . . . , h n } that includes h, and any data distribution D, returnsH ⋆ ⊆ {h 1 , . . . , h n } in time O(n 3) such that h ∈ H ⋆ , and that U (H ⋆ ) = max H⊆{h1,...,hn},h∈H U (H).While so far we worked with accuracy as the utility function of the learner, in this section, we consider other natural performance metrics and provide insights on the optimal information release for the proposed utility functions, without restricting ourselves to uniform priors. In particular, we consider utility functions that are based on False Negative Rate (FNR) and False Positive Rate (FPR) which are formally defined below. For any H ⊆ H such that h ∈ H,EQUATIONIn the following theorem, we establish that for any given prior π over a set {h 1 , h 2 , . . . , h n } ⊆ H, if the learner aims to minimize the FPR, no-information-release is preferable to full-informationrelease.11 Additionally, we show that for minimizing the FNR, an optimal strategy for the learner is full-information-release. By "no-information-release", we mean releasing any subset H such that H includes the support of the prior π: H ⊇ {h 1 , . . . , h n } which results in π| H = π.By "full-information-release", we mean revealing the classifier: H = {h}. Theorem 4.7. Fix any h ≥ f . For any prior π over {h 1 , . . . , h n } that includes h, we have 1)F P R(H) ≤ F P R({h}). 2) F N R({h}) ≤ F N R(H) for every H ⊆ H such that h ∈ H.The proof is provided in Appendix F. In Appendix G, we show that minimizing FPR, unlike minimizing FNR, does not always have a clear optimal solution. We provide three instances such that full-information-release is optimal for the first, no-information-release is optimal for the second, and neither is optimal for the third. 
conclusion: 
 We introduce Bayesian Strategic Classification, meaning strategic classification with partial knowledge (of the agents) and partial information release (of the learner). Our model relaxes the often unrealistic assumption that agents fully know the learner's deployed classifier. Instead, we model agents as having a distributional prior on which classifier the learner is using. Our results show the existence of previously unknown intriguing informational middle grounds; we also demonstrate the necessity of revisiting the fundamental modeling assumptions of strategic classification in order to provide effective recommendations to practitioners in high-stakes, real-world prediction tasks.A Limitations, and Broader Impacts, and Future WorkLimitations Potential limitations of our model are the following:• We assume the agents' prior is realizable, in the sense that the classifier deployed by the learner is in the support of the prior. This is a standard assumption in machine learning works, and it will be interesting to relax it in future works.• The learner, in order to decide on the optimal level of information release, must know the agents' prior. This assumption, while common in related settings like Bayesian persuasion, may be unrealistic in practice; although, in real-life, the learner may have an imperfect idea of or be able to partially recover the agents' priors from previous interactions with them. Beyond this, we note that in practice, different agents may also have different beliefs and priors about the learner's model; this can affect the way the learner should release information, given that this information release may affect different users differently.• A limitation of this model is that it assumes the learner must commit to a fixed classifier in advance. In real-life, classifiers are dynamically updated over time, using the additional information obtained from each decision. 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.• If agents know the prior distribution D and the mapping f from feature vectors to labels, they might infer information regarding h * when |H| > 1. We show an example of such a case in Appendix H.Broader Impacts On the plus side, our approach provides a deeper understanding of strategic behavior in machine learning settings, when strategic agents may not fully understand the deployed model. By doing so, we are taking the understanding of strategic classification one step closer to real life, providing useful insights on how much information a learner should provide about their model to prevent model manipulation and gaming.One potential negative impact is that our approach takes the point of view of the learner who is solely interested in maximizing his own accuracy (or utility). It is well-known that this focus on accuracy can lead to unfairness and disparate harms across different populations; further, prior work studying fairness in the standard strategic classification setting [Hu et al., 2019 , Milli et al., 2019] and in a related partial information setting [Bechavod et al., 2022] have shown that strategic classification can amplify these disparities.Future Work [Hu et al., 2019 , Milli et al., 2019] consider disparities across different groups due to differing cost functions. In our model of strategic classification, different population groups may not only have differing cost functions but also differing prior distributions: network homophily, social disparities, and stratification can cause population groups to have distinct priors, leading to further disparities across groups. In turn, it will be critical in future work to design fairness-aware information release strategies by a learner faced with strategic behavior. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] .Justification: This is a theoretical paper. All results are carefully proven, and do not require experiments to establish correctness.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 a 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. 
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 is a theoretical paper. All results are carefully proven, and do not require experiments to establish correctness.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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: We note that our work is in nature theoretical and we are not directly deploying new algorithms or technologies. However, our theory provides algorithms and insights that are motivated by and can be translated to practical applications such as loan decisions. As such, we discuss potential broader impacts in Section A, both positive and negative.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] .Justification: The work is entirely theoretical; we do not release new data or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] .Justification: We do not use existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] .Justification: The 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/model 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. 
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 as details about compensation (if any)?Answer: [NA] .Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor 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 NeurIPS 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. 
 
 Appendix: In this section we give a sufficient condition on the cost function under which we can give an approximation algorithm for the best response of the agents. In particular, for a given collection of classifiers V ⊆ H, we introduce the notion of V -submodular cost functions which is a natural condition that can arise in many applications. Borrowing results from the literature on submodular optimization, we then show that for any distribution P over a set V = {h 1 , . . . , h n }, if the cost function is V -submodular, there exists an oracle-efficient approximation algorithm for the best response problem. Recall, from Equation (3), that the best response problem faced by agent x can be written as max S⊆{h1,...,hn} g x (S) ≜ h ′ ∈S P (h ′ ) -c(x, S) where, with slight abuse of notation, we define c(x, S) ≜ minEQUATIONFor any S ⊆ {h 1 , . . . , h n }, c(x, S) is simply the minimum cost that the agent x has to incur in order to pass all classifiers in S, and can be computed via the oracle (Algorithm 1). We now state our main assumption on the cost function: Definition B.1 (V -Submodularity). Let V = {h 1 , . . . , h n } be any collection of classifiers. We say a cost function c is V -submodular, if for all x, the set function c(x, •) : 2 V → R defined in Equation 8is submodular: for every S, S ′ ⊆ V such that S ⊆ S ′ and everyh ′ / ∈ S ′ , c (x, S ∪ {h ′ }) -c (x, S) ≥ c (x, S ′ ∪ {h ′ }) -c (x, S ′ )This condition asks that the marginal cost of passing the new classifier h ′ is smaller when the new classifier is added to S ′ versus S, for any such h ′ , S, S ′ . Fix a collection of classifiers V . Informally speaking, a cost function is V -submodular if the agent's manipulation to pass a classifier only helps her (i.e., reduces her cost) to pass other classifiers: the more classifiers the agent passes, it becomes only easier for her to pass an additional classifier. This can happen in settings where some of the knowledge to pass a certain number of tests is transferable across tests. Some real-life examples include: 1) a student that is preparing for a series of math tests on topics like probability, statistics, and combinatorics. 2) a job applicant who is applying for multiple jobs within the same field and preparing for their interviews.We give a formal example of a V -submodular cost function below. In particular, we show that when X = R, the cost function c(x, x ′ ) = |x -x ′ | is V -submodular where V can be any set of single-sided threshold classifiers. Claim B.2. Let X = R, and V = {h 1 , . . . , h n } where every h i can be written ash i (x) = 1[x ≥ t i ] for some t i ∈ R. We have that the cost function c(x, x ′ ) = |x -x ′ | is V -submodular.Proof of Claim B.2. We will abuse notation and use h i for the thresholdt i (h i ≡ t i ∈ R). Fix any x. Consider S ⊆ S ′ ⊆ {h 1 , . . . , h n } and h ′ ∈ R such that h ′ / ∈ S ′ . Note that c(x, S) = max (max(S) -x, 0) , c (x, S ∪ {h ′ }) = max (max(S ∪ {h ′ }) -x, 0) c(x, S ′ ) = max (max(S ′ ) -x, 0) , c (x, S ′ ∪ {h ′ }) = max (max(S ′ ∪ {h ′ }) -x, 0)where max(F ) is simply the largest threshold in F , for any set F . Note that max(S) ≤ max(S ′ ) because S ⊆ S ′ . Suppose x ≤ max(S). We have three cases1. If h ′ ≥ max(S ′ ), then c (x, S ∪ {h ′ }) -c (x, S) = h ′ -max(S) ≥ h ′ -max(S ′ ) = c (x, S ′ ∪ {h ′ }) -c (x, S ′ ) 2. If max(S) ≤ h ′ ≤ max(S ′ ), then c (x, S ∪ {h ′ }) -c (x, S) = h ′ -max(S) ≥ 0 = c (x, S ′ ∪ {h ′ }) -c (x, S ′ ) 3. If h ′ ≤ max(S), then c (x, S ∪ {h ′ }) -c (x, S) = c (x, S ′ ∪ {h ′ }) -c (x, S ′ ) = 0So we have shown that the cost function is submodular if x ≤ max(S). We can similarly, using a case analysis, show that the cost function is submodular when x > max(S).We now state the main result of this section. Theorem B.3. Fix any H and any distribution P over some V = {h 1 , . . . , h n } ⊆ H. If the cost function c is V -submodular, then there exists an algorithm that for every agent x and every ϵ > 0, makes Õ(n/ϵ 2 ) calls to the oracle (Algorithm 1) and outputs a set Ŝ ⊆ V such that g x ( Ŝ) ≥ max S⊆V g x (S) -ϵ.Proof of Theorem B.3. Note that when the cost function is V -submodular, the objective function g x can be written as the difference of a monotone non-negative modular function12 and a monotone non-negative submodular function: g x : 2 V → R, g x (S) = h ′ ∈S P (h ′ ) -c(x, S). The result then follows from [El Halabi and Jegelka, 2020] where they provide an efficient algorithm for approximately maximizing set functions with such structure.Theorem 3.1. Ω(2 n / √ n) calls to the oracle (Algorithm 1) are required to compute the best response of an agent with 2/3 probability of success, even when X = R 2 and the cost function is c p for p ≥ 1.Proof of Theorem 3.1. To prove the claim, we reduce the following hidden-set detection problem with EQUALTO(•) oracle to our best response problem. In hidden-set detection problem, given two players, Alice and Bob, with Bob possessing a 'hidden' subset S ⋆ ⊆ [n] of size n/2, Alice aims to identify Bob's set S ⋆ using the minimum number of queries to Bob. She has query access to EQUALTO(T ) oracle that checks whether her set T ⊂ [n] matches Bob's set (S ⋆ ). It is trivial that any randomized algorithm for the hidden-set detection problem with success probability of at least 1 -O(1) requires n n/2 queries in the worst-case scenario. This is via a straightforward application of Yao's Min-Max principle Yao [1977] : consider a uniform distribution over all subsets of size n/2 from [n], as the Bob's set. Then, after querying half of the subsets of size n/2, the failure probability of Alice in detecting Bob's set is at least(1-1/n)(1-1/(n-1)) • • • (1-1/(n/2)) > (1-2/n) n/2 > e -1 (1-2/n) > 1/3for sufficiently large values of n.Next, corresponding to an instance of the hidden-set detection problem with S ⋆ , we create an instance of the agents' best response problem and show that any algorithm that computes the best response with success probability at least 2/3 using N oracle calls (Algorithm 1), detects the hidden set of the given instance of the hidden-set detection problem using at most N calls of EQUALTO(•) with probability at least 2/3. Hence, computing the best response problem with success probability at least 2/3 requires n n/2 = Ω(2 n / √ n) oracle calls.Let n = 2k and ϵ < 1/n. Corresponding to every subset S ⊂ [n] of size n/2 -1, there is a distinct point x S at distance 1/2 -ϵ from the origin, i.e., ∥x S ∥ p = 1/2 -ϵ. Corresponding to every subset S ⊂ [n] of size n/2, there are two distinct points x S,n and x S,f at distances respectively 1/2 -ϵ (near) and 1/2 + ϵ (far) from the origin, i.e., ∥x S,n ∥ p = 1/2 -ϵ and ∥x S,f ∥ p = 1/2 + ϵ.Now, we are ready to describe the instance I S ⋆ of our best response problem corresponding to the given hidden-set detection problem with S ⋆ . We define H = {h 1 , • • • , h n } and distribution P over H such that,• P is a uniform distribution over all classifiers H, i.e., P (h i ) = 1/n for every i ∈ [n].• For every subset T ⊂ [n] of size n/2 -1, we defineh i (x T ) = 1[i ∈ T ].• For every subset T ⊂ [n] of size n/2, we defineh i (x T,f ) = 1[i ∈ T ]. Moreover, if T ̸ = S ⋆ , then h i (x T,n ) = 0 for all i ∈ [n]. Otherwise, if T = S ⋆ , we define h i (x T,n ) = 1[i ∈ T ].• Finally, for the remaining points in X , i.e.,x ′ ∈ R 2 \ ({x T : T ⊂ [n] and |T | = n/2 -1} ∪ {x T,n , x T,f : T ⊂ [n] and |T | = n/2}), we define h i (x ′ ) = 0 for all i ∈ [n].In other words, points that do not correspond to subsets of size n/2 -1 or n/2 are classified as negative examples by every classifier in H.In the constructed instance I S ⋆ , no point is classified as positive by more than n/2 classifiers in H, and the p-norm distance from the origin for all points classified as positive by a subset of classifiers is at least 1/2 -ϵ. Therefore, the best response for an agent located at the origin of the space is x S ⋆ ,n , yielding a utility of 1/2 -(1/2 -ϵ) = ϵ > 0. Hence, the computational task in computing the best response involves identifying the (hidden) subset S ⋆ . Refer to Figure 1 for a description of I S * .Although we described the construction of I S ⋆ , what we need to show to get the exponential lower bound on the oracle complexity of the best response problem is constructing an oracle (i.e., an implementation of Algorithm 1), using the EQUALTO(•) oracle, consistent with I S ⋆ . To do so, given a subset of classifiers specified by T ⊂ [n], the oracle returns as follows:• if |T | > n/2: It returns an empty set.• if |T | < n/2: It returns x T ′ for an arbitrary set T ′ ⊇ T of size n/2-1. Note that ∥x T ′ ∥ p = 1/2-ϵ.• if |T | = n/2 and EQUALTO(T ) = FALSE: It returns x T,f . Note that ∥x T,f ∥ p = 1/2 + ϵ.Figure 1: In this example, we consider p = 2, i.e., c(x, x ′ ) = ∥x, x ′ ∥ 2 . The agent is located at the origin. Blue nodes correspond to a point in the intersection of the positive regions of subsets of classifiers of size n 2 -1, each located at a Euclidean distance of 1/2 -ϵ from the origin, where ϵ is a small positive value. Moreover, points in the intersection of the positive regions of subsets classifiers of size n 2 are indicated by red points, all except the one corresponding to S ⋆ are located at a Euclidean distance of 1/2 + ϵ from the origin. The red point corresponding to S ⋆ is uniquely placed at a distance of 1/2 -ϵ from the origin, similar to the blue nodes. Furthermore, all points, corresponding to different subsets, are located at distinct locations in the space.• if |T | = n/2 and EQUALTO(T ) = TRUE: It returns x T,n . Note that ∥x T,n ∥ p = 1/2 -ϵ.Remark C.1. As in each instance I S ⋆ the only point with strictly positive utility is x S * ,n , our proof for Theorem 3.1 essentially rules out the existence of any approximation algorithm for the best response problem with success probability at least 2/3 using o(2 n / √ n). (n, d) ≤ R(n -1, d) + R(n -1, d -1).The first term on the right hand side is the number of regions induced by {h 1 , . . . , h n-1 } and the second term is the number of splits (dividing a region into two) when h n is introduced. Note that {z : h n (z) = 0} is a d -1-dimensional hyperplane and the number of splits induced by h n is simply the number of regions induced by {h 1 , . . . , h n-1 } on {z :h n (z) = 0}, which is R(n -1, d -1). The recursive relationship implies that |R n | = R(n, d) ≤ d j=0 n j = O(n d ).We first state a remark about the tie-breaking of agents' best response problem: Remark D.1. As mentioned in the model section, when there are several utility-maximizing solutions for the agents, we always break ties in favor of the lowest cost solution. Furthermore, each agent x in our setup manipulate only to larger values of x (x ′ ≥ x); this is formally stated in the first part of Lemma D.2. Therefore, the tie-breaking of agents is in favor of smaller values of x ′ in our setup. In other words, given some released information H, an agent x chooses BR(x, H) = min argmaxx ′ ≥x u x (x ′ , H) (9)In the rest of this section, when we write argmax x ′ ≥x u x (x ′ , H), we implicitly are taking the smallest x ′ ≥ x that maximizes the utility of the agent x.Next, we state some useful facts about the agents' best response in our setup. Lemma D.2. Fix any prior π and any points x 2 ≥ x 1 . We have that, for any H ⊆ H,1. BR(x 1 , H) ≥ x 1 . 2. BR(x 2 , H) ≥ BR(x 1 , H). 3. If BR(x 1 , H) ≥ x 2 , then BR(x 1 , H) = BR(x 2 , H).Proof of Lemma D.2. Fix any x, and any H. We haveBR(x, H) = argmax x ′ Pr h ′ ∼π| H [x ′ ≥ h ′ ] -|x ′ -x| = argmax x ′ ≥x Pr h ′ ∼π| H [x ′ ≥ h ′ ] -(x ′ -x) = argmax x ′ ≥x Pr h ′ ∼π| H [x ′ ≥ h ′ ] -x ′ = argmax x ′ ≥x g H (x ′ )where we take gH (x ′ ) ≜ Pr h ′ ∼P | H [x ′ ≥ h ′ ] -x ′ .The first equality follows because agents do not gain any utility by moving to a point x ′ < x, and that tie-breaking is in favor of lowest cost solution.The first and the second part of the lemma follows from this derivation. For the third part, we haveBR(x 1 , H) = argmax x ′ ≥x1 g H (x ′ ) = argmax x ′ ≥x2 g H (x ′ ) = BR(x 2 , H)where the second equality follows because BR(x 1 , H) ≥ x 2 .In this section, we formally state the NP-hardness of the learner's optimization problem in the general setting.Theorem D.3. Consider an arbitrary prior π over a set of threshold classifiers {h 1 , h 2 , . . . , h n } ⊆ H that includes h. The problem of finding H ⊆ {h 1 , h 2 , . . . , h n } so that h ∈ H and the learner's utility U (H) is maximized is NP-hard.Proof of Theorem D.3. The proof is via a reduction from the subset sum problem. In particular, we consider a variant of the subset sum problem in which we are given a set of n positive numbers a 1 , • • • , a n , and the goal is to decide whether a subset S ⊂ [n] such that i∈S a i = T := (1/2) i∈[n] a i exists.Given an instance of the subset sum problem with input({a 1 , • • • , a n }, T := (1/2) i∈[n] a i ),we construct the following instance of our problem with one-dimensional threshold classifiers. Definef (x) = 1 [x ≥ 0], h(x) = 1 [x ≥ 2/3], and h i (x) = 1 [x ≥ 100 + i] for every i ∈ [n]. Moreover, suppose that the prior distribution of the agents π is given by: π(h) = 1/2 and for every i∈ [n], π(h i ) = a i /(4T ). Note that π(h) + i π(h i ) = 1.Let the data distribution D be the uniform distribution over [-1000, 1000] .Intuitively speaking, the inclusion of h i 's in H have no direct effect on the accuracy of the released subset H, as they can only lead to a subset of the agents located at x ≥ 100 to manipulate. However, their presence in H will impact the probability mass of h under the posterior π| H , which is given by π| H (h) = π(h)/π(H) ≜ ρ H . We will show that the learner can achieve perfect accuracy if and only if in the given instance subset sum problem there exists a subset which sums up to T . To see this consider the following cases for the released information H.• Case 1: ρ H > 2/3. For any such H, all agents at distance ρ H from 2/3 gain positive utility by manipulating to x ′ = 2/3. Hence, the utility of such solutions for the learner is given by1 -Pr x∼D [x ∈ [ 2 3 -ρ H , 0)] < 1. • Case 2: ρ H < 2/3.For any such H, as all classifiers in H \ {h} are located at t > 100, no agent belonging to [0, 2/3 -ρ H ) gain positive utility by manipulating to x ′ = 2/3. Hence, these points will be misclassified by h, and consequently, the utility of such solutions for the learner is given by1 -Pr x∼D [x ∈ [0, 2 3 -ρ H )] < 1. • Case 3: ρ H = 2/3. By similar arguments to the previous cases, all agents belonging to [0, 2/3) manipulate to x ′ = 2/3 and all points with negative labels (x < 0) stay at their location. Therefore, no one will be misclassified, and therefore, the utility of such solutions is 1.Note that because ρ H = π(h) π(H) = 1/2 1/2+π(H∩{h1,••• ,hn}) , we have that ρ H = 2/3 if and only if π(H ∩ {h 1 , • • • , h n }) = 1/4. But π(H ∩ {h 1 , • • • , h n }) = 1/(4T ) hi∈H a i .We therefore have that ρ H = 2/3 if and only if hi∈H a i = T . Hence, deciding whether the learner's optimization problem has a solution with perfect utility is equivalent to deciding whether in the given subset sum problem there exists a subset S ⊂ [n] such that i∈S a i = T := (1/2) i∈[n] a i .In this section, we provide closed-form solutions for continuous uniform priors. More concretely, we assume in this section that π is the uniform distribution over an interval [a, b] ⊂ R that includes h. The information release of the learner will then be releasing an intervalH = [c, d] ⊆ [a, b] such that h ∈ [c, d].For example, a student may know that a GPA of 3.5 or higher will guarantee admission to a certain college, but not the exact threshold. Similarly, a loan applicant might know that a credit score above 650 will likely suffice for securing a loan, but not the precise cutoff. These uncertainties are sometimes due to factors unknown to the agents, such as the financial situation of the lender. Therefore, agents treat the threshold as uniformly distributed within a known and reasonable range. Theorem D.4. Fix any data distribution D over X . Suppose the prior π is uniform over an interval [a, b] for some a, b such that h ∈ [a, b]. Define H c ≜ [c, d] where d ≜ min (b, max (h, f + 1)). If b -a < 1, we have that H ⋆ = H c is optimal for any c ∈ [a, h], with corresponding utility U (H c ) = 1 -Pr x∼D [d -1 < x < f ] d -1 < f 1 -Pr x∼D [f ≤ x ≤ d -1] d -1 ≥ f If b -a ≥ 1, we have that for any c ∈ (b -1, h],the optimal solution H ⋆ is given by a, b] is the released information by the learner. The agents then project their uniform prior π over [a, b] onto H, which leads to the uniform distribution over [c, d] for π| H , and then best respond according to π| H . Therefore, for any agent x,H ⋆ = H c U (H c ) > U ([a, b]) [a, b] U (H c ) ≤ U ([a, b]) where U (H c ) is given above and U ([a, b]) = 1 -Pr x∼D [f ≤ x < h] is the utility of releasing [a, b]. Proof of Theorem D.4. Suppose H = [c, d] ⊆ [BR(x, H) = argmax x ′ ≥x Pr h ′ ∼U nif [c,d] [x ′ ≥ h ′ ] -(x ′ -x)One can then show that if d -c ≥ 1, BR(x, H) = x for all x because for any manipulation (x ′ > x), the marginal gain in the probability of receiving a positive classification is less than the marginal cost.Furthermore, if d -c < 1, then we have BR(x, H) = d d -1 < x < d x Otherwise Therefore, for any H = [c, d] ⊆ [a, b], if d -c ≥ 1, we have U (H) = 1 -Pr x∼D [f ≤ x < h], and if d -c < 1, we have U (H) = 1 -Pr x∼D [d -1 < x < f ] d -1 < f 1 -Pr x∼D [f ≤ x ≤ d -1] d -1 ≥ fThis is because under d -c ≥ 1, no one manipulates, and thus, the error corresponds to the probability mass between f and h: the positives who cannot manipulate to pass h. Under d -c < 1, because every agent x > d -1 can receive positive classification by manipulating, the error of H corresponds to the probability mass between d -1 and f : if d -1 < f , this corresponds to the negatives who can manipulate and receive positive classification, and if d -1 ≥ f , this corresponds to the positives who cannot manipulate to receive positive classification.Now assume b -a < 1, which implies that d -c < 1. At a high level, to maximize U (H) in this case, we want to pick d such that d -1 is as close as possible to f . More formally, our goal is to pick , d] and that the probability mass between d -1 and f is minimized. In this case, one can see, via a case analysis, that d = min (b, max (h, f + 1)) is the optimal value, and that c can be any point in [a, h] . [c, d] ⊆ [a, b] such that h ∈ [cIf b -a ≥ 1, then both d -c < 1 and d -c ≥ 1 are possible. If d -c < 1,In this section we will provide an efficient algorithm for computing the learner's optimal information release when the prior π is a discrete uniform distribution over a set {h 1 , h 2 , . . . , h n } ⊆ H that includes the adopted classifier h. The objective of the learner is to release a H ⊆ {h 1 , h 2 , . . . , h n } such that h ∈ H. Throughout, we take h = h k where 1 ≤ k ≤ n, and assumeh 1 ≤ h 2 ≤ . . . ≤ h n .We first state some facts about the agents' best response for any prior π over {h 1 , h 2 , . . . , h n } ⊆ H.To start, we first show that the best response of any agent can be characterized as follows:Lemma E.1. For any agent x, and any prior π over {h 1 , h 2 , . . . , h n } ⊆ H, we have BR(x,H) ∈ {x} ∪ {h i ∈ H : h i > x}.Proof of Lemma E.1. Recall from Lemma D.2 that BR(x, H) ≥ x. Note that the utility of the agent x ∈ X from manipulating to a point x ′ ≥ x can be expressed asu x (x ′ , H) = i:hi≤x ′ π| H (h i ) -(x ′ -x) For any x ′ ≥ x such x ′ / ∈ {x} ∪ {h i ∈ H : h i > x},it is easy to see that the agent can increase her utility by moving to a point in {x} ∪ {h i ∈ H : h i > x}, which proves the lemma. This lemma basically tells us that the best response of any agent x is either to stay at its location, or to manipulate to h i ∈ H such that h i > x. Given such characterization of the agents' best response in our setup, we now characterize, for any classifier h i in the support of π, the set of agents that will manipulate to h i . Lemma E.2. Fix any prior π over {h 1 , . . . , h n } and any H. If for any i, {x :BR(x, H) = h i } ̸ = ∅, then for some α, {x : BR(x, H) = h i } = (α, h i ], where α satisfies u α (α, H) = u α (h i , H).Note that h(BR(x, H)) = 1 and BR(x, H) = h j implies that h j ≥ h, and therefore:u x (h, {h}) = 1 -(h -x) ≥ j i=1 π(h i ) -(h j -x) > i:hi≤x π(h k ) = u x (x, {h})Since Lemma E.1 implies that BR(x, {h}) ∈ {x, h}, we derive from the above inequality that h(BR(x, {h})) = 1. This proves the first part of the theorem.Next, we show that F N R({h}) ≤ F N R(H) for every H ⊆ H. Let x ∈ X be such that f (x) = 1 and h(BR(x, {h})) = 0, and let H be any subset of H. We will show that h(BR(x, H)) = 0.Lemma E.1 implies that BR(x, {h}) ∈ {x, h}. Together with h(BR(x, {h})) = 0, we derive that BR(x, {h}) = x, and thus:u x (h, {h}) = 1 -(h -x) ≤ u x (x, {h}) = 0Now, for every h j such that h j ≥ h, we have:u x (h j , H) = j i=1 π| H (h i ) -(h j -x) ≤ 1 -(h -x) ≤ 0 ≤ i:hi≤x π| H (h i ) = u x (x, H).As a result, when the learner releases H, the utility of agent x from remaining at x is greater than (or equal to) any manipulation h j such that h j ≥ h. This implies that h(BR(x, H)) = 0.We show that minimizing FPR, unlike minimizing FNR, does not always have a clear optimal solution for the learner, by providing three examples with very different optimal solutions. Example G.1 (Full-information-release is optimal for FPR). Fix any B > 1 and any 0 ≤ t < B -1. Let D be the uniform distribution over X = [0, B], and f(x) = 1 [x ≥ t].Let H be the class of single-sided threshold classifiers and suppose the adopted classifier h(x) = 1 [x ≥ t + 1]. Under any prior over H, one can show that the full information release of H = {h} achieves perfect FPR for this setting: F P R({h}) = 0. Example G.2 (No-information-release is optimal for FPR). Under the same setup as in Example 2.4, one can show that releasing the support of the prior H = {h 1.8 , h 2 } achieves F P R(H) = 0, whereas full information release of the adopted classifier h = h 2 achieves F P R({h}) = 0.9/1.9 ≈ 0.47. Note that H = {h 1.8 , h 2 } is the support of the prior, so it constitutes as no-information-release. In other words, we have F P R(H ′ ) = F P R(H) = 0 for every H ′ such that H ⊆ H ′ ⊆ H. Claim G.3. There exists an instance in which neither full-information-release nor no-informationrelease are optimal when the utility function of the learner is U F P R .14 Proof of Claim G.3. We construct such an instance as follows. Suppose the domain is X = {x 1 , x 2 } with x 1 = 0, x 2 = 0.4 and the distribution D is given by D(x 1 ) = D(x 2 ) = 0.5. In addition, consider f = 0.3, and hypothesis class H = {h 1 , h 2 , h 3 } where h 1 = 0.1, h 2 = 0.5, h 3 = 0.7, and a prior distribution π such that π(h 1 ) = 0.2, π(h 2 ) = 0.1, π(h 3 ) = 0.7.Observe that under full-information-release, F P R({h}) = 1 for every h ∈ H. Now suppose h = h 2 is the adopted classifier. We have that BR(x 1 , {h}) = 0.5 implying h(BR(x 1 , {h})) = 1 ̸ = f (x 1 ) = 0 implying x 1 is a false positive under {h} release. Additionally, BR(x 1 , H) = 0.7 implies that h(BR(x 1 , H)) = 1 ̸ = f (x 1 ) = 0 implying x 1 is a false positive under H release. Further, it holds that BR(x 1 , {h 1 , h 2 }) = 0.1 and so h(BR(x 1 , {h 1 , h 2 })) = 0 = f (x 1 ). Moreover, in this particular instance, releasing {h 1 , h 2 } achieves perfect utility as BR(x 2 , {h 1 , h 2 }) = 0.5 which implies h(BR(x 2 , {h 1 , h 2 })) = 1 = f (x 2 ).One limitation of our model is that if the agents have knowledge of the mapping f from feature vectors to labels, they might gain information on h * in cases when |H| > 1. More specifically, knowing the mapping D, the mapping f , and that the firm is optimizing the choice of H for accuracy, agents could deduce h * . In this case, the choice of H leaks more information than intended.We proceed by showing an example with threshold classifiers for such a case. Example H.1. Suppose a distribution D over agents x ∈ X = [0, 1] is uniform, c(x, x ′ ) = |x -x ′ |, and f (x) = 1 [x ≥ 0.15]. The set of classifiers available to the firm is H = {h 1 , h 2 } where α 1 = 0.1, α 2 = 0.9 is each classifier's respective threshold.Following our Bayesian model, the firm chooses to release a subset H ⊆ H over which the agents have a uniform prior π| H . The agents know that the firm is choosing H to optimize accuracy, i.e. the function U (H) = Pr x∼D [h * (∆ H (x)) = y] (where y = 1[x ≥ T ]). We will show that the firm can release a subset H which is in arg max H⊆H [U (H)|h * = h 1 ] but not in arg max H⊆H [U (H)|h * = h 2 ], allowing the agent to reason that h * must be h 1 . Proposition H.2. Consider Example H.1. If the agents know agents know that f (x) = 1 [x ≥ 0.15] and the prior D, they can infer that h * = h 1 .Proof. We first solve for arg max H⊆H [U (H)|h * = h 1 ]. Suppose H = {h 1 }. Then all agents know h * = h 1 . If x ≤ α 1 , the agent will manipulate to α 1 to get a positive outcome if 1 -c(x, α 1 ) > 0, which is always true. If x ≥ α 1 , agents will stay the same to get a positive outcome. So the set of misclassified agents is those with x ∈ [0, T ] and U ({h 1 }) = 1 -T = 0.85. Now suppose H = {h 1 , h 2 }. Agents believe each classifier is h * with probability 0.5. If x ≥ α 2 , agents are guaranteed a positive outcome and stay the same. If α 1 ≤ x ≤ α 2 , agents will manipulate to α 2 to get a positive outcome if 1 -c(x, α 2 ) > 0.5, so all agents with x ∈ (0.4, 0.9] will be classified correctly. The rest of the agents with x ∈ [α 1 , 0.4] will stay the same to get a positive outcome with probability 0.5, and those with x ∈ [α 1 , T ] will be misclassified. Lastly, if x < α 1 , agents will manipulate to α 2 to get a guaranteed positive outcome if 1 -c(x, α 2 ) > 0.5 -c(x, α 1 ) (a.k.a. 1 -0.9 -x > 0.5 -0.1 -x), which is never true, and otherwise manipulate to α 1 to get a positive outcome with probability 0.5 if 0.5 -c(x, α 1 ) > 0, which is always true. So the set of misclassified agents is those with x ∈ [0, T ] and U ({h 1 , h 2 }) = 1 -T = 0.85. Therefore arg max H⊆H [U (H)|h * = h 1 ] = {{h 1 }, {h 1 , h 2 }}.* = h 2 ]. Suppose H = {h 2 }.As before, all agents know h * = h 2 . If x ≤ α 2 , the agent will manipulate to α 2 to get a positive outcome if 1 -c(x, α 2 ) > 0, which is always true. If x ≥ α 2 , agents will stay the same to get a positive outcome. So the set of misclassified agents is those with x ∈ [0, T ] and U ({h 2 }) = 1 -T = 0.85. Now suppose H = {h 1 , h 2 }. As before, agents believe each classifier is h * with probability 0.5. If x ≥ α 2 , agents are guaranteed a positive outcome and stay the same. If α 1 ≤ x ≤ α 2 , agents will manipulate to α 2 to get a positive outcome if 1 -c(x, α 2 ) > 0.5, so all agents with x ∈ (0.4, 0.9] will be classified correctly. The rest of the agents with x ∈ [α 1 , 0.4] will stay the same to get a positive outcome with probability 0.5, and will be misclassified. Lastly, if x < α 1 , agents will manipulate to α 1 to get a positive outcome with probability 0.5, and will be classified correctly. So the set of misclassified agents is those with x ∈ (0.4, 0.9] and U ({h 1 , h 2 }) = 1 -|0.9 -0.4| = 0.5, which is less than for U ({h 2 }). Therefore arg max H⊆H [U (H)|h * = h 2 ] = {{h 2 }}.We have shown that if the firm choosesH * = {h 1 , h 2 }, the agent can reason that H * ∈ arg max H⊆H [U (H)|h * = h 1 ] but H * / ∈ arg max H⊆H [U (H)|h * = h 2 ], so h * must be h 1 .NeurIPS Paper ChecklistStanford University. Email: leeco@stanford.eduToyota Technological Institute at Chicago (TTIC). Email: saeed@ttic.edu, kevin@ttic.edu, vakilian@ttic.eduGeorgia Institute of Technology. Email: jziani3@gatech.edu 38th Conference on Neural Information Processing Systems (NeurIPS 2024).Agent priors may also arise from observing previous decisions made by this classifier, for example as is studied inBechavod et al. [2022]: the learner (e.g., a hiring company) has been using a classifier h (the hiring algorithm) to screen agents (applicants) for some time. Agents going up for a decision today may observe some of the previous decisions made by the current classifier h and use this information to form their prior.For example, recently, many U.S. universities have announced that they will not use race and ethnicity anymore in admissions, in line with a recent Supreme Court ruling.Ties are broken in favor of an arbitrarily lowest cost solution.We emphasize that here h is fixed -namely, H is the only variable in the optimization problem of the learner which is constrained to include h.The claim holds for any distribution D in which both x1 and x2 are in the support.The number of times the oracle is called by an algorithm.An algorithm that calls the oracle only polynomially many times.We note that in this section, while we work with discrete priors over some {h1, . . . , hn} ⊆ H, our results can be easily extended to any prior.A set function r is modular if r(S) = s∈S r(s) for any S.We remark that the claim holds when the utility function is U (as defined in Equation2) as well. 


Decision: After the author response and discussion, all the reviewers felt positively about the paper (to varying degrees) with some quite strongly enthusiastic about the paper.  Overall the new model introduced seems to make a nice contribution to this growing and important literature.

Reviews: review: paper_summary: paper_summary: The paper introduces a novel framework for strategic classification using a Bayesian setting for agents' beliefs about the classifiers. This framework departs from the traditional assumption that agents have complete knowledge of the deployed classifier and instead assumes that agents have a prior distribution over the possible classifiers. The main components of the model are a population of agents and a learner. Each agent is represented by a pair $(x, y)$, where $x \in X$ is a feature vector and $y \in \{0, 1\}$ is a binary label. An agent with $y = 0$ is called a “negative,” and an agent with $y = 1$ is called a “positive.” There exists a mapping $f: X \to \{0, 1\}$ that governs the relationship between $x$ and $y$, meaning $y = f(x)$ for every agent $(x, y)$.

The model includes the following key components:

1. **Agent Manipulations**: Each agent can manipulate their features, paying a cost function $c: X \times X \to [0, \infty)$, incurred when changing their features from $x$ to $x'$.

2. **Partial Knowledge of Agents**: Agents have a common prior distribution $\pi$ over the hypothesis class $H \subseteq \{0, 1\}^X$, representing their belief about the deployed classifier $h$. Formally, for every $h' \in H$, $\pi(h')$ is the probability that the learner is deploying $h'$ from the agents’ perspective.

3. **Partial Information Release by the Learner**: The learner can release partial information about the classifier to influence agents' beliefs. This is modeled by releasing a subset $H' \subseteq H$ such that $h \in H'$.

4. **Strategic Game with Partial Information Release**: After the partial information is released, each agent computes their posterior belief and then moves to a new point that maximizes their utility. 

The paper provides the following theoretical contributions:

1. **Oracle-Efficient Algorithms**: For low-dimensional linear classifiers, the authors present an oracle-efficient algorithm for computing the best response of agents. When $X = \mathbb{R}^d$ and $H$ contains only linear classifiers of the form $h(x) = 1[w^\top x + b \geq 0]$, the best response of the agents can be computed with $O(n^d)$ oracle calls, where $n$ is the number of linear classifiers and $d \ll n$.

2. **Theoretical Analysis of Learner’s Optimization**: The learner’s optimization problem is analyzed to maximize expected classification accuracy under the agents' strategic manipulations. The analysis considers various information release strategies and their impact on agents’ beliefs and manipulations.

3. **Examples and Scenarios**: The paper provides practical examples, such as job seekers using platforms like Glassdoor to form beliefs about hiring algorithms, which ground the theoretical concepts in real-world scenarios.

#### Mathematical Formulation

1. **Agents and Learner**:
    - Agents: $(x, y)$ where $x \in X$, $y \in \{0, 1\}$.
    - Mapping: $f: X \to \{0, 1\}$ such that $y = f(x)$.
    - Hypothesis class: $H \subseteq \{0, 1\}^X$, with the learner using a fixed classifier $h \in H$.

2. **Cost Function**:
    $$
    c: X \times X \to [0, \infty) \quad \text{where} \quad c(x, x') \text{ denotes the cost of changing } x \text{ to } x'.
    $$

3. **Prior Distribution**:
    $$
    \pi: H \to [0, 1] .
    $$


5. **Oracle-Efficient Algorithm**:
    - For linear classifiers $h(x) = 1[w^\top x + b \geq 0]$, with $d$ much smaller than $n$ , the algorithm partitions $X$ given by $n$ linear classifiers into $O(n^d)$ elements and computes the best response within each partition element.
    - The best response algorithm runs in $O(n^{d+1})$ time, making $O(n^d)$ oracle calls.

In summary, this paper presents a comprehensive framework for Bayesian strategic classification, providing both theoretical insights and practical algorithms. The introduction of a probabilistic aspect to agents’ beliefs and the exploration of partial information release by the learner are key contributions that enhance the understanding and modeling of strategic behavior in classification settings.
strength_weakness: strength_weakness: - Realizability Assumption: The assumption that agents’ priors are realizable (i.e., the classifier deployed by the learner is in the support of the agents' prior) may not hold in many practical situations.
- Fixed Classifier Assumption: The learner’s commitment to a fixed classifier limits the model's applicability in dynamic environments where classifiers are frequently updated.
- Empirical analysis: the paper could be enriched with an empirical study of the methods discussed theoretically.
questions: questions: - The focus on maximizing accuracy is essential, but how do the proposed methods perform with other utility functions, such as fairness, robustness, or cost-efficiency?
- How do the proposed algorithms and strategies perform in empirical settings? Are there practical examples or case studies that demonstrate their applicability and effectiveness?
- How can the model be extended to dynamic environments where classifiers are updated over time?
- Is there specific conditions where partial information release outperforms full information release? Are there scenarios where partial information could be detrimental?
- How does the Oracle complexity algorithm scale with higher dimensions or larger hypothesis classes when $d \approx n$? Are there potential computational bottlenecks?
limitations: limitations: The authors discuss the limitations of the methods adequately.
paper_summary: paper_summary: * This paper investigates strategic classification in a partial-information setting using a Bayesian common-prior framework.
* The setting extends standard strategic classification (Hardt et al. 2016) to a partial-information setting by assuming that the deployed classifier $h\\in\\mathcal{H}$ is not fully known to the agents, but rather assumed to be sampled from a common prior $\\pi$ over the hypothesis class. The learner has the ability to influence agent decisions by disclosing a subset of possible classifiers $H\\in\\mathcal{H}$ such that $h\\in H$. The agent moves their feature vector to maximize their expected utility (expected prediction according to posterior, minus cost). The goal of the learner is to deploy a classifier which maximizes accuracy under the agent’s best response.
* In Section 3, the authors consider the agents’ best-response problem. The first result shows that computing the agent’s best response requires (in the general case) exponentially-many calls to a projection oracle (where the hypothesis class is assumed to be finite and complexity is measured in terms of $n=|\\mathcal{H}|$). The second result shows an $O(n^d)$ upper bound for computing the best response when $\\mathcal{H}$ contains $n$ linear classifiers over $\\mathbb{R}^d$. In Section 4.1, an efficient algorithm is presented for optimizing the disclosure set of hypotheses $H$ over one-dimensional realizable threshold classifiers. Finally, Section 4.2 shows that no disclosure is optimal when optimizing false-positive rate, and that full disclosure is optimal when optimizing false-negative rate.
strength_weakness: strength_weakness: * The interaction model presented in the paper makes strong assumptions which may not be applicable in practical scenarios. In particular:
  * Assuming that the true relation between features and labels is known to the learner. In particular, the paper does not seem to discuss implications of learning from samples.
  * Assuming that the agents’ prior distribution $\\pi$ is known to the learner.
  * Assuming that $\\pi$ has finite support, and implying that all classifiers in the support can be enumerated in reasonable time. Common hypothesis classes (such as linear models and neural networks) are defined by a continuous parameter space, and have infinite cardinality.
* Interaction model seems to be vulnerable to learner dishonesty.
* The paper does not contain empirical evaluation, and it's not clear whether the proposed scheme is feasible in practical scenarios.
* Positive results on the learner’s optimal information disclosure are limited to one-dimensional classifiers.
questions: questions: * Common prior in practical settings:
  * What could be reasonable assumptions for the functional form of the common prior $\\pi$ in practical settings?
  * How can $\\pi$ be estimated from data?
  * In which plausible practical scenarios does the size of $\pi$'s support induce a practically-significant discrepancy between efficient and inefficient algorithms?
* Dishonest information disclosure:
  * How much power can the learner gain from acting in a non-truthful way?
  * Can truthful information sharing (by the learner) can be enforced or incentivized?
* What are the consequences of the learner not knowing the feature-label distribution $D$, and being required to estimate it from data?
* 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?
limitations: limitations: Limitations are discussed in the appendix.
paper_summary: paper_summary: The paper studies strategic classification problems where agents with partial information about the classifier can strategically report themselves at a cost. The problem is modeled as a Stackelberg game: The principal can first reveal partial information of the classifier, then the agents choose their strategy to report. The goal of the principal is to maximize the accuracy of the classification as if they know the true value of all the agents. They show that this partial information release from the principal, compared to releasing no information or all information, may improve the accuracy. The theoretical results include NP-hardness and efficient algorithms.
strength_weakness: strength_weakness: - All the positive results seem to be under strong constraints. This may imply that the problem itself is very difficult. 
- I feel that the title does not reflect the main idea of this paper. What I get from the introduction is that the key point is "partial information release" rather than "Bayesian", but partial information release is not mentioned at all in the title. I would prefer something like "Partial Information Release in Bayesian Strategic Classification". 
- It's kind of unclear what there is an oracle in the agent's best response problem and what does the oracle do.
questions: questions: 1. Could you describe more clearly and intuitively what the oracle does? Also why it requires an input as $R^+ \cap R^-$?
2. Why do you take an oracle into consideration in the agent best-response problem?
3. Remark 4.3: I don't quite get this part. Why the learner what to make the classification "harder"? Can you propose an example?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper studies partial information release in strategic classification.  Roughly speaking, the learner publishes a set of classifiers containing the actual one being used, and the agents update their beliefs accordingly and best respond.  The authors show that the agents' problem of best responding is generally hard, and give oracle-efficient (approximate) algorithms in certain cases.  They then consider the essentially one-dimensional case where quality is measured by a single number, and show (1) the problem of releasing the optimal set is generally hard, and (2) an efficient algorithm for uniform priors.
strength_weakness: strength_weakness: My two major concerns are regarding the model and the significance of section 4.  I feel certain parts of the model can be better justified.  I also feel that in some sense section 4 is trying to solve a problem that might not exist in the first place.  See detailed comments below.
questions: questions: 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).

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.

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?

Line 314, h \ge f: notation abused here.

Sec 4: 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.
limitations: limitations: I don't have concerns.

Comments: title: Response to Question
Part 2 of Rebuttal
comment: Thank you for the detailed response! The answers are very helpful, and I maintain my current rating.
Thank you for your response. This makes sense to me.
Thank you for your continued engagement in the discussion!

We note that in the case where the cost function $c(x,.)$ is convex in its second argument and the agent $x$ is facing linear threshold classifiers, the optimization problem of the oracle becomes a convex program (finding the closest point to intersection of halfspaces w.r.t. a convex cost $c$) and can be solved with convex optimization techniques.

In other cases, however, this problem is non-convex and can be hard in general. Having said that, the literature on non-convex optimization includes a plethora of practical optimization strategies that can handle non-convex problems. We emphasize that our major contribution is introducing and analyzing partial information release in strategic classification, and therefore, assuming such an oracle allows us to abstract away the challenges faced in non-convex optimization which is not the focus of our paper.
Thank you for your response! This answers my questions about the oracle and Remark 4.3. I have an additional question about the oracle. How should I expect the complexity of such an oracle in practical applications? That is if a strategic agent cannot optimize even on class efficiently, then calculating the overall best response would be even harder.
Thank you for your response!  It answers most of my questions (which are somewhat open-ended in the first place).  I agree that the model is reasonable given that the paper is an early attempt to study the phenomenon.  Accordingly, I will increase my score to 5.
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.