BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1776
DTSTAMP:20260917T044852Z
SUMMARY:Fair Allocation with Dichotomous Preferences over Item Complements
DESCRIPTION:Speaker: Soumyajit Pyne (TIFR)\n\nAbstract: \nFair division stu
 dies how to allocate items among agents while satisfying fairness requirem
 ents. This work focuses on indivisible items with nonnegative marginal val
 ues. For binary submodular valuations\, where each marginal value is eithe
 r zero or one\, the Yankee Swap algorithm computes an allocation that simu
 ltaneously satisfies envy-freeness up to any good (EFX)\, maximum utilitar
 ian social welfare (Max-USW)\, and maximum Nash welfare (MNW) in polynomia
 l time. We introduce Submodular Preferences Over Complements (SPOC)\, wher
 e each agent specifies a matching over the goods and has a binary submodul
 ar valuation over these complements. This captures applications such as co
 urse allocation\, where a student may value two complementary courses only
  when taken together.\nFor SPOC valuations\, we show that envy-freeness up
  to one good (EF1) and Pareto optimality (PO) need not coexist\, ruling ou
 t a general guarantee of EFX and Max-USW. However\, we give a polynomial-t
 ime algorithm that simultaneously achieves EFX\, a (1/3)-approximation to 
 Max-USW\, and a (1/(3+1/n))-approximation to the maximin share (MMS)\, whe
 re n is the number of agents. The welfare guarantee is almost to tight: th
 ere are instances where no EF1 allocation achieves more than half the opti
 mal utilitarian welfare. We also prove that maximizing utilitarian welfare
  is APX-hard and provide polynomial-time algorithms for a (1/2)-approximat
 ion to Max-USW and later another polytime algorithm that produces an alloc
 ation which is ((5\,1))-MNW allocation.\n
URL:https://www.tcs.tifr.res.in/web/events/1776
DTSTART;TZID=Asia/Kolkata:20260918T160000
DTEND;TZID=Asia/Kolkata:20260918T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR