TY - UNPB

T1 - The Two-Step Average Tree Value for Graph and Hypergraph Games

AU - Kang, Liying

AU - Khmelnitskaya, Anna

AU - Shan, Erfang

AU - Talman, Dolf

AU - Zhang, Guang

N1 - Kang, Liying and Khmelnitskaya, Anna and Shan, Erfang and Talman, Dolf and Zhang, Guang, The Two-Step Average Tree Value for Graph and Hypergraph Games (July 9, 2020). CentER Discussion Paper Nr. 2020-018, Available at SSRN: https://ssrn.com/abstract=3647009 or http://dx.doi.org/10.2139/ssrn.3647009

PY - 2020/8/7

Y1 - 2020/8/7

N2 - We introduce the two-step average tree value for transferable utility games with restricted cooperation represented by undirected communication graphs or hypergraphs. The solution can be considered as an alternative for both the average tree solution for graph games and the average tree value for hypergraph games. Instead of averaging players' marginal contributions corresponding to all admissible rooted spanning trees of the underlying (hyper)graph, which determines the average tree solution or value, we consider a two-step averaging procedure, in which in the first step for each player the average of players' marginal contributions corresponding to all admissible rooted spanning trees that have this player as the root is calculated, and in the second step the average over all players of all the payoff is obtained in the first step is computed. In general these two approaches lead to different solution concepts. When each component in the underlying communication structure is cycle-free, a linear cactus with cycles, or the complete graph, the two-step average tree value coincides with the average tree value. A comparative analysis of both solution concepts is done and an axiomatization of the the two-step average tree value on the subclass of TU games with semi-cycle-free hypergraph communication structure, which is more general than that given by a cycle-free hypergraph, is obtained.

AB - We introduce the two-step average tree value for transferable utility games with restricted cooperation represented by undirected communication graphs or hypergraphs. The solution can be considered as an alternative for both the average tree solution for graph games and the average tree value for hypergraph games. Instead of averaging players' marginal contributions corresponding to all admissible rooted spanning trees of the underlying (hyper)graph, which determines the average tree solution or value, we consider a two-step averaging procedure, in which in the first step for each player the average of players' marginal contributions corresponding to all admissible rooted spanning trees that have this player as the root is calculated, and in the second step the average over all players of all the payoff is obtained in the first step is computed. In general these two approaches lead to different solution concepts. When each component in the underlying communication structure is cycle-free, a linear cactus with cycles, or the complete graph, the two-step average tree value coincides with the average tree value. A comparative analysis of both solution concepts is done and an axiomatization of the the two-step average tree value on the subclass of TU games with semi-cycle-free hypergraph communication structure, which is more general than that given by a cycle-free hypergraph, is obtained.

KW - TU game

KW - hypergraph communication structure

KW - average tree value

KW - component fairness

UR - https://www.mendeley.com/catalogue/2880b438-31e8-3e63-bfcb-a23e7f4e44af/

U2 - 10.2139/ssrn.3647009

DO - 10.2139/ssrn.3647009

M3 - Preprint

T3 - SSRN electronic journal

BT - The Two-Step Average Tree Value for Graph and Hypergraph Games

ER -