Branislav Bosansky

IS Journal 2016 Journal Article

Case Studies of Network Defense with Attack Graph Games

• Karel Durkota
• Viliam Lisy
• Christopher Kiekintveld
• Branislav Bosansky
• Michal Pechoucek

The increasing complexity of securing modern computer networks makes decision support systems an important tool for administrators. A challenge many existing tools fail to address is that attackers react strategically to new security measures, adapting their behaviors in response. Game theory provides a methodology for making decisions that takes into account these reactions, rather than assuming static attackers. The authors present an overview of how game theory can be used to inform one type of security decision: how to optimally place honeypots in a network. They demonstrate this approach on a realistic case study and present initial validation results based on a study comparing their approach with human decision makers.

AAAI Conference 2016 Conference Paper

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

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

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.

AAAI Conference 2015 Conference Paper

Combining Compact Representation and Incremental Generation in Large Games with Sequential Strategies

• Branislav Bosansky
• Albert Xin Jiang
• Milind Tambe
• Christopher Kiekintveld

Many search and security games played on a graph can be modeled as normal-form zero-sum games with strategies consisting of sequences of actions. The size of the strategy space provides a computational challenge when solving these games. This complexity is tackled either by using the compact representation of sequential strategies and linear programming, or by incremental strategy generation of iterative double-oracle methods. In this paper, we present novel hybrid of these two approaches: compact-strategy doubleoracle (CS-DO) algorithm that combines the advantages of the compact representation with incremental strategy generation. We experimentally compare CS-DO with the standard approaches and analyze the impact of the size of the support on the performance of the algorithms. Results show that CS-DO dramatically improves the convergence rate in games with non-trivial support.

Highlights Conference 2015 Conference Abstract

Commitments to Correlated Strategies in Finite Sequential Games

• Branislav Bosansky

AAAI Conference 2015 Conference Paper

Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games

• Branislav Bosansky
• Jiri Cermak

Stackelberg equilibrium is a solution concept prescribing for a player an optimal strategy to commit to, assuming the opponent knows this commitment and plays the best response. Although this solution concept is a cornerstone of many security applications, the existing works typically do not consider situations where the players can observe and react to the actions of the opponent during the course of the game. We extend the existing algorithmic work to extensive-form games and introduce novel algorithm for computing Stackelberg equilibria that exploits the compact sequence-form representation of strategies. Our algorithm reduces the size of the linear programs from exponential in the baseline approach to linear in the size of the game tree. Experimental evaluation on randomly generated games and a security-inspired search game demonstrates significant improvement in the scalability compared to the baseline approach.

NeurIPS Conference 2013 Conference Paper

Convergence of Monte Carlo Tree Search in Simultaneous Move Games

• Viliam Lisy
• Vojta Kovarik
• Marc Lanctot
• Branislav Bosansky

In this paper, we study Monte Carlo tree search (MCTS) in zero-sum extensive-form games with perfect information and simultaneous moves. We present a general template of MCTS algorithms for these games, which can be instantiated by various selection methods. We formally prove that if a selection method is $\epsilon$-Hannan consistent in a matrix game and satisfies additional requirements on exploration, then the MCTS algorithm eventually converges to an approximate Nash equilibrium (NE) of the extensive-form game. We empirically evaluate this claim using regret matching and Exp3 as the selection methods on randomly generated and worst case games. We confirm the formal result and show that additional MCTS variants also converge to approximate NE on the evaluated games.

AAMAS Conference 2013 Conference Paper

Solving Extensive-Form Games with Double-Oracle Methods

• Branislav Bosansky

We investigate iterative algorithms for computing exact Nash equilibria in two-player zero-sum extensive-form games. The algorithms use an algorithmic framework of double-oracle methods. The main idea is to restrict the game by allowing the players to play only some of the strategies, and then iteratively solve this restricted game and exploit fast best-response algorithms to add additional strategies to the restricted game for the next iteration. The experimental evaluation on different games shows that the doubleoracle methods often provide significant improvement in runningtime, and can find exact solution of much larger games compared to the existing approaches.

IJCAI Conference 2013 Conference Paper

Using Double-Oracle Method and Serialized Alpha-Beta Search for Pruning in Simultaneous Move Games

• Branislav Bosansky
• Viliam Lisy
• Jiri Cermák
• Roman Vítek
• Michal Pechoucek

We focus on solving two-player zero-sum extensive-form games with perfect information and simultaneous moves. In these games, both players fully observe the current state of the game where they simultaneously make a move determining the next state of the game. We solve these games by a novel algorithm that relies on two components: (1) it iteratively solves the games that correspond to a single simultaneous move using a double-oracle method, and (2) it prunes the states of the game using bounds on the sub-game values obtained by the classical Alpha-Beta search on a serialized variant of the game. We experimentally evaluate our algorithm on the Goofspiel card game, a pursuitevasion game, and randomly generated games. The results show that our novel algorithm typically provides significant running-time improvements and reduction in the number of evaluated nodes compared to the full search algorithm.