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