iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S10479-011-1043-8
The minimum cost shortest-path tree game | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

The minimum cost shortest-path tree game

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

A minimum cost shortest-path tree is a tree that connects the source with every node of the network by a shortest path such that the sum of the cost (as a proxy for length) of all arcs is minimum.

In this paper, we adapt the algorithm of Hansen and Zheng (Discrete Appl. Math. 65:275–284, 1996) to the case of acyclic directed graphs to find a minimum cost shortest-path tree in order to be applied to the cost allocation problem associated with a cooperative minimum cost shortest-path tree game. In addition, we analyze a non-cooperative game based on the connection problem that arises in the above situation. We prove that the cost allocation given by an ‘à la’ Bird rule provides a core solution in the former game and that the strategies that induce those payoffs in the latter game are Nash equilibrium.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Bergantiños, G., & Lorenzo, L. (2004). A non-cooperative approach to the cost spanning tree problem. Mathematical Methods of Operations Research, 59, 393–403.

    Article  Google Scholar 

  • Bergantiños, G., & Lorenzo, L. (2005). Optimal equilibria in the non-cooperative game associated with cost spanning tree problems. Annals of Operations Research, 137, 101–115.

    Article  Google Scholar 

  • Bharath-Kumar, K., & Jaffe, J. M. (1983). Routing to multiple destinations in computer networks. IEEE Transactions on Communications, 31(3), 343–351.

    Article  Google Scholar 

  • Bird, C. G. (1976). On cost allocation for a spanning tree: a game theoretic approach. Networks, 6, 335–350.

    Article  Google Scholar 

  • Borm, P., Hamers, H., & Hendrickx, R. (2001). Operations research games: a survey. Top, 9, 139–216.

    Article  Google Scholar 

  • Curiel, I. (1997). Cooperative game theory and applications: cooperative games arising from combinatorial optimization problems. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Dusnik, B., & Miller, E. (1941). Partially ordered sets. American Journal of Mathematics, 63, 600–610.

    Article  Google Scholar 

  • Fernández, F. R., Hinojosa, M. A., & Puerto, J. (2004). Multi-criteria minimum cost spanning tree games. European Journal of Operations Research, 158, 399–408.

    Article  Google Scholar 

  • Fernández, F. R., Hinojosa, M. A., Mármol, A. M., & Puerto, J. (2009). Opportune moment strategies for a cost spanning tree game. Mathematical Methods of Operations Research, 70, 451–483 (2009).

    Article  Google Scholar 

  • Fragnelli, V., García-Jurado, I., & Méndez-Naya, L. (2000). On shortest path games. Mathematical Methods of Operations Research, 52, 251–264.

    Article  Google Scholar 

  • Gómez-Rúa, M., & Vidal-Puga, J. (2011). Balanced per capita contributions and level structure of cooperation. Top, 19(1), 167–176.

    Article  Google Scholar 

  • Gondran, M., & Minoux, M. (1984). Graphs and algorithms. New York: Wiley.

    Google Scholar 

  • Granot, D., & Huberman, G. (1981). Minimum cost spanning tree games. Mathematical Programming, 21, 1–18.

    Article  Google Scholar 

  • Hansen, P., & Zheng, M. (1996). Shortest path tree of a network. Discrete Applied Mathematics, 65, 275–284.

    Article  Google Scholar 

  • Marín, A. (2007). An extension to rapid transit network design problem. Top, 2, 231–241.

    Article  Google Scholar 

  • Voorneveld, M., & Grahn, S. (2002). Cost allocation in shortest path games. Mathematical Methods of Operations Research, 56, 323–340.

    Article  Google Scholar 

  • Wu, B. W., & Chao, K. (2004). Spanning trees and optimization problems. Cambridge: CRC Press.

    Google Scholar 

Download references

Acknowledgements

The authors would like to thanks the very constructive comments of one anonymous referee that have helped to improve the quality of the paper. This research has been partially funded by the Spanish Ministry of Science and Technology projects MTM2007-67433-C02-01, MTM2010-19576-C02-01, and Junta de Andalucía grants FQM-331, FQM-5849 and P06-FQM-01366.

Author information

Authors and Affiliations

  1. Institute of Mathematics (IMUS), Seville University, Seville, Spain

    F. R. Fernández & J. Puerto

Authors
  1. F. R. Fernández
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Puerto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Puerto.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fernández, F.R., Puerto, J. The minimum cost shortest-path tree game. Ann Oper Res 199, 23–32 (2012). https://doi.org/10.1007/s10479-011-1043-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-011-1043-8

Keywords

Search

Navigation