BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1367
DTSTAMP:20231207T030511Z
SUMMARY:Nearly Equitable Allocations Beyond Additivity and Monotonicity
DESCRIPTION:Speaker: Yeshwant Chandrakant Pandit (TIFR)\n\nAbstract: \nEqu
itability (EQ) in fair division requires that items be allocated such that
all agents value the bundle they receive equally. With indivisible items\
, an equitable allocation may not exist\, and hence we instead consider a
meaningful analog\, EQx\, that requires equitability up to any item. EQx a
llocations exist for monotone\, additive valuations. However\, if (1) the
agents' valuations are not additive or (2) the set of indivisible items in
cludes both goods and chores (positively and negatively valued items)\, th
en before the current work it was not known whether EQx allocations exist
or not.\nWe study both the existence and efficient computation of EQx allo
cations. (1) For monotone valuations (not necessarily additive)\, we show
that EQx allocations always exist. Also\, for the large class of weakly we
ll-layered valuations\, EQx allocations can be found in polynomial time. F
urther\, we prove that approximately EQx allocations can be computed effic
iently under general monotone valuations. (2) For non-monotone valuations\
, we show that an EQx allocation may not exist\, even for two agents with
additive valuations. Under some special cases\, however\, we show the exis
tence and efficient computability of EQx allocations. This includes the ca
se of two agents with additive valuations where each item is either a good
or a chore\, and there are no mixed items.\nThe focus of this talk will b
e on the results obtained under monotone valuations. This is joint work wi
th Siddharth Barman(IISC\, Bangalore)\, Umang Bhaskar(TIFR\, Mumbai) and S
oumyajit Pyne(TIFR\, Mumbai).\n
URL:https://www.tcs.tifr.res.in/web/events/1367
DTSTART;TZID=Asia/Kolkata:20231208T160000
DTEND;TZID=Asia/Kolkata:20231208T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR