Login
Talks & Seminars
Title: Approximating and Testing Equilibria
Dr. Siddharth Barman, California Institute of Technology
Date & Time: February 10, 2015 10:15
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
Algorithmic game theory is an active and impactful area of research that in recent years has found many applications in the study of large strategic environments, such as online markets and auctions, as well as social and biological systems. A basic message that emerged from this area is in fact negative: determining game-theoretic solution concepts -- e.g., Nash equilibria -- is computationally hard in general. But, given that such solution concepts are widely used in the design and analysis of strategic environments, these complexity barriers need to be addressed. Motivated by these considerations, in this talk I will present two complementary directions that address hardness results for Nash equilibria, 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 technical component of this work is an approximate version of Caratheodory's theorem; given the fundamental importance of Caratheodory's theorem, this approximate version is interesting in its own right. Then, I will describe how an empirical perspective can be employed to address the complexity of Nash equilibria in a number of cases. I will conclude by presenting a number of related problems and future research directions.
Speaker Profile:
Siddharth Barman is currently doing post-doctorate research at the California Institute of Technology. Siddharth completed his Ph.D. thesis Approximation Algorithms for Network Design and Partitioning Problems in June 2012 at the University of Wisconsin - Madison. Siddharth's research interests lie in the design, analysis, and applications of algorithms. His current research focuses on algorithmic game theory and approximation algorithms.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback