A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games

Understand

A central task of artificial intelligence is the design of artificial agents that act towards specified goals in partially observed environments.

• Since such environments frequently include interaction over time with other agents with their own goals, reasoning about such interaction relies on sequential game-theoretic models such as extensive-form games or some of their succinct representations such as multi-agent influence diagrams.
• The current algorithms for calculating equilibria either work with inefficient representations, possibly doubly exponential inthe number of time steps, or place strong assumptions on the game structure.
• In this paper,we propose a sampling-based approach, which calculates extensive-form correlated equilibria with small representations without placing such strong assumptions.