Bayesian Strategic Classification
Authors: Lee Cohen
Saeed Sharifi -Malvajerdi
Kevin Stangl
Ali Vakilian
Juba Ziani
Venue: NeurIPS 2024 poster (2024)
Keywords: strategic classification
strategic agents
game theory
Bayesian
Primary area: algorithmic_game_theory

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.

Bayesian Strategic Classification
Lee Cohen'
Saeed Sharifi- Sharifi-Malvajerdi
Kevin Stang!?
Ali Vakilian?
Juba Ziani
Abstract
In strategic classification, agents modify their features, at a cost, to obtain positive classification outcome from the learner's classifier, typically assuming agents have full knowledge of the deployed classifier. In contrast, we consider Bayesian setting where agents have common distributional prior 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 when the agents' cost function satisfies 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 real-valued number.
1 Introduction
Machine Learning critically relies on the assumption that the training data is representative of the unseen instances learner faces at time. Yet, in many real-life situations, this assumption fails when individuals (agents) manipulate decision-making algorithms for personal advantage, by modifying their features 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. job interviews, 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 context of
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. (016), aims understand how 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 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 several reasons for this: some machine learning models
Stanford University. Email: leeco @ stanford.edu
Toyota Technological Institute at Chicago (TTIC). Email: saeed @ntic@ttic.dd. kevin@ttic.eda vakilian @ ttic.edu
Georgia Institute of Technology. Email: |ziani3 @ gatech.edu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 [ Some classifiers are simply too complex in the first place to be understood and interpreted completely by 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 the learner's 's model.
There has been a relatively short line of work trying to understand the impact of incomplete informa- tion on strategic classification. Dagadeesan et al. [2021] and Bechavod et al. [2021] study the optimal classifiers in settings where agents can only gan partial or noisy information about the deployed model. Haghtalab et al. [2023) study calibrated Stackelherg 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 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 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 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 completely hiding it, our model considers wider spectrum of information revelation that includes both "fullinforrmaiion-reessss and ano-informaaion-relessss 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, tech firm might reveal 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.
Summary of contributions:
In Section 2 propose 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 '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 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 www-dimensional linear classifiers. We then move away from the linearity assumption and consider
"The exact algorithm used condense your credit report into FICO score is closely guarded secret, but we have a general layout how your credit score is calculated." Source: Business Insider. October 2023. [Link: https://wwws http:///wwwwbbbneeeeeeeeeee businessinsider
finance/what---nneeeeeeeee fico-score).
An oracle-efficient algorithm is one that calls given oracle only polynomially many times.

---

a natural condition on the agents' cost function for which we give an oracle-effiient approximation algorithm for the best response of the agents for any hypothesis class.
In Section 4 we study the learner's ss optimal information release problem. We consider screen- ing/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 one- dimensional 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 '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 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 (201) J]. Hardt al. (2116) Hardt al. (016) 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 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 al. [222T] Ghalme et al. [2021] Bechavod et al. [2022]. J and Hagh talab et al. [0033 relax the full information assumption and characterize the impact of opacity on the utility of the learner and agents. Jagadeesan al. [202T] are the first to introduce model of "biased" information about the learner's classifier: instead of observing the learner's deployed classifier exactly, noisy version of this classifier; one that is randomly shifted (by
agents observe and best respond an additive amount) from the true deployed classifier.
In contrast, Ghalme et al. [022] 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 s prediction) pairs. More precisely, Ghalme 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 be positive (in the context of strategic classification), meaning that 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 Ghalme et al. [2021]
Bechavod et al. 2022) consider 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 (c.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. Haaghtlab et al. [2023] consider agents with (calibrated) forecasts over the actions of the learner, but do not consider the learner's 's information release which is our focus. Additionally, in 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.c. 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 leamerr is truthful, which is 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 the underlying distribution over these agents' features.
3

---

2 Model
Our model consists of population of agents and learner. Each agent our model is represented by pair (z, y) where I E X is feature vector, and y E {0, is binary label. Throughout, we call an agent with y = a "negative", and an agent with y = 1 a "positive". We assume there exists a mapping f X' + f0, } that governs the relationship between z and y; i.e. y = f(x) for every agent (x,, v). 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 cost function e: X' x X + [0, x)) where o(r, 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. S {0, 1 denote our hypothesis class, and let h E 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 N E 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 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
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 S H such that h E 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 release any subset of the hypothesis class, so long as it includes the deployed classifier h. Below, we provide natural examples of information release that can be captured by our model.
Example 2.1 (Examples of Information Release via Subsets). Consider the class of linear halfspaces
in d dimensions: H {/w.b w [w², w² ...., W T E R4 E R} where (w)) & 1[ x b 2 0] and X' = Ed is the feature vector. Let h by be the classifier deployed by the learner for some wo, bo- Under this setting, revealing the corresponding parameter of feature, say x in h corresponds to releasing I/, & E H w w/] (e.g.. 'minimal GPA of 3.8 for grad school'). Revealing the top le features of h (e.g., the most significant class grades are algorithms and calculus) corresponds releasing H₂ {hweb H. w",, w²2 .... w'k are the i largest coordinates of w) Let Lo be such that wi # 0 iff i 1o. Revealing the relevant features of h, i.c. features with nonzero coefficients (c.g., sensitive attributes like race or gender will not be used in the decision) corresponds to releasing Ha ( E H. : w² + O, Vi E 1o). This a common form of information release in the real world
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 т and is formally ((H) I[h' e 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 the
defined by: Vh E H. π T| (h') & ((hh)
'Agent priors may also arise from observing previous decisions made by this classifier, for example as is studied in Bechavod et al. (2022]: the learner (e.g.. a hiring company) has been using classifier h (the hiring algorithm) screen agents (applicants) for some time. Agents going up for decision today may observe some of the previous decisions made by the current classifier 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 recent Supreme Court ruling.

---

h1 - f)
h2
hs
21
0
0
222 Table 1: Hypothesis class H. in Example 2.3
O
probability (according to π (r) 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 given by
Us (2',, H) A
Pr W/MTH
[x(x'')
= - c(2x22))
(1)
We let BR(x, H) denote the best response of agent i.e. point z' that maximizes un (z', H). 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.
(H) A Pr [MBB((,, H)) = f(x)].
aND
Definition 2.2 (Strategic Game with Partial Information Release). The game, between the learner who using h E H for classification, and the agents who have a prior a over H. proceeds as follows:
1. The learner (knowing J. D, G, π) publishes subset of hypotheses H C H such that h E H. Every agent x best responds by moving to a point BR(x, H) that maximizes their utility: BR(x, H)) E argmax,eex ua(x', H).
The learner's goal is to find a subset H* C H with h E H*, that maximizes its utility H E argmax (H)
We note that similar to standard strategic classification, the game defined in Definition 2.2 can be seen Stackelberg game in which the learner, 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 Defini- tion 2.2 not only captures both the partial knowledge of the agents and the leaner's '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. ).16). This is because the learner can always choose H = {h}. Next, we ask:
Can partial information release increase the learner's 'ss utility compared full information release?
Observe that by definition, U(H)) 2 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*) > ((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' = [x1, and that their probability weights under the distribution are given by D(x1) 2/3, ((x2) = 1/3, and their true labels are given by f f(x1) = 1. fx2) = 0. Suppose the cost function is given as follows: c(z1, (2) = 2. c(22, x1) 3/4. Let H {h1, h2, h2) be given by table ! One can show that under this setting, h = hy 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 is uniform. One can show that under this setting, and when h = h is the deployed classifier, releasing H' = (hg, h2) implies U(H") = 1 > U((h)) = 2/3. other words, the learner can exploit the agent's 's prior by releasing information in way that increases its own utility by significant amount.
*Ties are broken in favor of an arbitrarily lowest cost solution. 'We emphasize that here l fixed namely, H is only variable the optimization problem the learner which is constrained to include h.
The claim holds for any distribution D in which both æı and 22 are in the support.
5

---

Algorithm 1: Oracle(c, H))
Input: agent 2, region R Rt n specified Ri = n Nirr (2 h=(z) 1) and R = ier {2: (,(2) = 0} for some I+ and 7-
Output: argmingeR cZ7,2)
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 is optimized for full information release.
Example 2.4 (Partial vs. Full Information Release). Suppose X' = 2). D is the uniform distribution
over 0. 2). f(x) = 1 [ 2 1.9). H. {/2 E [0, 2 where (x) & 1 [a 2 fj. Suppose the cost function is given by the distance =(x,,²) x x'I. We have that under this setting, the optimal classifier in H under full information release is h h2, and that its corresponding utility Prz--Unif(0o.] [1 S 1.9] = 0.55. Now suppose the agents have the following prior over H: xTh)) 0.1 [[h' h2] 0.9 [ h1s8 s). Under this setting, and when h h2 is deployed for classification, one can see that releasing H = { h1.8} leads to perfect utility for the learner. We therefore have (11*) = U(th)) 0.55.
((hh)
3 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 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 complexity [ 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 algorithn for solving the best response problem when the hypothesis class is the class of low-dimensional linear classifiers. In Appendix [ 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 E X, and distribution P (e.g.. P х|н where is the prior and H is the released information) over set {/i...., 14 S H. we want to solve argmax,gx* (Pr [h'(2) = 1] c(x; 2)}. We consider an oracle that given any region R C X, specified by the intersection of positive (or negative) regions of h 's. returns the projection of the agent x onto R according to the cost function c: argmin.en c(x, 2). For example, when H is the class of linear classifiers and c(x, = || =II2. the oracle can compute the fz-projection of the agent x onto the intersection of any subset of the linear halfspaces in (M1..... ... )..). 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 {hi..... hn because:
max Pr [M()) =1] ((((=)=)]c((x,2))))) sEX
-(1,,))
max
Σ P(h') WES
min
2
(3)
WNP
=sh
This 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 2 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 every x, x' E Rdd, Cp (1,,,x') x') = | x'llp where p 1.
Theorem 3.1. 1222" / /T) calls to the oracle (Algorithm are required to compute the best response of an agent with 2/3 probability of success, even when X TR.2 and the cost function cp for p 2
'The number times the oracle called by an algorithm.
An algorithm that calls the oracle only polynomially many times.

---

Algorithm 2: Best Response of Agents in the Linear Case
Input: agent cost function e, arbitrary distribution P over linear classifiers (hi,... hen
Step 1. Compute the partitioning (Rn,) of the space given by (le,.... Nnn);
Initialize R1 {{2 (2) 1}, 22: (z(2) 0}};
for i = .2 do
R. t- RG-1;
for R E R do
if (2 : h=(=) = 00 R + 0 then
R, +- R4 R R:
// Remove R // Split H
H. + (22 (2) = 1, hx(2) = 03 R}:
Step 2. Given Ra, compute the best response;
for R E R., do
Let R = A n R where At = ler {z: hx(2) = 1} and A = ner- hx(2)) 03:
Call the oracle (Algorithm to solve za argmin c(x, 2);
Compute the utility of zr: (tility(z)) = Eie P(h+) c(z, zn);
Output: argmax,ez uzility(z) where Z = {2R R E R..
Now-Dimensions Linear Classifiers. Next, we show that when X' = Rd for some d, and when
H contains only linear classifiers, i.e., every E H can be written as h(x))= = 1 [ x + b 2 0] for some w E RRd and E R. then the best response of the agents can be computed with (nn) oracle calls when d < n.
The algorithm, which is described Algorithm 2 first computes the partitioning (R₂) of the space X' given by the linear classifiers. For any element of the partition in Rx it then solves the best response when we restrict the agent to select its best response from that particular element. This gives 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 cracle-ffficienc of the algorithm follows from the observation that n linear halfspaces in d dimensions partition the space into at most ((n))) elements when & n. Formally,
Theorem 3.2. Suppose x= Rdd for some d & n. and H contains only linear classifiers. Then for any agent x. any cost function c, and any distribution P over (h1,-.., hn C H. Algorithm 2 the best response of the agent in time On while making O(n²) calls the oracle (Algorithm 7
3.1
Generalizing to Arbitrary P
In Theorem 3.2 we require the distribution be over hh,, S H. e.g. to have finite support.
When this does not hold, ie. has infinite support size, we can ignore classifiers with sufficiently small probabilities (i.e., poly(c)), as they do not affect the manipulation strategy when searching for an (1 + -pappooxie solution. The number of classifiers in the support with probability at poly(e) for fixed e 0 is most 1/poly(E) which is finite number. Therefore, to obtain nearly optimal solution, it suffices to only consider probability distributions with finite support size.
4 The Learner's Optimal Information Release Problem
In this section we focus on the learner's s optimization problem as described in Definition 2.2 The learner is facing population of agents with prior π and wants to release partial information H C H so as to maximize its utility (H). We note that the learner's strategy space can be restricted the support of the agents' prior и because including anything in H that is outside of I r's support does not impact (H).. Therefore, one naive algorithm to compute the utility maximizing solution for the learner is to evaluate the utility on all subsets H C support( RT) and output the one that maximizes the utility. However, this solution 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 Sctup:
Classification Based on Test Scores. We adopt the following setup for the learner's 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 real-valued number, say, test
7

---

score. We therefore consider agents that live in the one dimensional Euclidean space: X' = [0, B] S I for some B. One can think of each x as the corresponding qualification level or test score of an agent where larger values of z correspond to higher qualification levels or higher test scores. As we are in strategic setting, agents can modify their true feature æ and "game" the learner by appearing more qualified than they actually are.
We let f(z)- 1 [ar 2 t] for some t: there exists some threshold & that separates qualified and unqualified agents. We take the hypothesis class H. to be the class of all single-sided threshold classifiers: every lı' E H can be written as h((x) _ [ 2 ['] for some L'. We further take the cost function of the agents be the standard distance metric in I: c(z,2') = I2'-
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 : X + [0, B] such that fx)) = 1[g(z) 2 for some t, and that the cost function is given by c(z, 2) = [g(z)= g(z)). Here, g(z) captures the qualification level test score of an agent T. Now observe that we can reduce this setting to the introduced setup of this section: take
X" = =g(x)) : x E X) C [0, BJ, f : X² {0, 1] is given by f(x') 1[x 2 1), and that the cost function c: X' x X" + (0, 0c) is given by ((x'222) 12' 3e'-a'p x'|.
Remark 4.2. Note that because every classifier h E H is uniquely specified by real-valued threshold, for simplicity of our notations, we abuse notation and use ht' interchungeably as both a mapping (the classifier) and 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 2 f. We note that it is natural to assume h 2 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 - choosing h < f will only hurt the learner's utility. Because we will extensively make use of the fact that h 2 f, we state it as a remark below.
Remark 4.3. The learner's 's adopted classifier is some h E H such that h 2 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
4.1 An Efficient Algorithm for Discrete Uniform Priors
Given the hardness of the learner's problem for arbitrary prior distributions, we focus on a specific family of priors, namely, uniform priors over given set, and examine the existence of efficient algorithms for such priors. In Appendix D.22, 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 set {h1, he..... hn C H. that includes the adopted classifier h. Here, the objective of the learner is to release a subset H S (h1, }n such that h H. Throughout, we take h h& where 1 S k S n, and assume hy I h2 S < hn The complete exposition of this section, including all details, proofs, necessary lemmas, and the description of the proposed algorithm, can be found in Appendix H
We first characterize the utility of any subset H released by the learner using a real-valued function of H. Define, for any H C (hi,..., hnn such that h E Ht
RH - inf {x: BR(x, H) 2 h1 Note that BR(x = h, H) 2 h for any H such that h E H. Therefore, (x BR(x, H) 2 h) is nonempty, and that RH S h for any H such that h E H. In the following lemma, we show that RH characterizes the utility of И for the learner, for any prior т over (hi,..., ,,
Lemma 4,4. Fix any prior π over (hi...., hn We have that for any H S (hi,..., hnd such that E H. the utility of the learner. given by Equation 2 can be written as
Pra-n [nu
< S]
Rh < Rs 2
U(H) = [ PraND [f S x S R
(5)
Our results can be extended to the case where c(e, x²) k/ 2| for some constant k.
8

---

Given such characterization of the learner's utility by Ry, we show that when the agents' prior is uniform over (h1...., J. there are only polynomially manry possible values that RØ can take, even though there are exponentially many H's. We characterize the set of possible values for RS well. For any possible value of Rs, our algorithm efficiently finds subset H such that RØ = R, such H exists, and finally outputs the one with maximal utility.
More formally, we consider the following partitioning of the space of subsets of { J. For any & E (1,2....,,]) and for any i E [k, k + I,...,,,., n.. define
S - { S (hi,...,hh,)
hnn h E H, H E, BR, H) = h;}
Note that (R = h2, H) E {h; : .12 } for any H. Therefore, {St,else gives us a proper partitioning of the space of subsets, which implies
max H (ha MEH
U
max max U(H) & HES,
Given this partitioning of the space, we show that RH can characterized as follows.
Lemma 4.5. If the prior π is uniform over {h1 hnn, then for any H E Si,, RH h; j/f where j = 1(h' E H : E h.]H
Given such characterization, our proposed algorithm (Algorithm 3p. for any i, e, enumerates over all possible j E f1.....f ft and returns a H such that H E St,t and Ry h; j/f. if such H exists. The algorithm then outputs the subset H with maximal utility according to Equation[5]
Theorem 4.6. There exists algorithm (Algorithm 3) that for any any uniform prior over (hr...., hn that includes h, and any data distribution D, returns H S (hi....,h,, hnd in time O(n²) such that h E H* and that U (H+))
(hi........ UH)..
4.2 Minimizing False Positive (Negative) Rates for Arbitrary Priors
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 based on False Negative Rate (FNR) and False Positive Rate (FPR) which are formally defined below. For any H S H such that E H.
UPPR H) FPR
Pr [M(BR(a, H)) = 1ff(x) = 0] anD
(6)
UPNR(H) H - FNR(H) Å
Pr [M(RR(,, H)) = 0lf(z) = 1] END
(7)
In the following theorem, we establish that for any given prior æ over a set [h1 he......... ......,,, S H. if the learner aims to minimize the FPR, no-information-rell releasee is preferable to full-information- release [1]] Additionally, we show that for minimizing the FNR, an optimal strategy for the learner full-informatioon-eelees.. By "no-inforrmation-rllesss""" that H includes the support of the prior म: H 2 (hi....,hh, hn) which results in x T|E = m. "full-infommaioon-releess"" we mean revealing the classifier: H (h).
mean releasing any subset H such
Theorem 4.7. Fix any h 2 f. For any prior over (li,..., hn,) that includes h, we have 1) FPR(H) & FPR((H)) 2) FNN(())) & F every C H such that E H.
The proof is provided in Appendix F In Appendix G show that minimizing FPR, unlike mini- mizing FNR, does not always have a clear optimal solution. We provide three instances such that mullinnformaiion-ellea is optimal for the first, no-information-relesse is optimal for the second, and neither is optimal for the third.
Conclusion
We introduce Bayesian Strategic Classification, meaning strategic classification with partial knowl- edge (of the agents) and partial information release (of the learner). Our model relaxes the often
We note that in this section, while we work with discrete priors over some (fu....,h S H. our results be easily extended any prior.

---

unrealistic assumption that agents fully know the learner's deployed classifier. Instead, we model agents as having distributional prior on which classifier the leamnrr 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.
Acknowledgements
The authors thank Avrim Blum for helpful discussions in the early stages of this work. Special thanks to Roy Long for suggesting that our model might leak more information than intended, and to Odelia Lorch for identifying an instance where this occurs and providing proof (located in Appendix (H).
Lee Cohen is supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, the Sloan Foundation Grant 2020- 1390-1 and the Simons Foundation investigators award 689988. Kevin Stangl was supported in part by the National Science Foundation under grants CCF- 2212968 and ECCS-2216899 by the Simons Foundation under the Simons Collaboration on the Theory of Algorithmic Fairness, and by the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003. The views expressed in this work do not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred.
References
Y. Bechavod, K. Ligett, S. Wu, and J. Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1234-1242, 2021.
Y. Bechavod, C. Podimata, S. Wu, and J. Ziani. Information discrepancy in strategic learning. In International Conference on Machine Learning (ICML), pages 1691-1715, 2022.
H. Beyhaghi, M. K. Camara, J. Hartline, A. Johnsen, and S. Long. Screening with Disadvantaged Agents. In 4th Symposium Foundations of Responsible Computing (FORC), volume 256 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:20, 2023.
R. Biden. Executive order on the safe, secure, and trustworthy development and use of artificial intelligence. 2023.
M. Braverman and S. Garg. The role of randomness and noise in strategic classification. In Foundations of Responsible Computing (FORC), volume 156 L/PIcs, pages 9:1-9:20, 2020.
M. Brückner and T. Scheffer. Stackelberg games for adversarial prediction problems. Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547-555, 2011.
M. El Halabi and S. Jegelka. Optimal approximation for unconstrained non- submuuuuuu minimization. In International Conference on Machine Learning, pages 3961-3972. PMLR, 2020.
G. Ghalme, Nair, Eilat, I. Aalaam-Cohent and N. Rosenfeld. Strategic classification the dark. In International Conference on Machine Learning, pages 3672-3681. PMLR, 2021.
N. Haghtalab, C. Podimata, and K. Yang. Calibrated stackelberg games: Learning optimal com- mitments against calibrated agents. Advances Neural Information Processing Systems, 36. 2023.
M. Hardt, N. Megiddo, C. Papadimitriou, and M. Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122, 2016.
K. Harris, V. Chen, J. Kim, A. Talwalkar, H. Heidari, and S. Z. Wu. Bayesian persuasion for algorithmic recourse. Advances in Neural Information Processing Systems, 35:11131-111 2022.
L. Hu, N. Immorlica, and J. W. Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259-268. 2019.
10

---

M. Jagadeesan, C. Mendler-Dünnnn and M. Hardt. Altemnttve microfoundations for strategic
classification, International Conference on Machine Learning, pages 4687-4697. PMLR, 2021.
E. Kamenica and M. Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590- 2615, 2011.
R. Lake.
How to
get
personal loan without credit check.
Time, 2024.
URL
how-to- get- aa--ersooaa--- -oreooonnlloon------ -wtrsoaaa--aaa--ttttto---------- a
S. Milli, J. Miller, A. D. Dragan, and M. Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 230-239, 2019.
G. D. Regulation. General data protection regulation (gdpr). Intersoft Consulting, Accessed in October, 24(1), 2018.
A. C.-C. Yao. Probabilistic computations: Toward unified measure of complexity. In 18th Anmual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227. IEEE Computer Society, 1977.

---

A Limitations, and Broader Impacts, and Future Work
Limitations 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 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 belief's 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 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
Broader Impacts On the plus side, our approach provides 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 real life, providing useful insights on how much information 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 al., 2019] Milli al. 2019] and in 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. turn, will be critical in future work to design fairness-wware information release strategies by learner faced with strategic behavior.
B Oracle-Efficient Approximate Best Response for -Submodular Costs
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 given collection of classifiers V C H. we introduce the notion of V-uumodullar cost functions which is a natural condition that arise in many applications. Borrowing results from the literature submodular optimization, we then show that for any distribution P over a set V = (ha,..., h, 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) & ENES P(h')- - c(c, S) where, with slight abuse of notation, we define
() 2
min
cxx,2) z)
(8)
a (.) wes
12

---

For any S S {hi...., h, c(x, S) is simply the minimum cost that the agent x has to incur in order to pass all classifiers S, and can be computed via the oracle (Algorithm We now state our main assumption on the cost function:
Definition B.1 (V -Submodularity). Let V (Il....,hn.) be any collection of classifiers. We say a
cost function is V-submodular, if for all the set function c(x, .) -2 - IK defined in Equation submodular; for every S, VV such that S S S' and every l $ 5'
e. cxx, UU (M)) c (z, S) 2 c (x. S' 1 (1() - c Sx
This condition asks that the marginal cost of passing the classifier h' is smaller when the new classifier is added to S" versus S. for any such h S, S". Fix collection of classifiers V. Informally speaking, a cost function is V-submodular if the agent's manipulation to pass classifier only helps her (i.c., 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 certain number of tests is transferable across tests. Some real-life examples include: 1) a student that is preparing for series of math tests on topics like probability, statisties, 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 IR the cost function e(z, x²) = Iz x'| is --submodular where V can be any set of single-sided threshold classifiers.
hn3 where every h1 can be written as hz 1 2 t. for some to E R. We have that the cost function c(x, x') = |r - I'1 is V susuboddular.
Claim B.2. Let X' R. and V {hi..... ,,,,...,,)),),,.
Proof of Claim B.2 We will abuse notation and use h; for the threshold & (h; = 4 IR).
Fix any x. Consider S S S' S {hi...... h and h' E R such that h' $ S'. Note that
dx, 5) = max (max(S) - x, 0), c cx. U {h'}) = max (max(S U (h'}) - 2;, 0) c(z, 5') = max (max(S") - x, 0), c (x, S' (MT) = max (max((S U {h'}) xx, 0) where max(F F) is simply the largest threshold in F, for any set F. Note that max(S) S max(S")
because S C S". Suppose x S max We have three cases
1. If 2 mSx then c(r, SU (V Sxx = =1' max(S) 2 h1 -max(5') = c S"x U((')) - c (ar,
mS) S N/' S max( then
0 cα2,5 (1/) - c (I, 1/ =0= c S")
-
3. If max then c c(z, S
U (h'}) c)x c
Sz - -c())
So we have shown that the cost function is submodular if x max(S). We can similarly, using 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 = (hi...., hn C H. If the cost function is V V-submodular, then there exists an algorithm that for every agent and every 0, makes Ö(n/e²) calls to the oracle (Algorithm 1) and outputs a set S C V such that
g.. ($) Z maxsçV
Proof of Theorem B.3 Note that when the cost function is V -submodulaar, the objective function Ja can be written the difference of monotone non-negative modular function and monotone nen-negative submodular function: 9x 2 + IR (S) = Eves P(t') c(r, S). The result then follows from (EI Halabi and Jegelkal 2020 where they provide an efficient algorithm for approximately maximizing set functions with such structure.
A set function is modular if r(S) Eves r(s) for any S.
13

---

C Missing Proofs of Section
Theorem 3.1. 52(2"/ /n) calls to the oracle (Algorithm of an agent with 2/3 probability of success, even when X R² and the cost function is cp for 1.
are required compute the best response
Proof of Theorem 3.7
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 'hidden' subset S* C [ni] of size n/2, Alice aims to identify Bob's set 5 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 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/22) 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 from [r]]. as the Bob's set. Then, after querying half of the subsets size n2/ 2, the failure probability Alice detecting Bob's 's set least (1 (/(nnn)))nn))- .. (1-11
> (1-2/n)*/2 > e e (1-2/n) 1/3
for sufficiently large values of n.
Next, corresponding to instance of the hidden-set detection problem with S*, 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) I 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 (.//2) =2(2" / /n) oracle calls.
Let 2k and 6 < 1/n. Corresponding to every subset S C [n] of size n/2 there is distinct
point 2.5 at distance 1/2 from the origin, i.e., | = 1/2
Corresponding to every subset C [n] of size n2/2, there are two distinct points FS,a and æs. distances respectively 1/2 - (near) and 1/2 + (far) from the origin, i.c., | lIp = 1/2 and || 1/2 +
Now, we are ready to describe the instance Is- of our best response problem corresponding to the given hidden-set detection problem with S*. We define H ( ... ,,, and distribution P over H. such that,
P is uniform distribution over all classifiers H. i.e. P(h.) 1/n for every i E [n].
For every subset T [ri] of size n/2 1, we define (xT) 1 T].
For every subset T [n]] of size n/2, we define h, h=(=),)) = 1 E T]. Moreover, if S* then ha(0r..)) = 0 for all E [n]. Otherwise, T = S*, we define h2 (XT..) = 1 E T).
Finally, for the remaining points in X, i.e., x' R² (HIT T C [n] and [T - (.T.M: XT. : T C [n] and [T| = n/22), we define h,(x') (xx))= for all E [n]. In other words, points that do not correspond to subsets of size n/2 1 n are classified as negative examples by every classifier H.
In the constructed instance 1s., no point is classified as positive by more than n n/2 classifiers in H. and the p-norm distance from the origin for all points classified as positive by subset of classifiers is least 1/2 c. Therefore, the best response for an agent located the origin of the space is ws yielding utility of 1/2 (1/2- c) > O. Hence, the computational task in computing the best response involves identifying the (hidden) subset S*. Refer to Figure I for a description of Is..
Although we described the construction of Ts+, what we need to show to get the exponential lower bound the oracle complexity of the best response problem is constructing oracle (i.e., implementation of Algorithm Tp. using the EQUALTT(-)) oracle, consistent with Ts-. To do so, given a subset of classifiers specified by T' [n)], the oracle returns as follows:
if [ > n2/2: It returns empty set. *
if [T] < n/2: It returns TT for arbitrary set 7 2 T of size n/2-1. Note that || 1|p = 1/2
if [ n// and EQUALTO(T) FALSE: It returns æT, Note that ||æT, 1/2 +
14

---

S
In this example, we consider p = 2, i.e., c(z, = ||x, The agent is located at the origin. Blue nodes correspond point in the intersection of the positive regions of subsets of classifiers of size 2 - 1, each located at a Euclidean distance of 1/2 from the origin, where c is small positive value. Moreover, points in the intersection of the positive regions of subsets classifiers of size 2 are indicated by red points, all except the one corresponding to S are located Euclidean distance of 1/2 + from the origin. The red point corresponding S* is uniquely placed at distance of 1/2 from the origin, similar to the blue nodes. Furthermore, all points, corresponding to different subsets, are located at distinct locations the space.
Figure 1:
if T n/2 and EQUALTO(T) TRUE: It returns 2T,.- Note that
|TT 1/2
Remark C.1. As in each instance Ig- the only point with strictly positive utility is xSS..n our proof for Theorem 3.7 essentially rules out the existence of any approximation algorithm for the best response problem with success probability at least 2/3 using o(2") /vn).
Theorem 3.2. Suppose = Rd for some d & n, and H contains only linear classifiers. Then for any agent x, any cost function c, and any distribution P over {hi,..., .2 S H. Algorithm 2 returns the best response of the agent in time In, while making (nn)) calls to the oracle (Algorithm) 7j.
The fact that Algorithm 2 returns the best response follows from the struction of the algorithm. We first prove the oracle and the runtime complexity for d = 2 and then generalize it to any d. The oracle complexity of Algorithm 2 is R2, Note that Ri 2, and for any n 2 2, RR, < RR.,,1 + n. This is because the line {a (z) 0} intersects the lines formed by (h1,.... hn-13 in at most n points, which will then partition (= (2) = 0} into at most n segments. Each segment of the new line then splits a region in R,-1 into two regions.
Proof of Theorem 3.2
So, there are at most new regions when hn is introduced. The recursive relationship implies
that |R, I 1+ I[=+1] = O(r)). The runtime complexity of the algorithm is then given by 2
O OEL R& = On?).
Now consider any dimension d and let R(n, d) denote the number of partitions induced by the classifiers (h,...., }. Note that this case we have R(n, d) S R(n 1.d) + R(n 1, 1). The first term on the right hand side is the number of regions induced by {li...., hn-. and the second term the number splits (dividing a region into two) when hú, is introduced. Note that {=: (z) 0} is a d 1-dimensional hyperplane and the number of splits induced by ht is simply the number of regions induced by {hi,.... hn-1) on {z: h2(2) = 0}, which is R(n 1, 1).
The recursive relationship implies that R, = R(n, d) & Ei=o ()) = O(n)).
D Missing Details of Section 4
We first state remark about the tie-breaking of agents' best response problem:
Remark D.I. As mentioned in the model section, when there are several utilitymaximizingg 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 (a! 2 x); this is formally stated in the first part of
15

---

Lemma D.2 Therefore, the tie 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 chooses
BR(x, Hf) min
argmax (n H)}
z'2a
In the rest of this section, when we write argmax,'2> uz H), we implicitly are taking the smallest x' 2 that maximizes the utility of the agent
Next, we state some useful facts about the agents' best response in our setup. Lemma D.2. Fix any prior and any points 22 2 21. We have that, for any II S H.
1. BR(x1, H) 2 Z
2. BR(x2, H) 2 BR 11 H).
3. If TL, H) 2 22 then BR( H) = BR(x2, H).
Proof of Lemma D.2 Fix any 2, and any H. We have
BR(x, H) = argmax
Pr NnTTa
[x' 2 1/] 10' - x
x'
argmax z'2o
Pr N
[x' 2 11 (x' -
argmax
Pr (N/=T/
[a'2M] x'
z'2a
z'2=
where we take gn() A PI [x' M] - x'. The first equality follows because agents do gain any utility by moving 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 have
BR( H) = argmax 9H (a') argmax 9n (x') = BR(x2, H) z'202
x' 2'201
where the second equality follows because (R H) 2 4/2
D.1 NP-Hardness of Learner's Optimization Problem with Arbitrary Prior Distributions
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 classifiers {h1, ho..h2..... hn C H that includes h. The problem of finding H C hfi,hg....,ht that h E H and the learner's utility (H) is maximized is NP-hard.
Proof of Theorem D.3 The proof is via reduction from the subset problem. In particular, we consider a variant of the subset sum problem which we are given a set n positive num- bers (1, ann and the goal is to decide whether subset S c [m] such that Eies T (1/2) Ei] ag exists.
Given instance of the subset sum problem with input (fa1,-.. :, (1/2) EiE(n) a.). construct the following instance of our problem with one-dimensional threshold classifiers. Define f(x) = 1 [x 2 0]. h(()) = 1 [x 2 2/3], and hx(x)) = 1 [æ 2 100 + for every i E [n]. Moreover, suppose that the prior distribution of the agents is given by: क (h) = 1/2 and for every E [n], x (h+) = / (4T). Note that (Thh) + Σ, T(h;) = 1. Let the data distribution D be the uniform distribution over 1000, 1000).
Intuitively speaking, the inclusion h,'s in H have no direct effect on the accuracy of the released subset H, as they only lead to subset of the agents located at > 100 to manipulate. However,
16

---

their presence in H will impact the probability mass of under the posterior π THH which is given by T/e (h) ( _ Pи- 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 To see this consider the following cases for the released information H.
Case PH > 2/3. For any such H. all agents at distance Pa from 2/3 gain positive utility by manipulating to x' = 2/3. Hence, the utility of such solutions for the learner is given by 1- Pr (a
Pn. 0j] 1.
Case 2: PH 22/3. For any such H, all classifiers H \ {h} are located at t 100, no agent belonging to |0, - PH) 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 by
1 -rPr Dr x [0, pn)] < 1.
Case 3: PH = 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 PH wHE [H n (h,,... hn,)) /4. But π (H n (h1,-- hn)) 1/(4T) En.e aN We therefore have that PH 2/3 if and only if Enenh O; 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 c [n] such that Eies a = T == (1/2) Eie(n) O3.
x(h)
1/24alH (() Ain we have that pn 2/3 if and only if
1/2
D.2 A Closed-form Solution for Continuous Uniform Priors
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, bj C R. that includes h. The information release of the learner will then be releasing an interval [c, d] C [a, bj such that h E [c, d].
For example, a student may know that GPA of 3.5 higher will guarantee admission 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 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 x is uniform over an interval [a, b) for some a, b such that h E b). Define H. - [c, where d a min (b, max (h, f + 1)). If 1, we have that H* Ha is optimal for any c. E {a, hi], with corresponding utility
d-1<f lfb 2 we have that for any E (b 1, h]. the optimal solution H" is given by
1 PI (d - 1 < x f
U(H = 1 PIaDD [ < <xsd-11 d d-12f
U(H.) > U((a, b)) [ He [a, U(H.) < U(a bl) =*
where U (HH) is given above and U(aa, b])
Pr [$ s < hi is the utility of releasing [a, b).
Proof of Theorem D.4 Suppose H = |c, d C [a, bJ is the released information by the learner. The agents then project their uniform prior и over (a, bj onto H, which leads the uniform distribution over (c, d] for x m|. and then best respond according to л | Therefore, for any agent
BR H) = arginax Z
Pr [M-Unifledd
1x' 2 h1] (x' xx)
One can then show that if e 1, (R(x, H) = x for all x because for any manipulation (a' > 2), the marginal gain in the probability of receiving positive classification is less than the marginal cost.
17

---

Furthermore, if - 1, then we have
d d-1<x= dd
(R H) x
Otherwise
Therefore, for any H |c, d] S (a, b). if c 1, we have U(H)= = if d - c 1, we have
PP 1 S < hl. and
Pr [d < < Pra-n / S x d 1 d-12/
d d-1<f
U(H)
This is because under d 2 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 - < 1, because every agent d 1 can receive positive classification by manipulating, the error of H corresponds to the probability mass between d - and f: if d - -1 < f. this corresponds to the negatives who can manipulate and receive positive classification, and d 1 2 f, this corresponds the positives who cannot manipulate to receive positive classification.
Now assume b case, we want to pick d such that d d- 1 is as close as possible to f. More formally, our goal is to pick [c, d] S [a, b) such that h E [c, d] and that the probability mass between - 1 and f minimized. In this case, one can see, via case analysis, that d = min (b, max (h, f + 1)) is the optimal value, and that e can be any point in [a, h].
1, which implies that c 1. At a high level, maximize U(H) in this
If b - a 2 1, then both d - c < 1 and c 2 1 are possible. If d - c < 1, then the optimality of [c, d] where e is any point in (b 1, h), and d min (b, max (h, f + 1)) can be established as above. Note that the choice of c E (b 1, h] guarantees that d - c < 1. If
c 2 1, then the utility of the learner doesn't I change if [c, d] [a, simply because the agents do not manipulate for any Ic, d] such that d 2 1. Finally, the optimal interval is chosen based on which case (d - c < 1 vs. c 1) leads to higher utility.
E
The Complete Exposition of Section 4.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 {h1, he,..., .hh) .h,).................... S H that includes the adopted classifier h. The objective of the learner is to release H C [h1, h2 hn)
such that H. Throughout, we take h h2 where S S n, and assume h h2 S ... S hn-
We first state some facts about the agents' best response for any prior π over (hi, /2, h2,...,, hmn C H. To start, 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 {h1, fe..... hn3 H. we have BR(x. x. H) {x) U (h, E H h4 > x}.
Proof of Lemma E Recall from Lemma D.2 that BR(x, H) 2 x. Note that the utility of the agent x E X from manipulating to a point x' 2 x can be expressed as
uzl H)
(1,) (x' -x)
thi
For any x' 2 x such x' & (z)
U (l. E H: by > x), it is easy see that the agent can increase her utility by moving to point in {a} (he e H:h, > z}. which proves the lemma.
This lemma basically tells us that the best response of any agent is either to stay at its location, or to manipulate to h2 E H such that h; > z. Given such characterization of the agents' best response in our setup, we now characterize, for any classifier h; in the support of т,, the set of agents that will manipulate to h;-
Lemma F.2. Fix any prior x over (hi...., hnr and any H. for any i, {x: BR(x, H) = h1) + then for some a, {x BR(z. H) h.) (a, hi], where a satisfies un (a, H) ua (h,, H).
18

---

Proof of Lemmal E.2 Let = inf {x: (R(BR H) h.). Take any 2 E (a, h,]. We have, by
the definition of a, that there exists x' E (a, x) such that x' E {z BR(z, H) h4). imply-
ing BR(x', H) = h4. Therefore, BR(x', H) 2 x. The third part of Lemma D.2 implies that
h4 BR(a', H)= = BR(x, H). This proves that
(a,h,) S for (R(r. H) = h,)
If > h4 then (R(,, H) h2 by the first part of Lemma D.2 Therefore & {x BR(2, H) he).
If x a, then BR zz H) < h; by the definition of a, implying 2 & {a BR H) h2).
If œ = a, we will show that (R(x, H) = at Note that a S (R H) S h; by Lemma D.2 But if (R(a, H) > a, then by the third part of Lemma D.2 BR(a, Ff) = h4- So BR(a, H) (a. h.). Suppose (R H) = h4g Therefore, there exists > 0 such that ua H) + < ua H). by the definition of agents' best response and the fact that tie-breaking is in favor of smaller values (Remark D.I). Let e' < (0. e/2] be such that {h' E H a-
é' < h' < a = 0. Consider x' = - é'. We have, by Lemma D.2 and E.1 that (R(x', Hf {x'} Ula, hi]. But because BR(a, H) hi.
Lemma D.2 implies that BR (x HH E {I',
(11,,11 143. Note that
Ugr Mxrl H) (a H) un (hi, H)
ug (he, H) (e ('-
implying that BR(x', H) = hs But x'= = a - e' and this contradicts with the definition of a. Therefore BR(a, H)) a, and this completes the proof of the first part of the lemma.
We now focus on the second part of the lemma. Note that un (a, H) 2 Uc (h,, H), because Uo (a, H) < uo (h2, H),, then & (R H) S h;, Together with the first part of this lemma, and Lemma [.2 this implies that BR(a, H) = h1; which is a contradiction with the first part of the lemma. Next, we show that una (a, H) S ua (h,, H). Suppose ua H) > u (h,, H) + for some > 0.
Consider x = a + e/2. We have that
Urr (2, H) 2 (a H) ua (h;, H) + e uz (ha, H) + e/2
implying that BR(x,, H) * h4. This is in contradiction with the first part of the lemma. Therefore, Ma (a, H) = un (h,, H).
Next, we characterize the utility of any subset H released by the learner using a real-valued function of H. Define, for any H C (hi,...,hi hn) such that h E H,
RH a inf fx: BR(x, H) 2 h}
(10)
Note that BR(x h. H) > h for any H such that h H. Therefore, fz : BR(x, H) 2 h} is nonempty, and that Rh S. h for any H such that h E H. Our next lemma shows that R characterizes the utility of H for the learner, for any prior x over (hi,..., hn).
Lemma 4.4. Fix any prior ι over (h1....,ho hn We have that for any H S (hi...., hn such that E H. the utility of the learner. given by Equation 2 can be written as
[] PrIND [R x < fl
Rh <
U(H)-
1 PranD [f S xx < Rul
RH 2 f
(5)
Proof of Lemma 4.4 Recall that U(H) = Prz-n [ -) f())].
The claim follows from
the fact that h(BR (sr, H)) 1 if and only if > Ru- Note that if x Ru. then BR(x, H) >
(equivalently, (x, H)) = 1) by the definition of R₁ and Lemma D.2 Further, if BR (z. H) 2
then x Rn by the definition of Rd-
Given such characterization of the learner's utility, we will show that when the agents' prior is uniform over (hi,..., hn there are only polynomially many possible values that R can take, even though there are exponentially many H s.. Our algorithm then for any possible value R of RH, finds a subset H such that RH R. if such H exists. The algorithm then outputs the H with maximal utility according to Equation 5] More formally, we consider the following partitioning of the space of
subsets of (hi..... h. For any E {1, 2, .., n.. and for any E {k, k + I..... n define
S H1 C (hi,... hn 1 E H, [M|| L, BR(h, H) = h:
Recall & is the index of h in (li,..., An). i.e. h = ha.
19

---

Note that by Lemma E.1 BR = hg, H) [hg : k) for any H. Therefore, {St,e),, gives us proper partitioning of the space of subsets, which implies
max
U max max U(H)
HC M.H
of HES,,e
We will show that when the prior is uniform, solving max U(H) can be done efficiently, by showing a construction of the optimal H E St.e in our algorithm. To do so, we first show that RH (defined in Equation T0 can be characterized by hú, when we restrict ourselves H Si,e-
Lemma E.3. Fix any prior x over (hi,...,hab h.). If H E St,e. then fx BR(x, , H) = h₂} = (RH,hu hi].
Proof of Lemma E.3 We first show that Ry = inf {a BR(r, H) = h1). Fix any H S... Let QH = inf {o BR(x, , H) h.). First note that because H Si,e, we have BR(h, Hf) his and
therefore {a (R(x, x. H) = h,} + 0, and that Qи S h. Additionally, because
{o BR(x, f H1 h.) [ {x BR( 11) 2 h}
we have that QH 2 RH- So we have RS S QH S h. If QH * RH. then there exists RS < x < QH. such that h S BR(x, H) < h4. But, for x' = (R(x, H). we have BR(x', H)) = h2 x'
BR(x, H). This is in contradiction with the third part of Lemma D.2 (taking Iı I, and T2 x'). Therefore, Qu = Rg, and this proves the first part of the lemma. The second part the lemma is followed from part one and Lemma E.2
In particular, this Lemma implies that for H E St.e. we have RØ inf {a BR(x, H) = h,). Next, we demonstrate the possible values that Ry can take for uniform priors. In particular, the following lemma establishes that Ru can take only polynomially many values.
Lemma E.4. If the prior is uniform over (hi,..., N.a), then for any H E St,, Ru h; - -jff where j = 1(h' E H: : (Rn, h:]ll
Fix any H E Si.e. Note that Lemma E.3 and Lemma E.2 together imply that Un (R H) Un (h,, H). This implies
Proof of Lemmal E.4
Pr RR h1
Pr WNTTW
[h. 2 M) (h: Ra)
h hn=
But Pro R 2 h/] 51/L and Pre RRy 2 ht' j2/L where 5i and j2 are the number of hypotheses in H that are smaller (or equal to) Ru. and smaller (or equal to) he respectively. In other words,
1= = 11 H:N S RRH,, j2 = 1(h1 E H 1/ s shHHl
Therefore,
RH h4 j2 ji
which completes the proof.
Given such characterization, Algorithm 3 for any i, E, enumerates over all possible j E (1.....6 E} and returns a H such that H E Si.e and RH h4 j/e, such И exists. To elaborate, for any i, E, J. such H = Hr is constructed by first picking the j largest classifiers that are between I;; j/ and h; (including both f; and ft). If there are not at least j classifiers between h; jj/ and h;, then no such /l exists for E.j because of Lemma E.4 After picking the first j elements as described, the remaining L - j classifiers are first chosen from all classifiers that are less than (or equal to) h j/t, and once these classifiers are exhausted, the rest are taken from the classifiers that are larger than h; starting from the largest possible classifier, and going down until l classifiers are picked.
Note that this construction of И = H3² guarantees that BR(,, H') is minimized among all H'' with corresponding values of (i, f). Therefore, if BR (h,, H) > h4, it is guaranteed that no H exists for (i, (.). If BR(h, H)) h, then the construction of H H. guarantees that Rø inf (x: BR(x, H) h,) } is as small as possible. Therefore, if inf {x BR H) = h4} h; - j/e. then is guaranteed that no such H exists for (i, E,j) (note that inf {x: BR(x, H) = h2) 2 h -j/E
by construction). The algorithm finally outputs, among all H's found, the subset H with maximum utility according to Equation 5
This proves the following theorem.
20

---

Algorithm 3: The Learner's Optimization Problem: Discrete Uniform Prior
Input: ground truth classifier f, adopted classifier h 2 f. prior's support (hu..... ltn) where 11 ... lt, and h& h, data distribution D
for i k, 1, ,...,,,, do for = 1, 2,...... 1,2....,,200
for j ......,, Ed
R f- h; 1/e;
// candidate value R for Ry
Si - {h' E (hr
hnt R< & shy;
// all classifiers between R and
h.
82 (h' (l....., hn) : 11' R}:
classifiers smaller than R. // all classifiers larger than hy
S. (h' E (h1..... hn h' h
if R [Si| < then
H t1;
// no H exists for (i,6,5).
else
H {h, ha]:
H) H U UMAA (St H1))):
// MAX.. A largest elements
[S]] 2 { then
T <- subset of size l from S2
else
+ 1+-SUUMAN -- (Sa):
11 MAX (+) m largest elements
H + H1 UT:
if BR(h,, H. hu then
H +l;
// no H exists for (1,55).
else
inf
x: BR(x, H hss then
H3 +1;
1/ H exists for (1,6,))
if
Hi U/e DCO
then
else
if
then
U.e + Prz-D R<<<<f // utility according to Equation
if R then
U t Pra-D [f < R] // utility according to Equation
Output: H HJ. where (i",E"; E argmax U.C.
Theorem 4.6. There exists an algorithm (Algorithm 3) that for any n, any uniform prior over (hi...., "at...,hhy hn that includes h, and any data distribution D, returns H* S (hi....,he hn) in time
Onn²) such that h e H* and that U (H+)= max HeH U(H).
F Missing Proof of Section 4.2
Theorem 4.7. Fix any h 2 f- For any prior n over (hi....,hhu hha that includes h, we have I)
FPR(H) & FPR((h)) 2) FNR(())) FNR(H) for every S H such that h E H.
Proof of Theorem 4.7 We begin by showing that FPR(H) < FPR((H)). Let & E X' be such that f(x) 0 and h (BRR H)) 1. We will show that h(BR(x, (h))) -.
Lemma E. together with 2 ff imply the existence h2 such that BR(x, H) hy > x (as f(x) * (BR(z, H.)). This further indicates that when H is released, the utility of the agent is strictly higher when it manipulates to hy. compared to not moving:
Up (h,, H) Σ m(h)) (hi -x)
>)>>>>>>>>>>>>>> >
Σ T(hi) ux H)
21

---

Note that h(BR(z, H)) = 1 and (R(x, H) = hy implies that h 2 h, and therefore:
Uz (h, (bb) =1 - (h- - x) 2 (h+) - (h1 - x)
T(12)) = Us (1 {h})
Eh
Since Lemma
E implies that BR(x, (ht)) E far we derive from the above inequality that h(R(E, (ht) 1. This proves the first part of the theorem.
Next, we show that (N)((()) < FN R(H) for every H S H. Let a E X be such that f(#) = and h (B,,, (b))) 0. and let H be any subset of H. We will show that ((BR(z, H)) = 0.
Lemma implies that (R {b}) E h). Together with ((BR(z, {h})) 0, we derive that BR(r, htj 2, and thus:
(h, (h)) 1 - (h- - x) S un (2., [h]) = 0
Now, for every hg such that h2 2 h, we have:
Un un(hi H) -b)
(h, 100--20 S
S 20
Σ M/ (ha) = ux (x H). Eh
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 hy such that hg h. This implies that h h(BR(z, H)) = O.
G Optimal Information Release for Minimizing FPR
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-informaation-ellless is optimal for FPR). Fix any B > 1 and any 0 < 1 < B
Let D be the uniform distribution over X' = [0, BJ. and f(x) single-sided threshold classifiers and suppose the adopted classifier h = 1 [x: 2 + 1]. Under any prior over H. one can show that the full information release of {h} achieves perfect FPR for this setting: F FPR((())))) = O.
[> 2 (). Let H be the class of
Example G.2 (No-information- -nfeeeerttioo-rleesse one can show that releasing the support of the prior H = [hi.s, h22) achieves FPR(H) = 0. whereas full information release of the adopted classifier h = hr achieves FPR (h)) = 0.9/1.9 1.9 x 0.47. Note that H (11.s, h2) } is the support of the prior, so it constitutes as no-informaaiio--eleasee In other words, we have FPR(H') = FPR(H)= = 0 for every H' such that H S H' C H.
release is optimal for FPR). Under the same setup as in Example 2.4
Claim G.3. There exists an instance in which neither full-nffu mull-information--eeeee release nor no-information- release are optimal when the utility function of the learner UPPR
Proof of Claim G.3 We construct such an instance follows. Suppose the domain is X {x1, x22
with I1 = 0, T2 = 0.4 and the distribution D is given by D(z1) = D(z2) = 0.5. In addition. consider 0.3, and hypothesis class H. {h1, h2, hs} where h1 0.1, h2 0.5, ha 0.7, and a prior distribution π such that (hh = 0.2, π (h2) = 0.1, 7 (ha) = 0.7.
Observe that under full-informatioo-releesss
1 for every h E H. Now suppose hg is the adopted classifier. We have that B B (h)) = 0.5 implying h ((BR(x1,
FPR (h))
= # f(x1) O implying Ji is false positive under (h) release. Additionally, BR H) = 0.7 implies that ((1((1, H)) = 1 + f(x1) = 0 implying x1 is a false positive under H release. Further, holds that BR((1, h2)) = 0.1 and so h(BR(I,, h2)) = 0 fz1). Moreover, in this particular instance, releasing { h2) achieves perfect utility as BR( (h1, h2))) = 0.5 which
implies h h(BR(22, (h1, hz))) 1 (xx2).
H Possible Information Leakage Through Firm's Choice of H
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 [ > 1. More specifically,
We remark that the claim holds when the utility function is U (as defined in Equation 2 well.
22

---

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 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 [0, is uniform, c(3;,a²) |or x/), and f(z) = 1 [x 2 0.15). The set of classifiers available to the firm is H. = {hi, h2g where Q1 0.1, 02 0.9 each classifier's respective threshold.
Following our Bayesian model, the firm chooses to release subset H C H. over which the agents have a uniform prior x H- The agents know that the firm is choosing H to optimize accuracy, i.e. the function (H) = Pr [h" (An release a subset H which is arg max (H)) = h1] but not in arg maxHcH (H))
= y] (where
[r: 2 TD. We will show that the firm can
h2]. allowing the agent to reason that h" must be h1.
Proposition H.2. Consider Example II. If the agents know agents know that f(x) = 1 [ 2 0.15] and the prior D, they can infer that h
h1-
Proof. We first solve for arg max (U))) = hi]. Suppose H = {h1] Then all agents know h" = h1. If x S 01, the agent will manipulate to on to get a positive outcome if c(x, 01) > O, which is always true. If x 2 0n, agents will stay the same to get positive outcome. So the set of misclassified agents is those with x E 0, T] and (((ha])
T 0.85. Now suppose H [h, h2). Agents believe each classifier is h" with probability 0.5. If x 2 022 agents are 0i I x S 02 agents will manipulate to
guaranteed a positive outcome and stay the same. 02 to get a positive outcome if 1 - c(2, a2) > 0.5. so all agents with E 0.94 will be classified correctly. The rest of the agents with x E [a1, 0.4] will stay the same to get a positive outcome with probability 0.5, and those with [a will be misclassified. Lastly, if x < a1, agents will manipulate to 0g to get a guarantced positive outcome if 1 - d(1, 02) > 0.5 c(1, a1) (a.k.a. 1- 0.9
0.5 0.1 - z), which is never true, and otherwise manipulate to aj to get a positive outcome with probability 0.5 if 0.5 c(x, 01) > 0. which is always true. So the set of misclassified agents is those with E [0, 7] and Ufh1, h2]) arg maxHCH
T 0.85. Therefore
h = h = {(h1). (h1, h2]l.
Now we consider arg max (HH)) (H) ht = h22. If S a2, the agent will manipulate to 02 to get a positive outcome if c(x, (v2) > O, which is always true. If i 2 a22 agents will stay the same to get a positive outcome. So the set of misclassified agents is those with x E [0, 7] and U((h2) = 1 1- T = 0.85. Now suppose H {h1, }. As before, agents believe each classifier is h" with probability 0.5. If x 2 ag agents are guaranteed a positive outcome and stay the same. If a; S x S a22 agents will manipulate to ag to get positive outcome if 1 c(x, 02) 0.5, all agents with correctly. The rest of the agents with x E [an, 0.4] will stay the same to get positive outcome with probability 0.5, and will be misclassified. Lastly, if x < 01, agents will manipulate to aq to get 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(fhi,, h2a) (.) Therefore arg max max (U())
h2]. Suppose H = [h2]. As before, all agents know
(0.4, 0.9) will be classified
00.9 0.4| = 0.5, which is less than for h2] = ((h2]]
We have shown that if the firm chooses H* (h1, the agent reason that H arg maxxcH(( (H) = hi] but H & arg mggxacc((U(H))) = h2). so ht must be h1. 0
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our introduction provides 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 contain all formal statements and their proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Section
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
24

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA].
Justification: This is theoretical paper. All results carefully proven, and do require experiments to establish correctness.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aublic//uiide//Coeettuiiiss cossssiinoooyyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtps/cccppplclguuiieeeeaec
Saaeee/CCoSSSubisss..S.. www.sssoiccgyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification: This is 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 the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
Justification: This is 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This is 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 paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpe///eerrppp..c//bb////hhiia
Answer: [Yes]
Justification: We have carefully read and comply with the NeurIPS code ethics. This work is theoretical and we do not foresee harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We note that our work 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, discuss potential broader impacts in Section A both positive and negative.
27

---

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 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA].
Justification: The work is entirely theoretical; do not release new data or models. Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
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 used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
28

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
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/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
29

---

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.
30


Reviews:
[{"review_id": "FNqUEA16Im", "reviewer": "Reviewer_F6uC", "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)$.\n\nThe model includes the following key components:\n\n1. **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'$.\n\n2. **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.\n\n3. **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'$.\n\n4. **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. \n\nThe paper provides the following theoretical contributions:\n\n1. **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$.\n\n2. **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.\n\n3. **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.\n\n#### Mathematical Formulation\n\n1. **Agents and Learner**:\n    - Agents: $(x, y)$ where $x \\in X$, $y \\in \\{0, 1\\}$.\n    - Mapping: $f: X \\to \\{0, 1\\}$ such that $y = f(x)$.\n    - Hypothesis class: $H \\subseteq \\{0, 1\\}^X$, with the learner using a fixed classifier $h \\in H$.\n\n2. **Cost Function**:\n    $$\n    c: X \\times X \\to [0, \\infty) \\quad \\text{where} \\quad c(x, x') \\text{ denotes the cost of changing } x \\text{ to } x'.\n    $$\n\n3. **Prior Distribution**:\n    $$\n    \\pi: H \\to [0, 1] .\n    $$\n\n\n5. **Oracle-Efficient Algorithm**:\n    - 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.\n    - The best response algorithm runs in $O(n^{d+1})$ time, making $O(n^d)$ oracle calls.\n\nIn 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.", "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?\n- How do the proposed algorithms and strategies perform in empirical settings? Are there practical examples or case studies that demonstrate their applicability and effectiveness?\n- How can the model be extended to dynamic environments where classifiers are updated over time?\n- Is there specific conditions where partial information release outperforms full information release? Are there scenarios where partial information could be detrimental?\n- How does the Oracle complexity algorithm scale with higher dimensions or larger hypothesis classes when $d \\approx n$? Are there potential computational bottlenecks?", "limitations": "The authors discuss the limitations of the methods adequately.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Bayesian modeling: shifting to a Bayesian framework where agents have a distributional prior on the classifier is a novel and realistic approach, providing a more flexible model than the standard full knowledge assumption.\n- Principled algorithms: the paper introduces oracle-efficient algorithms for low-dimensional linear classifiers and sub-modular cost functions, which are valuable contributions to strategic classification.\n- Mathematical and algorithmic analysis: the comprehensive analysis of the learner’s optimization problem, including conditions for the optimality of partial information release, adds depth to the study.\n- Real-world examples: practical examples, such as job seekers using Glassdoor, help ground the theoretical concepts in real-world scenarios.", "weaknesses": "- 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.\n- Fixed Classifier Assumption: The learner’s commitment to a fixed classifier limits the model's applicability in dynamic environments where classifiers are frequently updated.\n- Empirical analysis: the paper could be enriched with an empirical study of the methods discussed theoretically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for suggesting interesting questions that can be natural future directions of this work such as other utility functions and dynamic environments. \n\n- Regarding the performance of partial information release versus full information release, while we have examples where one outperforms the other, the exact characterization of instances in which one outperforms the other is not known. This is indeed an interesting question.\n\n- For any $n$ and $d$, the best response algorithm for linear classifiers (Algorithm 2) has oracle complexity of $\\sum_{j=0}^d {n \\choose j}$ which is $O(n^d)$ for $d \\ll n$ and $O(2^n)$ for $d \\approx n$. This is why we need that the dimension is relatively small compared to $n$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7TvpSDBEIO", "reviewer": "Reviewer_oMrT", "summary": "* This paper investigates strategic classification in a partial-information setting using a Bayesian common-prior framework.\n* 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.\n* 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.", "questions": "* Common prior in practical settings:\n  * What could be reasonable assumptions for the functional form of the common prior $\\\\pi$ in practical settings?\n  * How can $\\\\pi$ be estimated from data?\n  * In which plausible practical scenarios does the size of $\\pi$'s support induce a practically-significant discrepancy between efficient and inefficient algorithms?\n* Dishonest information disclosure:\n  * How much power can the learner gain from acting in a non-truthful way?\n  * Can truthful information sharing (by the learner) can be enforced or incentivized?\n* What are the consequences of the learner not knowing the feature-label distribution $D$, and being required to estimate it from data?\n* 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 are discussed in the appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Paper is very well-written, and easy to follow.\n* Model is clean and concise, and captures an interesting aspect of information disclosure.\n* Theoretical analysis presents both lower and upper bounds, helping establish a hardness spectrum that can motivate future work.", "weaknesses": "* The interaction model presented in the paper makes strong assumptions which may not be applicable in practical scenarios. In particular:\n  * 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.\n  * Assuming that the agents’ prior distribution $\\\\pi$ is known to the learner.\n  * 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.\n* Interaction model seems to be vulnerable to learner dishonesty.\n* The paper does not contain empirical evaluation, and it's not clear whether the proposed scheme is feasible in practical scenarios.\n* Positive results on the learner’s optimal information disclosure are limited to one-dimensional classifiers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these detailed comments which we shall now do our best to answer!\n\nPart 1\n\n**Interaction model, true relation between features and labels is known to the learner:**\n\nThis is an assumption made in prior work on strategic classification (e.g. see [2,4]). That being said, extending our results to a setting in which the learner only has access to labeled examples is an interesting future work.\n\n**Agents’ prior distribution is known to the learner:**\nThis is a common assumption in Bayesian Persuasion and in game-theoretic Bayesian settings, e.g., [1]. \n\nFrom a motivational point of view, for example, employers also have access to job interview questions dataset such as Glassdoor when hiring, and may have a good understanding of the information available to the agents. This prior can also encode agents having a very simple prior showing understanding top few features that are commonly known, which is reasonable in settings such as credit scoring (where everyone knows most agents understand that paying on time has a positive impact, for example). There are also natural cases where we can assume that the prior is uniform, corresponding to the agents having no prior information revelation in other Bayesian settings (e.g., active learning [5], the last section on  pg. 2.).\n\n\n**Assuming that $\\pi$ has finite support:**\n\n We will include this extension in the final version of the paper: note that one can often discretize the space of possible classifiers to reduce to a finite setting. We do note that only our results in Section 3 rely on finiteness, but small cardinality is not required, so discretization is sufficient for our purposes. We have complemented our results in Section 4 which primarily focuses on discrete uniform priors by considering the case of continuous uniform priors (which have infinitely many elements in their support); see Section D.2 in the Appendix for details.\n\nRegarding the discretization approach for Section 3, note that if $\\pi$ has infinite support size, we can ignore classifiers with sufficiently small probabilities (i.e., $poly(\\epsilon)$), as they do not affect the manipulation strategy when searching for a $(1+\\epsilon)$-approximate solution. The number of classifiers in the support with probability at least $poly(\\epsilon)$ for a fixed $\\epsilon>0$ is at most $1/poly(\\epsilon)$ which is a finite number. Therefore, to obtain a nearly optimal solution, it suffices to only consider probability distributions $\\pi$ with finite support size.\n\n\nAlso, observe that finite $\\pi$ captures broad phenomena already, like job interview questions on sites like Glassdoor/Leetcode. \n\n**Common prior in practical setting (1. What could be reasonable assumptions for the functional form of the common prior $\\pi$ in practical settings? 2. How can $\\pi$ be estimated from data? 3. In which plausible practical scenarios does the size of $\\pi$'s support induce a practically-significant discrepancy between efficient and inefficient algorithms?):**\n\n1. In Section 4.1, we think of the prior as uniform over a set; this can be seen as initially having no information about the classifier, thinking all classifiers are equally likely on the support (the support itself could encode information about what reasonable classifiers are). This can be easily estimated from data. If there is any prior knowledge (e.g., 0.1 fraction of technical interview questions involve dynamic programming questions), we assume the prior incorporates this knowledge.\n\n2. Estimating $\\pi$ from data is a good question. In some of the more specific settings that exist in practice, like humans adapting to high stakes test/interview questions, humans do maintain tables of counts over the discrete range of possible questions, and then create the prior by dividing the count for each question by the normalization term, e.g. summing over all counts. E.g. when people take a test they then share this information with their peers who also have access to the database. \n\n3. It is an interesting question thinking about the impact of $\\pi$ on efficient/inefficient algorithms in practice. This question will require further work.\n\n**Dishonest information disclosure How much power can the learner gain from acting in a non-truthful way?**\n\nWe restrict to truthful information disclosure as in Bayesian Persuasion [3]. Relaxing this requirement obviously extends the action space of the learner and hence can only increase the learner’s utility. Here is an example in which lying to the agents can achieve optimal utility for the learner: consider a case in which $X = [0,1]$, $D$ is uniform over $X$, and $f(x)=1[x \\geq 0.5]$ is the ground truth and $h=f$ is the deployed classifier. If the learner lies to the agents and tells them that the deployed classifier is $h’(x)=1$ (i.e. everyone is qualified), regardless of what the prior distribution of the agents is, no one will manipulate. The learner can then deploy $f$ for optimal accuracy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nvT4nYZ8TU", "reviewer": "Reviewer_XrSi", "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.", "questions": "1. Could you describe more clearly and intuitively what the oracle does? Also why it requires an input as $R^+ \\cap R^-$?\n2. Why do you take an oracle into consideration in the agent best-response problem?\n3. 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": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The problem of strategic classifying is well-motivated. The characterization of the Bayesian setting and partial information release is very reasonable. \n+ The Stackelberg model of the problem is reasonable. \n+ The technical results are non-trivial.", "weaknesses": "- All the positive results seem to be under strong constraints. This may imply that the problem itself is very difficult. \n- 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\". \n- It's kind of unclear what there is an oracle in the agent's best response problem and what does the oracle do.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for this review, we will now respond in detail. \n\n**Positive results seem to be under strong constraints. This may imply that the problem itself is very difficult:**\n\nA challenging aspect of work in strategic classification theory, along with other fields in ML is that with minimal assumptions, many problems are intractable.\n\nFor instance, we show that the learner’s optimal information release problem is NP-hard when the agents’ prior can be arbitrary, and a similar result is exhibited in the first strategic classification paper [Hardt et al. 2016].\n\nThat said, despite such hardness barriers, adding some assumptions to relax the problem is important so we can investigate specific challenges, craft initial algorithms that then can be used as a foundation for later empirically performant algorithms. \n\n**Role of the oracle:** \nDescription of the oracle: the oracle solves the following “projection” problem: given an agent $x$ with cost function $c$, a collection of classifiers $\\{h_1, \\ldots, h_n\\}$, and a binary (0/1) vector $b=(b_1, \\ldots, b_n)$, the oracle returns a point $z$ that minimizes the cost $c(x,z)$ for the agent such that for all $i$, $h_i (z) = b_i$. Instead of using the binary vector $b$, in our paper we adopt $R^+$ (classifiers whose corresponding $b_i$ is $1$) and $R^-$ (classifiers whose corresponding $b_i$ is $0$). Note that when $n=1$, this is simply projecting the point $x$ onto either $\\{h_1(z) = 1\\}$ or $\\{h_1(z) = 0\\}$, according to the cost function $c$. When $n>1$, this is the projection of $x$, according to the cost function $c$, onto one of the $2^n$ regions created by the $n$ classifiers (each classifier has a positive and a negative region) which we denote by $R^+ \\cap R^-$. Informally, the oracle abstracts out the task of finding the closest point, w.r.t. a given cost function, to a given point (an agent), that passes only the classifiers in $R^+$ without passing the classifiers in $R^-$ (or equivalently a point in $R^+ \\cap R^-$ because we require to pass exactly ones corresponding to $R^+$ and nothing more)..\n\n\n**Why we use an oracle:** we need an oracle model because solving the best response problem in Equation 1 may span a large class of potential deployed classifiers, prior distribution $\\pi$, and cost function $c$, and specialized optimization techniques are required for each problem class. In our setting, we want to focus on the details of information release so by assuming the oracle model we can isolate the impact of the information release, while abstracting away the agent’s ability to solve the best response problem which is tangential to our point. This allows our assumptions to model a range of agents using different optimization methods to solve Equation 1; further, we can plug in a large class of optimization methods in place of the oracle as needed for specific applications. \n\n\n**Re Question about Remark 4.3:**\nBy “harder”, we mean that the classifier $h$ is more stringent and harder to pass, in that it uses a higher threshold than the true classifier $f$. The reason we need to do so is because the agents’ ability to manipulate their features allows them to obtain a *higher* perceived score than their true score. The learner needs to make the classifier more difficult to pass to compensate for this strategic behavior and inflated scores. This is relatively standard in strategic classification, where the classifier is “pushed to the right” to be robust to manipulation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nT1SpiLZV6", "reviewer": "Reviewer_VHeD", "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.", "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).\n\nLine 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.\n\nDef 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?\n\nLine 314, h \\ge f: notation abused here.\n\nSec 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": "I don't have concerns.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Conceptually, the problem of \"ambiguous\" classifiers is natural and interesting.  The paper makes an attempt at modeling the problem and presents a variety of results, which might trigger further progress.  The paper (especially the introductory parts) is also quite well written and polished.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for these questions, we will now respond in detail.\n\n**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).):**\n\nWhile working with randomized classifiers is an interesting direction for future work, it is still susceptible to the same criticism of the reviewer: over time the agents will be able to learn what distribution the learner is using and best respond according to that. Also, in practice, it may be undesirable for a learner to constantly change their deployed classifier, both because it is costly but also because it may be perceived as unreliable or unfair.\n\nWe believe our model is a natural and simple first attempt towards understanding incomplete information in strategic classification. Having said that, we completely agree with the reviewer that the use of randomized models is an interesting direction for future work, as we have mentioned it in the limitations section: “... However, we note that changing the screening algorithm requires significant resources, and the rate at which the classifier is updated is generally slower than the rate at which decisions are made. In practice, this means that strategic agents effectively face a fixed model in each “batch” between updates.”\n\n**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.):**\n\n\n\nWe call it truthful because we require that the learner includes its deployed classifier $h$ in the shortlist $H$. In other words, we don’t allow the learner to `lie’ to the agents. Moreover, after releasing $H$, regardless of what the common prior distribution $\\pi$ is, the probability of $h$ in the posterior $\\pi \\vert_H$ can only increase.\n\nWe note that the behavior of our agents follow a traditional Bayes update, the natural model used for updating informational beliefs in the vast majority of related game theory and in particular Bayesian Persuasion [3] literature. Truthfulness and believing that the learner is truthful are also the standard assumption in settings involving information revelation [3], with the motivation that these games are played in a repeated context where lying is observable and punishable in the long-term.\n\n\n\n**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?):**\n\nThe reviewer is correct that if $h$ is not the strategic optimal classifier (i.e., one that maximizes the strategic accuracy in the full information release game), this will not be a generalization of the full information release game. We will clarify it in the final version of the paper.\n\nWe assume that $h$ is fixed and the learner is not willing to change it due to cost issues: as mentioned in the paper, “... However, we note that changing the screening algorithm requires significant resources, and the rate at which the classifier is updated is generally slower than the rate at which decisions are made”.\n\nWe further note that in the case where the fixed $h$ is the strategic optimal classifier in the full information release game (i.e. “standard” strategic classification), our game essentially becomes a generalization of the full information release game because the learner can always choose $H=\\{h\\}$. \n\n**Line 314, $h \\ge f$: notation abused here.** Remark 4.2 explains the notational abuse that we adopt for simplicity. We simply view $f$ (or $h$) both as a function and their corresponding real-valued threshold, so $h \\ge f$ simply means that the threshold for $h$ is larger than or equal to the threshold for $f$.\n\n**Sec 4: why not publish $h = f + 1$ (in this setup, why shouldn't the learner simply publish the exact optimal classifier ($h = f + 1$, which is perfectly accurate after manipulation)? I guess this is also where fixing h as an input parameter makes less sense.):**\n\nReleasing $h=f+1$ is not necessarily an optimal or even a feasible solution because in general the space of thresholds is bounded (which is natural because test scores are normally bounded, and so must be the thresholds we work with on those test scores). Observe that this is shown in Example 2.4.\n\n[3] Kamenica, Emir, and Matthew Gentzkow. \"Bayesian persuasion.\" American Economic Review 101, no. 6 (2011): 2590-2615.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)