Strategic Apple Tasting

Algorithmic decision-making in high-stakes domains often involves assigning decisions to agents with incentives to strategically modify their input to the algorithm. We formalize this setting as an online learning problem with apple-tasting feedback where a principal makes decisions about a sequence of T agents, each of which is represented by a context that may be strategically modified. Our goal is to achieve sublinear strategic regret, which compares the performance of the principal to that of the best fixed policy in hindsight, if the agents were truthful when revealing their contexts. Our main result is a learning algorithm which incurs \tilde{\mathcal{O}}(\sqrt{T}) strategic regret when the sequence of agents is chosen stochastically. We also give an algorithm capable of handling adversarially-chosen agents, albeit at the cost of \tilde{\mathcal{O}}(T {(d 1)/(d 2)}) strategic regret (where d is the dimension of the context).