BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/224
DTSTAMP:20230914T125915Z
SUMMARY:Approximation Algorithm for Security Games with Costly Resources
DESCRIPTION:Speaker: Sayan Bhattacharya\nDuke University\nDepartment of Com
puter Science\nN303\, North Building\n304 Research Drive\nDurham\, NC 2770
8\nUnited States of America\n\nAbstract: \nIn recent years\, algorithms fo
r computing game-theoretic solutions have been developed for real-world se
curity domains. These games are between a defender\, who must allocate her
resources to defend potential targets\, and an attacker\, who chooses a t
arget to attack. Existing work has assumed the set of defender’s resourc
es to be ﬁxed. This assumption precludes the effective use of approximat
ion algorithms\, since a slight change in the defender’s allocation stra
tegy can result in a massive change in her utility. In contrast\, we consi
der a model where resources are obtained at a cost\, initiating the study
of the following optimization problem: Minimize the total cost of the purc
hased resources\, given that every target has to be defended with at least
a certain probability. We give an efficient logarithmic approximation alg
orithm for this problem (joint work with Vincent Conitzer and Kamesh Munag
ala).\n
URL:https://www.tcs.tifr.res.in/web/events/224
DTSTART;TZID=Asia/Kolkata:20111129T160000
DTEND;TZID=Asia/Kolkata:20111129T170000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR