Effective solutions for real-world Stackelberg games: when agents must deal with human uncertainties

ABSTRACT

How do we build multiagent algorithms for agent interactions with human adversaries? Stackelberg games are natural models for many important applications that involve human interaction, such as oligopolistic markets and security domains. In Stackelberg games, one player, the leader, commits to a strategy and the follower makes their decision with knowledge of the leader's commitment. Existing algorithms for Stackelberg games efficiently find optimal solutions (leader strategy), but they critically assume that the follower plays optimally. Unfortunately, in real-world applications, agents face human followers (adversaries) who --- because of their bounded rationality and limited observation of the leader strategy --- may deviate from their expected optimal response. Not taking into account these likely deviations when dealing with human adversaries can cause an unacceptable degradation in the leader's reward, particularly in security applications where these algorithms have seen real-world deployment. To address this crucial problem, this paper introduces three new mixed-integer linear programs (MILPs) for Stackelberg games to consider human adversaries, incorporating: (i) novel anchoring theories on human perception of probability distributions and (ii) robustness approaches for MILPs to address human imprecision. Since these new approaches consider human adversaries, traditional proofs of correctness or optimality are insufficient; instead, it is necessary to rely on empirical validation. To that end, this paper considers two settings based on real deployed security systems, and compares 6 different approaches (three new with three previous approaches), in 4 different observability conditions, involving 98 human subjects playing 1360 games in total. The final conclusion was that a model which incorporates both the ideas of robustness and anchoring achieves statistically significant better rewards and also maintains equivalent or faster solution speeds compared to existing approaches.

REFERENCES

• 1: Fox, C. personal communication.
• 2: Michele Aghassi , Dimitris Bertsimas, Robust game theory, Mathematical Programming: Series A and B, v.107 n.1, p.231-273, June 2006 [doi>10.1007/s10107-005-0686-0]
• 3: Noa Agmon , Vladimir Sadov , Gal A. Kaminka , Sarit Kraus, The impact of adversarial knowledge on adversarial planning in perimeter patrol, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 4: Gerald Brown , Matthew Carlyle , Javier Salmerón , Kevin Wood, Defending Critical Infrastructure, Interfaces, v.36 n.6, p.530-544, November 2006 [doi>10.1287/inte.1060.0252]
• 5: J. Cardinal, M. Labbé, S. Langerman, and B. Palop. Pricing of geometric transportation networks. In 17th Canadian Conference on Computational Geometry, 2005.
• 6: Vincent Conitzer , Tuomas Sandholm, Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, p.82-90, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134717]
• 7: M. Friedman. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 32 No. 100:675--701, 1937.
• 8: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 9: J. C. Harsanyi and R. Selten. A generalized Nash solution for two-person bargaining games with incomplete information. Management Science, 18(5):80--106, 1972.
• 10: Christopher Kiekintveld , Manish Jain , Jason Tsai , James Pita , Fernando Ordóñez , Milind Tambe, Computing optimal randomized resource allocations for massive security games, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
• 11: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 12: A. Nilim and L. E. Ghaoui. Robustness in markov decision problems with uncertain transition matrices. In NIPS, 2004.
• 13: F. Ordóñez and N. E. Stier-Moses. Robust wardrop equilibrium. In NET-COOP, 2007.
• 14: Praveen Paruchuri , Jonathan P. Pearce , Janusz Marecki , Milind Tambe , Fernando Ordonez , Sarit Kraus, Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 15: Praveen Paruchuri , Milind Tambe , Fernando Ordóñez , Sarit Kraus, Security in multiagent systems by policy randomization, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160681]
• 16: James Pita , Manish Jain , Janusz Marecki , Fernando Ordóñez , Christopher Portway , Milind Tambe , Craig Western , Praveen Paruchuri , Sarit Kraus, Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track, May 12-16, 2008, Estoril, Portugal
• 17: A. Rubinstein. Modeling Bounded Rationality. MIT Press, 1998.
• 18: K. E. See, C. R. Fox, and Y. S. Rottenstreich. Between ignorance and truth: Partition dependence and learning in judgment under uncertainty. Journal of Experimental Psychology: Learning, Memory, and Cognition, 32:1385--1402, 2006.
• 19: H. Simon. Rational choice and the structure of the environment. Psychological Review, 63:129--138, 1956.
• 20: A. Tversky and D. J. Koehler. Support thoery: A nonextensional representation of subjective probability. Psychological Review, 101:547--567, 1994.
• 21: B. von Stengel and S. Zamir. Leadership with commitment to mixed strategies. In CDAM Research Report LSE-CDAM-2004-01, London School of Economics, 2004.
• 22: K. K. Yuen. The two-sample trimmed t for unequal population variances. Biometrika, 61:165--170, 1974.

INDEX TERMS

General Terms:
Algorithms, Experimentation, Human Factors, Security

Keywords:
Bayesian and Stackelberg games, game theory, security of agent systems