# Approximate Core Allocation for Large Cooperative Security Games

Authors: Saman Zonouz; Parisa Haghani
Journal: ISRN Communications and Networking
 (2012)

---

## Abstract

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 ascore 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 10−15 times its initial hypervolume.


---

## Body

## 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 cybercrimes, can deter cyber attacks by up to 24%. Cooperative attack and defense for a range of distributed network applications, with an emphasis on phishing, has been examined in [23] and the results highlight the need for cooperative information sharing.Building suitable models based on cooperation for a variety of security problems has been the subject of some recent studies. Coalition game theory has been used for security risk management [22] in divisions of an organization as well as secure wireless transmissions [16] in ad hoc wireless networks, and against network security attacks [5]. In detecting [12, 19] and mitigating [21] DDos attacks, cooperation has been affirmed. While many studies advocate the use of coalition games for modeling large scale security problems, the question of revenue allocation, as an important step in turning these game theoretical models to practical robust solutions, has not been studied and warrants greater attention.Cooperative game theory studies the problem of revenue allocation for a set ofn participants, called players, in a joint project where a value function v is defined for each subset of players, representing the revenue achieved by the players in that subset without assistance of other players. In the context of security, we call these games cooperative security games. In cooperative security games players are the defenders (e.g., organizations cooperating for intrusion detection) and revenue is the security benefit they achieve through cooperation. We will present a formal definition in the next Section. In general, each solution concept defines a set 𝒳 of allocation vectors. Obtaining 𝒳 is usually a nontrivial problem and has always been an important issue in the study of cooperative game theory. A particularly interesting theme to the study of such decision problems is that of the bounded rationality, which argues that decisions made by real-life agents may not spend an unbounded amount of resources to evaluate all the possibilities for optimal outcome [17]. Much effort has been made in the study of the bounded rationality in computational resource for solution concepts of cooperative games.The definition of a cooperative game involves an exponential number (in the number of players) of values, one for each subset of players. Moreover, the definitions of many solution concepts, for example, the core [1], would involve an exponential number of constraints. Therefore, it becomes infeasible to get the set of fair allocation vectors 𝒳 for a large cooperative game using traditional approaches, such as linear programming. Megiddo [25] observed that, for many games, the game value is calculated through succinctly defined structures and for such games, he suggested that finding a solution should be done by a good algorithm (following Edmonds [28]), that is, within time polynomial in the number of players. Deng and Papadimitriou [14] suggested computational complexities be taken into consideration as another measure of fairness for evaluating and comparing different solution concepts.In this paper, we present bounding-boxed core (BBC), an approximate revenue allocation algorithm for large cooperative security games that are intractable to be solved using traditional algorithms such as linear programming. Previous work in security revenue allocation investigate all coalitions and their corresponding values before computing the core. This is not feasible with large number of players, that is, organizations that attempt to protect security of their assets, because increasing number of players result in exponential growth of the coalition space. Our algorithm, to the best of our knowledge, is the first algorithm to provide an approximate solution to this problem. In addition, we utilize the special characteristics of the core, namely, its convexity, to analyze the approximation error and provide bounds on the worst case errors.This paper is organized as follows. In Section2, we describe the security game model and the revenue allocation problem. In Section 3 we present an overview of related background literature. The BBC algorithm is briefly explained in Section 4. Section 5 is devoted to the bounding box shrinking algorithm. Approximate core allocation approach is discussed in Section 6. Finally, experimental results for a case study cooperative game with 25 players is presented in Section 7 and Section 8 concludes the paper.


## 2. Security Model and Basic Definitions

We start by describing a simplified security problem and subsequently formally define a cooperative security game. Assume a finite set of organizations denoted by𝒩={1,2,…,n}. Each organization has its own security resources and valuable assets which it protects against security attacks. Any subset S⊆𝒩 is called a coalition. The security profit function v:𝒫(𝒩)→ℝ is a function with v(ϕ)=0, where 𝒫(𝒩) denotes the power set of 𝒩. For each coalition S⊆𝒩, v(S) is the value of S that is interpreted as the security profit achieved by the collective action of organizations in S without any assistance of organizations in 𝒩-S. A security cooperative game is given by specifying the security profit function, that is, a value for every coalition. The security profit can be defined based on different measures, such as security resources of a coalition, the type and probability of successful attacks against these security measures, and the expected cost of such attacks. Instead of a security profit function, a security cost function can be used. In this paper we only deal with profit games, however, symmetric statement holds for cost games. Security profit functions are assumed to be superadditive, that is, the value of a union of disjoint coalitions is no less than the sum of the coalitions’ separate values:
(1)v(S)+v(T)≤v(S∪T)∀S,T⊆𝒩∋S∩T=ϕ.Given a pair(𝒩,v), the focus is how to fairly distribute the collective income. We denote the income distributed to individual organizations by a payoff vector x={x1,x2,…,xn} satisfying ∑i∈𝒩‍xi=v(𝒩), called an allocation. An allocation vector x is called an imputation of the game (𝒩,v) if it also satisfies the individual rationality condition:
(2)v({i})≤xi∀i∈𝒩.As an illustrative example, consider a set of online shopping sites which are willing to cooperate against intrusion detection attacks by sharing worm and virus signatures identified by their antivirus systems. The valuable assets in this scenario consists of a database of credit-card information. We consider a dollar value as the security profit associated with an attack. Let us consider two of these shopping sites{1,2}. Let the expected security profit of site 1 be v({1})=c1-300, while this value is v({2})=c2-50 for site 2. If they cooperate by sharing their signatures, the expected security profit of their coalition would be v({1,2})=c1+c2-400. The allocation problem involves assigning x1 and x2 in a fair manner, which also motivates the formation of a coalition.Additional requirements for fairness, stability, and rationality lead to different sets of allocations, which are generally referred to as solution concepts. Here, we shall discuss the most important one that is the core.Sum of the coalitions' separate values.The concept of the core was first introduced by Gillies [1] based on the concept of subgroup rationality.Definition 1.
The core of a game(𝒩,v) is defined by
(3)C(v)={x∈ℝ|𝒩|:∑i∈𝒩‍xi=v(𝒩);∑i∈S‍xi≥v(S)∀S⊆𝒩}.The constraints imposed onC(v) ensure that no coalition would have an incentive to split from the grand coalition 𝒩 and do better on its own. The core is a subset of the hyperplanes defined by the equation ∑i∈S‍xi=v(S) [16], and since the inequalities xi≥v({i}) are included in (3), the core is bounded. Thus, C(v) is a compact convex polyhedron, and possibly empty, of dimension at most n-1. The definition of the core, involves an exponential number of constraints, therefore, exact computation of the core is infeasible in large scale games. In this paper, we present an approximate algorithm for core allocation.


## 3. Related Work

In the security community, there has been considerable effort in introducing models based on cooperation for defenders of a security attack, see for example [12, 19, 21, 23]. Here, we review the ones which explicitly use coalition games as their models. The authors in [22] define a coalition game for modeling risk management. In their model, divisions of an organization are the players of the game. They use an influence graph to specify the positive and negative effects that each division of the organization can have on other divisions. The security benefit of each coalition is then defined as a function involving the influence graph, the security resources of each division, and threats against vulnerabilities. They further enrich their model by introducing a friction graph which denotes the costs associated with cooperation. They analyze the formation of coalitions based on this model. Coalition game theory has also been used in modeling secure transmissions in a wireless network [16]. In this problem a set of wireless transmitters try to transmit a message to a set of destinations in presence of eavesdroppers. The goal is to avoid the overhead of cryptography and self-organize the wireless transmitter such that secure wireless communication can be achieved. Coalition of transmitters can decode-and-forward (DF) or amplify-and-forward (AF) a signal, and in this way, completely null the signal at the eavesdroppers. In another recent study, [5] models defenders of a network security attack with coalition games. They analyze coalition formation in three canonical security games described previously in [26] for non-cooperative games.The above mentioned papers mostly consider the problem of coalition formation. In this paper, we consider another important problem, namely, revenue allocation. Much of cooperative game theory is built around the question of distributing the collective income in fair and rational manners. Different philosophies result in different solution concepts that constitute the bargaining set family, that is, the various bargaining sets [15, 24], the Kernel [20] and the Nucleolus [11]; in effect, these notions are defined separately for each coalition structure. By contrast, the Shapley value [3], Core [1], and Von Neumann-Morgenstern solutions [6] are not a priori defined with reference to a coalition structure. In this part, we review related literature on determining the core.One of the most important problems regarding the core istesting nonemptiness that is determining whether a given instance of the game has a nonempty core. Generally, determining core nonemptiness is NP-complete for cooperative games both with and without transferable utility [8]. However, recently there has been increasing interest in investigating this problem in more specific games with a description polynomial in n (number of players). As a case in point, the core nonemptiness testing problem is solvable in polynomial time for weighted graph games [14]; for minimum base game with no all-negative circuits can be solved in oracle-polynomial time [10].Since the core is usually empty, some related solution concepts arise from the core via relaxing its constraints. Shapley and Shubik [27] recommended the concepts of (strong) ε-core and weak ε-core for a cooperative game. Their main idea is to relax the requirements of subgroup rationality by x(S)≥v(S)-ε and x(S)≥v(S)-ε|S| for each proper subset S of 𝒩, respectively.Later, Tijs and Driesssen [7] introduced the concept of multiplicative ε-tax core by using x(S)≥v(S)-ε[v(S)-∑i∈S‍v({i})] instead. Faigle and Kern [9] modified the requirement of Tijs and Driessen as x(S)≥(1-ε)v(S) to define another approximate core, called multiplicative ε-core. One explanation of these concepts is that cooperation may not be as hopeless even when the core is empty. Cooperation may be possible with the subsidies of the central authority.All of the above mentioned algorithms need to investigate all coalitions and their corresponding values before computing the core; however, this is not feasible in cooperative games with large number of players due to the exponential growth of the coalition space.


## 4. The Bounding Boxed Core

The bounding-boxed Core (BBC) algorithm is a practical best-effort approach to distribute the collective security profit in an approximately fair manner among the involved organizations (players) in a given large cooperative security game(𝒩,v).More specifically, BBC consists of two main stages: tightening bounding box, and approximate core allocation. The former is an iterative global search algorithm to solve an axis-aligned smallest enclosing box problem. It finds the minimum-hypervolumen-dimensional bounding box enclosing the core, that is, closed and convex set, subject to the constraint that the edges of the box are parallel to the (Cartesian) coordinate axes. Starting from some initial large bounding box, BBC iteratively tries to tighten the bounding box, obtained at the previous iteration, by heuristically considering some useful subset of constraints by the core (3). Consequently, a bounding box B=[a1,b1]×[a2,b2]×⋯×[an,bn] is generated once a given deadline is passed or some convergences condition is met. In the approximate core allocation step, BBC computes a unique payoff vector in the generated bounding box B. The allocation values for individual players are determined by calculating the gravity center of the resulting bounding box B.


## 5. Bounding Box Tightening

In this section, the iterative bounding box tightening algorithm is explained in details. The goal is to find the minimum-hypervolume bounding box enclosing the coreB(C(v)) using an iterative search algorithm. We use Bt to denote the bounding box, obtained at t-th iteration step. Initially, we know that player i gets a payoff of xi∈[v({i}),v(𝒩)-v(𝒩-{i})] in the core C(v). The lower bound denotes individual rationality, that is, no player receives less than what it could get on its own; and the upper bound is obtained using one of the core constraints:
(4)∑j∈𝒩-{i}‍xj≥v(𝒩-{i}),
along with the efficiency condition:
(5)∑i∈𝒩‍xi=v(𝒩).Therefore, we assign as shown in (13) to be the initial, that is, t=0, bounding box enclosing the core. Throughout this paper, we will use notations Btl(i) and Btu(i) to denote the lower and upper bounds for the ith player in the tth bounding box.The initial bounding boxB0 is further tightened during several iterations. First, we describe the single iteration t of the tightening procedure given a permutation π∈Π on the set of players:
(6)π=(π(1),π(2),…,π(n)),
where, π is in fact a one-to-one function from 𝒩 onto 𝒩. Moreover, as a shorthand notation, we use πij (i≤j) to denote (π(i),π(i+1),…,π(j)).


### 5.1. Recursive Tree Construction

At each iterationt, tightening algorithm starts with constructing a full binary tree on a given permutation of players π, in a top-down manner. The root node, which covers all players π1n, has two children nodes denoting two disjoint subsets of 𝒩: π1i0 and πi0+1n (1≤i0<n). Breaking point i0 is optimally determined in a way that the bounding box is tightened the most (discussed later). Recursively, children nodes are further partitioned into two disjoint subsets of their corresponding players: π1i1, πi1+1i0⊆π1i0, and πi0+1i2, πi2+1n⊆πi0+1n. Leaf nodes of the tree represent individual players, for example, πii=(π(i)).To determine the optimal breaking point, let us consider an arbitrary parent node which covers a subset of playersπik. Suppose j (i≤j<k) is the breaking point so that πik is partitioned into children nodes πij,πj+1k⊆πik. Using the core constraints (3), and the bounding box Bt-1, obtained at the previous iteration t-1, we know
(7)∑q∈πik‍xq_≤∑q∈πik‍xq≤∑q∈πik‍xq¯,
where in the root node both bounds are equal to v(𝒩), but in lower level nodes
(8)∑q∈πik‍xq_=max(∑q∈πik‍Bt-1l(q),v(πik)),∑q∈πik‍xq¯=min(∑q∈πik‍Bt-1u(q),v(𝒩)-v(𝒩-πik)).Similar conditions hold for children nodes, that is,πij,πj+1k. Furthermore, each child node can make use of its sibling's bounds to update, that is, tighten, its own bounds. As a case in point, we update bounds on the left child, that is, πij:
(9)ℒπij≤∑q∈πij‍xq≤𝒰πij,
where,
(10)ℒπij=max(∑q∈πij‍xq_,∑q∈πik‍xq_-∑q∈πjk‍xq¯),𝒰πij=min(∑q∈πij‍xq¯,∑q∈πik‍xq¯-∑q∈πjk‍xq_).The right child also updates her bounds using the same justification. Consequently, the optimal breaking pointj* is determined using
(11)j*=argmaxxi≤j<kj∈ℤ(𝒯ij+𝒯j+1k),
where,
(12)𝒯ij=[(∑q∈πij‍xq¯-∑q∈πij‍xq_)-(𝒰πij-ℒπij)],
and 𝒯j+1k is defined similarly. Once the optimal breaking point j* is determined: (1) players in the parent node πik are partitioned into two children coalitions πij*,πj*+1k⊆πik; (2) upper and lower bounds on children are updated. As a result, recursive tree construction procedure is terminated when it gets to leaf nodes, that is, the players' payoffs, and updates their upper and lower bounds.Figure1 shows how the recursive tree construction algorithm updates the initial bounding box for a sample 3-player game, that is, 𝒩={1,2,3}. Characteristic values for different coalitions of the game are given in the Figure 1. The initial bounding box enclosing the core
(13)B0=([v({1}),v(𝒩)-v(𝒩-{1})],…,[v({n}),v(𝒩)-v(𝒩-{n})])
is obtained as 0≤xi≤8∀i∈𝒩 that results in 0≤x1+x3≤16 as shown in Figure 1. The updated values are illustrated in red font.Figure 1
A Sample 3-player game: tightening the initial boundingbox.


### 5.2. Iterative Search

In the previous section, we described how a given permutation of players is used in constructing a binary tree for tightening the bounding box. The permutation used, can be chosen at random, or as we describe in this section, it can be produced by an evolutionary algorithm which tends to generated permutations which result in larger reductions of the bounding box volume. During each iterationt of the algorithm, we have a population P, for example, P=100, of permutations Πt⊆Π, which are used for tightening the bounding box as explained in Section 5.1. Once the bounding box around feasible point in the core is updated, the fitness function is calculated as follows for each permutation in current population π∈Πt and measures its quality, that is, how helpful it was in tightness improvement:
(14)lclψt(π)=∑i∈𝒩‍|[Bt,aπu(i)-Bt,aπl(i)]-[Bt,bπu(i)-Bt,bπl(i)]|,
where Bt,bπ (Bt,aπ) denote bounds, at iteration t, just before (after) they are updated using recursive tree construction on permutation π. Once we have the population and the fitness function defined, iterative search algorithm proceeds to initialize a population of permutations randomly, then improves tightness of the bounding box through repetitive application of mutation, crossover, inversion and selection operators (discussed later).Initialization
Initially,P permutations are randomly generated from the search space Π to form an initial population.Selection
During each iterationt, a proportion 2α ( α∈[0,0.5]) of the existing population Πt is selected to breed a new generation of permutations Πt+1. Individual permutations are selected through a fitness-based process, where top 2α·P fittest permutations, as measured by ψt(.) (14), are selected.Reproduction
The next step is to generate the next generation population of permutationsΠt+1 from those selected. For each new permutation to be produced, a pair of parent permutations, that is, πp1 and πp2, is selected for breeding from the pool selected previously. By producing a child permutation πchild using function composition, that is, πchild(i)=πp1∘πp2(i), a new permutation is created. New parents are selected for each child, that is, α·P children permutations. Furthermore, (1-α)·P new permutations are randomly generated. These processes ultimately result in the next generation population Πt+1 of permutations. Generally, the average fitness will have increased by this procedure for the population, since only the most useful permutation from the previous generation are selected.Termination
This iterative search process is repeated until a termination condition has been reached. Terminating conditions can be defined regarding various criteria, such as:(1) all possible permutations Π are investigated; (2) a predefined deadline is passed deadline<t; (3) tightness improvement in the last iteration t was less than some nonnegative threshold ϵ, that is, ∑π∈Πt‍ψt(π)≤ϵ.


## 5.1. Recursive Tree Construction

At each iterationt, tightening algorithm starts with constructing a full binary tree on a given permutation of players π, in a top-down manner. The root node, which covers all players π1n, has two children nodes denoting two disjoint subsets of 𝒩: π1i0 and πi0+1n (1≤i0<n). Breaking point i0 is optimally determined in a way that the bounding box is tightened the most (discussed later). Recursively, children nodes are further partitioned into two disjoint subsets of their corresponding players: π1i1, πi1+1i0⊆π1i0, and πi0+1i2, πi2+1n⊆πi0+1n. Leaf nodes of the tree represent individual players, for example, πii=(π(i)).To determine the optimal breaking point, let us consider an arbitrary parent node which covers a subset of playersπik. Suppose j (i≤j<k) is the breaking point so that πik is partitioned into children nodes πij,πj+1k⊆πik. Using the core constraints (3), and the bounding box Bt-1, obtained at the previous iteration t-1, we know
(7)∑q∈πik‍xq_≤∑q∈πik‍xq≤∑q∈πik‍xq¯,
where in the root node both bounds are equal to v(𝒩), but in lower level nodes
(8)∑q∈πik‍xq_=max(∑q∈πik‍Bt-1l(q),v(πik)),∑q∈πik‍xq¯=min(∑q∈πik‍Bt-1u(q),v(𝒩)-v(𝒩-πik)).Similar conditions hold for children nodes, that is,πij,πj+1k. Furthermore, each child node can make use of its sibling's bounds to update, that is, tighten, its own bounds. As a case in point, we update bounds on the left child, that is, πij:
(9)ℒπij≤∑q∈πij‍xq≤𝒰πij,
where,
(10)ℒπij=max(∑q∈πij‍xq_,∑q∈πik‍xq_-∑q∈πjk‍xq¯),𝒰πij=min(∑q∈πij‍xq¯,∑q∈πik‍xq¯-∑q∈πjk‍xq_).The right child also updates her bounds using the same justification. Consequently, the optimal breaking pointj* is determined using
(11)j*=argmaxxi≤j<kj∈ℤ(𝒯ij+𝒯j+1k),
where,
(12)𝒯ij=[(∑q∈πij‍xq¯-∑q∈πij‍xq_)-(𝒰πij-ℒπij)],
and 𝒯j+1k is defined similarly. Once the optimal breaking point j* is determined: (1) players in the parent node πik are partitioned into two children coalitions πij*,πj*+1k⊆πik; (2) upper and lower bounds on children are updated. As a result, recursive tree construction procedure is terminated when it gets to leaf nodes, that is, the players' payoffs, and updates their upper and lower bounds.Figure1 shows how the recursive tree construction algorithm updates the initial bounding box for a sample 3-player game, that is, 𝒩={1,2,3}. Characteristic values for different coalitions of the game are given in the Figure 1. The initial bounding box enclosing the core
(13)B0=([v({1}),v(𝒩)-v(𝒩-{1})],…,[v({n}),v(𝒩)-v(𝒩-{n})])
is obtained as 0≤xi≤8∀i∈𝒩 that results in 0≤x1+x3≤16 as shown in Figure 1. The updated values are illustrated in red font.Figure 1
A Sample 3-player game: tightening the initial boundingbox.


## 5.2. Iterative Search

In the previous section, we described how a given permutation of players is used in constructing a binary tree for tightening the bounding box. The permutation used, can be chosen at random, or as we describe in this section, it can be produced by an evolutionary algorithm which tends to generated permutations which result in larger reductions of the bounding box volume. During each iterationt of the algorithm, we have a population P, for example, P=100, of permutations Πt⊆Π, which are used for tightening the bounding box as explained in Section 5.1. Once the bounding box around feasible point in the core is updated, the fitness function is calculated as follows for each permutation in current population π∈Πt and measures its quality, that is, how helpful it was in tightness improvement:
(14)lclψt(π)=∑i∈𝒩‍|[Bt,aπu(i)-Bt,aπl(i)]-[Bt,bπu(i)-Bt,bπl(i)]|,
where Bt,bπ (Bt,aπ) denote bounds, at iteration t, just before (after) they are updated using recursive tree construction on permutation π. Once we have the population and the fitness function defined, iterative search algorithm proceeds to initialize a population of permutations randomly, then improves tightness of the bounding box through repetitive application of mutation, crossover, inversion and selection operators (discussed later).Initialization
Initially,P permutations are randomly generated from the search space Π to form an initial population.Selection
During each iterationt, a proportion 2α ( α∈[0,0.5]) of the existing population Πt is selected to breed a new generation of permutations Πt+1. Individual permutations are selected through a fitness-based process, where top 2α·P fittest permutations, as measured by ψt(.) (14), are selected.Reproduction
The next step is to generate the next generation population of permutationsΠt+1 from those selected. For each new permutation to be produced, a pair of parent permutations, that is, πp1 and πp2, is selected for breeding from the pool selected previously. By producing a child permutation πchild using function composition, that is, πchild(i)=πp1∘πp2(i), a new permutation is created. New parents are selected for each child, that is, α·P children permutations. Furthermore, (1-α)·P new permutations are randomly generated. These processes ultimately result in the next generation population Πt+1 of permutations. Generally, the average fitness will have increased by this procedure for the population, since only the most useful permutation from the previous generation are selected.Termination
This iterative search process is repeated until a termination condition has been reached. Terminating conditions can be defined regarding various criteria, such as:(1) all possible permutations Π are investigated; (2) a predefined deadline is passed deadline<t; (3) tightness improvement in the last iteration t was less than some nonnegative threshold ϵ, that is, ∑π∈Πt‍ψt(π)≤ϵ.


## 6. Approximate Core Allocation

Once the bounding box around feasible points in the core is generated (see Section5) B=[a1,b1]×[a2,b2]×⋯×[an,bn], the candidate approximate core is computed as follows:
(15)CB(v)=(a1+b12,a2+b22,…,an+bn2).However,CB(v) may not be in the actual core; therefore, here we analyze the worst case error, that is, distance between the core C(v) and the approximate CB(v). First, we need to define the distance between the point CB(v) and the core C(v), that is, a convex set of points:
(16)d(CB(v),C(v))=minx∈C(v)d(x,CB(v)).In other words, the distance between a point and a set is the infimum of the distances between the point and those in the set.Here, we exploit the convexity of the core in analyzing the worst case error of the the approximate core,CB(v), that is defined as follows
(17)Υ(B)=maxQ∈𝒞s.t.B(Q)=Bd(CB(v),Q),
where 𝒞 is the convex set space in ℝ|𝒩|; and B(Q) denotes the minimum-volume axis-aligned bounding box around the set Q.We first obtainΥ when |𝒩|=3, and then, generalize the result to higher dimensional spaces. Given B=[a1,b1]×[a2,b2]×[a3,b3], w.l.o.g. we transfer B to the origin using the linear transformation B′=B-((a1+b1)/2,(a2+b2)/2,(a3+b3)/2); therefore, we get the bounding box B′ that consists of 2×3=6 planes:
(18)B′=[-Δ12,Δ12]×[-Δ22,Δ22]×[-Δ32,Δ32],
and CB′(v)=(0,0,0), where Δi=bi-ai. As discussed earlier (Section 2), the core is a convex subset of the hyperplanes. It can be shown that the worst case error Υ(B′) (see (17)) is caused by Q∈𝒞 whose closest hyperplane HQ to the point CB′(v) includes those 3 vertices of B′, any pair of which have exactly one of the 6 bounding box planes in common:
(19)p1=(Δ12,-Δ22,Δ32),p2=(-Δ12,Δ22,Δ32),p3=(Δ12,Δ22,-Δ32);
therefore,
(20)HQ:x+Δ1Δ2y+Δ1Δ3z-Δ12=0.Hence,Υ(B′) is obtained as the distance between the point CB′(v) and HQ:
(21)Υ(B′)=12×1/Δ12+1/Δ22+1/Δ32.As a case in point, letΔi=Δ∀i∈𝒩. Without considering convexity of the core, we know Υ(B′)=Δ.3/2 that is the distance between any of the vertices of B′ and its gravity center CB′(v). But, exploiting the convexity of the core (21) yields a better result Υ(B′)=Δ.3/6<Δ.3/2.For higher dimensional spaces, that is, games with more than3 players, discussions remain exactly the same and the worst case error is obtained as: (22)Υ(B′)=12×1/(b1-a1)2+1/(b2-a2)2+⋯+1/(bn-an)2.


## 7. Evaluations

In this section, we present the results from our prototype implementation of BBC on a case study large cooperative game. The system we used for implementation was a 2.20 GHz AMD Athlon 64 processor 3700+ with 2.00 GB of memory and Windows XP SP3 operating system. Because of large number of coalitions the bottleneck is usually the memory that caused our first prototype to crash; hence, we reimplemented the whole algorithm in C++ from scratch using more sophisticated data structures to speed up the iterative search and reduce memory consumption.Here, we present the evaluation results of the BBC algorithm for a cooperative game with 25 players in which there are about 34 million coalitions of players.Figure2 shows the number of coalitions in each coalition class that is defined based on its size, that is, number of players. As discussed earlier, every cooperative game is determined by its characteristic function for each coalition. Figure 3 shows the maximum characteristic value for each coalition class. As shown in the figure, value for grand coalition is 1604. Furthermore, coalition values satisfy supperadditivity property.Figure 2
Number of coalitions in each coalition class with particular no. of players.Figure 3
Maximum characteristic value distribution on coalition classes.Given the characteristic values for the cooperative game, we start iterative tightening of the 25-dimensional bounding box. Figure4 illustrates the initial lower and upper bounds for individual dimensions, that is, players' payoffs, of the initial bounding box, as in (13), and their corresponding updated bounds. In this experiment, we assigned P=100 and α=0.3.Figure 4
Bounding box tightening result for each dimension inℝ25.Finally, bounding box volume reduction, during the iterative tightening algorithm, is shown in Figure5 with 1020 scale. As illustrated in the logarithmic-scale graph, although the bounding box volume has shrank more than 1012 units during only a few seconds, tightening speed significantly decreases afterwards. Consequently, after about 25 minutes, bounding-box volume is 10-15 times its initial value.Figure 5
Bounding box volume improvement during iterative search.


## 8. Conclusion

In this paper, we present an approximate core allocation algorithm, called the bounding-boxed core (BBC), for cooperative security games with large number of organizations (players). Since the definition of core involves an exponential number of constraints in terms of the number of organizations, it is infeasible to solve this problem for exact solutions. We present an analysis of the maximum approximation error incurred by BBC. We also proposed a heuristic search algorithm based on Genetic algorithms to search the input space. Experimental results show that BBC significantly speeds up core allocation. In modeling cooperation among large number of organizations, this is an important step in achieving a practical solution in limited time.



---

*Source: 913294-2012-10-24.xml*