Security Games: Solution Concepts and Algorithms

dc.contributor.advisor

Conitzer, Vincent

dc.contributor.author

Korzhyk, Dmytro

dc.date.accessioned

2013-11-14T19:13:43Z

dc.date.available

2013-11-14T19:13:43Z

dc.date.issued

2013

dc.department

Computer Science

dc.description.abstract

Algorithms for finding game-theoretic solutions are now used in several real-world security applications. Many of these applications are based on different but related game-theoretical models collectively known as security games. Much of the research in this area has focused on the two-player setting in which the first player (leader, defender) commits to a strategy, after which the second player (follower, attacker) observes that strategy and responds to it. This is commonly known as the Stackelberg, or leader-follower, model. If none of the players can observe the actions of the others then such a setting is called a simultaneous-move game. A common solution concept in simultaneous-move games is the Nash equilibrium (NE). In the present dissertation, we contribute to this line of research in two ways.

First, we consider new ways of modeling commitment. We propose the new model in which the leader can commit to a correlated strategy. We show that this model is equivalent to the Stackelberg model in two-player games and is different from the existing models in games with three or more players. We propose an algorithm for computing a solution to this model in polynomial time. We also consider a leader-follower setting in which the players are uncertain about whether the follower can observe. We describe an iterative algorithm for solving such games.

Second, we analyze the computational complexity of computing Stackelberg and NE strategies in security games. We describe algorithms to solve some variants of the security game model in polynomial time and prove NP-hardness of solving other variants of the model. We also extend the family of security games by allowing the attacker have multiple resources. We provide an algorithm for computing an NE of such games in polynomial time, and we show that computing a Stackelberg strategy is NP-hard.

dc.identifier.uri

https://hdl.handle.net/10161/8020

dc.subject

Computer science

dc.subject

Economics

dc.subject

Game theory

dc.subject

nash equilibrium

dc.subject

security games

dc.subject

stackelberg strategy

dc.title

Security Games: Solution Concepts and Algorithms

dc.type

Dissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Korzhyk_duke_0066D_12021.pdf
Size:
1.58 MB
Format:
Adobe Portable Document Format

Collections