Algorithmic contract theory
Inbal Talgam-Cohen (Technion – Israel Institute of Technology)
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
Series comments: Description: Theoretical Computer Science
|Organizers:||Clément Canonne*, Anindya De, Sumegha Garg, Gautam Kamath, Ilya Razenshteyn, Oded Regev, Tselil Schramm, Thomas Vidick, Erik Waingarten|
|*contact for this listing|