Bayesian Persuasion for Algorithmic Recourse

• URL: http://arxiv.org/abs/2112.06283v1
• Date: Sun, 12 Dec 2021 17:18:54 GMT
• Title: Bayesian Persuasion for Algorithmic Recourse
• Authors: Keegan Harris, Valerie Chen, Joon Sik Kim, Ameet Talwalkar, Hoda Heidari, Zhiwei Steven Wu
• Abstract summary: In some situations, the underlying predictive model is deliberately kept secret to avoid gaming. This 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 sends a signal, e.g., an action recommendation, to a decision subject to incentivize them to take desirable actions.
• Score: 28.586165301962485
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: When subjected to automated decision-making, decision-subjects will strategically modify their observable features in ways they believe will maximize their chances of receiving a desirable outcome. In many situations, the underlying predictive model is deliberately kept secret to avoid gaming and maintain competitive advantage. This 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 sends a signal, e.g., an action recommendation, to a decision subject to incentivize them to take desirable actions. We formulate the decision-maker's problem of finding the optimal Bayesian incentive-compatible (BIC) action recommendation policy as an optimization problem and characterize the solution via a linear program. Through this characterization, we observe that while the problem of finding the optimal BIC recommendation policy can be simplified dramatically, the computational complexity of solving this linear program is closely tied to (1) the relative size of the decision-subjects' action space, and (2) the number of features utilized by the underlying predictive model. Finally, we provide bounds on the performance of the optimal BIC recommendation policy and show that it can lead to arbitrarily better outcomes compared to standard baselines.

Related papers

• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• Optimization's Neglected Normative Commitments [3.3388234549922027]
  A paradigm used to approach potentially high-stakes decisions, optimization relies on abstracting the real world to a set of decision(s), objective(s) and constraint(s) This paper describes the normative choices and assumptions that are necessarily part of using optimization. It then identifies six emergent problems that may be neglected.
  arXiv  Detail & Related papers  (2023-05-27T12:43:15Z)
• Algorithmic Assistance with Recommendation-Dependent Preferences [2.864550757598007]
  We consider the effect and design of algorithmic recommendations when they affect choices. We show that recommendation-dependent preferences create inefficiencies where the decision-maker is overly responsive to the recommendation.
  arXiv  Detail & Related papers  (2022-08-16T09:24:47Z)
• Off-Policy Evaluation with Policy-Dependent Optimization Response [90.28758112893054]
  We develop a new framework for off-policy evaluation with a textitpolicy-dependent linear optimization response. We construct unbiased estimators for the policy-dependent estimand by a perturbation method. We provide a general algorithm for optimizing causal interventions.
  arXiv  Detail & Related papers  (2022-02-25T20:25:37Z)
• Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
  We derive a novel policy gradient-style robust optimization approach, PG-BROIL, to balance expected performance and risk. Results suggest PG-BROIL can produce a family of behaviors ranging from risk-neutral to risk-averse.
  arXiv  Detail & Related papers  (2021-06-11T16:49:15Z)
• Learning MDPs from Features: Predict-Then-Optimize for Sequential Decision Problems by Reinforcement Learning [52.74071439183113]
  We study the predict-then-optimize framework in the context of sequential decision problems (formulated as MDPs) solved via reinforcement learning. Two significant computational challenges arise in applying decision-focused learning to MDPs.
  arXiv  Detail & Related papers  (2021-06-06T23:53:31Z)
• Inverse Active Sensing: Modeling and Understanding Timely Decision-Making [111.07204912245841]
  We develop a framework for the general setting of evidence-based decision-making under endogenous, context-dependent time pressure. We demonstrate how it enables modeling intuitive notions of surprise, suspense, and optimality in decision strategies.
  arXiv  Detail & Related papers  (2020-06-25T02:30:45Z)
• Causal Strategic Linear Regression [5.672132510411465]
  In many predictive decision-making scenarios, such as credit scoring and academic testing, a decision-maker must construct a model that accounts for agents' propensity to "game" the decision rule. We join concurrent work in modeling agents' outcomes as a function of their changeable attributes. We provide efficient algorithms for learning decision rules that optimize three distinct decision-maker objectives.
  arXiv  Detail & Related papers  (2020-02-24T03:57:22Z)
• Decisions, Counterfactual Explanations and Strategic Behavior [16.980621769406923]
  We find policies and counterfactual explanations that are optimal in terms of utility in a strategic setting. We show that, given a pre-defined policy, the problem of finding the optimal set of counterfactual explanations is NP-hard. We demonstrate that, by incorporating a matroid constraint into the problem formulation, we can increase the diversity of the optimal set of counterfactual explanations.
  arXiv  Detail & Related papers  (2020-02-11T12:04:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.