Author name cluster

Dmytro Korzhyk

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

IJCAI Conference 2016 Conference Paper

Catcher-Evader Games

Yuqian Li
Vincent Conitzer
Dmytro Korzhyk

Algorithms for computing game-theoretic solutions have recently been applied to a number of security domains. However, many of the techniques developed for compact representations of security games do not extend to Bayesian security games, which allow us to model uncertainty about the attacker's type. In this paper, we introduce a general framework of catcher-evader games that can capture Bayesian security games as well as other game families of interest. We show that computing Stackelberg strategies is NP-hard, but give an algorithm for computing a Nash equilibrium that performs well in experiments. We also prove that the Nash equilibria of these games satisfy the interchangeability property, so that equilibrium selection is not an issue.

PDF Details

AAAI Conference 2014 Conference Paper

Beat the Cheater: Computing Game-Theoretic Strategies for When to Kick a Gambler out of a Casino

Troels Sørensen
Melissa Dalis
Joshua Letchford
Dmytro Korzhyk
Vincent Conitzer

Gambles in casinos are usually set up so that the casino makes a profit in expectation—as long as gamblers play honestly. However, some gamblers are able to cheat, reducing the casino’s profit. How should the casino address this? A common strategy is to selectively kick gamblers out, possibly even without being sure that they were cheating. In this paper, we address the following question: Based solely on a gambler’s track record, when is it optimal for the casino to kick the gambler out? Because cheaters will adapt to the casino’s policy, this is a game-theoretic question. Specifically, we model the problem as a Bayesian game in which the casino is a Stackelberg leader that can commit to a (possibly randomized) policy for when to kick gamblers out, and we provide efficient algorithms for computing the optimal policy. Besides being potentially useful to casinos, we imagine that similar techniques could be useful for addressing related problems—for example, illegal trades in financial markets.

PDF Details

JAAMAS Journal 2013 Journal Article

On the value of commitment

Joshua Letchford
Dmytro Korzhyk
Vincent Conitzer

Abstract In game theory, it is well known that being able to commit to a strategy before other players move can be beneficial. In this paper, we analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is similar to concepts such as the value of mediation and the price of anarchy. Specifically, we introduce and study the value of pure commitment (the benefit of committing to a pure strategy), the value of mixed commitment (the benefit of committing to a mixed strategy), and the mixed versus pure commitment ratio (how much can be gained by committing to a mixed strategy rather than a pure one). In addition to theoretical results about how large these values are in the extreme case in various classes of games, we also give average-case results based on randomly drawn normal-form games.

Details DOI

AAMAS Conference 2011 Conference Paper

A Double Oracle Algorithm for Zero-Sum Security Games on Graphs

Manish Jain
Dmytro Korzhyk
Ond
#X159; ej Van
#X11b; k
Vincent Conitzer
Michal P
#X11b; chou

In response to the Mumbai attacks of 2008, the Mumbai police have started to schedule a limited number of inspection checkpoints on the road network throughout the city. Algorithms for similar security-related scheduling problems have been proposed in recent literature, but security scheduling in networked domains when targets have varying importance remains an open problem at large. In this paper, we cast the network security problem as an attackerdefender zero-sum game. The strategy spaces for both players are exponentially large, so this requires the development of novel, scalable techniques. We first show that existing algorithms for approximate solutions can be arbitrarily bad in general settings. We present RUGGED (Randomization in Urban Graphs by Generating strategies for Enemy and Defender), the first scalable optimal solution technique for such network security games. Our technique is based on a double oracle approach and thus does not require the enumeration of the entire strategy space for either of the players. It scales up to realistic problem sizes, as is shown by our evaluation of maps of southern Mumbai obtained from GIS data.

PDF

AAAI Conference 2011 Conference Paper

Commitment to Correlated Strategies

Vincent Conitzer
Dmytro Korzhyk

The standard approach to computing an optimal mixed strategy to commit to is based on solving a set of linear programs, one for each of the follower’s pure strategies. We show that these linear programs can be naturally merged into a single linear program; that this linear program can be interpreted as a formulation for the optimal correlated strategy to commit to, giving an easy proof of a result by von Stengel and Zamir that the leader’s utility is at least the utility she gets in any correlated equilibrium of the simultaneous-move game; and that this linear program can be extended to compute optimal correlated strategies to commit to in games of three or more players. (Unlike in two-player games, in games of three or more players, the notions of optimal mixed and correlated strategies to commit to are truly distinct.) We give examples, and provide experimental results that indicate that for 50 × 50 games, this approach is usually signiﬁcantly faster than the multiple-LPs approach.

PDF Details

IJCAI Conference 2011 Conference Paper

Security Games with Multiple Attacker Resources

Dmytro Korzhyk
Vincent Conitzer
Ronald Parr

Algorithms for finding game-theoretic solutions are now used in several real-world security applications. This work has generally assumed a Stackelberg model where the defender commits to a mixed strategy first. In general two-player normal-form games, Stackelberg strategies are easier to compute than Nash equilibria, though it has recently been shown that in many security games, Stackelberg strategies are also Nash strategies for the defender. However, the work on security games so far assumes that the attacker attacks only a single target. In this paper, we generalize to the case where the attacker attacks multiple targets simultaneously. Here, Stackelberg and Nash strategies for the defender can be truly different. We provide a polynomial-time algorithm for finding a Nash equilibrium. The algorithm gradually increases the number of defender resources and maintains an equilibrium throughout this process. Moreover, we prove that Nash equilibria in security games with multiple attackers satisfy the interchange property, which resolves the problem of equilibrium selection in such games. On the other hand, we show that Stackelberg strategies are actually NP-hard to compute in this context. Finally, we provide experimental results.

PDF Details DOI

AAMAS Conference 2011 Conference Paper

Solving Stackelberg Games with Uncertain Observability

Dmytro Korzhyk
Vincent Conitzer
Ronald Parr

Recent applications of game theory in security domains use algorithms to solve a Stackelberg model, in which one player (the leader) first commits to a mixed strategy and then the other player (the follower) observes that strategy and best-responds to it. However, in real-world applications, it is hard to determine whether the follower is actually able to observe the leader's mixed strategy before acting. In this paper, we model the uncertainty about whether the follower is able to observe the leader's strategy as part of the game (as proposed in the extended version of Yin et al. [17]). We describe an iterative algorithm for solving these games. This algorithm alternates between calling a Nash equilibrium solver and a Stackelberg solver as subroutines. We prove that the algorithm finds a solution in a finite number of steps and show empirically that it runs fast on games of reasonable size. We also discuss other properties of this methodology based on the experiments.

PDF

AAAI Conference 2010 Conference Paper

Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games

Dmytro Korzhyk
Vincent Conitzer
Ronald Parr

Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.

PDF Details

AAMAS Conference 2010 Conference Paper

Stackelberg vs. Nash in Security Games: Interchangeability, Equivalence, and Uniqueness

Zhengyu Yin
Dmytro Korzhyk
Christopher Kiekintveld
Vincent Conitzer
Milind Tambe

There has been significant recent interest in game theoretic approaches to security, with much of the recent research focused onutilizing the leader-follower Stackelberg game model; for example, these games are at the heart of major applications such asthe ARMOR program deployed for security at the LAX airportsince 2007 and the IRIS program in use by the US Federal AirMarshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit toa randomized strategy; while their adversaries (followers) choosetheir best response after surveillance of this randomized strategy. Yet, in many situations, the followers may act without observation of the leader's strategy, essentially converting the game intoa simultaneous-move game model. Previous work fails to addresshow a leader should compute her strategy given this fundamentaluncertainty about the type of game faced. Focusing on the complex games that are directly inspired by realworld security applications, the paper provides four contributionsin the context of a general class of security games. First, exploiting the structure of these security games, the paper shows that theNash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, resolving theleader's dilemma, it shows that under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibriumstrategy; and furthermore, the solution is unique in a class of realworld security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, manyof these properties no longer hold. Fourth, our experimental resultsemphasize positive properties of games that do not fit our restrictions. Our contributions have major implications for the real-worldapplications.

PDF