Truthful Cake Cutting Mechanisms with Externalities

Speaker(s)

Qiang Zhang

Affiliation

Instytut Informatyki, Wydział MIM UW

Date

Nov. 19, 2015, 12:15 p.m.

Room

room 3320

Seminar

Seminar Games, Mechanisms, and Social Networks

---

Cake cutting is a fundamental problem that studies fair resource division among agents. In this talk, I will review some classical cake cutting algorithms and discuss research directions in cake cutting problems. In particular, we will see truthful cake cutting mechanisms when agents not only value their ownpieces of cake but also care for the pieces assigned to other agents. Specifically, agents derive benefits or costs from the pieces of cake assigned to other agents. This phenomenon is often referred to as positive or negative externalities. We propose and study the following model: given an allocation, externalities of agents are modeled as percentages of the reported values that other agents have for their pieces. We show that even in this restricted class of externalities, under some natural assumptions, no truthful cake cutting mechanisms exist when externalities are either positive or negative. However, when the percentages agents get from each other are small, we show that there exists a truthful cake cutting mechanism with other desired properties.

---