A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack

Herbert Hamers, Bart Husslage, R. Lindelauf, Tjeerd Campen

Research output: Working paperDiscussion paperOther research output

488 Downloads (Pure)

Abstract

The Shapley value (Shapley (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 that 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. (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. (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 (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.
Original languageEnglish
Place of PublicationTilburg
PublisherCentER, Center for Economic Research
Number of pages17
Volume2016-042
Publication statusPublished - 21 Nov 2016

Publication series

NameCentER Discussion Paper
Volume2016-042

Fingerprint

Sampling
Game theory
Refining
Computational complexity
Costs

Keywords

  • approximation method
  • Shapley value
  • cooperattive game theory

Cite this

Hamers, H., Husslage, B., Lindelauf, R., & Campen, T. (2016). A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack. (CentER Discussion Paper; Vol. 2016-042). Tilburg: CentER, Center for Economic Research.
Hamers, Herbert ; Husslage, Bart ; Lindelauf, R. ; Campen, Tjeerd. / A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack. Tilburg : CentER, Center for Economic Research, 2016. (CentER Discussion Paper).
@techreport{8a67b41610914efea1a6721ebeda8272,
title = "A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack",
abstract = "The Shapley value (Shapley (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 that 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. (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. (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 (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 theattack.",
keywords = "approximation method, Shapley value, cooperattive game theory",
author = "Herbert Hamers and Bart Husslage and R. Lindelauf and Tjeerd Campen",
year = "2016",
month = "11",
day = "21",
language = "English",
volume = "2016-042",
series = "CentER Discussion Paper",
publisher = "CentER, Center for Economic Research",
type = "WorkingPaper",
institution = "CentER, Center for Economic Research",

}

Hamers, H, Husslage, B, Lindelauf, R & Campen, T 2016 'A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack' CentER Discussion Paper, vol. 2016-042, CentER, Center for Economic Research, Tilburg.

A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack. / Hamers, Herbert; Husslage, Bart; Lindelauf, R.; Campen, Tjeerd.

Tilburg : CentER, Center for Economic Research, 2016. (CentER Discussion Paper; Vol. 2016-042).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack

AU - Hamers, Herbert

AU - Husslage, Bart

AU - Lindelauf, R.

AU - Campen, Tjeerd

PY - 2016/11/21

Y1 - 2016/11/21

N2 - The Shapley value (Shapley (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 that 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. (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. (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 (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 theattack.

AB - The Shapley value (Shapley (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 that 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. (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. (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 (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 theattack.

KW - approximation method

KW - Shapley value

KW - cooperattive game theory

M3 - Discussion paper

VL - 2016-042

T3 - CentER Discussion Paper

BT - A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Hamers H, Husslage B, Lindelauf R, Campen T. A New Approximation Method for the Shapley Value Applied to the WTC 9/11 Terrorist Attack. Tilburg: CentER, Center for Economic Research. 2016 Nov 21. (CentER Discussion Paper).