Eventi del

20 2021 16:00 - 17:15
Stanza 3-E4-SR03 / Zoom

Speeding up equilibrium computation in sequential games: from predictive convergence to Nash equilibrium, to optimal team coordination

Gabriele Farina (Carnegie Mellon University)

Abstract: In this talk, we will focus on recent advances in equilibrium finding for sequential (that is, extensive-form) imperfect-information games such as poker or bridge. No prior knowledge of extensive-form games is required. We will show how to decompose the problem of computing strong strategies in sequential games into local optimization problems at each decision point in the game. By designing novel predictive online optimization algorithms for those local decision points, we will construct the fastest known predictive algorithms for converging to Nash equilibria in large two-player zero-sum games. Then, we will illustrate how a similar decomposition framework enables us to construct the first scalable (regret-minimization) method for computing optimal extensive-form correlated equilibria. Finally, we will discuss how the theory of correlated equilibria can help compute optimal strategies for teams of two players coordinating against a third opponent—for example, in the card-playing phase of bridge or when two players secretly collude against a third at a poker table. We will focus both on computational aspects, giving some of the fastest algorithms known for the three solution concepts mentioned (Nash equilibrium, extensive-form correlated equilibrium, and coordinated team equilibrium), as well as new, positive, complexity results.

 

Per maggiori informazioni o per ricevere il link Zoom scrivere a elisur.magrini@unibocconi.it