Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games

Jiri Cermak, Branislav Bosansky, Karel Durkota, Viliam Lisy, Christopher Kiekintveld

In AAAI Conference on Artificial Intelligence (AAAI). 2016.

This is the author's version of the work.

Download

Abstract

Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive- Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.