%0 Journal Article
%T Approximate Core Allocation for Large Cooperative Security Games
%A Saman Zonouz
%A Parisa Haghani
%J ISRN Communications and Networking
%D 2012
%R 10.5402/2012/913294
%X 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
%U http://www.hindawi.com/journals/isrn.communications.networking/2012/913294/