Timezone: »
Automated decision-making tools increasingly assess individuals to determine if they qualify for high-stakes opportunities. A recent line of research investigates how strategic agents may respond to such scoring tools to receive favorable assessments. While prior work has focused on the short-term strategic interactions between a decision-making institution (modeled as a principal) and individual decision-subjects (modeled as agents), we investigate interactions spanning multiple time-steps. In particular, we consider settings in which the agent's effort investment today can accumulate over time in the form of an internal state - impacting both his future rewards and that of the principal. We characterize the Stackelberg equilibrium of the resulting game and provide novel algorithms for computing it. Our analysis reveals several intriguing insights about the role of multiple interactions in shaping the game's outcome: First, we establish that in our stateful setting, the class of all linear assessment policies remains as powerful as the larger class of all monotonic assessment policies. While recovering the principal's optimal policy requires solving a non-convex optimization problem, we provide polynomial-time algorithms for recovering both the principal and agent's optimal policies under common assumptions about the process by which effort investments convert to observable features. Most importantly, we show that with multiple rounds of interaction at her disposal, the principal is more effective at incentivizing the agent to accumulate effort in her desired direction. Our work addresses several critical gaps in the growing literature on the societal impacts of automated decision-making - by focusing on longer time horizons and accounting for the compounding nature of decisions individuals receive over time.
Author Information
Keegan Harris (Carnegie Mellon University)
Hoda Heidari (Carnegie Mellon University)
Steven Wu (Carnegie Mellon University)
More from the Same Authors
-
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 : 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 -
2022 Poster: On Privacy and Personalization in Cross-Silo Federated Learning »
Ken Liu · Shengyuan Hu · Steven Wu · Virginia Smith -
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: 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: Bayesian Persuasion for Algorithmic Recourse »
Keegan Harris · Valerie Chen · Joon Kim · Ameet Talwalkar · Hoda Heidari · Steven Wu -
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 Workshop: Learning and Decision-Making with Strategic Feedback (StratML) »
Yahav Bechavod · Hoda Heidari · Eric Mazumdar · Celestine Mendler-Dünner · Tijana Zrnic -
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 -
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 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: Locally Private Gaussian Estimation »
Matthew Joseph · Janardhan Kulkarni · Jieming Mao · Steven Wu -
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 -
2016 Poster: Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs »
Shahin Jabbari · Ryan Rogers · Aaron Roth · Steven Wu