Mechanisms for a No-Regret Agent: Beyond the Common Prior

A rich class of mechanism design problems can be understood as incomplete-information games between a principal who commits to a policy and an agent who responds, with payoffs determined by an unknown state of the world. Traditionally, these models require strong and often-impractical assumptions about beliefs (a common prior over the state). In this paper, we dispense with the common prior. Instead, we consider a repeated interaction where both the principal and the agent may learn over time from the state history. We reformulate mechanism design as a reinforcement learning problem and develop mechanisms that attain natural benchmarks without any assumptions on the state-generating process. Our results make use of novel behavioral assumptions for the agent -centered around counterfactual internal regret -that capture the spirit of rationality without relying on beliefs.

• This work began as part of the 2018 Special Quarter on Data Science and Online Markets at Northwestern. We are especially grateful to Simina Brânzei and Katya Khmelnitskaya for their early contributions to this project. We are also grateful to Eddie Dekel, Marciano Siniscalchi, and several anonymous referees for helpful comments, in addition to audiences at the 70th Midwest Theory Day and Northwestern. Jason Hartline and Aleck Johnsen were supported in part by NSF grant CCF-1618502.