BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1626
DTSTAMP:20251001T044323Z
SUMMARY:Fair Randomized Allocations under Lexicographic Preferences
DESCRIPTION:Speaker: Surya Panchapakesan (IISER Pune)\n\nAbstract: \nA cent
 ral problem in fair division involves allocating a set of M indivisible 
 goods among N agents in a fair and efficient manner. The quintessenti
 al fairness notion is "envy freeness" (EF) where every agent prefers their
  own assignment over that of any other agent's. In the deterministic setti
 ng\, EF allocations may not always exist\, motivating the study of relaxat
 ions such as envy-freeness up to any good (EFX). While deciding the exi
 stence of EFX allocations remains unresolved even for just four agents wit
 h additive valuations\, interestingly\, Hosseini et al. showed that EF
 X allocations always exist and can be computed efficiently when agents hav
 e lexicographic preferences.\n \nTraditional approaches in the literatu
 re focus either on randomized allocations that are fair in expectation o
 r deterministic allocations that are "approximately" fair. Recently\, th
 ese two approaches have been reconciled in the form of "best-of-both-worl
 ds" guarantees [AFSV '24]\, wherein one seeks a randomized allocation tha
 t is fair in expectation (i.e.\, ex-ante fairness) while also being suppor
 ted on approximately fair allocations (i.e.\, ex-post fairness). \n \nIn
  this talk\, I will discuss some of our approaches at achieving best-of-bo
 th-worlds guarantees for agents with lexicographic preferences. I will fi
 rst introduce some of the techniques we use in our methods\, and then pres
 ent an algorithm that achieves ex-ante 6/7-EF and ex-post (EFX + PO). Foll
 owing this (if time permits)\, we shall see a refinement that strengthens 
 the ex-ante ratio to 9/10-EF while preserving the ex-post guarantees. \n
  \nThe talk is based on joint work with Telikepalli Kavitha\, Vignesh Vis
 wanathan\, Rohit Vaish and Jatin Yadav.\n
URL:https://www.tcs.tifr.res.in/web/events/1626
DTSTART;TZID=Asia/Kolkata:20251003T160000
DTEND;TZID=Asia/Kolkata:20251003T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR