TY - GEN
T1 - Mechanisms for a no-regret agent
T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
AU - Camara, Modibo K.
AU - Hartline, Jason D.
AU - Johnsen, Aleck
N1 - Funding Information:
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.
Publisher Copyright:
© 2020 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - 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-based on counterfactual internal regret-that capture the spirit of rationality without relying on beliefs. 11For the full version of this paper, see https://arxiv.org/abs/2009.05518.
AB - 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-based on counterfactual internal regret-that capture the spirit of rationality without relying on beliefs. 11For the full version of this paper, see https://arxiv.org/abs/2009.05518.
KW - n/a
UR - http://www.scopus.com/inward/record.url?scp=85100345184&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100345184&partnerID=8YFLogxK
U2 - 10.1109/FOCS46700.2020.00033
DO - 10.1109/FOCS46700.2020.00033
M3 - Conference contribution
AN - SCOPUS:85100345184
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 259
EP - 270
BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PB - IEEE Computer Society
Y2 - 16 November 2020 through 19 November 2020
ER -