Centrality rewarding Shapley and Myerson values for undirected graph games

Anna Borisovna Khmelnitskaya, Gerard van der Laan, Dolf Talman

Research output: Book/ReportReport

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. They do not take into account the position of a player in the graph in the sense that, when the graph is connected, in the unanimity game on the grand coalition all players are treated equally and so players with a more central position in the graph get the same payoff as players that are not central. The two new values take into account the position of a player in the graph. The first one respects centrality, but not the communication abilities of any player. The second value reflects both centrality and the communication 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.
LanguageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages27
StatePublished - Sep 2016

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Department of Applied Mathematics
No.2057
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • Cooperative game
  • C71
  • restricted cooperation
  • Communication graph
  • EWI-27198
  • IR-101250
  • Centrality
  • Shapley value
  • METIS-318513

Cite this

Khmelnitskaya, A. B., van der Laan, G., & Talman, D. (2016). Centrality rewarding Shapley and Myerson values for undirected graph games. (Memorandum / Department of Applied Mathematics; No. 2057). Enschede: University of Twente, Department of Applied Mathematics.
Khmelnitskaya, Anna Borisovna ; van der Laan, Gerard ; Talman, Dolf. / Centrality rewarding Shapley and Myerson values for undirected graph games. Enschede : University of Twente, Department of Applied Mathematics, 2016. 27 p. (Memorandum / Department of Applied Mathematics; 2057).
@book{f5d924b84a404f108fb16cae5c64f01a,
title = "Centrality rewarding Shapley and Myerson values for undirected graph games",
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. They do not take into account the position of a player in the graph in the sense that, when the graph is connected, in the unanimity game on the grand coalition all players are treated equally and so players with a more central position in the graph get the same payoff as players that are not central. The two new values take into account the position of a player in the graph. The first one respects centrality, but not the communication abilities of any player. The second value reflects both centrality and the communication 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.",
keywords = "Cooperative game, C71, restricted cooperation, Communication graph, EWI-27198, IR-101250, Centrality, Shapley value, METIS-318513",
author = "Khmelnitskaya, {Anna Borisovna} and {van der Laan}, Gerard and Dolf Talman",
note = "eemcs-eprint-27198",
year = "2016",
month = "9",
language = "Undefined",
series = "Memorandum / Department of Applied Mathematics",
publisher = "University of Twente, Department of Applied Mathematics",
number = "2057",

}

Khmelnitskaya, AB, van der Laan, G & Talman, D 2016, Centrality rewarding Shapley and Myerson values for undirected graph games. Memorandum / Department of Applied Mathematics, no. 2057, University of Twente, Department of Applied Mathematics, Enschede.

Centrality rewarding Shapley and Myerson values for undirected graph games. / Khmelnitskaya, Anna Borisovna; van der Laan, Gerard; Talman, Dolf.

Enschede : University of Twente, Department of Applied Mathematics, 2016. 27 p. (Memorandum / Department of Applied Mathematics; No. 2057).

Research output: Book/ReportReport

TY - BOOK

T1 - Centrality rewarding Shapley and Myerson values for undirected graph games

AU - Khmelnitskaya,Anna Borisovna

AU - van der Laan,Gerard

AU - Talman,Dolf

N1 - eemcs-eprint-27198

PY - 2016/9

Y1 - 2016/9

N2 - 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. They do not take into account the position of a player in the graph in the sense that, when the graph is connected, in the unanimity game on the grand coalition all players are treated equally and so players with a more central position in the graph get the same payoff as players that are not central. The two new values take into account the position of a player in the graph. The first one respects centrality, but not the communication abilities of any player. The second value reflects both centrality and the communication 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.

AB - 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. They do not take into account the position of a player in the graph in the sense that, when the graph is connected, in the unanimity game on the grand coalition all players are treated equally and so players with a more central position in the graph get the same payoff as players that are not central. The two new values take into account the position of a player in the graph. The first one respects centrality, but not the communication abilities of any player. The second value reflects both centrality and the communication 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.

KW - Cooperative game

KW - C71

KW - restricted cooperation

KW - Communication graph

KW - EWI-27198

KW - IR-101250

KW - Centrality

KW - Shapley value

KW - METIS-318513

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - Centrality rewarding Shapley and Myerson values for undirected graph games

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Khmelnitskaya AB, van der Laan G, Talman D. Centrality rewarding Shapley and Myerson values for undirected graph games. Enschede: University of Twente, Department of Applied Mathematics, 2016. 27 p. (Memorandum / Department of Applied Mathematics; 2057).