Date: Wednesday, May 24th, 2023
9:00 am – 10:00 am Pacific Time
12:00 pm – 1:00 pm Eastern Time
Location: Weekly Seminar, Zoom
Title: Algorithmic Decision-Making under Incentives: Apple Tasting Feedback and Multiclass Learnability
Abstract:
Algorithmic systems have recently been used to aid in or automate decision-making in high-stakes domains in order to, e.g. improve efficiency or reduce human bias. When subjugated to decision-making in these settings, decision-subjects (or agents) have an incentive to strategically modify their observable attributes in order to appear more qualified. Moreover, in many domains of interest (e.g. lending and hiring), the decision-maker only observes feedback if they assign a positive decision to an agent; this type of feedback is often referred to as apple tasting (or one-sided) feedback.
In the first part of the talk, we examine the effects of apple tasting feedback in the online (binary) strategic classification setting. We provide several algorithms which achieve sublinear regret with respect to the best fix policy in hindsight if the agents were truthful (i.e. non-strategic). We also show how our results may be easily adapted to the setting where the decision-maker receives bandit feedback.
Next, we shift our focus to the multiclass extension of strategic classification. Despite being well-motivated in settings such as e-commerce and medical domains, the multiclass version of the problem has received relatively little attention in the current literature on classification under incentives. Perhaps somewhat surprisingly, we show that unlike in the binary setting, strategyproof multiclass classification is generally not possible, even when full feedback is observed.
This talk is based on joint work with Anish Agarwal, Chara Podimata, and Steven Wu.
Bio:
Keegan is a Ph.D. student in the School of Computer Science at Carnegie Mellon University. His research interests span machine learning, algorithmic game theory, econometrics, and their various intersections. He is advised by Nina Balcan and Steven Wu, and supported by the NDSEG Fellowship. Previously, he received a M.S. in Machine Learning from Carnegie Mellon University, a B.S. in Computer Science from Penn State University, and a B.S. in Physics from Penn State University.