The Communication Tree Value for TU-games with Graph Communication

T. Huseynov, A.J.J. Talman

Research output: Working paperDiscussion paperOther research output

257 Downloads (Pure)

Abstract

Abstract: A new solution is presented for transferable utility games with graph communication where the cooperation possibilities are represented by a graph. Players are only able to cooperate and obtain some worth in a coalition if they form a connected set in the given graph. To determine the payoff for each player, a single-valued solution, the communication tree value, is proposed for this class of games. The idea is that to form the grand coalition of all players a player can join a set of players only if this player is connected in the graph to at least one of the players in the set. To a set of players, starting with an arbitrary single player, from each maximally connected subset of remaining players one player joins who is connected to one or more of the players in that set. In this way a (rooted) tree on the set of players is obtained, called a communication tree. For a given game each communication tree of the graph induces a marginal contribution vector, in which any player receives a payoff equal to what he contributes in worth when he joins his subordinates in the tree. The average payoff over all communication trees of the graph determines the value. In case the underlying graph is cycle-complete the value coincides with the average tree solution. When there is complete communication between all players, which is the special case of cycle-completeness, players join one by one, yielding the Shapley value. A weak form of convexity is introduced, under which the value is guaranteed to be an element of the core. For games with complete graph communication the condition coincides with convexity and in case the underlying graph is cycle-free it is weaker than super-additivity.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages24
Volume2012-095
Publication statusPublished - 2012

Publication series

NameCentER Discussion Paper
Volume2012-095

Fingerprint

Communication

Keywords

  • Cooperative game
  • communication structure
  • Myerson value
  • core stability
  • convexity
  • rooted tree

Cite this

Huseynov, T., & Talman, A. J. J. (2012). The Communication Tree Value for TU-games with Graph Communication. (CentER Discussion Paper; Vol. 2012-095). Tilburg: Operations research.
Huseynov, T. ; Talman, A.J.J. / The Communication Tree Value for TU-games with Graph Communication. Tilburg : Operations research, 2012. (CentER Discussion Paper).
@techreport{6ba97d871ac64af7a981aaff62a6e3db,
title = "The Communication Tree Value for TU-games with Graph Communication",
abstract = "Abstract: A new solution is presented for transferable utility games with graph communication where the cooperation possibilities are represented by a graph. Players are only able to cooperate and obtain some worth in a coalition if they form a connected set in the given graph. To determine the payoff for each player, a single-valued solution, the communication tree value, is proposed for this class of games. The idea is that to form the grand coalition of all players a player can join a set of players only if this player is connected in the graph to at least one of the players in the set. To a set of players, starting with an arbitrary single player, from each maximally connected subset of remaining players one player joins who is connected to one or more of the players in that set. In this way a (rooted) tree on the set of players is obtained, called a communication tree. For a given game each communication tree of the graph induces a marginal contribution vector, in which any player receives a payoff equal to what he contributes in worth when he joins his subordinates in the tree. The average payoff over all communication trees of the graph determines the value. In case the underlying graph is cycle-complete the value coincides with the average tree solution. When there is complete communication between all players, which is the special case of cycle-completeness, players join one by one, yielding the Shapley value. A weak form of convexity is introduced, under which the value is guaranteed to be an element of the core. For games with complete graph communication the condition coincides with convexity and in case the underlying graph is cycle-free it is weaker than super-additivity.",
keywords = "Cooperative game, communication structure, Myerson value, core stability, convexity, rooted tree",
author = "T. Huseynov and A.J.J. Talman",
note = "Pagination: 24",
year = "2012",
language = "English",
volume = "2012-095",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Huseynov, T & Talman, AJJ 2012 'The Communication Tree Value for TU-games with Graph Communication' CentER Discussion Paper, vol. 2012-095, Operations research, Tilburg.

The Communication Tree Value for TU-games with Graph Communication. / Huseynov, T.; Talman, A.J.J.

Tilburg : Operations research, 2012. (CentER Discussion Paper; Vol. 2012-095).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - The Communication Tree Value for TU-games with Graph Communication

AU - Huseynov, T.

AU - Talman, A.J.J.

N1 - Pagination: 24

PY - 2012

Y1 - 2012

N2 - Abstract: A new solution is presented for transferable utility games with graph communication where the cooperation possibilities are represented by a graph. Players are only able to cooperate and obtain some worth in a coalition if they form a connected set in the given graph. To determine the payoff for each player, a single-valued solution, the communication tree value, is proposed for this class of games. The idea is that to form the grand coalition of all players a player can join a set of players only if this player is connected in the graph to at least one of the players in the set. To a set of players, starting with an arbitrary single player, from each maximally connected subset of remaining players one player joins who is connected to one or more of the players in that set. In this way a (rooted) tree on the set of players is obtained, called a communication tree. For a given game each communication tree of the graph induces a marginal contribution vector, in which any player receives a payoff equal to what he contributes in worth when he joins his subordinates in the tree. The average payoff over all communication trees of the graph determines the value. In case the underlying graph is cycle-complete the value coincides with the average tree solution. When there is complete communication between all players, which is the special case of cycle-completeness, players join one by one, yielding the Shapley value. A weak form of convexity is introduced, under which the value is guaranteed to be an element of the core. For games with complete graph communication the condition coincides with convexity and in case the underlying graph is cycle-free it is weaker than super-additivity.

AB - Abstract: A new solution is presented for transferable utility games with graph communication where the cooperation possibilities are represented by a graph. Players are only able to cooperate and obtain some worth in a coalition if they form a connected set in the given graph. To determine the payoff for each player, a single-valued solution, the communication tree value, is proposed for this class of games. The idea is that to form the grand coalition of all players a player can join a set of players only if this player is connected in the graph to at least one of the players in the set. To a set of players, starting with an arbitrary single player, from each maximally connected subset of remaining players one player joins who is connected to one or more of the players in that set. In this way a (rooted) tree on the set of players is obtained, called a communication tree. For a given game each communication tree of the graph induces a marginal contribution vector, in which any player receives a payoff equal to what he contributes in worth when he joins his subordinates in the tree. The average payoff over all communication trees of the graph determines the value. In case the underlying graph is cycle-complete the value coincides with the average tree solution. When there is complete communication between all players, which is the special case of cycle-completeness, players join one by one, yielding the Shapley value. A weak form of convexity is introduced, under which the value is guaranteed to be an element of the core. For games with complete graph communication the condition coincides with convexity and in case the underlying graph is cycle-free it is weaker than super-additivity.

KW - Cooperative game

KW - communication structure

KW - Myerson value

KW - core stability

KW - convexity

KW - rooted tree

M3 - Discussion paper

VL - 2012-095

T3 - CentER Discussion Paper

BT - The Communication Tree Value for TU-games with Graph Communication

PB - Operations research

CY - Tilburg

ER -

Huseynov T, Talman AJJ. The Communication Tree Value for TU-games with Graph Communication. Tilburg: Operations research. 2012. (CentER Discussion Paper).