DOS Seminar - Rediet Abebe

Event Details
  • Date/Time:
    • Friday April 7, 2017 - Saturday April 8, 2017
      11:00 am - 11:59 am
  • Location: Groseclose 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar - Rediet Abebe

Full Summary: No summary paragraph submitted.

TITLE: Fair Division via Social Comparison


We study cake cutting on a graph, where agents can only evaluate their shares relative to their neighbors. This is an extension of the classical problem of fair division to incorporate the notion of social comparison from the social sciences. We say an allocation is locally envy-free if no agent envies a neighbor’s allocation, and locally proportional if each agent values its own allocation as much as the average value of its neighbors’ allocations. We generalize the classical “Cut and Choose” protocol for two agents to this setting, by fully characterizing the set of graphs for which an oblivious single-cutter protocol can give locally envy-free (thus also locally-proportional) allocations. We study the price of envy-freeness, which compares the total value of an optimal allocation with that of an optimal, locally envy-free allocation. Surprisingly, a lower bound of Ω(√n) on the price of envy-freeness for global allocations also holds for local envy-freeness in any connected graph, so sparse graphs do not provide more flexibility asymptotically with respect to the quality of envy-free allocations.



Rediet Abebe is a PhD student in the Department of Computer Science at Cornell University, advised by Jon Kleinberg. Her research focuses on algorithms, computational social science, and social networks. In particular, she is interested in using insights from theoretical computer science to better understand and implement interventions in socioeconomic inequality and opinion dynamics. She is the 2016 recipient of the Google Generation Scholarship. Prior to Cornell, she completed a B.A. in Mathematics from Harvard University, an M.A. in Mathematics from the University of Cambridge, and an M.S. in Applied Mathematics from Harvard University. She was born and raised in Addis Ababa, Ethiopia.


Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Mar 28, 2017 - 7:19am
  • Last Updated: Apr 13, 2017 - 5:12pm