IDEAS home Printed from https://ideas.repec.org/p/nwu/cmsems/1119.html
   My bibliography  Save this paper

A Linear Programming Framework for Network Games

Author

Listed:
  • A.B. Gamble
  • A.I. Pazgal

Abstract

In this paper we present a linear programming game that is motivated by the assignment game of Shapley and Shubik. This new game is a very natural generalization of many of the network optimization games that have been well studied in the past. We first show that for this general class of games the core is nonempty. In fact any dual optimal solution of the underlying linear programming probem gives rise to a core allocation. We also show that for a particular subclass of games (which include the assignment, max flow and location games) the core exactly coincides with the set of optimal dual solutions. Additionally we study the relationship between this linear programming game and the production game of Owen.

Suggested Citation

  • A.B. Gamble & A.I. Pazgal, 1995. "A Linear Programming Framework for Network Games," Discussion Papers 1119, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    • Handle: RePEc:nwu:cmsems:1119
    as

    Download full text from publisher

    File URL: http://www.kellogg.northwestern.edu/research/math/papers/1119.pdf
    File Function: main text
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Ehud Kalai & Eitan Zemel, 1980. "On Totally Balanced Games and Games of Flow," Discussion Papers 413, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    2. Dov Samet & Eitan Zemel, 1984. "On the Core and Dual Set of Linear Programming Games," Mathematics of Operations Research, INFORMS, vol. 9(2), pages 309-316, May.
    3. Pradeep Dubey & Lloyd S. Shapley, 1982. "Totally Balanced Games Arising from Controlled Programming Problems," UCLA Economics Working Papers 262, UCLA Department of Economics.
    4. Curiel, I. & Tijs, S.H., 1986. "Assignment games and permutation games," Other publications TiSEM c9a47c3b-28d3-4874-b0a2-f, Tilburg University, School of Economics and Management.
    5. Ehud Kalai & Eitan Zemel, 1982. "Generalized Network Problems Yielding Totally Balanced Games," Operations Research, INFORMS, vol. 30(5), pages 998-1008, October.
    6. Xiaotie Deng & Christos H. Papadimitriou, 1994. "On the Complexity of Cooperative Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 257-266, May.
    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. Mariusz Kaleta & Eugeniusz Toczyłowski, 2009. "A cost allocation framework for LP and GLP games," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 19(4), pages 27-46.
    2. Mariusz Kaleta & Eugeniusz Toczylowski, 2009. "A cost allocation framework for lp and glp games," Operations Research and Decisions, Wroclaw University of Technology, Institute of Organization and Management, vol. 4, pages 27-46.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Peter Borm & Herbert Hamers & Ruud Hendrickx, 2001. "Operations research games: A survey," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 9(2), pages 139-199, December.
    2. Csóka, Péter & Herings, P. Jean-Jacques & Kóczy, László Á., 2009. "Stable allocations of risk," Games and Economic Behavior, Elsevier, vol. 67(1), pages 266-276, September.
    3. Nicholas G. Hall & Zhixin Liu, 2010. "Capacity Allocation and Scheduling in Supply Chains," Operations Research, INFORMS, vol. 58(6), pages 1711-1725, December.
    4. Péter Csóka & P. Herings & László Kóczy, 2011. "Balancedness conditions for exact games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 74(1), pages 41-52, August.
    5. Csóka Péter & Pintér Miklós, 2016. "On the Impossibility of Fair Risk Allocation," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 16(1), pages 143-158, January.
    6. Ichiro Nishizaki & Tomohiro Hayashida & Yuki Shintomi, 2016. "A core-allocation for a network restricted linear production game," Annals of Operations Research, Springer, vol. 238(1), pages 389-410, March.
    7. Ichiro Nishizaki & Tomohiro Hayashida & Shinya Sekizaki & Kojiro Furumi, 2023. "A two-stage linear production planning model with partial cooperation under stochastic demands," Annals of Operations Research, Springer, vol. 320(1), pages 293-324, January.
    8. Ichiro Nishizaki & Tomohiro Hayashida & Shinya Sekizaki & Kenta Tanaka, 2023. "Averaged dual solution for linear production games and its characterization," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(2), pages 523-555, June.
    9. Ichiro Nishizaki & Tomohiro Hayashida & Yuki Shintomi, 2016. "A core-allocation for a network restricted linear production game," Annals of Operations Research, Springer, vol. 238(1), pages 389-410, March.
    10. Qizhi Fang & Bo Li & Xiaohan Shan & Xiaoming Sun, 2018. "Path cooperative games," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 211-229, July.
    11. Zhanwen Shi & Erbao Cao, 2020. "Contract farming problems and games under yield uncertainty," Australian Journal of Agricultural and Resource Economics, Australian Agricultural and Resource Economics Society, vol. 64(4), pages 1210-1238, October.
    12. van Gellekom, J. R. G. & Potters, J. A. M. & Reijnierse, J. H. & Engel, M. C. & Tijs, S. H., 2000. "Characterization of the Owen Set of Linear Production Processes," Games and Economic Behavior, Elsevier, vol. 32(1), pages 139-156, July.
    13. Okan Örsan Özener & Özlem Ergun, 2008. "Allocating Costs in a Collaborative Transportation Procurement Network," Transportation Science, INFORMS, vol. 42(2), pages 146-165, May.
    14. Sanchez-Soriano, Joaquin, 2006. "Pairwise solutions and the core of transportation situations," European Journal of Operational Research, Elsevier, vol. 175(1), pages 101-110, November.
    15. Tejada, J. & Borm, P.E.M. & Lohmann, E.R.M.A., 2013. "A Unifying Model for Matching Situations," Other publications TiSEM 18155a8c-1961-495d-a20d-f, Tilburg University, School of Economics and Management.
    16. Giulia Cesari & Roberto Lucchetti & Stefano Moretti, 2017. "Generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 919-939, November.
    17. Ehud Lehrer, 2009. "A new integral for capacities," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 39(1), pages 157-176, April.
    18. Nishizaki, Ichiro & Sakawa, Masatoshi, 2001. "On computational methods for solutions of multiobjective linear production programming games," European Journal of Operational Research, Elsevier, vol. 129(2), pages 386-413, March.
    19. Martí Jané Ballarín, 2023. "The complexity of power indices in voting games with incompatible players," UB School of Economics Working Papers 2023/441, University of Barcelona School of Economics.
    20. Yuto Ushioda & Masato Tanaka & Tomomi Matsui, 2022. "Monte Carlo Methods for the Shapley–Shubik Power Index," Games, MDPI, vol. 13(3), pages 1-14, June.

    More about this item

    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:nwu:cmsems:1119. See general information about how to correct material in RePEc.

    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 bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Fran Walker (email available below). General contact details of provider: https://edirc.repec.org/data/cmnwuus.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.