Robust Strategic Classification under Decision-Dependent Cost Uncertainty

Humans facing algorithmic decision systems have been found to ``game'' them by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm). The growing literature on strategic classification seeks to develop robust machine learning algorithms that account for, and reduce, unwanted strategic behavior. A limitation of these existing works is that they assume the cost of strategic behavior to be fixed and independent of the classifier's decision. In practice, however, manipulation costs evolve and depend on past algorithmic decisions: today's decisions influence tomorrow's costs. This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies. We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time.

When people face an artificial intelligence (AI) algorithm that decides whether they should get invited for a job interview, get a loan, or be admitted to college, they behave strategically: they first try to figure out how the AI makes decisions, and then they change how they present themselves to the algorithm to receive better outcomes. Often, this is done in ways that reduce the ability of the AI algorithm to accurately identify qualified candidates. Researchers have been studying how to design algorithms that remain accurate even when people strategically change their behavior. However, existing studies so far have a common limitation: they assume that the difficulty or cost that people face for changing their behavior stays fixed over time. Yet, in reality, as algorithms adapt to people, people’s cost of responding to them changes in return. For example, when some universities stopped using SAT exam scores in their admission processes, the cost of getting essay coaching and extracurriculars increased instead. In our work, we set out to cover this gap, and study how AI algorithms should make decisions when human behavior costs evolve over time and depend on previous decisions. We model this interaction using a two-step mathematical optimization model that captures how today’s decisions influence tomorrow’s costs. Our results show that an algorithm should sometimes sacrifice a small amount of short-term accuracy in order to improve long-term performance, and that it can guide people to adopt strategic behavior in a way that benefits both qualified candidates and the algorithm.