Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games

A. Khmelnitskaya, G. van der Laan, Dolf Talman

Research output: Working paperDiscussion paperOther research output

Abstract

In this paper we introduce two values for cooperative games with communication
graph structure. For cooperative games the shapley value distributes the worth of
the grand coalition amongst the players by taking into account the worths that can
be obtained by any coalition of players, but does not take into account the role of
the players when communication between players is restricted. Existing values for
communication graph games as the Myerson value and the average tree solution
only consider the worths of connected coalitions and respect only in this way the
communication restrictions. The two values take into account the position of a
player in the graph. The rst one respects centrality, but not the communication
abilities of any player. The second value reflects both centrality and the commu-
nication ability of each player. That implies that in unanimity games players that
do not generate worth but are needed to connect worth generating players are
treated as those latter players, and simultaneously players that are more central
in the graph get bigger shares in the worth than players that are less central. For
both values an axiomatic characterization is given on the class of connected cycle-free graph games.
LanguageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages31
Volume2016-035
StatePublished - 5 Sep 2016

Publication series

NameCentER Discussion Paper
Volume2016-035

Fingerprint

Myerson value
Communication
Shapley value
Centrality
Graph
Cooperative game
Axiomatic characterization
Unanimity

Keywords

  • cooperative game
  • Shapley value
  • communication graph
  • restricted cooperation
  • Centrality

Cite this

Khmelnitskaya, A., van der Laan, G., & Talman, D. (2016). Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games. (CentER Discussion Paper; Vol. 2016-035). Tilburg: Operations research.
Khmelnitskaya, A. ; van der Laan, G. ; Talman, Dolf. / Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games. Tilburg : Operations research, 2016. (CentER Discussion Paper).
@techreport{f449b9075e194702b48ea1c812747507,
title = "Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games",
abstract = "In this paper we introduce two values for cooperative games with communicationgraph structure. For cooperative games the shapley value distributes the worth ofthe grand coalition amongst the players by taking into account the worths that canbe obtained by any coalition of players, but does not take into account the role ofthe players when communication between players is restricted. Existing values forcommunication graph games as the Myerson value and the average tree solutiononly consider the worths of connected coalitions and respect only in this way thecommunication restrictions. The two values take into account the position of aplayer in the graph. The rst one respects centrality, but not the communicationabilities of any player. The second value reflects both centrality and the commu-nication ability of each player. That implies that in unanimity games players thatdo not generate worth but are needed to connect worth generating players aretreated as those latter players, and simultaneously players that are more centralin the graph get bigger shares in the worth than players that are less central. Forboth values an axiomatic characterization is given on the class of connected cycle-free graph games.",
keywords = "cooperative game, Shapley value, communication graph, restricted cooperation, Centrality",
author = "A. Khmelnitskaya and {van der Laan}, G. and Dolf Talman",
year = "2016",
month = "9",
day = "5",
language = "English",
volume = "2016-035",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Khmelnitskaya, A, van der Laan, G & Talman, D 2016 'Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games' CentER Discussion Paper, vol. 2016-035, Operations research, Tilburg.

Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games. / Khmelnitskaya, A.; van der Laan, G.; Talman, Dolf.

Tilburg : Operations research, 2016. (CentER Discussion Paper; Vol. 2016-035).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games

AU - Khmelnitskaya,A.

AU - van der Laan,G.

AU - Talman,Dolf

PY - 2016/9/5

Y1 - 2016/9/5

N2 - In this paper we introduce two values for cooperative games with communicationgraph structure. For cooperative games the shapley value distributes the worth ofthe grand coalition amongst the players by taking into account the worths that canbe obtained by any coalition of players, but does not take into account the role ofthe players when communication between players is restricted. Existing values forcommunication graph games as the Myerson value and the average tree solutiononly consider the worths of connected coalitions and respect only in this way thecommunication restrictions. The two values take into account the position of aplayer in the graph. The rst one respects centrality, but not the communicationabilities of any player. The second value reflects both centrality and the commu-nication ability of each player. That implies that in unanimity games players thatdo not generate worth but are needed to connect worth generating players aretreated as those latter players, and simultaneously players that are more centralin the graph get bigger shares in the worth than players that are less central. Forboth values an axiomatic characterization is given on the class of connected cycle-free graph games.

AB - In this paper we introduce two values for cooperative games with communicationgraph structure. For cooperative games the shapley value distributes the worth ofthe grand coalition amongst the players by taking into account the worths that canbe obtained by any coalition of players, but does not take into account the role ofthe players when communication between players is restricted. Existing values forcommunication graph games as the Myerson value and the average tree solutiononly consider the worths of connected coalitions and respect only in this way thecommunication restrictions. The two values take into account the position of aplayer in the graph. The rst one respects centrality, but not the communicationabilities of any player. The second value reflects both centrality and the commu-nication ability of each player. That implies that in unanimity games players thatdo not generate worth but are needed to connect worth generating players aretreated as those latter players, and simultaneously players that are more centralin the graph get bigger shares in the worth than players that are less central. Forboth values an axiomatic characterization is given on the class of connected cycle-free graph games.

KW - cooperative game

KW - Shapley value

KW - communication graph

KW - restricted cooperation

KW - Centrality

M3 - Discussion paper

VL - 2016-035

T3 - CentER Discussion Paper

BT - Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games

PB - Operations research

CY - Tilburg

ER -

Khmelnitskaya A, van der Laan G, Talman D. Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games. Tilburg: Operations research. 2016 Sep 5, (CentER Discussion Paper).