Timezone: »
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.
Author Information
Keegan Harris (Carnegie Mellon University)
Valerie Chen (Carnegie Mellon University)
Joon Kim (Carnegie Mellon University)
Ameet Talwalkar (CMU)
Hoda Heidari (Carnegie Mellon University)
Steven Wu (Carnegie Mellon University)
More from the Same Authors
-
2021 : Simulated User Studies for Explanation Evaluation »
Valerie Chen · Gregory Plumb · Nicholay Topin · Ameet S Talwalkar -
2021 : What Would the Expert do()?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods »
Terrance Liu · Giuseppe Vietri · Steven Wu -
2021 : What Would the Expert do()?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Sik Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Information Discrepancy in Strategic Learning »
Yahav Bechavod · Chara Podimata · Steven Wu · Juba Ziani -
2021 : Gaming Helps! Learning from Strategic Interactions in Natural Dynamics »
Yahav Bechavod · Katrina Ligett · Steven Wu · Juba Ziani -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet S Talwalkar · Hoda Heidari · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : What Would the Expert $do(\cdot)$?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 : Information Discrepancy in Strategic Learning »
Yahav Bechavod · Chara Podimata · Steven Wu · Juba Ziani -
2021 : Gaming Helps! Learning from Strategic Interactions in Natural Dynamics »
Yahav Bechavod · Katrina Ligett · Steven Wu · Juba Ziani -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet S Talwalkar · Hoda Heidari · Steven Wu -
2022 : Strategy-Aware Contextual Bandits »
Keegan Harris · Chara Podimata · Steven Wu -
2022 : AutoML for Climate Change: A Call to Action »
Renbo Tu · Nicholas Roberts · Vishak Prasad C · Sibasis Nayak · Paarth Jain · Frederic Sala · Ganesh Ramakrishnan · Ameet Talwalkar · Willie Neiswanger · Colin White -
2022 : Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance »
Xin Gu · Gautam Kamath · Steven Wu -
2022 : Strategy-Aware Contextual Bandits »
Keegan Harris · Chara Podimata · Steven Wu -
2022 : Strategy-Aware Contextual Bandits »
Keegan Harris · Chara Podimata · Steven Wu -
2022 : Differentially Private Gradient Boosting on Linear Learners for Tabular Data »
Saeyoung Rho · Shuai Tang · Sergul Aydore · Michael Kearns · Aaron Roth · Yu-Xiang Wang · Steven Wu · Cedric Archambeau -
2022 : Counterfactual Decision Support Under Treatment-Conditional Outcome Measurement Error »
Luke Guerdan · Amanda Coston · Kenneth Holstein · Steven Wu -
2023 Poster: Scalable Membership Inference Attacks via Quantile Regression »
Martin Bertran · Shuai Tang · Aaron Roth · Michael Kearns · Jamie Morgenstern · Steven Wu -
2023 Poster: Meta-Learning Adversarial Bandit Algorithms »
Misha Khodak · Ilya Osadchiy · Keegan Harris · Maria-Florina Balcan · Kfir Y. Levy · Ron Meir · Steven Wu -
2023 Poster: Strategic Apple Tasting »
Keegan Harris · Chara Podimata · Steven Wu -
2023 Poster: Adaptive Privacy Composition for Accuracy-first Mechanisms »
Ryan Rogers · Gennady Samorodnitsk · Steven Wu · Aaditya Ramdas -
2023 Poster: Adaptive Principal Component Regression with Applications to Panel Data »
Anish Agarwal · Keegan Harris · Justin Whitehouse · Steven Wu -
2023 Poster: Improved Self-Normalized Concentration in Hilbert Spaces: Sublinear Regret for GP-UCB »
Justin Whitehouse · Aaditya Ramdas · Steven Wu -
2023 Poster: Learning Shared Safety Constraints from Multi-task Demonstrations »
Konwoo Kim · Gokul Swamy · ZUXIN LIU · DING ZHAO · Sanjiban Choudhury · Steven Wu -
2023 Tutorial: Governance & Accountability for ML: Existing Tools, Ongoing Efforts, & Future Directions »
· Daniel Ho · Hoda Heidari -
2022 Competition: AutoML Decathlon: Diverse Tasks, Modern Methods, and Efficiency at Scale »
Samuel Guo · Cong Xu · Nicholas Roberts · Misha Khodak · Junhong Shen · Evan Sparks · Ameet Talwalkar · Yuriy Nevmyvaka · Frederic Sala · Anderson Schneider -
2022 Poster: Use-Case-Grounded Simulations for Explanation Evaluation »
Valerie Chen · Nari Johnson · Nicholay Topin · Gregory Plumb · Ameet Talwalkar -
2022 Poster: On Privacy and Personalization in Cross-Silo Federated Learning »
Ken Liu · Shengyuan Hu · Steven Wu · Virginia Smith -
2022 Poster: Provably tuning the ElasticNet across instances »
Maria-Florina Balcan · Misha Khodak · Dravyansh Sharma · Ameet Talwalkar -
2022 Poster: Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints »
Justin Whitehouse · Aaditya Ramdas · Steven Wu · Ryan Rogers -
2022 Poster: Incentivizing Combinatorial Bandit Exploration »
Xinyan Hu · Dung Ngo · Aleksandrs Slivkins · Steven Wu -
2022 Poster: Sequence Model Imitation Learning with Unobserved Contexts »
Gokul Swamy · Sanjiban Choudhury · J. Bagnell · Steven Wu -
2022 Poster: Learning Predictions for Algorithms with Predictions »
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar · Sergei Vassilvitskii -
2022 Poster: Private Synthetic Data for Multitask Learning and Marginal Queries »
Giuseppe Vietri · Cedric Archambeau · Sergul Aydore · William Brown · Michael Kearns · Aaron Roth · Ankit Siva · Shuai Tang · Steven Wu -
2022 Poster: Minimax Optimal Online Imitation Learning via Replay Estimation »
Gokul Swamy · Nived Rajaraman · Matt Peng · Sanjiban Choudhury · J. Bagnell · Steven Wu · Jiantao Jiao · Kannan Ramchandran -
2022 Poster: Efficient Architecture Search for Diverse Tasks »
Junhong Shen · Misha Khodak · Ameet Talwalkar -
2022 Poster: NAS-Bench-360: Benchmarking Neural Architecture Search on Diverse Tasks »
Renbo Tu · Nicholas Roberts · Misha Khodak · Junhong Shen · Frederic Sala · Ameet Talwalkar -
2021 : [S9] Simulated User Studies for Explanation Evaluation »
Valerie Chen · Gregory Plumb · Nicholay Topin · Ameet S Talwalkar -
2021 : Leveraging strategic interactions for causal discovery »
Steven Wu -
2021 : Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Sik Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
2021 : What Would the Expert do()?: Causal Imitation Learning »
Gokul Swamy · Sanjiban Choudhury · James Bagnell · Steven Wu -
2021 Poster: Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods »
Terrance Liu · Giuseppe Vietri · Steven Wu -
2021 Poster: Federated Hyperparameter Tuning: Challenges, Baselines, and Connections to Weight-Sharing »
Mikhail Khodak · Renbo Tu · Tian Li · Liam Li · Maria-Florina Balcan · Virginia Smith · Ameet Talwalkar -
2021 Poster: Stateful Strategic Regression »
Keegan Harris · Hoda Heidari · Steven Wu -
2021 Poster: Rethinking Neural Operations for Diverse Tasks »
Nicholas Roberts · Mikhail Khodak · Tri Dao · Liam Li · Christopher Ré · Ameet Talwalkar -
2021 Poster: Learning-to-learn non-convex piecewise-Lipschitz functions »
Maria-Florina Balcan · Mikhail Khodak · Dravyansh Sharma · Ameet Talwalkar -
2020 Workshop: International Workshop on Scalability, Privacy, and Security in Federated Learning (SpicyFL 2020) »
Xiaolin Andy Li · Dejing Dou · Ameet Talwalkar · Hongyu Li · Jianzong Wang · Yanzhi Wang -
2020 Poster: PLLay: Efficient Topological Layer based on Persistent Landscapes »
Kwangho Kim · Jisu Kim · Manzil Zaheer · Joon Kim · Frederic Chazal · Larry Wasserman -
2020 Poster: Regularizing Black-box Models for Improved Interpretability »
Gregory Plumb · Maruan Al-Shedivat · Ángel Alexander Cabrera · Adam Perer · Eric Xing · Ameet Talwalkar -
2020 Poster: Metric-Free Individual Fairness in Online Learning »
Yahav Bechavod · Christopher Jung · Steven Wu -
2020 Poster: Understanding Gradient Clipping in Private SGD: A Geometric Perspective »
Xiangyi Chen · Steven Wu · Mingyi Hong -
2020 Poster: Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms »
Xiangyi Chen · Tiancong Chen · Haoran Sun · Steven Wu · Mingyi Hong -
2020 Spotlight: Understanding Gradient Clipping in Private SGD: A Geometric Perspective »
Xiangyi Chen · Steven Wu · Mingyi Hong -
2020 Oral: Metric-Free Individual Fairness in Online Learning »
Yahav Bechavod · Christopher Jung · Steven Wu -
2020 Session: Orals & Spotlights Track 20: Social/Adversarial Learning »
Steven Wu · Miro Dudik -
2019 : TBD »
Ameet Talwalkar -
2019 Poster: Equal Opportunity in Online Classification with Partial Feedback »
Yahav Bechavod · Katrina Ligett · Aaron Roth · Bo Waggoner · Steven Wu -
2019 Poster: Random Quadratic Forms with Dependence: Applications to Restricted Isometry and Beyond »
Arindam Banerjee · Qilong Gu · Vidyashankar Sivakumar · Steven Wu -
2019 Poster: Private Hypothesis Selection »
Mark Bun · Gautam Kamath · Thomas Steinke · Steven Wu -
2019 Poster: Adaptive Gradient-Based Meta-Learning Methods »
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar -
2019 Poster: Locally Private Gaussian Estimation »
Matthew Joseph · Janardhan Kulkarni · Jieming Mao · Steven Wu -
2018 Poster: Model Agnostic Supervised Local Explanations »
Gregory Plumb · Denali Molitor · Ameet Talwalkar -
2018 Poster: Representer Point Selection for Explaining Deep Neural Networks »
Chih-Kuan Yeh · Joon Kim · Ian En-Hsu Yen · Pradeep Ravikumar -
2017 : Spotlights »
Antti Kangasrääsiö · Richard Everett · Yitao Liang · Yang Cai · Steven Wu · Vidya Muthukumar · Sven Schmit -
2017 Poster: Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM »
Katrina Ligett · Seth Neel · Aaron Roth · Bo Waggoner · Steven Wu -
2017 Poster: Variable Importance Using Decision Trees »
Jalil Kazemitabar · Arash Amini · Adam Bloniarz · Ameet S Talwalkar -
2017 Poster: Federated Multi-Task Learning »
Virginia Smith · Chao-Kai Chiang · Maziar Sanjabi · Ameet S Talwalkar -
2016 : Invited Talk: Paleo: A Performance Model for Deep Neural Networks (Ameet Talwalkar, UCLA) »
Ameet S Talwalkar -
2016 Poster: Yggdrasil: An Optimized System for Training Deep Decision Trees at Scale »
Firas Abuzaid · Joseph K Bradley · Feynman Liang · Andrew Feng · Lee Yang · Matei Zaharia · Ameet S Talwalkar -
2016 Poster: Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs »
Shahin Jabbari · Ryan Rogers · Aaron Roth · Steven Wu -
2014 Workshop: Distributed Machine Learning and Matrix Computations »
Reza Zadeh · Ion Stoica · Ameet S Talwalkar -
2011 Workshop: Sparse Representation and Low-rank Approximation »
Ameet S Talwalkar · Lester W Mackey · Mehryar Mohri · Michael W Mahoney · Francis Bach · Mike Davies · Remi Gribonval · Guillaume R Obozinski -
2011 Poster: Divide-and-Conquer Matrix Factorization »
Lester W Mackey · Ameet S Talwalkar · Michael Jordan -
2010 Workshop: Low-rank Methods for Large-scale Machine Learning »
Arthur Gretton · Michael W Mahoney · Mehryar Mohri · Ameet S Talwalkar -
2009 Poster: Ensemble Nystrom Method »
Sanjiv Kumar · Mehryar Mohri · Ameet S Talwalkar