A Game-Theoretic Perspective on Trustworthy Algorithms

Abstract: Many algorithms are trained on data provided by humans, such as those that power recommender systems and hiring decision aids. Most data-driven algorithms assume that user behavior is exogenous: a user would react a given prompt (e.g., a recommendation or hiring suggestion) in the same way no matter what algorithm generated it. For example, algorithms that rely on an i.i.d. assumption inherently assume exogeneity. In practice, user behavior is not exogenous---users are *strategic*. For example, there are documented cases of TikTok users changing their scrolling behavior after realizing that the TikTok algorithm pays attention to dwell time, and Uber drivers changing how they accept and cancel rides based on Uber's matching algorithm.

What are the implications of breaking the exogeneity assumption? We answer this question in our work, modeling the interactions between a user and their data-driven platform as a repeated, two-player game. We leverage results from misspecified learning to characterize the effect of strategization on data-driven algorithms. As one of our main contributions, we find that designing trustworthy algorithms can go hand in hand with accurate estimation. That is, there is not necessarily a trade-off between performance and trustworthiness. We provide a formalization of trustworthiness that inspires potential interventions.