BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1412
DTSTAMP:20240403T092106Z
SUMMARY:The complexity of contracts [Roughgarden et. al.]
DESCRIPTION:Speaker: Soumyajit Pyne (TIFR)\n\nAbstract: \nThe paper focuses
on principal-agent settings with succinctly described outcome space (expo
nentially large). The goal of the principal is to design a contract that m
aximizes its expected payoff. The authors show that for n > 2 actions this
problem turns out to be NP-hard. For settings with a constant number of a
ctions\, the authors present a fully polynomial-time approximation scheme
(FPTAS) for the separation oracle of the dual of the problem of minimizing
the principal's payment to the agent\, and use this subroutine to efficie
ntly compute a delta-incentive-compatible (delta-IC) contract whose expect
ed payoff matches or surpasses that of the optimal IC contract.With an arb
itrary number of actions\, the authors prove that the problem is hard to a
pproximate within any constant c. This inapproximability result holds even
for delta-IC contracts where delta is a sufficiently rapidly-decaying fun
ction of c. On the positive side\, the authors show that simple linear del
ta-IC contracts with constant delta are sufficient to achieve a constant-f
actor approximation of the "first-best" (full-welfare-extracting) solution
\, and that such a contract can be computed in polynomial time.\nHere is t
he link to the paper : https://arxiv.org/abs/2002.12034\n
URL:https://www.tcs.tifr.res.in/web/events/1412
DTSTART;TZID=Asia/Kolkata:20240405T160000
DTEND;TZID=Asia/Kolkata:20240405T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR