BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1724
DTSTAMP:20260604T082839Z
SUMMARY:Truthful-in-Expectation Mechanisms for MMS Approximation
DESCRIPTION:Speaker: Moshe Babaioff (Hebrew University of Jerusalem)\n\nAbs
 tract: \nHow can we fairly divide a set of m indivisible goods among n sel
 f-interested agents with additive valuations who might lie about their pre
 ferences? This fundamental problem sits at the intersection of mechanism d
 esign and fair division. While compelling fairness benchmarks like the Max
 imin Share (MMS) are approximately achievable algorithmically\, severe imp
 ossibility results arise in the strategic setting. In particular\, in prio
 r work with Noam Manaker Morag (EC 2025)\, we showed that the best MMS a
 pproximation achievable by deterministic mechanisms that are truthful\, no
 n-bossy\, and neutral is a mere O(1/m). This poor guarantee is matched by 
 a trivial mechanism: letting every agent but the last pick exactly one goo
 d\, and giving all remaining goods to the last agent.\nIn this talk\, we s
 eek to design randomized mechanisms that are truthful-in-expectation (TIE)
  while also obtaining strong fairness guarantees in every realized outcome
 .  Previously\, the best-known TIE mechanism guaranteed only a 1/n-fract
 ion of each agent's MMS ex-post. We present new randomized mechanisms that
  dramatically improve the MMS approximation: first\, an ordinal TIE mechan
 ism guaranteeing about 1/log n-MMS ex-post\, which is nearly optimal for
  ordinal mechanisms\; second\, a mechanism that slightly relaxes truthfuln
 ess-in-expectation and improves the guarantee to Ω(1/log log n)-MMS\; 
 and finally\, for two agents\, a TIE mechanism guaranteeing 2/3-MMS ex-po
 st. All these mechanisms run in polynomial time and are ex-ante proportion
 al. Thus\, they provide strategic "Best-of-Both-Worlds" results: proportio
 nality in expectation\, together with strong MMS guarantees in every reali
 zed allocation.\nJoint work with Uriel Feige and Noam Manaker Morag.Link 
 to arXiv: https://arxiv.org/abs/2604.27211\n \nBio: Prof. Moshe Babaioff
  is an Associate Professor in the School of Computer Science and Engineeri
 ng at the Hebrew University of Jerusalem and a member of the Federmann Cen
 ter for the Study of Rationality. His research lies at the intersection of
  theoretical computer science\, game theory\, and economics\, with interes
 ts including algorithmic game theory\, mechanism design\, auction theory\,
  and fairness. Prior to joining the Hebrew University\, he was a Senior Pr
 incipal Researcher at Microsoft Research. He received his Ph.D. from the H
 ebrew University of Jerusalem under the supervision of Prof. Noam Nisan.\n
URL:https://www.tcs.tifr.res.in/web/events/1724
DTSTART;TZID=Asia/Kolkata:20260616T160000
DTEND;TZID=Asia/Kolkata:20260616T170000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR