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