BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1126
DTSTAMP:20230914T125951Z
SUMMARY:Fair Cake Division
DESCRIPTION:Speaker: Nidhi Rathi (IISc Bangalore)\n\nAbstract: \nThe theory
  of Fair Division addresses the fundamental problem of allocating goods am
 ong agents with equal entitlements but distinct preferences. The classic c
 ake-cutting problem provides a model for addressing fair and efficient all
 ocation of a divisible\, heterogeneous resource (metaphorically\, the cake
 ) among agents with varied preferences. Classic results of Stromquist (198
 0) and Su (1999) show that envy-free (fair) cake divisions (with contiguou
 s pieces) are guaranteed to exist under mild conditions. These strong exis
 tential results follow from fixed-point theorems and stand without an algo
 rithmic counterpart.\n\nIn this talk\, I will present two of the recent re
 sults that complements the existential (and non-constructive) guarantees a
 nd various hardness results either by developing polynomial-time approxima
 tion algorithms or by identifying computationally tractable instances for 
 fair cake division. Our work identifies a broad class of cake division ins
 tances that essentially admits a polynomial time algorithm for computing f
 air and efficient allocations. In particular\, our algorithmic result hold
 s when (all) agents' valuations are induced either by linear translations 
 of any log-concave function\, Gaussian\, exponential\, linear\, or binomia
 l distributions.\n\nJoint work with Siddharth Barman\, Eshwar Ram Arunchal
 eswaran and Rachitesh Kumar.\n\nhttps://arxiv.org/abs/2006.00481\nhttps://
 arxiv.org/abs/1907.11019\n\nZoom link: https://zoom.us/j/98132227553?pwd=K
 2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1126
DTSTART;TZID=Asia/Kolkata:20210416T171500
DTEND;TZID=Asia/Kolkata:20210416T181500
END:VEVENT
END:VCALENDAR