BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/574
DTSTAMP:20230914T125930Z
SUMMARY:Approximating and Testing Equilibria
DESCRIPTION:Speaker: Siddharth Barman (California Institute of Technology\n
1200 E. California Boulevard\nPasadena\, CA 91125\nUnited States of Americ
a)\n\nAbstract: \nAbstract: Algorithmic game theory is an active and impac
tful area of research that in recent years has found many applications in
the study of large strategic environments\, like online markets and auctio
ns\, as well as social and biological systems. A basic message that emerge
d from this area is in fact negative: determining game-theoretic solution
concepts---e.g.\, Nash equilibria---is computationally hard in general. Bu
t\, given that such solution concepts are widely used in the design and an
alysis of strategic environments\, these complexity barriers need to be ad
dressed.\n\nMotivated by these considerations\, in this talk I will presen
t two complementary directions that address hardness results for Nash equi
libria\, which are one of the most well-studied solution concepts in game
theory. First\, I will show that for a relevant class of two-player games
an approximate Nash equilibrium can be efficiently determined. A key techn
ical component of this work is an approximate version of Caratheodoryâ€™s
theorem\; given the fundamental importance of Caratheodoryâ€™s theorem\, t
his approximate version is interesting in its own right. Then\, I will des
cribe how an empirical perspective can be employed to address the complexi
ty of Nash equilibria in a number of cases. I will conclude by presenting
a number of related problems and future research directions.\n
URL:https://www.tcs.tifr.res.in/web/events/574
DTSTART;TZID=Asia/Kolkata:20150212T143000
DTEND;TZID=Asia/Kolkata:20150212T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR