A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack

Tjeerd van Campen, Herbert Hamers, Bart Husslage, Roy Lindelauf

Research output: Contribution to journalArticleScientificpeer-review

Abstract

The Shapley value (Shapley in Ann Math Stud 2:28, 1953) is one of the most prominent one-point solution concepts in cooperative game theory that divides revenues (or cost, power) that can be obtained by cooperation of players in the game. The Shapley value is mathematically characterized by properties that have appealing real-world interpretations and hence its use in practical settings is easily justified. The down part is that its computational complexity increases exponentially with the number of players in the game. Therefore, in practical problems that consist of more than 25 players the calculation of the Shapley value is usually too time expensive. Among others the Shapley value is applied in the analysis of terrorist networks (cf.Lindelauf et al. in Eur J Oper Res 229(1):230-238, 2013) which generally extend beyond the size of 25 players. In this paper we therefore present a new method to approximate the Shapley value by refining the random sampling method introduced by Castro et al. (Comput Oper Res 36(5):1726-1730, 2009). We show that our method outperforms the random sampling method, reducing the average error in the Shapley value approximation by almost 30%. Moreover, our new method enables us to analyze the extended WTC 9/11 network of Krebs (Connections 24(3):43-52, 2002) that consists of 69 members. This in contrast to the restricted WTC 9/11 network considered in Lindelauf et al. (2013), that only considered the operational cells consisting of the 19 hijackers that conducted the attack.

LanguageEnglish
Article number3
Number of pages12
JournalSocial Network Analysis and Mining
Volume8
Issue number1
DOIs
StatePublished - Dec 2018

Keywords

  • Approximation method
  • Shapley value
  • Cooperative game theory
  • GAMES
  • CENTRALITY
  • NETWORKS
  • POWER

Cite this

@article{4132632032f84d5e80008eac50ee9275,
title = "A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack",
abstract = "The Shapley value (Shapley in Ann Math Stud 2:28, 1953) is one of the most prominent one-point solution concepts in cooperative game theory that divides revenues (or cost, power) that can be obtained by cooperation of players in the game. The Shapley value is mathematically characterized by properties that have appealing real-world interpretations and hence its use in practical settings is easily justified. The down part is that its computational complexity increases exponentially with the number of players in the game. Therefore, in practical problems that consist of more than 25 players the calculation of the Shapley value is usually too time expensive. Among others the Shapley value is applied in the analysis of terrorist networks (cf.Lindelauf et al. in Eur J Oper Res 229(1):230-238, 2013) which generally extend beyond the size of 25 players. In this paper we therefore present a new method to approximate the Shapley value by refining the random sampling method introduced by Castro et al. (Comput Oper Res 36(5):1726-1730, 2009). We show that our method outperforms the random sampling method, reducing the average error in the Shapley value approximation by almost 30{\%}. Moreover, our new method enables us to analyze the extended WTC 9/11 network of Krebs (Connections 24(3):43-52, 2002) that consists of 69 members. This in contrast to the restricted WTC 9/11 network considered in Lindelauf et al. (2013), that only considered the operational cells consisting of the 19 hijackers that conducted the attack.",
keywords = "Approximation method, Shapley value, Cooperative game theory, GAMES, CENTRALITY, NETWORKS, POWER",
author = "{van Campen}, Tjeerd and Herbert Hamers and Bart Husslage and Roy Lindelauf",
year = "2018",
month = "12",
doi = "10.1007/s13278-017-0480-z",
language = "English",
volume = "8",
journal = "Social Network Analysis and Mining",
issn = "1869-5450",
publisher = "Springer Wien",
number = "1",

}

A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack. / van Campen, Tjeerd; Hamers, Herbert; Husslage, Bart; Lindelauf, Roy.

In: Social Network Analysis and Mining, Vol. 8, No. 1, 3, 12.2018.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A new approximation method for the Shapley value applied to the WTC 9/11 terrorist attack

AU - van Campen,Tjeerd

AU - Hamers,Herbert

AU - Husslage,Bart

AU - Lindelauf,Roy

PY - 2018/12

Y1 - 2018/12

N2 - The Shapley value (Shapley in Ann Math Stud 2:28, 1953) is one of the most prominent one-point solution concepts in cooperative game theory that divides revenues (or cost, power) that can be obtained by cooperation of players in the game. The Shapley value is mathematically characterized by properties that have appealing real-world interpretations and hence its use in practical settings is easily justified. The down part is that its computational complexity increases exponentially with the number of players in the game. Therefore, in practical problems that consist of more than 25 players the calculation of the Shapley value is usually too time expensive. Among others the Shapley value is applied in the analysis of terrorist networks (cf.Lindelauf et al. in Eur J Oper Res 229(1):230-238, 2013) which generally extend beyond the size of 25 players. In this paper we therefore present a new method to approximate the Shapley value by refining the random sampling method introduced by Castro et al. (Comput Oper Res 36(5):1726-1730, 2009). We show that our method outperforms the random sampling method, reducing the average error in the Shapley value approximation by almost 30%. Moreover, our new method enables us to analyze the extended WTC 9/11 network of Krebs (Connections 24(3):43-52, 2002) that consists of 69 members. This in contrast to the restricted WTC 9/11 network considered in Lindelauf et al. (2013), that only considered the operational cells consisting of the 19 hijackers that conducted the attack.

AB - The Shapley value (Shapley in Ann Math Stud 2:28, 1953) is one of the most prominent one-point solution concepts in cooperative game theory that divides revenues (or cost, power) that can be obtained by cooperation of players in the game. The Shapley value is mathematically characterized by properties that have appealing real-world interpretations and hence its use in practical settings is easily justified. The down part is that its computational complexity increases exponentially with the number of players in the game. Therefore, in practical problems that consist of more than 25 players the calculation of the Shapley value is usually too time expensive. Among others the Shapley value is applied in the analysis of terrorist networks (cf.Lindelauf et al. in Eur J Oper Res 229(1):230-238, 2013) which generally extend beyond the size of 25 players. In this paper we therefore present a new method to approximate the Shapley value by refining the random sampling method introduced by Castro et al. (Comput Oper Res 36(5):1726-1730, 2009). We show that our method outperforms the random sampling method, reducing the average error in the Shapley value approximation by almost 30%. Moreover, our new method enables us to analyze the extended WTC 9/11 network of Krebs (Connections 24(3):43-52, 2002) that consists of 69 members. This in contrast to the restricted WTC 9/11 network considered in Lindelauf et al. (2013), that only considered the operational cells consisting of the 19 hijackers that conducted the attack.

KW - Approximation method

KW - Shapley value

KW - Cooperative game theory

KW - GAMES

KW - CENTRALITY

KW - NETWORKS

KW - POWER

U2 - 10.1007/s13278-017-0480-z

DO - 10.1007/s13278-017-0480-z

M3 - Article

VL - 8

JO - Social Network Analysis and Mining

T2 - Social Network Analysis and Mining

JF - Social Network Analysis and Mining

SN - 1869-5450

IS - 1

M1 - 3

ER -