Abstract
There has been recent interest in applying Stackelberg games to infrastructure security, in which a defender must protect targets from attack by an adaptive adversary. In real-world security settings the adversaries are humans and are thus boundedly rational. Most existing approaches for computing defender strategies against boundedly rational adversaries try to optimize against specific behavioral models of adversaries, and provide no quality guarantee when the estimated model is inaccurate. We propose a new solution concept, monotonic maximin, which provides guarantees against all adversary behavior models satisfying monotonicity, including all in the family of Regular Quantal Response functions. We propose a mixed-integer linear program formulation for computing monotonic maximin. We also consider top-monotonic maximin, a related solution concept that is more conservative, and propose a polynomial-time algorithm for top-monotonic maximin.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agmon, N., Kraus, S., Kaminka, G.A.: Multi-robot perimeter patrol in adversarial settings. In: ICRA (2008)
Basilico, N., Gatti, N., Amigoni, F.: Leader-follower strategies for robotic patrolling in environments with arbitrary topologies. In: AAMAS (2009)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust optimization. Princeton University Press (2009)
Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: EC: Proceedings of the ACM Conference on Electronic Commerce (2006)
Goeree, J.K., Holt, C.A., Palfrey, T.R.: Regular quantal response equilibrium. Experimental Economics 8(4), 347–367 (2005)
Haile, P.A., Hortaçsu, A., Kosenok, G.: On the empirical content of quantal response equilibrium. The American Economic Review, 180–200 (2008)
Harsanyi, J.: Games with incomplete information played by “Bayesian” players, i-iii. part i. the basic model. Management Science 14(3), 159–182 (1967)
Kiekintveld, C., Islam, T., Kreinovich, V.: Security games with interval uncertainty. In: AAMAS (2013)
Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ordóñez, F., Tambe, M.: Computing optimal randomized resource allocations for massive security games. In: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 689–696. International Foundation for Autonomous Agents and Multiagent Systems (2009)
Korzhyk, D., Conitzer, V., Parr, R.: Complexity of computing optimal stackelberg strategies in security resource allocation games. In: Proc. of The 24th AAAI Conference on Artificial Intelligence, pp. 805–810 (2010)
Luce, R.D.: Individual Choice Behavior: A Theoretical Analysis. Wiley (1959)
McFadden, D.: Conditional logit analysis of qualitative choice behavior. Frontiers of Econometrics, 105–142 (1974)
McKelvey, R.D., Palfrey, T.R.: Quantal Response Equilibria for Normal Form Games. Games and Economic Behavior 10(1), 6–38 (1995)
Pita, J., Jain, M., Ordóñez, F., Tambe, M., Kraus, S., Magori-Cohen, R.: Effective solutions for real-world stackelberg games: When agents must deal with human uncertainties. In: Proc. of The 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2009)
Pita, J., John, R., Maheswaran, R., Tambe, M., Kraus, S.: A robust approach to addressing human adversaries in security games. In: ECAI (2012)
Tambe, M.: Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press (2011)
Wald, A.: Statistical decision functions which minimize the maximum risk. The Annals of Mathematics 46(2), 265–280 (1945)
Yang, R., Kiekintveld, C., Ordonez, F., Tambe, M., John, R.: Improving Resource Allocation Strategy Against Human Adversaries in Security Games. In: IJCAI (2011)
Yang, R., Ordonez, F., Tambe, M.: Computing optimal strategy against quantal response in security games. In: AAMAS (2012)
Yin, Z., Jain, M., Tambe, M., Ordonez, F.: Risk-Averse Strategies for Security Games with Execution and Observational Uncertainty. In: Proc. of the 25th AAAI Conference on Artificial Intelligence (AAAI), pp. 758–763 (2011)
Yin, Z., Jiang, A.X., Johnson, M.P., Tambe, M., Kiekintveld, C., Leyton-Brown, K., Sandholm, T., Sullivan, J.: TRUSTS: Scheduling randomized patrols for fare inspection in transit systems. In: IAAI (2012)
Yin, Z., Tambe, M.: A unified method for handling discrete and continuous uncertainty in Bayesian Stackelberg games. In: AAMAS (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Jiang, A.X., Nguyen, T.H., Tambe, M., Procaccia, A.D. (2013). Monotonic Maximin: A Robust Stackelberg Solution against Boundedly Rational Followers. In: Das, S.K., Nita-Rotaru, C., Kantarcioglu, M. (eds) Decision and Game Theory for Security. GameSec 2013. Lecture Notes in Computer Science, vol 8252. Springer, Cham. https://doi.org/10.1007/978-3-319-02786-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-02786-9_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02785-2
Online ISBN: 978-3-319-02786-9
eBook Packages: Computer ScienceComputer Science (R0)