Principal-agent Boolean games

David Hyland, Julian Gutierrez, Michael Wooldridge

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


We introduce and study a computational version of the principal-agent problem - a classic problem in Economics that arises when a principal desires to contract an agent to carry out some task, but has incomplete information about the agent or their subsequent actions. The key challenge in this setting is for the principal to design a contract for the agent such that the agent's preferences are then aligned with those of the principal. We study this problem using a variation of Boolean games, where multiple players each choose valuations for Boolean variables under their control, seeking the satisfaction of a personal goal, given as a Boolean logic formula. In our setting, the principal can only observe some subset of these variables, and the principal chooses a contract which rewards players on the basis of the assignments they make for the variables that are observable to the principal. The principal's challenge is to design a contract so that, firstly, the principal's goal is achieved in some or all Nash equilibrium choices, and secondly, that the principal is able to verify that their goal is satisfied. In this paper, we formally define this problem and completely characterise the computational complexity of the most relevant decision problems associated with it.

Original languageEnglish
Title of host publicationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
EditorsEdith Elkind
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781956792034
Publication statusPublished - 2023
EventInternational Joint Conference on Artificial Intelligence 2023 - Macao, China
Duration: 19 Aug 202325 Aug 2023
Conference number: 32nd (Proceedings) (Website)

Publication series

NameProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
PublisherIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823


ConferenceInternational Joint Conference on Artificial Intelligence 2023
Abbreviated titleIJCAI 2023
Internet address


  • Agent-based and Multi-agent Systems
  • Agent theories and models
  • Coordination and cooperation
  • Formal verification, validation and synthesis

Cite this