IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v224y2013i1p132-140.html
   My bibliography  Save this article

Shortest path games

Author

Listed:
  • Rosenthal, Edward C.

Abstract

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.

Suggested Citation

  • Rosenthal, Edward C., 2013. "Shortest path games," European Journal of Operational Research, Elsevier, vol. 224(1), pages 132-140.
  • Handle: RePEc:eee:ejores:v:224:y:2013:i:1:p:132-140 DOI: 10.1016/j.ejor.2012.06.047
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712005346
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Grahn, Sofia, 2001. "Core and Bargaining Set of Shortest Path Games," Working Paper Series 2001:3, Uppsala University, Department of Economics.
    2. Rosenthal, Edward C., 1990. "Monotonicity of solutions in certain dynamic cooperative games," Economics Letters, Elsevier, vol. 34(3), pages 221-226, November.
    3. Rosenthal, E C, 1990. "Monotonicity of the Core and Value in Dynamic Cooperative Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(1), pages 45-57.
    4. Grahn, S., 2001. "Core and Bargaining Set of Shortest Path Games," Papers 2001:03, Uppsala - Working Paper Series.
    5. S. C. Littlechild & G. Owen, 1973. "A Simple Expression for the Shapley Value in a Special Case," Management Science, INFORMS, vol. 20(3), pages 370-372, November.
    6. Bergantiños, Gustavo & Vidal-Puga, Juan, 2010. "Realizing fair outcomes in minimum cost spanning tree problems through non-cooperative mechanisms," European Journal of Operational Research, Elsevier, vol. 201(3), pages 811-820, March.
    7. Laporte, Gilbert & Mesa, Juan A. & Perea, Federico, 2010. "A game theoretic framework for the robust railway transit network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 447-459, May.
    8. repec:spr:compst:v:56:y:2002:i:2:p:323-340 is not listed on IDEAS
    9. Laporte, G. & Mesa, J.A. & Ortega, F.A. & Perea, F., 2011. "Planning rapid transit networks," Socio-Economic Planning Sciences, Elsevier, vol. 45(3), pages 95-104, September.
    10. Sprumont, Yves, 1990. "Population monotonic allocation schemes for cooperative games with transferable utility," Games and Economic Behavior, Elsevier, vol. 2(4), pages 378-394, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Richard Startz & Kwok Ping Tsang, 2014. "On the Present Value Model in a Cross Section of Stocks," Working Papers e07-47, Virginia Polytechnic Institute and State University, Department of Economics.
    2. Trudeau, Christian, 2014. "Minimum cost spanning tree problems with indifferent agents," Games and Economic Behavior, Elsevier, vol. 84(C), pages 137-151.
    3. repec:has:discpr:1321 is not listed on IDEAS
    4. Bahel, Eric & Trudeau, Christian, 2014. "Stable lexicographic rules for shortest path games," Economics Letters, Elsevier, pages 266-269.
    5. Eric Bahel & Christian Trudeau, 2014. "Stable cost sharing in production allocation games," Working Papers 1402, University of Windsor, Department of Economics.
    6. Balázs Sziklai & Tamás Fleiner & Tamás Solymosi, 2014. "On the Core of Directed Acyclic Graph Games," IEHAS Discussion Papers 1418, Institute of Economics, Centre for Economic and Regional Studies, Hungarian Academy of Sciences.
    7. Xiaojin Sun & Kwok Ping Tsang, 2013. "Housing Markets, Regulations and Monetary Policy," Working Papers e07-45, Virginia Polytechnic Institute and State University, Department of Economics.
    8. Borkotokey, Surajit & Kumar, Rajnish & Sarangi, Sudipta, 2015. "A solution concept for network games: The role of multilateral interactions," European Journal of Operational Research, Elsevier, vol. 243(3), pages 912-920.
    9. Uhan, Nelson A., 2015. "Stochastic linear programming games with concave preferences," European Journal of Operational Research, Elsevier, vol. 243(2), pages 637-646.
    10. Eric Bahel, 2016. "On the core and bargaining set of a veto game," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(3), pages 543-566, August.
    11. Rosenthal, Edward C., 2017. "A cooperative game approach to cost allocation in a rapid-transit network," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 64-77.

    More about this item

    Keywords

    Game theory; Shortest paths; Network design;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:224:y:2013:i:1:p:132-140. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/locate/eor .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.