Bayesian Persuasion for Algorithmic Recourse
Authors: Keegan Harris
Valerie Chen
Joon Sik Kim
Ameet Talwalkar
Hoda Heidari
Steven Wu
Venue: NeurIPS 2022 Accept (2022)
Keywords: bayesian persuasion
algorithmic recourse
strategic learning

Abstract: When subjected to automated decision-making, decision subjects may strategically modify their observable features in ways they believe will maximize their chances of receiving a favorable decision. In many practical situations, the underlying assessment rule is deliberately kept secret to avoid gaming and maintain competitive advantage. The resulting opacity forces the decision subjects to rely on incomplete information when making strategic feature modifications. We capture such settings as a game of Bayesian persuasion, in which the decision maker offers a form of recourse to the decision subject by providing them with an action recommendation (or signal) to incentivize them to modify their features in desirable ways. We show that when using persuasion, the decision maker and decision subject are never worse off in expectation, while the decision maker can be significantly better off. While the decision maker’s problem of finding the optimal Bayesian incentive compatible (BIC) signaling policy takes the form of optimization over infinitely many variables, we show that this optimization can be cast as a linear program over finitely-many regions of the space of possible assessment rules. While this reformulation simplifies the problem dramatically, solving the linear program requires reasoning about exponentially-many variables, even in relatively simple cases. Motivated by this observation, we provide a polynomial-time approximation scheme that recovers a near-optimal signaling policy. Finally, our numerical simulations on semi-synthetic data empirically demonstrate the benefits of using persuasion in the algorithmic recourse setting.

Bayesian Persuasion for Algorithmic Recourse
Keegan Harris Carnegie Mellon University keeganh@cmu.edt
Valerie Chen Carnegie Mellon University
Joon Sik Kim
Carnegie Mellon University
valerriechencmm.ed
joonkim@cmu. edu
Ameet Talwalkar Carnegie Mellon University talwalkar@cmu. edu
Hoda Heidari
Zhiwei Steven Wu Carnegie Mellon University
Carnegie Mellon University hheidar @cmu. edu
zstevenwu@mmu.c edu
Abstract
When subjected to automated decision-making, decision subjects may strategically modify their observable features ways they believe will maximize their chances of receiving a favorable decision. In many practical situations, the underlying assessment rule is deliberately kept secret avoid gaming and maintain competitive advantage. The resulting opacity forces the decision subjects to rely incomplete information when making strategic feature modifications. We capture such settings game of Bayesian persuasion, in which the decision maker offers form of recourse to the decision subject by providing them with an action recommendation (or signal) to incentivize them to modify their features in desirable ways. We show that when using persuasion, the decision maker and decision subject are never worse off in expectation, while the decision maker can be significantly better off. While the decision maker's problem of finding the optimal Bayesian incentive-compatible (BIC) signaling policy takes the form of optimization over infinitely-man many variables, we show that this optimization can be cast as a linear program finitel-many regions of the space of possible assessment rules. While this reformulation simplifies the problem dramatically, solving the linear program requires reasoning about exponentially -many variables, even in relatively simple cases. Motivated by this observation, we provide a polynomial-time approximation scheme that recovers near-optimal signaling policy. Finally, our numerical simulations on semi-synthetic data empirically demonstrate the benefits of using persuasion in the algorithmic recourse setting.
Introduction
High-stakes decision-making systems increasingly utilize data-driven algorithms to assess individuals in such domains as education [3]. employment [ [6], and lending [24]. Individuals subjected to
these assessments (henceforth, decision subjects) may strategically modify their observable features
in ways they believe maximize their chances receiving favorable decisions [21 [ The decision
subject often has of actions/interventions available them. Each of these actions leads to some measurable effect on their observable features, and subsequently, the decision they receive. From the decision maker's perspective, some of these actions may be more desirable than others. Consider credit scoring as an example Credit scores predict how likely an individual applicant
'Oteer examples of strategic settings which arise as result of decision-making include college admissions, in which college/university decides whether or not to admit a prospective student. hiring. in which company decides whether not hire a job applicant, and lending, in which banking institution decides to accept reject somcone applying for loan. Oftentimes, the decision maker aided by automated decision-makee making tools in these situations (c.g.,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is to pay back a loan on time. Financial institutions regularly utilize credit scores to decide whether to offer applicants their financial products and determine the terms and conditions of their offers (e.g., by setting the interest rate or credit limit). Applicants regularly attempt to improve their scores given their (partial) knowledge of credit scoring instruments. For instance, a business applying for loan may improve its score by paying off existing debt or cleverly manipulating its financial records to appear more profitable. While both of these interventions may improve credit score, the former is more desirable than the latter from the perspective of the financial institution offering the loan. The question we are interested in answering in this work is: how can the decision maker incentivize decision subjects take such beneficial actions while discouraging manipulations?
The strategic interactions between eeeision-making algorithms and decision subjects has motivated a growing literature known as strategic learning (see e.g., [8] [TT 40 29 [9]). While much of the prior work in strategic learning operates under the assumption of full transparency (i.e., the assessment rule is public knowledge), we consider settings where the full disclosure of the assessment rule is not viable. In many real-world situations, revealing the exact logic of the decision rule is either infeasible or irresponsible. For instance, credit scoring formulae are closely guarded trade secrets, in part to prevent the risk of default rates surging applicants learn how to manipulate them. Moreover, the underlying decision rule is often fixed ahead of time due to institutional structuring. In our credit scoring example, one department of the bank may be in charge of determining the threshold on the credit assessment, while another department may be in charge of offering recourse
In such settings, the decision maker may still have a vested interest in providing some information about the decision rule to decision subjects in order to provide a certain level of fransparency and recourse. In particular, the decision maker may be legally obliged, or economically motivated, to guide decision subjects to take actions that improve their underlying qualifications. To this end, instead of fully revealing the assessment rule, the decision maker can recommend actions for decision subjects to take. Of course, such recommendations need to be chosen carefully and credibly; otherwise, self-interested decision subjects may not follow them or may utilize the recommendations to find pathways for manipulation.
We study a model of strategic learning in which the underlying assessment rule is not revealed to decision subjects. Our model captures several key aspects of the setting described above: First, even though the assessment rule is not revealed the decision subjects, they often have prior knowledge about what the rule may be. Secondly, when the decision maker provides recommendations to decision subjects on which action to take, the recommendations should be compatible with the subjects' incentives to ensure they will follow the recommendation. Finally, our model assumes the decision maker discloses how they generate recommendations for recourse-an increasingly relevant requirement under recent regulations (e.g.. 110
Utilizing our model, we aim to design a mechanism for a decision maker to provide recourse to a decision subject who has incomplete information about the underlying assessment rule. We assume the assessment rule makes predictions about some future outcome of the decision subject (c.g.. whether they will pay back loan in time if granted one). Before the assessment rule is trained (i.e., before the model parameters are fit), the decision maker and decision subject have some prior belief about the realization of the assessment rule. This prior represents the "common knowledge" about the importance of various observable features for making accurate predictions. After training. the assessment rule is revealed to the decision maker, who then recommends action for the decision subject to take, based on their pre-determined signaling policy. Upon receiving this action recommendation, the decision subject updates their belief about the underlying assessment rule. They then take the action which they believe will maximize their utility (i.c., the benefit from the decision they receive, minus the cost of taking their selected action) in expectation. Finally, the decision maker uses the assessment rule to make a prediction about the decision subject.
The interaction described above is an instance of Bayesian persuasion, game-theoretic model of information revelation originally due to Kamenica and Gentzkow] The specific instance of Bayesian persuasion we consider in this work is summarized in Figure
"Similar logic applies to other examples of strategic settings including: college admissions, in which someone associated with the university may have the ability to offer advice to applicants, but does not have the ability to unilaterally change the underlying assessment rule, or hiring, where a recruiter for a company may have knowledge of the factors the company uses to make hiring decisions, but may not be able to change this criteria or reveal it to job applicants.

---

Interaction protocol between the decision maker and decision subject
1. The decision maker and decision subject initially have some prior/belicf about the assessment rule that will be trained.
2. Before training, the decision maker commits to a signaling policy. After training, the assessment rule is revealed to the decision maker.
3. The decision maker then uses their signaling policy and knowledge of the assessment rule to recommend an action for the decision subject to take.
4. The decision subject updates their belief given the recommendation, and chooses action that they believe maximizes their utility.
5. The decision subject receives a prediction through the assessment rule.
Figure 1: Summary of the setting we consider.
Our contributions. Our central conceptual contribution is to cast the problem of offering recourse under partial transparency as game of Bayesian persuasion. Our key technical contributions consist of comparing optimal action recommendation policies in this new setup with two natural alternatives: (1) fully revealing the assessment rule to the decision subjects, or (2) revealing no information at all about the assessment rule. We provide new insights about the potentially significant advantages of action recommendation over these baselines, and offer efficient formulations to derive the optimal recommendations. More specifically, our analysis offers the following takeaways:
1. Using tools from Bayesian persuasion, we show that it is possible for the decision maker to provide
action recommendations that encourage rational decision subjects to modify their features through beneficial interventions. While the decision maker and decision subjects are never worse off in expectation from using optimal incentive-comye compatible recommen- dations, we show that situations exist in which the decision maker significantly better off in expectation utilizing the optimal signaling policy (as opposed to the two baselines, Section
2. We derive the optimal signaling policy for the decision maker. While the decision maker's optimal signaling policy initially appears challenging to compute (as it involves optimizing over continuoully-many variables), we show that the problem can naturally be cast linear program defined in terms of a finite set of variables. However, solving this linear program may require reasoning about exponentially-man variables. Motivated by this observation, we provide a polynomial-time algorithm to approximate the optimal signaling policy (Section
3. We empirically evaluate our persuasion mechanism on semi-synthetic data based on the Home Equity Line of Credit (HELOC) dataset, and find that the optimal signaling policy performs significantly better than the two natural alternatives across wide range of instances (Section
1.1 Related work
Strategic responses to unknown predictive models. To the best of our knowledge, our work is the first to use tools from persuasion to model the strategic interaction between a decision maker and strate- gic decision subjects when the underlying predictive model is not public knowledge. Several prior works have addressed similar problems through different models and techniques. For example, Akyol et al. [I] quantify the "price of transparency". a quantity which compares the decision maker's utility when the predictive model fully known with their utility when the model is not revealed to the deci- sion subjects. Tsirtsis and Rodriguez [1] study the effects of counterfactual explanations on strategic behavior. Ghalme et al. [7 compare the prediction error of a classifier when it is public knowledge with the error when decision subjects must learn version of it, and label this difference the "price of opacity". They show that small errors in decision subjects' estimates of the true underlying model may lead to large errors in the performance of the model. The authors argue that their work provides formal incentives for decision makers to adopt full transparency as policy. Our work, in contrast, is based on the observation that even if decision makers willing to reveal their models, legal require- ments, privacy concerns, and intellectual property restrictions may prohibit full transparency. So we instead study the consequences of partial transparency- common condition in real-world domains.
Bechavod et al. 2 study the effects of information discrepancy across different sub- sub-populations of decision subjects on their ability to improve their observable features in strategic learning settings.
3

---

Like us, they do not assume the predictive model is fully known to the decision subjects. Instead, the authors model decision subjects as trying to infer the underlying predictive model by learning from their social circle of family and friends, which naturally causes different groups to form within the population. In contrast to this line of work, we study setting which the decision maker provides customized feedback to each decision subject individually. Additionally, while the models proposed by [7 2
circumvent the assumption of full information about the deployed model, they restrict the decision subjects' knowledge to be obtained only through past data.
Algorithmic recourse. Our work is closely related to recent work on algorithmic recourse [2 Algorithmic recourse is concerned with providing explanations and recommendations to individuals who have received unfavorable automated decisions. A line of algorithmic recourse methods including focus on suggesting actionable or realistic changes to underlying qualifications to decision subjects interested in improving their decisions. Our action recommendations are "actionable" in the sense that they are interventions which promote long-term desirable behaviors while ensuring that the decision subject is not worse off in expectation.
4 2 [5]
Transparency. Recent legal and regulatory frameworks, such as the General Data Protection Regulation (GDPR) [T motivate the development of forms of algorithmic transparency suitable for real-world deployment. While this work can be thought of as providing additional transparency into the prcision-making process, it does not naturally fall into the existing organizations of explanation methods (e.g., as outlined in [77), as our policy does not simply recommend actions based on the decision rule. Rather, our goal is to incentivize actionable interventions on the decision subjects' observable features which are desirable to the decision maker, and we leverage persuasion techniques to ensure compliance.
Bayesian persuasion. There has been growing interest in Bayesian persuasion in the computer science and machine learning communities in recent years. Dughmi and Xu 12 characterize the computational complexity of computing the optimal signaling policy for several popular models of persuasion. Castiglioni al. 4 study the problem of learning the receiver's utilities through repeated interactions. Work in the multi-arm bandit literature 34] 33 22
6 39 leverages techniques from Bayesian persuasion to incentivize agents to perform bandit exploration. Finally, linear programming- based approaches to Bayesian persuasion have been studied in the economics literature [30 although the persuasion setting we study differs considerably.
Other strategic learning settings. The strategic learning literature 18
20
16
broadly studies machine learning questions in the presence of strategic decision subjects. There has been a long line of work in strategic learning that focuses on how strategic decision subjects adapt their input to machine learning algorithm in order receive more desirable prediction, although most prior work in this literature assumes that the underlying assessment rule is fully revealed to the decision subjects, which is typically not true in reality.
2 Setting and background
Consider setting in which decision maker assigns a predicted label 9 E {-1,+1} (e.g.. whether or not someone will repay a loan if granted one) to a decision subject with initial observable features XD- (f.. -T, 1) E Rd (e.g., amount of current debt, bank account balance, etc.) assume the decision maker uses a fixed linear decision rule to make predictions, i.c., 9 sign 0}.
f We
where the assessment rule 0 E θ C Rd The goal of the decision subject is to receive positive classification (e.g., get approved for loan). Given this goal, the decision subject may choose to take some action a from some set of possible actions A to modify their observable features (for example, they may decide to pay off a certain amount of existing debt, or redistribute their debt to game the credit score). We assume that the decision subject has actions {ai, 02,.... .am] ) E A at their disposal in order to improve their outcomes. For convenience, we add og to A to denote taking "no action". By taking action a, the decision subject incurs some cost c(a) R. This could be an actual monetary cost, but it can also represent non mon-monttrry notions of cost such as opportunity cost or the time/effort the decision subject may have to exert to take the action. We assume taking an action a changes a decision subject's 's observable feature values from Xy to Xg + Ax(a), where Ax(a) E ddd, and (a) specifies the change in the jth observable feature as the result of taking
We append 1 to the decision subject's feature vector for notational convenience.

---

action a For the special case of ag. we have Ax(as) = 0, c(ap) ) = 0. As result of taking action a decision subject, ds, receives utility uas (a. 0) = sign (xo + Ax(a)) 0} c(a). In other words, the decision subject receives some positive (negative) utility for positive (negative) classification,
subject to cost for taking the action.
If the decision subject had exact knowledge of the assessment rule O used by the decision maker, they could solve an optimization problem to determine the best action to take in order to maximize their utility. However, in many settings it is not realistic for decision subject to have perfect knowledge of 0. Instead, we model the decision subject's 's information through a prior II over 8, which can be thought of as "common knowledge" about the relative importance of various observable features in predicting the outcome of interest. For example, the decision subject may believe that prior payment history would likely be highly correlated with future default. We will use (-)) to denote the probability density function of II (so that (() denotes the probability of the deployed assessment rule being 0). We assume the decision subject is rational and risk-neutral. So any point during the interaction, if they hold a belief I1' about the underlying assessment rule, they would pick an action a" that maximize their expected utility with respect that belief. More precisely, they solve a" E arg max Ea-1r [Msssa O).
From the decision maker's 's perspective, some actions may be more desirable than others. For example, a bank may prefer that an applicant pay off more existing debt than less when apply- ing for loan. To formalize this notion of action preference, we say that the decision maker receives some utility udm (a) E R. when the decision subject takes action a. In the loan example, Udd (pay off more debt) Udd (pay off less debt).
2.1 Bayesian persuasion in the algorithmic recourse setting
The decision maker has an information advantage over the decision subject, due to the fact that they know the true assessment rule 0, whereas the decision subject does not. The decision maker may be able to leverage this information advantage to incentivize the decision subject to take a more favorable action (compared to the one they would have taken according to their prior) by recommending an action to the decision subject according to a commonly known signaling policy.
Definition 2.1 (Signaling policy). A signaling policy S A A is a (possibly stochastic) mapping from assessment rules to actions
We use a ~ S(O) to denote the action recommendation sampled from signaling policy S, where A is the realized recommended action.
The decision maker's signaling policy is assumed to be fixed and common knowledge. This is because in order for the decision subject to perform Bayesian update based on the observed recommendation, they need to know the signaling policy. Additionally, the decision maker must have the power of commitment, i.c., the decision subject must believe that the decision maker will select actions according to their signaling policy. In our setting, this will be the case since the decision maker commits to their signaling policy before training the assessment rule. This can be seen a form of transparency, as the decision maker is publicly announcing how they will use their assessment rule to provide action recommendationn/rccourse before they train the assessment rule. For simplicity, we assume that the decision maker shares the same prior beliefs II as the decision subject over the observable features before the model trained. These assumptions are standard in the Bayesian persuasion literature (see, e.g.,
In order for the decision subject be incentivized to follow the actions recommended by the decision maker, the signaling policy S needs to be Bayesian ceeepiiv-compaibbe..
Definition 2.2 (Bayesian incentive-compatiiiiis
Consider a decision subject ds with initial observ- able features Xo and prior 11. A signaling policy S is Bayesian incentive-compatbbe (BIC) for ds if "E-nnlus O)la = a] > Ee-nluu (a', O)la = a) for all actions a, a' E such that S(O) has positive support on o a.
"Since focus single decision subject, we hide the dependence of Ax the initial feature value Xo keep the notation simple.
'Note that since our model is focused on the decision maker's interactions with single decision subject, we drop the dependence of a on the decision subject's characteristics.
5

---

Example signaling policy S())
Case 1: E L. Recommend action d1 with probability g and action ag with probability 1 -
Case 2: e M.. Recommend action di with probability
Case 3: E H. Recommend action dj with probability g and action ag with probability 1
Figure 2: Signaling policy for the example of Section B
In other words, a signaling policy S is BIC if, given that the decision maker recommends action a, the decision subject's 's expected utility is at least as high as the expected utility of taking any other action a'.
We remark that while for the ease of exposition decision maker and a single decision subject, our results can be extended to a heterogeneous pop- ulation of decision subjects-an long as assume their interactions with the decision-maker are independent of one another (e.g., this assumption rules out one subject updating their belief based on the outcome of another subject's prior interaction with the decision-maker). Under such setting, the decision maker would publicly commit to a method of computing the signaling policy, given a decision subject's initial observable features as input. Once a decision subject arrives, their feature values are observed and the signaling policy is computed.
model focuses the interactions between the
3 Characterizing the utility gains of persuasion
the decision maker can achieve higher expected utility with an optimized signaling policy compared to if they provided no recommendation or fully disclosed the model. To characterize how much leveraging the decision maker's s information advantage may improve their expected utility under our setting, we study the following example.
As is generally the case in the persuasion literature 27 26 13
Consider a simple setting under which single decision subject has one observable feature zo (e.g., credit scorc) and two possible actions: ag = "do nothing" (i.c., Ar(as) = 0, c(ag) = 0, Udm (ap) = 0) and d₃ = "pay off existing debt" (i.e., Ar(a,) > 0, c(a,) O, Udm (a,) = 1). which in turn raises their credit score. For the sake of our illustration, we assume
to be mutually desirable trait, and credit scores to be a good measure of werthnsworsssssss. We assume the decision maker would like to design signaling policy to maximize the chance of the decision subject whether or not the applicant will receive the loan. this simple setting, the decision maker's decision rule can be characterized by a single threshold parameter 0, i.e. the decision subject receives a positive classification if x + 2 and a negative classification otherwise. Note that while the decision subject does not know the exact value of 6 they instead have some prior over it, denoted by II.
taking action a,, regardless
Given the true value of 0, the decision maker recommends an action a E {ag, a1} for the decision subject to take. The decision subject then takes a possibly different action a E {ay, a1}, J. which changes their observable feature from Zy to z Zo + Ar(a). Recall that the decision subject's utility takes the form Uds (a. 8) sign (xo + Ar(a)) + 0} c(a). Note that c(a1) > then was(ap, 0) > (ai 0) holds for any value of 0 meaning that it is impossible to incentivize any rational decision subject to play action d1. Therefore, order to enable the decision maker to incentivize action 11, we assume c(a1) 2.
We observe that in this simple setting, we can bin values of 0 into three different "regions", based on the outcome the decision subject would receive if 0 were actually in that region. First, if To + Ar(a1) + 0 O. the decision subject will not receive positive classification, even if they take action 01. In this region, the decision subject's initial feature value Zy is "too low" for taking the desired action to make a difference in their classification. We refer to this region as L. Second, To + 0 2 0, the decision subject will receive positive classification no matter what action they take. In this region, 2o is "too high" for the action they take to make any difference on their classification.
We refer to this region as H. Third, if xo + 0 < 0 and zo + Ar((1) + 0 > O. the decision subject will receive a positive classification if they take action an and negative elassification if they take action dg. We refer to this region as M. Consider the signaling policy in Figure

---

In Case 2, S recommends the action (a1) that the decision subject would have taken had they known the true 0, with probability However, in Case 1 and Case 3, the decision maker recommends, with probability q, an action (a1) that the decision subject would not have taken knowing 0, leveraging the fact that the decision subject does not know exactly which case they are currently in. If the decision subject follows the decision maker's recommendation from S, then the decision maker expected utility will increase from O to q if the realized 0 E L or 0 E H. and will remain the same otherwise. Intuitively, if q is "small enough" (where the precise definition of "small" depends on the prior over and the cost of taking action a1), then will be in the decision subject's s best interest to follow the decision maker's 's recommendation, even though they know that the decision maker may sometimes recommend taking action a1 when it is not in their best interest to take that action. That is, the decision maker may recommend that decision subject pay off existing debt with probability when it is unnecessary for them to do so in order to secure a loan. We now give a criteria on which ensures the signaling policy S is BIC.
Proposition 3.1. Signaling policy S is Bayesian incentive-compatibbee if min x(M((2- where a (M) == (o- + + < and zo + Ar(a1) + 0 0).
c(ai)( ((a)[1-<(M))) 1}.
Proof Sketch, We show that Eg- (ag, 0)lo aol Ee-iiluas 0)lo ag] and Egonnuu (a1, 0) = a1] 2 Eg-11 (M (ap, 0)la a1]. Since these conditions are satisfied, s BIC. The full proof may be found in Appendix
Next, we show that the decision maker's 's expected utility when recommending actions according to the optimal signaling policy can be arbitrarily higher than their expected utility from revealing full information or no information. We prove the following result in Appendix [
Proposition 3.2. For any E > O, there exists problem instance such that the expected decision maker utility from recommending actions according to the optimal signaling policy is 1 and the expected decision maker utility for revealing full information or revealing no information is at most e.
Computing the optimal signaling policy
In Section we show a one-dimensional example, where signaling policy can obtain arbitrarily better utilities compared to revealing full information and revealing no information. We now derive the decision maker's ' optimal signaling policy for the general setting with arbitrary numbers of observable features and actions described in Section 2 Under the general setting, the decision maker's optimal signaling policy can be described by the following optimization:
max p(aza V Ea-- (a))
S.t.
(e-n|uas 0) (a', 0)]o 2 0, Va,a' E.,
where we omit the valid probability constraints over p(o a 0), a E A for brevity. In words, the decision maker wants to design a signaling policy S in order to maximize their expected utility, subject to the constraint that the signaling policy is BIC. At first glance, the optimization may initially seem hopeless as there are infinitely many values of p(a alO) (one for every possible 0 E θ) that the decision maker's optimal policy must optimize over. However, we will show that the decision maker's 's optimal policy can actually be recovered by optimizing over finitely many variables.
By rewriting the BIC constraints as integrals over O and applying Bayes' rule, our optimization over p(a al0), A takes the following form
max p(a=a Ves.A BB [ad)
S.L. [ plo
( 2 0, Va, a' e A.
Note that if uds (a, 0) uds (a', 0) is the same for some "equivalence region" R S O (which we formally define below), we can pull (a 0) uas , 0) out of the integral and instead sum over the different equivalence regions. Intuitively, an equivalence region can be thought of as the set of all 0 E + pairs that are indistinguishable from a decision subject's perspective because they lead to the exact same utility for any possible action the decision subject could take. Based on this idea, we formally define region of θ as follows.
7

---

Definition 4.1 (Equivalence Region). Two assessments 8, 6' are equivalent (w.rt. was) if und (a, 8) Vas(a', 0) Uds (a. - la )¹), Va, a' E A. An equivalence region R is a subset of such that for any 0 E R, all 0' equivalent to 0 are also in R. We denote the set of all equivalence regions by R.
For more intuition about the definition of an equivalence region, see Figure in Appendix pulling the decision subject utility function out of the integral, we can integrate p( = a each equivalence region R. We denote p( R) as the probability that the true A E R according to the prior. Finally, since it is possible to write the constraints in terms of p(a R)) Va E A, R R. suffices to optimize directly over these quantities. For completeness, we include the constraints which make each {p(cr = (R) YR valid probability distribution.
E After over
Theorem 4.2 (Optimal signaling policy). The decision maker's optimal signaling policy can be characterized by the following linear program OPT-LP:
ΣV E A
p(R)p(o al alR)uam(a)
p(aza A.
RER
s.f.
Σ
plo a ())((R)(((a(()))) R) Uas R)) 2 0, Va,a' E'A
(OPT-LP)
RER
Σ p(a = R) = 1, VR, p(o = a R) 2 O, VRER,GEA,
where p(o = a (R) denotes the probability of sending recommendation o = a if 0 E R. Note that the linear program OPT-LP is always feasible, as the decision maker can always recommend the action the decision subject would play according to the prior, which is BIC. Similarly, always recommending the action the decision subject would take had they known the assessment rule is also feasible.
While the problem of determining the decision maker's optimal signaling policy can be transformed from an optimization over infinitely many variables into an optimization over the of finitely many equivalence regions R. [R]] may be exponential in the number of observable features d (see Appendix F for more details). This is perhaps unsurprising as without any assumptions on O the representation of the prior II can scale exponentially with d. In this case, we expect the running time of an algorithm which takes the entire prior as input to be exponential in the number of features as well. This motivates the need for a computationally efficient algorithm to approximate (PPT-LP) which does not require the full prior IT as input.
We adapt the sampling- based approximation algorithm of Dughmi and Xu 15 to our setting in order to compute an e-optimal and e-approximate signaling policy in polynomial time, as shown in Algorithm ii Appendix G At high level, Algorithm D samples polynomially-man prior distribution over the space of assessment rules, and solves an empirical analogue of (OPP-LPP) In Appendix probability, for any E > O. Formally, we prove the following statement.
times from the
G we show that the resulting signaling policy is e-BIC, and is c-optimal with high
Theorem 4.3. Algorithm 7 runs in poly(m, 1) time (where m |A)), and implements an e-BIC signaling policy that is e-optimal with probability at least 1 - ó.
We leave open the question of whether there are classes of suceinetly represented priors that permit efficient algorithms for computing the exact optimal policy in time polynomial in d and m. It is also plausible to design efficient algorithms that only require some form of query access to the prior distri- bution. However, information-theoreti lower bounds of [13 rule out query access through sampling.
5 Experiments
In this section, we provide experimental results using a semi-synthetic setting where decision subjects are based on individuals in the Home Equity Line of Credit (HELOC) dataset [15]. The HELOC dataset contains information about 9,282 customers who received a Home Equity Line of Credit. Each individual in the dataset has 23 observable features related to an applicant's 's financial history (e.g., percentage of previous payments that were delinquent) and a label which characterizes their loan repayment status (repaid/defaulted). We compare the decision maker utility for different models of information revelation: our optimal signaling policy, revealing full information about the model, revealing no information about the model. As our theory predicts, the expected decision maker utility when recommending actions according to the optimal signaling policy either matches exceeds the
8

---

Average Desicion-mat Utility Across Different & and Cost
Figure Total decision maker utility averaged across all cost and Ax(a) configurations for three different prior variances. The optimal signaling policy (red) consistently yields higher urility compared to the two baselines: revealing full information (blue) and no information (green). This gap increases when the decision subject is less certain about the model being used (higher o²).
1200
1000
800
400
BIC
200
None
0.1
1305
1300
1302
1320
Auynn
1200
1100
1100
1302
1000
900
1050
900
R03
1020
505
800
Ar(ay)
0.5
0.25
0.5
0.25 c(2))
0.5
0.5
0.25
2x
0.5
0.25
1.0
0.5
1.0
0.5
10
0.5
1.0 0.5
Figure 4: Expected utility across different c(a) and Ax(a) configurations for 0² = 0.4. Optimal signaling policy (red) effectively upper-bounds the two baselines, revealing everything (blue) and revealing nothing (green) in all settings.
expected utility from revealing full information or no information about the assessment rule across all problem instances. Moreover, the expected decision maker utility from signaling significantly higher on average. Next, we explore how the decision maker's s expected utility changes when action costs and changes in observable features are varied jointly. Our results are summarized in Figures and
In order to adapt the HELOC dataset to our strategic setting, we select four features and define five hypothetical actions A {ag, Q1 02 a3, a4} that decision subjects may take in order improve their observable features. Actions {a1, 02 03, a4} result in changes to each of the decision subject's four observable features, whereas action ag does not. For simplicity, we view actions {ai, 42 03 aa) as equally desirable to the decision maker, and assume they are all more desirable than ag- Using these four features, we train a logistic regression model that predicts whether an individual is likely to pay back loan if given one, which will serve as the decision maker's 's realized assessment rule. For more information on how we constructed our experiments, see Appendix !|
Given { (c(a:), Ax(a))) 1 instance and information revelation scheme, we calculate the decision maker's total expected utility by summing their expected utility for each applicant. Figure D shows the average total expected decision maker utility across different Ax and cost configurations for priors with varying amounts of uncertainty. See Figure in Appendix [.3 for plots of all instances which were used to generate Figure 3 Across all instances, the optimal signaling policy (red) achieves higher average total utility compared the other information revelation schemes (blue and green). The difference is further amplified whenever the decision subjects are less certain about the true assessment rule (i.e., when a is large). Intuitively, this is because the decision maker leverages decision subjects' uncertainty about the true assessment rule in order to incentivize them to take desirable actions, and as the uncertainty increases, so does their ability persuasion.
To better understand how the decision maker's expected utility changes as a function of c(a) and Ax(a), we sweep through multiple {c((a,), Ax (x;)))) tuples on a grid of (c(a;), Ax(a,) (0. 0.2.5.500 0.5] (0. 0.5. 1.0} for é 2,,2,3, 3, 4} and measure the effectiveness of the three information revelation schemes. Figure shows the surface of the decision maker utility as function of (c(a,), Ax(a:) for the optimal signaling policy (red), revealing full information (blue), and revealing no information (green). When c(a,) is high and Ax(a;) is low, the total expected decision maker utility is low as there is less incentive for the decision subject to take actions (although even under this setting, the optimal signaling policy outperforms the other two baselines). As c(a:) decreases and Ax(a:) increases, the total expected decision maker utility increases.

---

Conclusion
We investigate the problem of offering algorithmic recourse without requiring full transparency (i.e., revealing the assessment rule). We cast this problem as game of Bayesian persuasion, and offer several new insights regarding how decision maker can leverage their information advantage over decision subjects to incentivize mutually beneficial actions. Our stylized model relies on several simplifying assumptions, which suggest important directions future work:
Public persuasion. We assume that the recommendations received by each decision subject are private. However, if decision subject is given access to recommendations for multiple individuals, it may be possible for them to reconstruct the underlying model. While out of the scope of this work, would be interesting study models of public persuasion the algorithmic recourse setting,
Beyond linear decision rules. We focus on settings with linear decision rules and assume all decision subject parameters (e.g., cost function, initial observable features, etc.) are known to the decision maker. We leave it for future work to extend our findings to non- non-linear decision rules, or settings in which some of the decision subjects' parameters unknown to the decision maker.
7
Acknowledgements
KH is supported by a NDSEG Fellowship. ZSW and KH were supported in part by the NSF FAI Award #1939606, Google Faculty Research Award, J.P. Morgan Faculty Award, a Facebook Research Award, and Mozilla Research Grant. AT was supported in part by the National Science Foundation grants IIS 1705121, IIS1838017, ISS2046613, IIS21 12471, funding from Meta, Morgan Stanley and Amazon. HH acknowledges support from NSF IIS2040929, a CyLab 2021 grant, and Meta (Facebook) research award. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies. KH would like to thank Haifeng Xu for insightful conversations about Dughmi and Xu [33. KH would also like to thank James Best, Yatong Chen, Jeremy Cohen, Daniel Ngo, Chara Podimata, and Logan Stapleton for helpful suggestions and conversations.
10

---

References
[T] E. Akyol, C. Langbort, and Basar. Price of transparency in strategic machine learning. CoRR, abs/1610.08210, 2016. URL http://arxiv org/ aabs//610. 08210
[2] Y. Bechavod, C. Podimata, Z. S. Wu, and J. Ziani. Information discrepancy in strategic learning. In K. Chaudhuri, S. Jegelka, I.. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 1691-1715. PMLR, 2022. URL Wwk.httpp://proceediin .mlg......r.... mlr. press.resssvve htt/////ecaw/d2222/ html
[3] R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4):324-34) 1952. ISSN 00063444. URL http:
[4] M. Castiglioni, A. Celli, A. Marchesi, and N. Gatti. Online bayesian persuasion. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information
Processing Systems 33: Anmual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 12, 2020, virtual, 2020. URL https::/ neur neurips 10wcdbe 00t.0000000000000--btttt........
cc cc/paper/2020/
[5] A. Chalfin, O. Danieli, A. Hillis, Z. Jelveh, M. Luca, J. Ludwig, and S. Mullainathan. Pro- ductivity and selection of human capital with machine learning. American Economic Review, 106(5): 124 27, May 2016. doi: 10. 20.1257/eer,2201612222 articles?id 10. 1257 /er 2055///e..20016022. p20161029
URL https: //wp://wwwww. wwwweb..wbb............ org/
[6] B. Chen, P. I. Frazier, and D. Kempe. Incentivizing exploration by heterogeneous users. In Bubeek, V. Perchet, and Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages
PMLR, 2018. URL http://proceeding mlr press/v75..
Chen18a. html
[7] V. Chen, J. Li, J. S. Kim, G. Plumb, and A. Talwalkar. Interpretable machine learning: moving from mythos to diagnostics. Commun. ACM, 65(8):43-50, 2022. doi: 10.1145/3546036. URL
https://doi. org/ 10. 1145/3546036
[8] Y. Chen, Wang, and Y. Liu. Strategic classification with a light touch: Learning classifiers that incentivize constructive adaptation, 2021.
[9] D. Citron and F. Pasquale. The scored society: Due process for automated predictions. Wash- ington Law Review, 89:1-33, 03 2014.
[10] Council of European Union Council regulation (EU) no 679/2016, 2016. https://eww 1ex. europa. www.app..weeggaaoooooooeeeeeeeee
CELEX:
32016R0679
[11] J. Dong, A. Roth, Z. Schutzman, B. Waggoner, and Z. S. Wu. Strategic classification from
revealed preferences. É. Tardos, E. Elkind, and R. Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithuca, NY, USA, June 18-22, 2018, pages 55-70. ACM, 2018 doi: 10.1145/2211666321992 URL htttt::///o/: org/ 1 1145/ 01111666.2299999
[12) S. Dughmi and H. Xu. Algorithmic persuasion with no externalities. In C. Daskalakis, M. Babaioff, and H. Moulin, editors, Proceedings of the 20/7 ACM Conference on Economies and Computation, EC 17, Cambridge, MA, USA, June 26-30, 2017, pages 351-368. ACM, 2017. doi: 10.1145/3033274.30855
httsttss::////// http://oii.oogg////// 11tp///0.1114//333774444 308833333333330.322222 30851522
[13] S. Dughmi and H. Xu. Algorithmic bayesian persuasionn SIAM J. Comput., 50(33, 2021. doi:
10.1137/16M1098333 URL URL /tttpp://doi.rrrg:: 111.00111//1111111131111
[14] P. Dworczak and G. Martini. The simple economics of optimal persuasion. Journal of Political Economy, 127(5):1933-2445 2019.
doi: 10.1086/701813. URL https://doi.orrg org/10
1086/701813
[15] FICO. Explainable machine learning challenge. explainable machine- wewniiinneeeeannnn--een challenge, 2018.
https://conmunti www.coooomnitt.i.ii.oooooooooo com/ com/s/
[16] A. Frankel and N. Kartik. Improving Information from Manipulable Data. Journal of the
European Economic Association, 20 20(1):79-1155 06 2021. ISSN 1542-4766. doi: 10. 1099/eaee
jvab017. URL https: //wii org 10. 1093/ vvab017
11

---

[17] G. Ghalme, V. Nair, I. Eilat, I. Talgam- Cohen, and N. Rosenfeld. Strategic classification in the dark. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3672-3681 PMLR, 2021. URL BtR..htttp:/pprceeeeii
mlr. prwss/v139 v1tps/vv/////// wwt.//1aa99/emell..ee ghwlme21a... html
[18] M. Hardt, N. Megiddo, C. H. Papadimitriou, and M. Wootters. Strategic classification. In M. Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical
Computer Science, Cumbridge, MA, USA, January 14-16, 2016, pages 111-122. ACM, 2016. BRRLhttps:.. /top::://do...o org 10. 0011//2//27222 2840030
doi: 10.1 10.1145/2840728.. 7778444788.8847700
[19] K. Harris, H. Heidari, and 7. Wu. Stateful strategic regression.
M. Ran- zato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances Neural Information Processing Systems 34: Annual Conference on Neural Informa- tion Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages
2021. URL httpp:://proceedings seaeeeeiinnnnnuuriisp. ctciiiss.cccccccccc httppppppp//2////eep f F1404c2624fa7 wtw.:/aae02200000040555a wtwpaaafffooobootaaaaaodaaeaaeee Wwwtrbat..ttt....
[20] K. Harris, D. D. Ngo, L. Stapleton, H. Heidari, and S. Wu. Strategic instrumental vari- able regression: Recovering causal relationships from strategic responses. In K. Chaudhuri, S. Jegelka, I.. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, International Conference on Machine Learning, ICML 2022. 17-23 July 2022, Baltimore, Maryland, USA. volume 162 of Proceedings of Machine Learning Research, pages 8502-8522. PMLR, 2022. URL https://proceeedingg mlr, press/ wwtes/vv62//// w116//harris2// html
[21] T. Homonoff, R. O'Brien, and A. B. Sussman. Does knowing your fico score change financial behavior? evidence from a field experiment with student loan borrowers. Review of Economics and Statistics, 103(():236-25) 250, 2021.
[22] N. Immorlica, J. Mao, A. Slivkins, and 7. S. Wu. Bayesian exploration with heterogeneous agents. In L. Liu, R. W. White, A. Mantrach, F. Silvestri, J. J. McAuley, R. Baeza- Yates, and L. Zia, editors, The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 751-761, ACM, 2019, doi: 10.1145/3308558.331366 URL https //doi.org/10 1 11111 3308558888888 3313649
[23] M. Jagadeesan, C. Mendler-Dünner and M. Hardt. Alternative microfoundations for strategic classification. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 4687-4697. PMLR, 2021. URL //proceedings.co mlr, wwt.:.lt........ee.. /
html
[24] J. Jagtiani and C. Lemieux. The roles of alternative data and machine learning in fintech lending: Evidence from the lendingclub consumer platform. Financial Management, 48(4): 2019. doi: https://doi.org/ http://oo.orr/11.0111111 11.1111/fmma............ 1/fima. 12295. URL https:://oolneeellrrrrrreee wiley. com/ doi/abs/100 1111/fima. 12295
12295.
[25] S. Joshi, O. Koyejo. W. Vijitbenjaronk, B. Kim, and J. Ghosh. Towards realistic individ- ual recourse and actionable explanations in black-box decision making systems. CoRR, abs/1907.096 2019. URL httt:://aaxiii org/ ab//abbs//11/ 0tt//99907.00955555
[26] E. Kamenica. Bayesian persuasion and information design. Annual Review of Economics, 11 (1):249-272, 2019. doi: 10.1 1e1.44///ame---oooooiss------ 00222207811..9 URL attps://don org/10. 1146/ annurev- wttp://ooooooocooo011---------
[27] F. Kamenica and M. Gentzkow. Bayesian persuasion. American Economic Review, 101(6):
2590-2615,, October 2011. doi: 10. 10.1257/aer.101...3 101.6.2590. URL
org/
articles7id=11 1257 101. 1...6.22. 2590
[28] A. Karimi, G. Barthe, B. Schölkopf, and I. Valera, A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. CoRR, abs/2010.04050, 2020. URL https://arxiv
org/abss/010..4405 04050
[29] J. M. Kleinberg and M. Raghavan. How do classifiers induce agents to invest effort strategically? ACM Trons. Economics and Comput. 19:11999,, 2020. doi: 10.1145/3417742. URL.
https://doi. org/10. 1145/3417742
12

---

[30] A. Kolotilin. Optimal information disclosure: A linear programminng approach. Theoretical Economics, 13(2):607-635, 2018. doi: https///doi.rrg//03998//7 1ttg////00000021118005 URL https:// enlinelibrary wiley. httm//oi/abb//// 3982/TE1805
[31] D. Kučak, V. Juričić, and G. Dambić. Machine learning in education-a survey of current research trends. Annals of DAAAM & Proceedings, 29, 2018.
[32] S. Levanon and N. Rosenfeld. Strategic classification made practical. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6243-6253. PMLR, 2021. levanon21a.html
mlr prt.spresss//
[33] Y. Mansour, A. Slivkins, V. Syrgkanis, and Z. S. Wu. Bayesian exploration: Incentivizing exploration in bayesian games. In V. Conitzer, D. Bergemann, and Y. Chen, editors, Proceed- ings of the 2016 ACM Conference Netherlands, July 24-28, 2016, page 661. ACM, 2016. doi: 10.1145/2940716.24477777 URL
Economics and Computation, EC '1, Maastricht, The
https://8oi orgo 10. 1145 0114//940716.... 2940755
[34] Y. Mansour, A. Slivkins, and V. Syrgkanis. Bayesian incentive-compatible bandit exploration. Oper. Res., 68(4) 2020. doi: 10. 20.11887/pre.2019..9929 1949. URL httts:://ooi. org/
10. 10..18//opre.eo 2019 1949
[35] C. McDiarmid. On the method of bounded differences, page 148-188 London Math- ematical Society Lecture Note Series. Cambridge University Press, 1989. doi: 10.1017/
CIO97811073359949)
[36] M. Raghavan, S. Barocas, J. M. Kleinberg, and K. Levy. Mitigating bias in algorithmic hiring: evaluating claims and practices. In M. Hildebrandt, C. Castillo, L. E. Celis, S. Ruggieri, L. Taylor, and G. Zanfir-Fortuna, editors. FAT* '20; Conference on Fairness, Accountability, and Transparency, Barcelona, Spain, Jamuary 27-30, 2020. pages 469-481 ACM, 2020. doi: URL https:///o/ org/ 1t////1...111/333 1011113333319555 3372888
10.1 00.1145//3510995337755
[37] K. Rawal and H. Lakkaraju. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-
12. 2020, virtual, 2020. URL http:: /tttps://proceedinngs wwwrroceedinggsnuuip.pp.... neurips. cttpppssccp/pppr//22220 /hash/
[38] J. Sánchez-Monedero, L. Dencik, and L. Edwards. What does it mean 'solve' the problem of discrimination in hiring?: social, technical and legal perspectives from the UK on automated hiring systems. In M. Hildebrandt, C. Castillo, L. E. Celis, S. Ruggieri, L. Taylor, and G. Zanfiirr-ooruua, editors, FAT '20: Conference on Fairness, Accountability, and Transparency, Barcelona, Spain, January 27-30, 2020, pages 458-468. ACM. 2020. doi: 10.1145/3351095. 3372849, URL https:://doi org/10
3372849
[39] M. Sellke and A. Slivkins. The price of incentivizing exploration: A characterization via thompson sampling and sample complexity. In P. Biró, S. Chawla, and F. Echenique, editors, EC '21: The 22nd ACM Conference on Économics and Computation, Budapest, Hungary, July 18-23, 2021, pages 795-796. ACM, 2021. doi: 1..1445734654553446554999 URL httpps oodoi.org/10 11110..14133455 0tt..///../...111/46666666633330
[40] Y. Shavit, B. L. Edelman, and B. Axelrod. Causal strategic linear regression. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8676-8686. PMLR, 2020. URL wRL htttp://proceedingss mlr
[41] S. Tsittsis and M. G. Rodriguez. Decisions, counterfactual explanations and strate- gic behavior. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https://proceedingss wtw.reedddinnn..nuiis....e cttccc/ppppppe htpp//apper//// (aaper/2000/hahh. c2bbbb6444223000011100000.ooode3 Abstract. html
[42] B. Ustun, A. Spangher, and Y. Liu. Actionable recourse in linear classification. danah boyd and J. H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountability, and
13

---

Transparency, E 2019, Arlanta, GA, USA, Jamuary 29-31, 2019, pages 10-19, ACM, 2019. doi: 10.1145/328750022285566 URL http:tt////bbi..rg///// 1111///////////8560001 3287566
[43] S. Wachter, B. D. Mittelstadt, and C. Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. CoRR, abs/1711.00099) 2017. URL http://axivv.oorrab/////////
14


Reviews:
[{"review_id": "nMuA8WRQ1R_", "reviewer": "Reviewer_WZjo", "summary": "The paper studies a setting of algorithmic recourse in the classification setting, where the decision subjects present strategic behavior. The authors propose a model, using the framework of Bayesian persuasion, where a decision maker and a decision subject have prior beliefs about the parameters of a predictive model. The decision maker first commits to a form of transparency (signaling policy), trains the predictive model and communicates to a decision subject which action to take in order to change their features in a way that the model gives them a positive prediction. The decision subject, based on the recommendation, adapts their posterior belief about the model parameters and takes an action that maximizes their expected utility. The goal of the paper is to compute a signaling policy that maximizes the decision maker's expected utility under the constraint of \"Bayesian incentive compatibility\", i.e., that it is in the best interest of the decision subject to take the action recommended to them by the decision maker. The authors propose an approximation algorithm for the problem, based on linear programming, and evaluate their methodology using semi-synthetic data.", "questions": "My 2 main concerns/questions regarding the assumptions of the proposed model that I would like the authors to discuss are the following:\n1. What is the real need to assume that the decision maker has a prior over the model parameters $\\theta$? They have the data, they train the model. Where is the uncertainty about $\\theta$ coming from if the training process is completely under their control? More technically, in the problem definition of Section 4, why does the decision maker sample $\\theta$ from $\\Pi$? Related to that, why would the decision maker commit to a signaling policy before training? These look to me like assumptions needed to make the whole thing fit to the Bayesian persuasion setting but they slightly disregard how algorithmic recourse would work in real-life applications. I think these assumptions need to be better motivated in the text.\n2. Why is the decision maker's utility assumed to be a function of the action $a$ and not a function of $x_0 +\\Delta x(a)$? If it is independent of $x_0$, then the decision maker gets the same utility from two decision subjects taking the same action but with one of them crossing the threshold and the other one not crossing it. This sounds a bit weird to me. Is a completely untrustworthy loan applicant who pays some of their existing debt the same as a borderline candidate who repays some of their existing debt? How is it natural that the final output of the classifier doesn't contribute to the decision maker's utility?", "limitations": "I think the authors sufficiently discuss the limitations of their methodology, specifically that it focuses solely on linear models and it doesn't consider shared information between different decision subjects. The societal implications section is also ok.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: To the best of my knowledge, this is the first paper framing algorithmic recourse as an instance of Bayesian persuasion. This connection is a novel and conceptually interesting contribution. The paper contains a quite comprehensive related work section discussing work on strategic machine learning, algorithmic recourse and bayesian persuasion. Although the technical setup is different, there is some relevant work (see [1]) connecting counterfactual explanations (concept almost equivalent to algorithmic recourse) with strategic machine learning and also tries to compute personalized recommendations that maximize the decision maker's utility. I believe it should be cited and discussed in the \"strategic responses to unknown predictive models\" subsection.\n\nQuality: I found the paper technically sound. I read part of the proofs in the Appendix and they appear to be correct. The framing of  algorithmic recourse as an instance of Bayesian persuasion and the overall formulation is mostly reasonable. However, there are certain assumptions of the model that I am not sure to what extent they reflect the real-life problem that the paper is studying. I elaborate more on these assumptions in the \"Questions\" section. Finally, the experimental evaluation is satisfying but I think that it could have been a bit more extensive. My main concern related to the experiments is that the authors assume all the available actions give equal utility to the decision maker and they are all more desirable than the null action that doesn't change the decision subject's features. However, a large part of the strategic machine learning literature is studying malicious adaptation which is performed to \"trick\" the decision maker and therefore, in the current setup, would lead to negative utility. As far as I understand, the authors' framework could capture this by considering a set of actions with a mixture of negative and positive utilities. I believe that, in that case, the results of Figure 1 might have been different. For example, I think that \"Full information\" could lead to lower utility than \"No information\" and it would be interesting to see how the method proposed by the authors would perform in comparison.\n\nClarity: The paper is nicely written and easy to follow. I have a few minor suggestions for improvement which I list below.\n1. Starting in line 202, the authors discuss the assumption that the decision maker publishes and commits to a signaling policy. However, the arguments presented are trying to fit algorithmic recourse to the Bayesian persuasion setting rather than explaining how the interaction described in the table of page 2 would work in practice. It is not clear to me what it means for a decision maker to publish a signaling policy in lending, college admissions, hiring e.t.c. I think the authors could improve this paragraph by adding some real-life examples.\n2. There is a full stop punctuation mark missing in line 206.\n3. In lines 210-211 the authors talk about \"prior beliefs $\\Pi$ over the observable features\" which kind of implies that $\\Pi$ is a belief about the distribution of features $x$. However, as far as I understand, $\\Pi$ is a belief about the model parameters $\\theta$. I think the aforementioned phrase is causing confusion.\n4. There is a citation number missing in line 331.\n5. I would encourage the authors to bring Algorithm 1 to the main body of the paper. The authors provide a high-level description of it but, since the algorithm itself is not super complicated and it is their main technical tool towards solving their problem, it shouldn't be left for the appendix.\n6. In lines 335 & 337, the authors mention that the algorithm leads to an $\\epsilon$-BIC signaling policy, however, only the definition of a BIC policy has been given in the paper so far and $\\epsilon$-BIC is undefined.\n7. In the experimental section, it would be useful if the authors presented in detail their baselines \"full information\" and \"no information\". To my understanding, these two correspond to the decision subject best-responding based on a posterior $\\Pi'$ which is (i) a point mass on $\\theta$ and (ii) equal to the prior $\\Pi$. If that is correct, I think the authors should write it explicitly when describing the experimental setup.\n8. There is a missing reference in line 652 (Appendix F).\n\nSignificance: I think the paper carries interesting ideas regarding the general problem of algorithmic recourse, namely that the decision subjects have prior beliefs about the decision rule and that the decision maker can provide recommendations to incentivize beneficial long-term outcomes (e.g., repaying existing debts instead of manipulating financial records in the credit scoring example). Therefore, the conceptual contributions are important and the accompanying methodology is sound.\n\n[1] Tsirtsis, Stratis, and Manuel Gomez Rodriguez. \"Decisions, counterfactual explanations and strategic behavior.\" Advances in Neural Information Processing Systems 33 (2020): 16749-16760.\n\nPOST REBUTTAL\n-------------------------------------\nI read the authors response and the authors addressed most of my concerns about the proposed model. I keep my initial score, in favor of accepting the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mbqQE1zg0_F", "reviewer": "Reviewer_qh5D", "summary": "The paper studies an application of Bayesian persuasion to a linear classification model. In this model, a decision maker uses a linear decision rule to make a decision on a subject, which is represented by a feature vector. The subject is uncertain about the specific rule the decision maker uses to reach the decision but only has a prior belief over it. The decision maker can then strategically reveal this information to persuade the subject to take certain actions. The goal of the study is to design an algorithm to compute the optimal persuasion strategy, so that the decision maker's utility is maximized.", "questions": "As described above, it would be great if the authors could explain why the decision maker does not directly optimize the distribution of $\\theta$ but choose to use signaling.", "limitations": "The authors did not seem to discuss any potential nagative social impact. I think there is the possibility that banks or financial institutions use their information advantage to manipulate customers to act in favor of them but not in favor of the social welfare.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The model is original. The idea of applying Bayesian persuasion to the linear classification model is interesting. The paper is well-writen and clear overall. The thecnical results look somewhat standard and unsurprising, following mostly the standard approach to solving the private signaling problem. \n\nMy major concern is about the setup of the model. In the model, the decision maker selects both the state (i.e. decision rule) and the signaling strategy. This is different from typical Bayesian persuasion models where the decision maker has no control over the state. Crucially, this raises the question whether it is indeed useful to use signaling in such a model. In other words, why doesn't the decision maker just optimize their strategy about how to choose the decision rule (i.e. optimize the distribution of $\\theta$) - I think they can well just do this to acheive the same (or even a better) outcome without using signaling. (Analogously, in Stackelberg games, the leader does not benifit from signaling when they already have the power to make a commitment.) \n\nThe authors didn't seem to have justified this setup adequately in the paper. I tried to come up with a justification but found it hard to justify the model if the decision maker has control over $\\theta$ but chooses to _not_ optimize the distribution of it. So it seems that this setup is justifiable only in the case where the decision maker cannot choose the decision rule. Nevertheless, this seems to deviate from the motivating examples (eg. bank and a customer applying for a loan): one particular question is if the decision maker does not choose the rule, then who does that in these examples? Notice that this is different than saying that the decision maker cannot control the prior belief of the subject - even when the decision maker cannot control the subject's prior belief, they can still optimize their actual selection of $\\theta$.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jJ7nPtX0LPO", "reviewer": "Reviewer_iKBd", "summary": "This paper models a strategic interaction between a decision maker and a decision subject in an incomplete information game using Bayesian persuasion, which can be applied to credit scoring.  Specifically, the utilities of both the decision maker and decision subject depend on the action of each other, while their true decision rules are not public information. Moreover, there is an action recommendation system designed by the decision maker to incentivize the decision subject to modify their actions. In their model, the authors show that the decision maker can design an incentive-compatible recommendation system such that the modified action of the decision subject will benefit both participants. Furthermore, they develop an algorithm to approximately build this system within polynomial time. Finally, they also use numerical experiments to illustrate the benefits of their approach.", "questions": "1. I have a question about the extension to multiple decision subjects. When there is a heterogeneous group of decision subjects, will the decision maker assign the same threshold parameter $\\theta$ for all participants or assign different parameters from the same distribution?\n        \n2. Another question is about manipulations, which is mentioned in the introduction as follows ''The question we are interested in answering in this work is: how can the decision maker incentivize decision subjects to take such beneficial actions while discouraging manipulations?\". I wonder whether the utility function, actions, and related rewards and consumptions of the decision subject are public information available to the decision maker. If it is true, the decision subject cannot make profits based on private knowledge. Thus, this model might not be able to reflect manipulations by the decision subject.\n        \n        \n3. For the numerical experiments part, what is the difference between the obtained utility of the decision subject in your model and that in the full information model?", "limitations": "I think there is no potential negative social impact of the work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This is the first work to use Bayesian persuasion to model the interaction described in the summary part based on the previous literature.\n        \n2. In their model, the authors show the existence of an incentive-compatible action recommendation system.\n        \n3. The authors develop an approach to construct this system and another time-efficient algorithm to approximately design the desired system in polynomial time.\n\nWeaknesses:\n\n1. The model only contains one decision maker and one single decision subject. Although the authors state that this model can be extended to a heterogeneous case with heterogeneous decision subjects, I still have one question listed in the question part below.\n        \n2. The authors may have implicitly assumed that the utility function, actions, and corresponding consequences of the decision subject are known to the decision maker when designing the algorithm. Please see bullet 2 in the question part for more detail. \n        ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YSNUauR2XXy", "reviewer": "Reviewer_x6ZH", "summary": "This work explores the Algorithmic Recourse problem through the lens of Bayesian Persuasion. The recourse problem is cast as a persuasion problem, where the Decision Maker/Principal is the operator of machine learning system (represented as a classifier), and the Decision Subject/Agent is the consumer of prediction. Motivating example is online banking, where the decision subject applies for a loan, and the classifier decides if they are eligible.\n\nClassifiers are assumed to be linear  $y=\\mathrm{sign}(\\theta^T x)$, where $x$ is the feature vector, and the weights $\\theta$ are assumed to be distributed according to a common prior $\\theta \\sim \\Pi$. For the interaction protocol, the decision maker first commits to a signaling scheme which is the agent action to recommend as a function of model weights $\\theta$. After the signaling scheme is set, an instance $\\theta \\sim \\Pi$ is picked at random and revealed to the decision maker, the signaling scheme is applied, and the decision subject takes the rationally-optimal action according to their posterior belief. In this persuasion setting, actions $a\\in\\mathcal{A}$ are modeled as changes to the feature vector, such that $x’=x+\\Delta(a)$ when action $a$ is taken. Each action is also assumed to entail a cost $c(a)$.\n\nAuthors present three sets of results. The first result attempts to illustrate the importance of taking persuasion considerations into account by presenting an instance of the problem in which the utility discrepancy between naive and strategic decision maker behavior can be arbitrarily close to the maximal discrepancy (Proposition 3.2). The second set of results discusses the computational complexity of the problem, and presents an efficient sampling-based algorithm which calculates an approximately optimal policy in $poly(m,\\frac{1}{\\epsilon})$ time (Theorem 4.3). The algorithm requires a polynomial number of samples of $\\theta \\sim \\Pi$. The third set of results is an empirical evaluation using the HELOC lending dataset.", "questions": "* Realistic model assumptions - One possible way to model the randomness in model parameters $\\theta$ is assuming that $\\theta$ is the result of an Empirical Risk Minimization process on a dataset of feature-label pairs $(x_1,y_1),\\dots,(x_n,y_n)$ sampled iid from a distribution $\\mathcal{D}$. If we assume this, does a common prior assumption on $\\theta$ entail equivalent assumption in terms of $\\mathcal{D}$? In other words - If we assume that $\\theta$ is obtained using ERM, is the common prior assumption on $\\theta$ equivalent to assuming that both Principal and Agent have the ability to train the prediction model themselves?\n* What happens if the same value of $\\theta$ is reused across many instances of the persuasion?\n* What are the main insights from the set of empirical evaluations? Can we design an experiment which tests the method under more realistic assumptions? I guess that both positive or negative results will be interesting in this context.\n* Is it possible to add components to the mechanism, or describe a setting in which the decision maker is likely to adhere to their commitment, and don't examine any data privately before committing to the signaling scheme?\n* Algorithm 1 assumes that $\\theta$ can be sampled polynomially-many times. Assuming that sampling from $\\Pi$ can be very costly, is it possible to trade off running time for lower sample complexity?\n", "limitations": "Main limitation of this work from my perspective is the modeling assumptions, which may not hold in many realistic use cases. I think these should be outlined as a basis for further discussion. See details above.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* Problem is well-motivated. From the theoretical perspective, it is interesting to find new domains where the Bayesian Persuasion perspective can be useful. From the practical perspective, strategic response and recourse are becoming increasingly prevalent in real-world systems.\n* Writing is clear and easy to follow, mathematical limitations of results are clearly illustrated.\n* Work brings up interesting directions for discussion and future work.\n\nWeaknesses \n* Some of the core assumptions made by the model are not realistic. In particular, assuming that a common prior exists for $\\theta$ seems highly non-trivial - For example, decision makers usually have a resource advantage, and for example are likely to conduct a market survey revealing more details about $\\Pi$ before committing to a signaling scheme - Breaking the common prior assumption. Moreover, model training in the real world is often very costly, so it is more realistic to assume that model parameters $\\theta$ will be reused many times, and obtaining fresh samples $\\theta \\sim \\Pi$ (e.g as assumed by the presented algorithm) will be very costly. In addition, in many realistic settings users have the ability to share data and possibly collude.\n* Not sure whether this model naturally extends beyond linear classification and one-shot settings. As an extreme example - Will it be realistic to assume that both parties have a common prior over the parameters of a modern, large-scale neural network?\n* It seems to me that the empirical evaluation section mainly provides a numerical validation for the theoretical results, and does not explore much beyond them. As the theoretical model relies on non trivial assumptions, the experiments section can be an opportunity to explore limitations and robustness.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept