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

*(English)*Zbl 1138.91006This 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.

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.

Reviewer: Swapan Das Gupta (Halifax)

##### MSC:

91A12 | Cooperative games |

##### Keywords:

minimum cost spanning tree problem; optimistic TU game; pessimistic TU game; Shapley value; equal contribution property
PDF
BibTeX
XML
Cite

\textit{G. Bergantiños} and \textit{J. J. Vidal-Puga}, Int. J. Game Theory 36, No. 2, 223--239 (2007; Zbl 1138.91006)

Full Text:
DOI

##### References:

[1] | Bergantiños G, Lorenzo L (2004) A non-cooperative approach to the cost spanning tree problem. Math Methods Operat Res 59:393–403 · Zbl 1076.90004 |

[2] | Bergantiños G, Vidal-Puga JJ (2005a) A fair rule in minimum cost spanning tree problems. Mimeo. Available from the authors on request · Zbl 1132.91366 |

[3] | Bergantiños G, Vidal-Puga JJ (2005b) Several approaches to the same rule in minimum cost spanning tree problems. Mimeo. Available from the authors on request |

[4] | Bird CG (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6:335–350 · Zbl 0357.90083 · doi:10.1002/net.3230060404 |

[5] | Branzei R, Moretti S, Norde H, Tijs S (2004) The P-value for cost sharing in minimum cost spanning tree situations. Theory Decisi 56:47–61 · Zbl 1127.91316 · doi:10.1007/s11238-004-5635-5 |

[6] | Chun Y (2006) A pessimisic approach to the queuing problem. Math soc Sci 51:171–181 · Zbl 1162.91311 · doi:10.1016/j.mathsocsci.2005.08.002 |

[7] | Dutta B, Kar A (2004) Cost monotonicity, consistency and minimum cost spanning tree games. Games Econ Behav 48:223–248 · Zbl 1117.91308 · doi:10.1016/j.geb.2003.09.008 |

[8] | Feltkamp V, Tijs S, Muto S (1994) On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Mimeo. Tilburg University |

[9] | Granot D, Huberman G (1981) Minimum cost spanning tree games. Math Program 21:1–18 · Zbl 0461.90099 · doi:10.1007/BF01584227 |

[10] | Granot D, Huberman G (1984) On the core and nucleolus of the minimum cost spanning tree games. Math Program 29:323–347 · Zbl 0541.90099 · doi:10.1007/BF02592000 |

[11] | Kalai E, Samet D (1987) On weighted Shapley values. Int J Game Theory 16:205–222 · Zbl 0633.90100 · doi:10.1007/BF01756292 |

[12] | Kar A (2002) Axiomatization of the Shapley value on minimum cost spanning tree games. Games Econ Behav 38:265–277 · Zbl 1035.91007 · doi:10.1006/game.2001.0883 |

[13] | Kruskal J (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48–50 · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |

[14] | Maniquet F (2003) A characterization of the Shapley value in queuing problems. J Econ Theory 109:90–103 · Zbl 1032.91020 · doi:10.1016/S0022-0531(02)00036-4 |

[15] | Myerson RB (1980) Conference structures and fair allocation rules. Int J Game Theory 9:169–182 · Zbl 0441.90117 · doi:10.1007/BF01781371 |

[16] | Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Technol J 36:1389–1401 |

[17] | Shapley LS (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games II. Princeton University Press, Princeton, pp 307–317 |

[18] | Thomson W (2003) Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: a survey. Math Soc Sci 45:249–297 · Zbl 1042.91014 · doi:10.1016/S0165-4896(02)00070-7 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.