Algorithmic contract theory

Abstract: Algorithms increasingly interact with strategic, self-interested players; their design must take player incentives into account or risk being "gamed" and failing miserably. The algorithmic game theory literature traditionally focused on "mechanisms" - algorithms that incentivize players to truthfully report the input. In this talk we shift focus from mechanisms to "contracts", which are concerned with the algorithm's output and players' incentives to carry it out. The goal of this talk is to describe where we're at in forming a new algorithmic theory of contract design.

I will demonstrate how algorithmic approaches – in particular the approach of beyond worst-case analysis – can shed light on a classic economic puzzle regarding simple contracts. Within the realm of incentives and learning, I will discuss how classifiers induce incentives and show a formal relation to contracts.

Based on joint works with Tal Alon, Magdalen Dobson, Paul Duetting, Ron Lavi, Ariel Procaccia, Tim Roughgarden, Elisheva Shamash and Jamie Tucker-Foltz.

computational complexitycomputational geometrycryptography and securitydiscrete mathematicsdata structures and algorithmsgame theorymachine learningquantum computing and informationcombinatoricsinformation theoryoptimization and controlprobability

Audience: researchers in the topic

TCS+

Series comments: Description: Theoretical Computer Science

People can register to a talk via our webpage sites.google.com/site/plustcs/livetalk , or subscribe to our calendar and mailing list at sites.google.com/site/plustcs/rss-feeds