קולוקוויום בית הספר למדעי המחשב

Abstract 

As the influence of algorithms on economics and society grows, so does their interaction with strategic, self-interested players. Algorithm design must take such players’ incentives into account, or risk being “gamed” and failing miserably. Up until recently, a big part of the Algorithmic Game Theory (AGT) literature focused on mechanisms, i.e., algorithms that use payments to incentivize players to truthfully report the input. There is considerable interest in exploring additional ways in which algorithms and incentives intersect.

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. I will describe where we’re at in forming Algorithmic Contract Design, and how recent trends in AGT are shaping this new theory. In the main part of the talk I will demonstrate how algorithmic approaches – in particular the approach of beyond worst-case analysis (Trend #1) – can shed light on a classic economic puzzle regarding simple contracts. I will also discuss advancements in unifying different branches of algorithmic incentive design (Trend #2), including contract and mechanism design. Within the realm of incentives and learning (Trend #3), 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.