Game Theory is a formal framework for analyzing competitive situations to determine the optimal course of action for a self-interested agent. Computational game theory uses computational methods for modeling and solving game-theoretic problems. In our basic research, we focus on creating novel faster algorithms for solving games in standard representations, as well as creating new game-theoretic models that allow representing and solving specific classes of games more efficiently. In the applied research, we model specific real-world problems in the game-theoretic framework; we propose domain-specific improvements of the existing algorithms for computing (an approximation of) optimal solutions; and we evaluate the computed strategies in computer simulations. The problem domain we focused on include network security, transportation networks, and military operations.

Basic Research

Computing optimal behaviors of agents in competitive situations is often computationally very expensive task. In many instances, it is NP hard in the size of the game representation and the game representation is typically exponentially large in the basic parameters of a game, such as the number of players or the number of consequent moves a player can perform. In order to solve practically large game instances, it is important to develop efficient algorithms and to use structural properties of the games to simplify the computation. This is the main focus of our group in the area of computational game theory.

Extensive-form games

Extensive-form game (EFGs) are a standard model for representing games that develop in time, in which each player executes a finite number of actions. The model sufficiently general to represent stochastic random events and imperfect information of the players at the time of their decisions. The well known artificial games that can be represented as extensive-form games include practically all card games (such as Poker and Bridge) and board games (such as Chess or Monopoly). Besides the artificial games, the extensive-form games can model also many competitive real-world problems, such models of search for, or pursuit of, an intelligent adversary.

In our research, we focus on two player zero-sum extensive-form games and we develop algorithms for exact and approximate computation of the optimal strategies of the players in large instances of these games. We use two main approaches to do that: (1) iterative construction of sequence-form linear program using best-response oracles, and (2) Monte-Carlo sampling guided by adversarial bandit algorithms.

The first method extends the framework of double-oracle methods, that has been very successful in solving normal form games, to be applicable in extensive-form games. The idea is to iteratively restrict the game by allowing the players to play only some of the sequences of available actions, solve this restricted game using a standard linear programming method, and exploit fast best-response algorithms to add additional sequences to the restricted game for the next iteration. This way, the solution can be found using only a small fraction of the strategy space. This approach is explained in [1] and we are working on an journal version of a paper presenting substantially improved version of this approach.

The second method is inspired by the success of Monte-Carlo tree search in large perfect-information games, such as GO. We are applying the same principles in imperfect information games. The method uses large number of random samples of play form the beginning of the game to its end. The first samples are purely random and the later samples are biased, using the statistics obtained from earlier samples, to explore more often the more promising parts of the search space. This bias allows the algorithm to quickly learn a good strategy and gradually improve it, if more computational time is available. We have experimentally shown feasibility of this approach in [2] and we are currently working on a formal proof of convergence of a variant of this algorithm to a Nash equilibrium.

Implementations of most of the algorithms we have developed are available as a unified framework in our mercurial repository:

hg clone http://jones.felk.cvut.cz/repo/gtlibrary

Security Games

Security games are games in which a defender uses limited resources to protect a set of targets against an attack from a malicious attacker. There are many variants of the security games, but a common assumption is that the defender uses a randomized strategy to minimize the predictability of its actions and that the attacker knows this strategy. The motivation behind this assumption is to create strategies that are efficient even in case that the attacker learns the defender's strategy from observation or obtains the strategy from an insider. The game-theoretic solution concept that fits to this situation is the Stackelberg equilibrium, computing of which is usually the goal while solving these games.

Our research contributes to the state of the art in security games in two ways. First, we focus on security games that are played on graphs, be it the road-network that restricts the movement of the defender's or attacker's resources, or a computer network that represent the environment of the game. Second, we extend the security games with the temporal dimension. We are interested in security games with defender's strategies and attacks that proceed in time. Many of the models we studied include both these components.

A representative of a graph-based security games representing the transportation networks is the adversarial transit game. In this game, one player ties to transit a transportation network without being detected on by the other player schedules patrols to intercept and detect the transit. In various use cases, the role of the attacker and the defender can be opposite in this game. This game has been described in most details in [3]. We have analyzed a similar game model, in which the attacker tries to cross the network and the defender allocates static checkpoints, in transportation network [4] as well as network security [5].

An example of our research on security games with explicit treatment of time are the patrolling games, in which the attack of the attacker takes some time and the defender seeks a movement policy that maximizes the probability that such an attack will be interrupted. One of our major contribution to this research is summarized in [6], in which we show how an existing solution technique can be adjusted to allow protection of moving targets. We are interested also in more general treatment of time and observations in security games. One of our current projects is focused on developing a general model of extensive-form security games, which allow creating strategies of the defender that prescribe the optimal reaction to the (possibly deceptive) observations available to the defender.

Deception Games

Deception is a commonly used technique in many domains. It can have the form of honeypots in computer networks, camouflage in military domains, or obfuscation in privacy preserving use of location-based services. We work on formalizing the notion of deception using game-theoretic concepts. We currently define deception games as strongly information-asymmetric two-player zero-sum games. One player knows the exact state of the world and is able to modify it to a limited extend. The second player observes the modified state of the world and makes a decision, which would have been trivial, knowing the state of the world before modification.

We have analyzed two solutions of this problem. First, we explored the robust optimization theory and identified the minimax regret as the solution of the problem [7]. Later, we added the assumption of the common knowledge of the prior probability distribution of original states of the world, which allows us to consider a more standard solution in the form of Nash equilibrium [8]. Currently, we aim to more carefully compare these two approaches and develop more efficient solution techniques for this class of games.

Applied Research

Applying game-theoretic approaches to real-world problems creates many challenges. The representation of the strategy spaces of the opponents has to be sufficiently complete in order represent all important actions they can play in the game. The state space of the game often has to be discretized in a way that will create instances solvable in reasonable time and still applicable in the original problem. The players in real world problems are often not completely rational, as it is assumed by classical game theory; hence, we have to analyze robustness of the solutions with more realistic assumptions. We have experience with game theoretic models for problems from the following domains.

Network Security

Network security is a domain full of interactions between the attackers and network administrators. Both these groups of players do their best to counter-act the actions of their adversaries; hence, many situations in network security can be modeled as games. In last years, we have used the network-based security games to created a game-theoretic model of deep packet inspection in computer networks [5]. We have used the model of extensive-form games to model the problem of identifying the plan that is currently being executed by an attacker in the network [2]. We have formulated the problem of adding honeypots to computer network as a deception game and we have analyzed the optimal strategies of the defender, who adds the honeypots, as well as the attacker, who is selecting a target to attack. Currently, we are further improving the models for the last two problems.

Transportation Networks

The domains of transportation networks also include many competitive situations, many of which can be modeled using graph-based security games. We have used the model of transit game for planning the paths of the cargo ships that minimize the probability of encounter with pirates in the gulf of eden [3]. In the same problem domain, we used the model of patrolling game to compute the optimal strategies for a navy ships that can prevent or interrupt a pirate attack. Furthermore, we collaborated with University of South California on application of graph-based security games for solving the problem of ticket inspection in public transport [9]. Currently, we are still working on all the above mentioned problems.

Military operations

Military operations are the most obvious domain that include parties with conflicting interests. In this domain, we currently focus mainly on applications of unmanned vehicles in tactical operations. These operations include several canonical problems that can be modeled using game theory. One of them is the problem of pursuit of intelligent targets in partially observable environment. We discretize the environment a graph and model the problem as an imperfect-information extensive-form game. In order to create fast anytime algorithms, we combine the Monte-Carlo tree search in information-set tree representation of the game [10] with strong forward pruning based on domain-specific knowledge we developed earlier [11]. Currently, we are working on application of the developed algorithms on hardware aircrafts. Another problem that commonly appear in applications of unmanned vehicles in military domains is patrolling. We have applied our solution for the patrolling games with moving targets for the problem of patrolling several convoys in a dangerous environment usingonly single UAV. We have evaluated all the approaches from this paragraph in multi-agent simulation [12] with promising results.

People

Viliam Lisy (contact person), Branislav Bosansky, Ondrej Vanek, Radek Pibil, Jiri Cermak

Publications

[1] Branislav Bosansky and Christopher Kiekintveld and Viliam Lisy and Michal Pechoucek: Iterative Algorithm for Solving Two-player Zero-sum Extensive-form Games with Imperfect Information. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI) 2012.
[2] Viliam Lisy and Radek Pibil and Jan Stiborek and Branislav Bosansky and Michal Pechoucek: Game-theoretic Approach to Adversarial Plan Recognition. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI), 2012, vol. 242, p. 546-551.
[3] Ondrej Vanek, Branislav Bosansky, Michal Jakob, Viliam Lisy and Michal Pechoucek: Extending Security Games to Defenders with Constrained Mobility. In Proceedings of AAAI Spring Symposium GTSSH. 2012. 
[4] Manish Jain and Dmytro Korzhyk and Ondrej Vanek and Vincent Conitzer and Milind Tambe and Michal Pechoucek: Double Oracle Algorithm for Zero-Sum Security Games on Graph. The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2011.
[5] Ondrej Vanek, Zhengyu Yin, Manish Jain, Branislav Bosansky, Milind Tambe and Michal Pechoucek: Game-theoretic Resource Allocation for Malicious Packet Detection in Computer Networks. The Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2012. 
[6] Branislav Bosansky, Viliam Lisy, Michal Jakob and Michal Pechoucek: Computing Time-Dependent Policies for Patrolling Games with Mobile Targets. The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2011. 
[7] Viliam Lisy and Roie Zivan and Katia Sycara and Michal Pechoucek: Deception in Networks of Mobile Sensing Agents. The Ninth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2010, p. 1031--1038. 
[8] Radek Pibil, Viliam Lisy, Christopher Kiekintveld, Branislav Bosansky and Michal Pechoucek: Game Theoretic Model of Strategic Honeypot Selection in Computer Networks. The Third Conference on Decision and Game Theory for Security (GameSec) (to appear). 2012.
[9] Michal Jakob, Zbynek Moler, Antonin Komenda, Zhengyu Yin, Albert Xin Jiang, Matthew P. Johnson, Michal Pechoucek and Milind Tambe: AgentPolis: Towards a Platform for Fully Agent-based Modeling of Multi-Modal Transportation (Demonstration). The Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2012.
[10] Viliam Lisy and Branislav Bosansky and Michal Pechoucek: Anytime Algorithms for Multi-agent Visibility-based Pursuit-evasion Games (Extended Abstract). The Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2012. 
[11] Viliam Lisy and Branislav Bosansky and Michal Jakob and Michal Pechoucek: Adversarial Search with Procedural Knowledge Heuristic. In The Eighth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009). 2009, p. 899--906. 
[12] Peter Novak, Antonin Komenda, Viliam Lisy, Branislav Bosansky, Michal Cap, and Michal Pechoucek: Tactical operations of multi-robot teams in urban warfare (Demonstration). The Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2012