The optimistic \(TU\) game in minimum cost spanning tree problems (Q2458425)

This paper studies the Shapley value of an optimistic TU game associated with each minimum cost spanning tree problem (mcstp), in contrast with extant literature in which pessimistic TU games are studied. The terms pessimistic or optimistic refer to whether the worth of a coalition of agents, who can be serviced by a common supplier through connections which can be direct or indirect, i.e., through other agents already connected, is measured by the cost of connection under the assumption that the rest of the agents are not connected, i.e., cost of a stand alone connection, (pessimistic) or under the assumption that the rest of the agents are already connected and that connection is possible through them at no extra charge (optimistic). In general there is no relationship between the optimistic and the pessimistic TU game, however, the authors show that if the mcstp is in a irreducible form, i.e., if reduction of the cost of an arc always leads to the reduction of the total connection cost, then the two TU games are dual, i.e., if \(\nu \) and \(\omega \) are the characteristic functions of the two TU games then \(\upsilon \left( S\right) +\omega \left( N\backslash S\right) \) is constant for all \(S.\) This result is then applied to the issue of cost sharing rules for a minimum cost spanning tree. By using the solution concept of Shapley Value to each of the optimistic and pessimistic TU game of the original mcstp, as well as its irreducible form, they get four different possible allocation rules. They prove that the Shapley values of the optimistic TU games of the original and its irreducible form as well as that of the pessimistic TU game of the irreducible form coincide but the classical Shapley value differs from these three. Finally, focusing attention on the allocation rule common to the three of the four possible cases mentioned above, and which the authors believe is the more suitable one for msctp's, they go on to characterize it as the only rule which satisfies the normative property of equal contributions, i.e., the impact of the connection of agent \(j\) on agent \(i\)'s cost is equal to the impact of the connection of agent \(i\) on agent \(j\)'s cost.