A Note on the Shapley Value for Characteristic Functions on Bipartitions

Research output: Working paperDiscussion paperOther research output

Abstract

We consider a cooperative game with a bipartition that indicates which players are participating. This paper provides an analytical solution for the Shapley value when the worth of a coalition only depends on the number of participating coalition players. The computational complexity grows linearly in the number of players, which contrasts with the usual exponential increase. Our result remains true when we introduce (i) randomization of the bipartition, and (ii) randomly draw a characteristic function.
Original languageEnglish
Place of PublicationDen Haag
PublisherCPB Netherlands Bureau for Economic Policy Analysis
Number of pages12
DOIs
Publication statusPublished - 28 Aug 2011
Externally publishedYes

Publication series

NameCPB Discussion Paper
Volume189

Fingerprint

Shapley value
Characteristic function
Analytical solution
Cooperative game
Computational complexity
Randomization

Keywords

  • Shapley value
  • computational complexity
  • bipartition

Cite this

Muns, S. (2011). A Note on the Shapley Value for Characteristic Functions on Bipartitions. (CPB Discussion Paper ; Vol. 189). Den Haag: CPB Netherlands Bureau for Economic Policy Analysis. https://doi.org/10.2139/ssrn.1921323
Muns, Sander. / A Note on the Shapley Value for Characteristic Functions on Bipartitions. Den Haag : CPB Netherlands Bureau for Economic Policy Analysis, 2011. (CPB Discussion Paper ).
@techreport{fc7f1583efe142bba21244da20f504c8,
title = "A Note on the Shapley Value for Characteristic Functions on Bipartitions",
abstract = "We consider a cooperative game with a bipartition that indicates which players are participating. This paper provides an analytical solution for the Shapley value when the worth of a coalition only depends on the number of participating coalition players. The computational complexity grows linearly in the number of players, which contrasts with the usual exponential increase. Our result remains true when we introduce (i) randomization of the bipartition, and (ii) randomly draw a characteristic function.",
keywords = "Shapley value, computational complexity, bipartition",
author = "Sander Muns",
year = "2011",
month = "8",
day = "28",
doi = "10.2139/ssrn.1921323",
language = "English",
series = "CPB Discussion Paper",
publisher = "CPB Netherlands Bureau for Economic Policy Analysis",
type = "WorkingPaper",
institution = "CPB Netherlands Bureau for Economic Policy Analysis",

}

Muns, S 2011 'A Note on the Shapley Value for Characteristic Functions on Bipartitions' CPB Discussion Paper , vol. 189, CPB Netherlands Bureau for Economic Policy Analysis, Den Haag. https://doi.org/10.2139/ssrn.1921323

A Note on the Shapley Value for Characteristic Functions on Bipartitions. / Muns, Sander.

Den Haag : CPB Netherlands Bureau for Economic Policy Analysis, 2011. (CPB Discussion Paper ; Vol. 189).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - A Note on the Shapley Value for Characteristic Functions on Bipartitions

AU - Muns, Sander

PY - 2011/8/28

Y1 - 2011/8/28

N2 - We consider a cooperative game with a bipartition that indicates which players are participating. This paper provides an analytical solution for the Shapley value when the worth of a coalition only depends on the number of participating coalition players. The computational complexity grows linearly in the number of players, which contrasts with the usual exponential increase. Our result remains true when we introduce (i) randomization of the bipartition, and (ii) randomly draw a characteristic function.

AB - We consider a cooperative game with a bipartition that indicates which players are participating. This paper provides an analytical solution for the Shapley value when the worth of a coalition only depends on the number of participating coalition players. The computational complexity grows linearly in the number of players, which contrasts with the usual exponential increase. Our result remains true when we introduce (i) randomization of the bipartition, and (ii) randomly draw a characteristic function.

KW - Shapley value

KW - computational complexity

KW - bipartition

U2 - 10.2139/ssrn.1921323

DO - 10.2139/ssrn.1921323

M3 - Discussion paper

T3 - CPB Discussion Paper

BT - A Note on the Shapley Value for Characteristic Functions on Bipartitions

PB - CPB Netherlands Bureau for Economic Policy Analysis

CY - Den Haag

ER -

Muns S. A Note on the Shapley Value for Characteristic Functions on Bipartitions. Den Haag: CPB Netherlands Bureau for Economic Policy Analysis. 2011 Aug 28. (CPB Discussion Paper ). https://doi.org/10.2139/ssrn.1921323