Computer Science Speaking Skills Talk
Speaker
GABRIELE FARINA
Ph.D. Student
Computer Science Department
Carnegie Mellon University
When
-
Where
In Person
Description
Computational game theory studies optimal decision making in multi-agent interactions ("games") under imperfect information and strategic behavior. While much work has focused on solving decision-making problems in which all agents act once and simultaneously, I will focus on the more realistic case in which each agent faces a tree-form decision problem with potentially multiple acting points and partial observability ("extensive-form games").
In the first part of the talk, I will give new learning algorithms for agents in extensive-form games. Specifically, I will introduce the current theoretical and practical state-of-the-art algorithms for Nash equilibrium in large two-player zero-sum games. Furthermore, I will discuss the first efficient uncoupled no-regret learning dynamics for extensive-form correlated equilibrium in games with any number of players, closing a long-standing open question.
In the second part of the talk, I will move away from uncoupled learning dynamics to focus on settings in which the agents can explicitly correlate their strategies. I will give the first positive and parameterized complexity results for the problems of learning team-correlated equilibria and computing social-welfare-maximizing correlated equilibria in games with any number of players, as well as the theoretical and practical state-of-the-art algorithms for both problems.
Finally, in the third part of the talk I will relax the assumption of perfect rationality of the agents, and study the computation of classic subsets of Nash equilibria, called "trembling-hand refinements'', which are robust to mistakes of the players. I will establish positive complexity results in two-player games, and give state-of-the-art algorithms that, for the first time, enable the computation of exact trembling-hand refinements at scale.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.