Skip to main content
Duke University Libraries
DukeSpace Scholarship by Duke Authors
  • Login
  • Ask
  • Menu
  • Login
  • Ask a Librarian
  • Search & Find
  • Using the Library
  • Research Support
  • Course Support
  • Libraries
  • About
View Item 
  •   DukeSpace
  • Theses and Dissertations
  • Duke Dissertations
  • View Item
  •   DukeSpace
  • Theses and Dissertations
  • Duke Dissertations
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Computational Aspects of Stackelberg Games

Thumbnail
View / Download
1.3 Mb
Date
2013
Author
Letchford, Joshua
Advisor
Conitzer, Vincent
Repository Usage Stats
371
views
794
downloads
Abstract

Game theory involves the study of how self-interested agents interact in various settings. Perhaps the best-known game theoretic solution concept is that of Nash equilibrium. However, Nash equilibrium makes a number of assumptions, such as rationality of all of the players and the ability of the players to choose the same equilibrium when more than one exists. Because of these assumptions, it is unclear if simply solving for Nash equilibrium is always the correct thing to do. In some settings, one player can instead credibly commit to a strategy, and communicate this to the other player, before the other player can make a decision. This has become known as a Stackelberg game. Computing optimal strategies to commit to in normal-form or Bayesian Stackelberg games is a topic that has recently been gaining attention, in part due to the application of such algorithms in various security and law enforcement scenarios. My work on Stackelberg games falls into three main areas.

First, I focus on general games, where we give efficient algorithms and hardness results for Bayesian, extensive-form and stochastic games. In each of these settings we study the relationship between different modeling assumptions and the tractability of finding an optimal strategy to commit to. For Bayesian games our results are mainly negative; we show that not only are the problems here NP-hard, but in many cases they are also inapproximable. Our results for extensive-form games are more mixed; we are able to give polynomial time algorithms for four cases. However, we also show that if we relax the assumptions made in these four cases, then the problem usually becomes NP-hard. Finally, our results for stochastic games are again somewhat negative, as we show that the problem is NP-hard is most reasonable cases. However, here we are also able to give an approximation algorithm to compute optimal commitment strategies in a setting where correlation is allowed.

I next focus on Stackelberg security games. Stackelberg security games usually involve the scheduling of scarce defense resources to cover some subset of potential targets. We first study methods for going from marginal solutions (which ignore overlapping coverage between different schedules) to valid mixed commitment strategies in graphical settings. Here we are able to characterize two new classes of games where mixed strategies corresponding to the marginal probabilities are guaranteed to exist, and give algorithms for finding them. Next, we offer a simple model of interdependencies between nodes in a network based on probabilistic failure cascades, extending the well-known independent cascade model of the spread of infectious diseases or ideas. We give an algorithm for this problem and experimentally show that this algorithm scales to realistic security settings and outperforms the state of-the-art alternatives. Finally, we create an approach for optimal interdiction of attack plans. We show how to model an attack plan interdiction problem as a large-scale integer linear program similar to an integer programming approach for solving partial satisfaction planning problems. We also give several oracle-based approaches for solving this and then evaluate them experimentally.

Third, I analyze how much benefit a player can derive from commitment in various types of games, in a quantitative sense that is similar to known concepts such as the value of mediation and the price of anarchy. To do this 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 vs. pure commitment ratio (how much can be gained by committing to a mixed strategy rather than a pure one).

Type
Dissertation
Department
Computer Science
Subject
Computer science
Game Theory
Stackelberg games
Permalink
https://hdl.handle.net/10161/7218
Citation
Letchford, Joshua (2013). Computational Aspects of Stackelberg Games. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/7218.
Collections
  • Duke Dissertations
More Info
Show full item record
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License.

Rights for Collection: Duke Dissertations


Works are deposited here by their authors, and represent their research and opinions, not that of Duke University. Some materials and descriptions may include offensive content. More info

Make Your Work Available Here

How to Deposit

Browse

All of DukeSpaceCommunities & CollectionsAuthorsTitlesTypesBy Issue DateDepartmentsAffiliations of Duke Author(s)SubjectsBy Submit DateThis CollectionAuthorsTitlesTypesBy Issue DateDepartmentsAffiliations of Duke Author(s)SubjectsBy Submit Date

My Account

LoginRegister

Statistics

View Usage Statistics
Duke University Libraries

Contact Us

411 Chapel Drive
Durham, NC 27708
(919) 660-5870
Perkins Library Service Desk

Digital Repositories at Duke

  • Report a problem with the repositories
  • About digital repositories at Duke
  • Accessibility Policy
  • Deaccession and DMCA Takedown Policy

TwitterFacebookYouTubeFlickrInstagramBlogs

Sign Up for Our Newsletter
  • Re-use & Attribution / Privacy
  • Harmful Language Statement
  • Support the Libraries
Duke University