Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:

1. This is the first work to use Bayesian persuasion to model the interaction described in the summary part based on the previous literature.
        
2. In their model, the authors show the existence of an incentive-compatible action recommendation system.
        
3. The authors develop an approach to construct this system and another time-efficient algorithm to approximately design the desired system in polynomial time.

Weaknesses:

1. 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.
        
2. 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. 
        
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?
        
2. 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.
        
        
3. 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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. 

My 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.) 

The 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$.
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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

Classifiers 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)$.

Authors 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.
strengths_and_weaknesses: Strengths
* 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.
* Writing is clear and easy to follow, mathematical limitations of results are clearly illustrated.
* Work brings up interesting directions for discussion and future work.

Weaknesses 
* 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.
* 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?
* 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.

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?
* What happens if the same value of $\theta$ is reused across many instances of the persuasion?
* 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.
* 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?
* 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?

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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

Quality: 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.

Clarity: The paper is nicely written and easy to follow. I have a few minor suggestions for improvement which I list below.
1. 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.
2. There is a full stop punctuation mark missing in line 206.
3. 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.
4. There is a citation number missing in line 331.
5. 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.
6. 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.
7. 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.
8. There is a missing reference in line 652 (Appendix F).

Significance: 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.

[1] Tsirtsis, Stratis, and Manuel Gomez Rodriguez. "Decisions, counterfactual explanations and strategic behavior." Advances in Neural Information Processing Systems 33 (2020): 16749-16760.

POST REBUTTAL
-------------------------------------
I 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.
questions: My 2 main concerns/questions regarding the assumptions of the proposed model that I would like the authors to discuss are the following:
1. 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.
2. 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.
review_title: null

Meta-review: metareview: The paper formulates the problem of algorithmic recourse under partial transparency as a Bayesian persuasion game. It is shown that the decision-maker can design an incentive-compatible action signaling strategy with guarantees that both the decision-maker and decision-subjects are not worse off in terms of expected utility. The results provide several insights into the complexity of computing an optimal signaling strategy;  moreover, a polynomial-time approximation algorithm is provided to compute a near-optimal signaling strategy. The reviewers acknowledged that the paper considers an important problem setting and provides new technical insights into algorithmic recourse using the framework of Bayesian persuasion. However, the reviewers also raised several concerns and questions in their initial reviews. We want to thank the authors for their detailed responses and for actively engaging with the reviewers during the discussion phase. The reviewers appreciated the responses, which helped in answering their key questions. The reviewers have an overall positive assessment of the paper, and there is a consensus for acceptance. The reviewers have provided detailed feedback in their reviews, and we strongly encourage the authors to incorporate this feedback when preparing the final version of the paper.
confidence: Certain
Decision: Accept