Coalition games have been recently used for modeling a variety of security problems. From securing the wireless transmissions in decentralized networks to employing effective intrusion detection systems in large organizations, cooperation among interested parties has shown to bring significant benefits. Motivating parties to abide to a solution is, however, a key problem in bridging the gap between theoretical models and practical solutions. Benefits should be distributed among players (wireless nodes in a network, different divisions of an organization in security risk management, or organizations cooperating to fight spam), such that no group of players is motivated to break off and form a new coalition. This problem, referred to as core allocation, grows computationally very expensive with a large number of agents. In this paper, we present a novel approximate core allocation algorithm, called the bounding boxed core (BBC), for large cooperative security games in characteristic form that rely on superadditivity. The proposed algorithm is an anytime (an algorithm is called anytime if it can be interrupted at any time point during execution to return an answer whose value, at least in certain classes of stochastic processes, improves in expectation as a function of the computation time) algorithm based on iterative state space search for better solutions. Experimental results on a 25-player game, with roughly 34 million coalitions, show that BBC shrinks the 25-dimensional bounding-box to times its initial hypervolume. 1. Introduction In the recent years, there has been a growing interest for modeling defenders in different security problems with coalition games. This is mainly due to results which confirm that many security goals can be better reached through cooperation among the interested parties. Millions of connected computers and networks of them have turned security to a problem characterized by interdependence [4]. In this interconnected world of computers, the security of a particular user is not independent of others and it heavily depends on the efforts of other users. As a prominent example in Internet security, in combating spam and unsolicited communications, the Organization for Economic Co-operation and Development recommends international cooperation and promotes cross-border enforcement cooperation on spam-related problems [18]. With regard to cyber attacks originated from any particular country, a recent study [13] shows that international cooperation in enforcement as measured by the indicator of joining the convention on
References
[1]
D. B. Gillies, “Solutions to general non-zero-sum games,” in Contributions to the Theory of Games 4, R. D. Luce and A. W. Tucker, Eds., Annals of Mathematics Studies, pp. 47–85, Princeton, 1959.
[2]
L. S. Shapley, “Cores of convex games,” International Journal of Game Theory, vol. 1, no. 1, pp. 11–26, 1971.
[3]
L. S. Shapley, “A value for n-person games,” in Contributions to the Theory of Games 2, H. W. Kuhn and A. W. Tucker, Eds., Annals of Mathematics Studies, pp. 307–317, Princeton, 1953.
[4]
H. Kunreuther and G. Heal, “Interdependent Security,” Journal of Risk and Uncertainty, vol. 26, no. 2-3, pp. 231–249, 2003.
[5]
H. Narasimhan, V. Varadarajan, and U. Rangan, “Towards a cooperative defense model against network security attacks,” in Proceeding of the 9th Workshop on the Economics of Information Security (WEIS '10).
[6]
J. V. Neumann and O. Morgenstern, Theory of Games and Economic Behaviour, Princeton, 1944.
[7]
S. H. Tijs and T. S. H. Driessen, “Extensions of solution concepts by means of multiplicative ε-tax games,” Mathematical Social Sciences, vol. 12, no. 1, pp. 9–20, 1986.
[8]
V. Conitzer and T. Sandholm, “Complexity of determining nonemptiness of the core,” in Proceedings of the 4th ACM Conference on Electronic Commerce, pp. 230–231, June 2003.
[9]
U. Faigle and W. Kern, “On some approximately balanced combinatorial cooperative games,” Methods and Models of Operations Research, vol. 38, no. 2, pp. 141–152, 1993.
[10]
H. Nagamochi, D. Z. Zeng, N. Kabutoya, and T. Ibaraki, “Complexity of the minimum base game on matroids,” Mathematics of Operations Research, vol. 22, no. 1, pp. 146–164, 1997.
[11]
D. Schmeidler, “The nucleolus of a characteristic function game,” SIAM Journal of Applied Mathematics, vol. 17, no. 1163, 1170 pages, 1969.
[12]
D. Frincke, D. Tobin, J. Mcconnell, J. Marconi, and D. and Polla, “A framework for cooperative intrusion detection,” in Proceedings of the 21st NIST-NCSC National Information Systems Security Conference, pp. 361–373, 1998.
[13]
Q. Hong Wang and S. Hyun Kim, “Cyber attacks: Cross-country interdependence and enforcement,” in Proceeding of the 8th Work shop on the Economics of Information Security (WEIS 2009).
[14]
X. Deng and C. Papadimitriou, “On the complexity of cooperative game solution concepts,” Mathematics of Operations Research, vol. 19, pp. 257–266, 1994.
[15]
M. Davis and M. Maschler, “Existence of stable payoff configurations for cooperative games,” in Essays in Mathematical Economics in Honor of Oskar Morgenstern, M. Shubik, Ed., pp. 39–52, Princeton, 1967.
[16]
W. Saad, Z. Han, T. Ba？ar, M. Debbah, and A. Hj？rungnes, “Distributed coalition formation games for secure wireless transmission,” Mobile Networks and Applications, vol. 16, no. 2, pp. 231–245, 2011.
[17]
H. A. Simon, “Theories of bounded rationality,” in Decision and Organization, C. Radner and R. Radner, Eds., pp. 161–176, 1972.
[18]
Report of the OECD task force on spam, “Antispam toolkit of recommended policies and measures,” Tech. Rep., Directorate for Science, Technology and Industry, Committee on Consumer Policy Committee for Information, Computer and Communications Policy, 2006.
[19]
F. Cuppens and A. Miège, “Alert correlation in a cooperative intrusion detection framework,” in Proceedings of the Symposium on Security and Privacy, pp. 202–215, IEEE Computer Society, Washington, DC, USA, May 2002.
[20]
M. Davis and M. Maschler, “The kernel of a cooperative game,” Naval Research Logistics, vol. 12, pp. 223–259, 1965.
[21]
D. Nojiri, J. Rowe, and K. Levitt, “Cooperative response strategies for large scale attack mitigation,” in Proceedings of the 3rd DARPA Information Survivability Conference and Exposition (DISCEX '03), pp. 293–302, 2003.
[22]
W. Saad, T. Alpcan, T. Ba？ar, and A. Hj？rungnes, “Coalitional game theory for security risk management,” in Proceedings of the 5th International Conference on Internet Monitoring and Protection (ICIMP '10), pp. 35–40, Washington, DC, USA, May 2010.
[23]
T. Moore, “Cooperative attack and defense in distributed networks,” Tech. Rep. UCAM-CL-TR-718, Computer Laboratory, University of Cambridge, 2008.
[24]
R. J. Aumann and M. Maschler, “The bargaining set for cooperative games,” in Advances in Game Theory, M. Dresher, L. S. Shapley, and A. W. Tucker, Eds., Annals of Mathematics Studies, pp. 443–476, Princeton, 1964.
[25]
N. Megiddo, “Computational complexity and the game theory approach to cost allocation for a tree,” Mathematics of Operations Research, vol. 3, pp. 189–196, 1978.
[26]
J. Grossklags, N. Christin, and J. Chuang, “Secure or insure? a game-theoretic analysis of information security games,” in Proceedings of the 17th International Conference on World Wide Web (WWW '08), pp. 209–218, New York, NY, USA, April 2008.
[27]
L. Shapley and M. Shubik, “Quasi-cores in a monetary economy with nonconvex preference,” Econometrica, vol. 34, pp. 805–827, 1966.
[28]
J. Edmonds, “Path, tree, and flowers,” Canadian Journal of Mathematics, vol. 17, pp. 449–469, 1965.
