The average covering tree value for directed graph games

Anna Borisovna Khmelnitskaya, Özer Selcuk, Dolf Talman

Research output: Book/ReportReport

Abstract

We introduce a single-valued solution concept, the so-called average covering tree value, for the class of transferable utility games with limited communication structure represented by a directed graph. The solution is the average of the marginal contribution vectors corresponding to all covering trees of the directed graph. The covering trees of a directed graph are those (rooted) trees on the set of players that preserve the dominance relations between the players prescribed by the directed graph. The average covering tree value is component efficient and under a particular convexity-type condition is stable. For transferable utility games with complete communication structure the average covering tree value equals to the Shapley value of the game. If the graph is the directed analog of an undirected graph the average covering tree value coincides with the gravity center solution.
LanguageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages18
StatePublished - May 2012

Publication series

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

Keywords

  • IR-80404
  • METIS-289643
  • JEL-C71
  • EWI-21864
  • TU game
  • Stability
  • Myerson value
  • Directed communication structure
  • Marginal contribution vector
  • Average tree solution

Cite this

Khmelnitskaya, A. B., Selcuk, Ö., & Talman, D. (2012). The average covering tree value for directed graph games. (Memorandum / Department of Applied Mathematics; No. 1981). Enschede: University of Twente, Department of Applied Mathematics.
Khmelnitskaya, Anna Borisovna ; Selcuk, Özer ; Talman, Dolf. / The average covering tree value for directed graph games. Enschede : University of Twente, Department of Applied Mathematics, 2012. 18 p. (Memorandum / Department of Applied Mathematics; 1981).
@book{4b3ee056aaf546eeaba31fe948a40ced,
title = "The average covering tree value for directed graph games",
abstract = "We introduce a single-valued solution concept, the so-called average covering tree value, for the class of transferable utility games with limited communication structure represented by a directed graph. The solution is the average of the marginal contribution vectors corresponding to all covering trees of the directed graph. The covering trees of a directed graph are those (rooted) trees on the set of players that preserve the dominance relations between the players prescribed by the directed graph. The average covering tree value is component efficient and under a particular convexity-type condition is stable. For transferable utility games with complete communication structure the average covering tree value equals to the Shapley value of the game. If the graph is the directed analog of an undirected graph the average covering tree value coincides with the gravity center solution.",
keywords = "IR-80404, METIS-289643, JEL-C71, EWI-21864, TU game, Stability, Myerson value, Directed communication structure, Marginal contribution vector, Average tree solution",
author = "Khmelnitskaya, {Anna Borisovna} and {\"O}zer Selcuk and Dolf Talman",
year = "2012",
month = "5",
language = "Undefined",
series = "Memorandum / Department of Applied Mathematics",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1981",

}

Khmelnitskaya, AB, Selcuk, Ö & Talman, D 2012, The average covering tree value for directed graph games. Memorandum / Department of Applied Mathematics, no. 1981, University of Twente, Department of Applied Mathematics, Enschede.

The average covering tree value for directed graph games. / Khmelnitskaya, Anna Borisovna; Selcuk, Özer; Talman, Dolf.

Enschede : University of Twente, Department of Applied Mathematics, 2012. 18 p. (Memorandum / Department of Applied Mathematics; No. 1981).

Research output: Book/ReportReport

TY - BOOK

T1 - The average covering tree value for directed graph games

AU - Khmelnitskaya,Anna Borisovna

AU - Selcuk,Özer

AU - Talman,Dolf

PY - 2012/5

Y1 - 2012/5

N2 - We introduce a single-valued solution concept, the so-called average covering tree value, for the class of transferable utility games with limited communication structure represented by a directed graph. The solution is the average of the marginal contribution vectors corresponding to all covering trees of the directed graph. The covering trees of a directed graph are those (rooted) trees on the set of players that preserve the dominance relations between the players prescribed by the directed graph. The average covering tree value is component efficient and under a particular convexity-type condition is stable. For transferable utility games with complete communication structure the average covering tree value equals to the Shapley value of the game. If the graph is the directed analog of an undirected graph the average covering tree value coincides with the gravity center solution.

AB - We introduce a single-valued solution concept, the so-called average covering tree value, for the class of transferable utility games with limited communication structure represented by a directed graph. The solution is the average of the marginal contribution vectors corresponding to all covering trees of the directed graph. The covering trees of a directed graph are those (rooted) trees on the set of players that preserve the dominance relations between the players prescribed by the directed graph. The average covering tree value is component efficient and under a particular convexity-type condition is stable. For transferable utility games with complete communication structure the average covering tree value equals to the Shapley value of the game. If the graph is the directed analog of an undirected graph the average covering tree value coincides with the gravity center solution.

KW - IR-80404

KW - METIS-289643

KW - JEL-C71

KW - EWI-21864

KW - TU game

KW - Stability

KW - Myerson value

KW - Directed communication structure

KW - Marginal contribution vector

KW - Average tree solution

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

BT - The average covering tree value for directed graph games

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Khmelnitskaya AB, Selcuk Ö, Talman D. The average covering tree value for directed graph games. Enschede: University of Twente, Department of Applied Mathematics, 2012. 18 p. (Memorandum / Department of Applied Mathematics; 1981).