Mechanisms for a no-regret agent: Beyond the common prior

Modibo K. Camara, Jason D. Hartline, Aleck Johnsen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Pages259-270
Number of pages12
ISBN (Electronic)9781728196213
DOIs
StatePublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN (Print)0272-5428

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Country/TerritoryUnited States
CityVirtual, Durham
Period11/16/2011/19/20

Keywords

  • n/a

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Mechanisms for a no-regret agent: Beyond the common prior'. Together they form a unique fingerprint.

Cite this