Computational Fair Division and Mechanism Design

Simina Branzei
Hebrew University of Jerusalem
03.01.2017 11:00 to 12:00
AVW 4172

The emergence of online platforms has brought about a fundamental shift in economic thinking: the design of economic systems is now a problem that computer science can tackle. For the first time we are able to move from the study of economic systems as natural systems to carefully designing and executing them on a computer. Prominent examples of digital market mechanisms include auctions for ads (run by companies such as Google) and electromagnetic spectrum (used by the US government). I will discuss several recent developments in fair division and mechanism design. I will start with a dictatorship theorem for fair division (cake cutting), showing that requiring truthfulness gives rise to a dictator. Next, I will turn to the paradigmatic model of multi-unit markets, where I will show that truthfulness requires discarding resources, but this problem can be alleviated when the market is even mildly competitive. More generally, I will discuss the theme of simplicity and complexity in mechanism design, and the interplay between economics and computation and learning.