skip to main content
10.5555/1838206.1838428acmotherconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

How to protect a city: strategic security placement in graph-based domains

Published: 10 May 2010 Publication History

Abstract

We apply game-theoretic techniques to urban security deployment and propose new algorithms to efficiently solve real-world domains that are intractable with existing algorithms.

References

[1]
Battle for Mumbai ends, death toll rises to 195. Times of India, 29 November 2008.
[2]
S. A. Ali. Rs 18L seized in nakabandi at Vile Parle. Times of India, 4 August 2009.
[3]
N. Basilico, N. Gatti, and F. Amigoni. Leader-follower strategies for robotic patrolling in environments with arbitrary topologies. In AAMAS-09, 2009.
[4]
V. Conitzer and T. Sandholm. Computing the optimal strategy to commit to. In ACM EC-06, pages 82--90, 2006.
[5]
K. J. Cormican, D. P. Morton, and R. K. Wood. Stochastic network interdiction. Oper. Res., 46(2):184--197, 1998.
[6]
N. Gatti. Game theoretical insights in strategic patrolling: Model and algorithm in normal-form. In ECAI-08, pages 403--407, 2008.
[7]
E. Halvorson, V. Conitzer, and R. Parr. Multi-step Multi-senor Hider-Seeker Games. In IJCAI, 2009.
[8]
E. Israeli and R. K. Wood. Shortest-path network interdiction. Networks, 40(2):97--111, 2002.
[9]
C. Kiekintveld, M. Jain, J. Tsai, J. Pita, M. Tambe, and F. Ordóñez. Computing Optimal Randomized Resource Allocations for Massive Security Games. In AAMAS-09, 2009.
[10]
M. Mavronicolas, V. Papadopoulou, A. Philippou, and P. Spirakis. A network game with attackers and a defender. Algorithmica, 51(3):315--341, 2008.
[11]
P. Paruchuri, J. P. Pearce, J. Marecki, M. Tambe, F. Ordóñez, and S. Kraus. Playing games with security: An efficient exact algorithm for Bayesian Stackelberg games. In AAMAS-08, pages 895--902, 2008.
[12]
A. Washburn and K. Wood. Two-person zero-sum games for network interdiction. Operations Research, 43(2):243--251, 1995.

Index Terms

  1. How to protect a city: strategic security placement in graph-based domains

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1
    May 2010
    1578 pages
    ISBN:9780982657119

    Sponsors

    • IFAAMAS

    In-Cooperation

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 10 May 2010

    Check for updates

    Author Tags

    1. algorithms
    2. game theory
    3. patrolling
    4. randomization
    5. risk analysis
    6. security
    7. stackelberg games
    8. uncertainty

    Qualifiers

    • Research-article

    Conference

    AAMAS '10
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 83
      Total Downloads
    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 01 Mar 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media