# Bayesian Persuasion for Algorithmic Recourse arXiv: https://arxiv.org/abs/2112.06283 ยท HTML: https://mlsanity.com/paper/2112.06283/ ## Key facts - Cited by 14 papers in the map (data through 14 Oct 2026). - Builds on 25 of its 60 references that are in the map. - First posted on arXiv 12 Dec 2021. ## Builds on (most cited first, 25 of 25) - [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017) - [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018) - [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015) - [Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices](https://mlsanity.com/paper/1906.09208/) (2019) - [Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems](https://mlsanity.com/paper/1907.09615/) (2019) - [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017) - [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020) - [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021) - [How Do Classifiers Induce Agents To Invest Effort Strategically?](https://mlsanity.com/paper/1807.05307/) (2018) - [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021) - [Causal Strategic Linear Regression](https://mlsanity.com/paper/2002.10066/) (2020) - [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021) - [Bayesian Incentive-Compatible Bandit Exploration](https://mlsanity.com/paper/1502.04147/) (2015) - [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021) - [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021) - [Decisions, Counterfactual Explanations and Strategic Behavior](https://mlsanity.com/paper/2002.04333/) (2020) - [What does it mean to solve the problem of discrimination in hiring? Social, technical and legal perspectives from the UK on automated hiring systems](https://mlsanity.com/paper/1910.06144/) (2019) - [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016) - [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021) - [Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses](https://mlsanity.com/paper/2107.05762/) (2021) - [The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity](https://mlsanity.com/paper/2002.00558/) (2020) - [Algorithmic Bayesian Persuasion](https://mlsanity.com/paper/1503.05988/) (2015) - [Bayesian Exploration with Heterogeneous Agents](https://mlsanity.com/paper/1902.07119/) (2019) - [Algorithmic Persuasion with No Externalities](https://mlsanity.com/paper/1609.06825/) (2016) - [Price of Transparency in Strategic Machine Learning](https://mlsanity.com/paper/1610.08210/) (2016) ## Built on by (most cited first, 14 of 14) - [Bayesian Strategic Classification](https://mlsanity.com/paper/2402.08758/) (2024) - [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023) - [The Double-Edged Sword of Behavioral Responses in Strategic Classification: Theory and User Studies](https://mlsanity.com/paper/2410.18066/) (2024) - [Learning under Imitative Strategic Behavior with Unforeseeable Outcomes](https://mlsanity.com/paper/2405.01797/) (2024) - [Strategyproof Decision-Making in Panel Data Settings and Beyond](https://mlsanity.com/paper/2211.14236/) (2022) - [Prediction without Preclusion: Recourse Verification with Reachable Sets](https://mlsanity.com/paper/2308.12820/) (2023) - [Contextual Dynamic Pricing with Strategic Buyers](https://mlsanity.com/paper/2307.04055/) (2023) - [Incentives to Offer Algorithmic Recourse](https://mlsanity.com/paper/2301.12884/) (2023) - [Algorithmic Recourse with Missing Values](https://mlsanity.com/paper/2304.14606/) (2023) - [To Give or Not to Give? The Impacts of Strategically Withheld Recourse](https://mlsanity.com/paper/2504.05891/) (2025) - [Explanation Design in Strategic Learning: Sufficient Explanations that Induce Non-harmful Responses](https://mlsanity.com/paper/2502.04058/) (2025) - [Personalized Path Recourse for Reinforcement Learning Agents](https://mlsanity.com/paper/2312.08724/) (2023) - [Off-Policy Evaluation with Strategic Agents via Local Disclosure](https://mlsanity.com/paper/2606.07308/) (2026) - [Robust Strategic Classification under Decision-Dependent Cost Uncertainty](https://mlsanity.com/paper/2606.30136/) (2026) ## Abstract (arXiv) 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.