Wednesday, 16:15 - 16:40 h, Room: MA 043


Kazutoshi Ando
Computation of the Shapley value of minimum cost spanning tree games: #P-hardness and polynomial cases


We show that computing the Shapley value of minimum cost spanning tree games is #P-hard even if the cost functions of underlying networks are restricted to be {0,1}-valued. The proof is by a reduction from counting the number of minimum 2-terminal vertex cuts of an undirected graph, which is #P-complete. We also investigate minimum cost spanning tree games whose Shapley values can be computed in polynomial time. We show that if the cost function of the given network is a subtree distance, which is a generalization of a tree metric, then the Shapley value of the associated minimum cost spanning tree game can be computed in O(n4) time, where n is the number of players.


Talk 3 of the contributed session Wed.3.MA 043
"Solving cooperative games" [...]
Cluster 8
"Game theory" [...]


  unsecured personal loans . In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.