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" [...]


  Most online loan lenders allow getting New Jersey Payday Loans without visiting a bank, straight to your bank account. In rare cases, the smarting in eyes and the tumefaction of eyelids can happen. In case of long term Cialis Black administration the side effects become less perceptible or disappear at all.