IDEAS home Printed from https://ideas.repec.org/a/eee/matsoc/v58y2009i1p121-131.html
   My bibliography  Save this article

Network flow problems and permutationally concave games

Author

Listed:
  • Trudeau, Christian

Abstract

We examine network problems where agents have to be connected to a source in order to obtain goods, and in which costs on different arcs are a function of the flow of goods. When all cost functions are concave, the resulting game might have an empty core. We introduce a set of problems with concave functions, called the ordered quasi-symmetric congestion problems. We show that they generate permutationally concave games, a weakening of the concept of concavity, that ensures non-emptiness of the core.

Suggested Citation

  • Trudeau, Christian, 2009. "Network flow problems and permutationally concave games," Mathematical Social Sciences, Elsevier, vol. 58(1), pages 121-131, July.
    • Handle: RePEc:eee:matsoc:v:58:y:2009:i:1:p:121-131
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0165-4896(09)00004-3
    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. Quant, Marieke & Borm, Peter & Reijnierse, Hans, 2006. "Congestion network problems and related games," European Journal of Operational Research, Elsevier, vol. 172(3), pages 919-930, August.
    2. Dutta, Bhaskar & Kar, Anirban, 2004. "Cost monotonicity, consistency and minimum cost spanning tree games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 223-248, August.
    3. Meca, Ana & Timmer, Judith & Garcia-Jurado, Ignacio & Borm, Peter, 2004. "Inventory games," European Journal of Operational Research, Elsevier, vol. 156(1), pages 127-139, July.
      • Meca-Martinez, A. & Timmer, J.B. & Garcia-Jurado, I. & Borm, P.E.M., 1999. "Inventory Games," Discussion Paper 1999-53, Tilburg University, Center for Economic Research.
      • Meca-Martinez, A. & Timmer, J.B. & Garcia-Jurado, I. & Borm, P.E.M., 1999. "Inventory Games," Other publications TiSEM 21f26b3f-7fae-4f19-908f-a, Tilburg University, School of Economics and Management.
      • Meca, A. & Timmer, J.B. & Garcia-Jurado, I. & Borm, P.E.M., 2004. "Inventory games," Other publications TiSEM 49368f2d-02fc-49c9-9d74-8, Tilburg University, School of Economics and Management.
    4. Willard I. Zangwill, 1968. "Minimum Concave Cost Flows in Certain Networks," Management Science, INFORMS, vol. 14(7), pages 429-450, March.
    5. Bas van Velzen & Herbert Hamers, 2003. "On the balancedness of relaxed sequencing games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 57(2), pages 287-297, May.
    6. van Velzen, Bas, 2006. "Sequencing games with controllable processing times," European Journal of Operational Research, Elsevier, vol. 172(1), pages 64-85, July.
    7. Ichiishi, Tatsuro, 1981. "Super-modularity: Applications to convex games and to the greedy algorithm for LP," Journal of Economic Theory, Elsevier, vol. 25(2), pages 283-286, October.
    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. Trudeau, Christian, 2014. "Minimum cost spanning tree problems with indifferent agents," Games and Economic Behavior, Elsevier, vol. 84(C), pages 137-151.
    2. Eric Bahel & Christian Trudeau, 2018. "Stable cost sharing in production allocation games," Review of Economic Design, Springer;Society for Economic Design, vol. 22(1), pages 25-53, June.
    3. Leanne Streekstra & Christian Trudeau, 2024. "Stable source connection and assignment problems as multi-period shortest path problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 53(3), pages 939-975, September.

    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. Gerichhausen, Marloes & Hamers, Herbert, 2009. "Partitioning sequencing situations and games," European Journal of Operational Research, Elsevier, vol. 196(1), pages 207-216, July.
    2. van Velzen, S. & Hamers, H.J.M. & Norde, H.W., 2005. "A Note on Permutationally Convex Games," Discussion Paper 2005-83, Tilburg University, Center for Economic Research.
    3. Trudeau, Christian & Vidal-Puga, Juan, 2020. "Clique games: A family of games with coincidence between the nucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 8-14.
    4. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Other publications TiSEM 2bddbf5c-c56d-4b10-ba47-5, Tilburg University, School of Economics and Management.
    5. Heuvel, Wilco van den & Borm, Peter & Hamers, Herbert, 2007. "Economic lot-sizing games," European Journal of Operational Research, Elsevier, vol. 176(2), pages 1117-1130, January.
    6. Gerichhausen, M. & Hamers, H.J.M., 2007. "Partitioning Sequencing Situations and Games," Discussion Paper 2007-40, Tilburg University, Center for Economic Research.
    7. Bergantiños, G. & Gómez-Rúa, M. & Llorca, N. & Pulido, M. & Sánchez-Soriano, J., 2014. "A new rule for source connection problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 780-788.
    8. Drechsel, J. & Kimms, A., 2010. "Computing core allocations in cooperative games with an application to cooperative procurement," International Journal of Production Economics, Elsevier, vol. 128(1), pages 310-321, November.
    9. Ciftci, B.B., 2009. "A cooperative approach to sequencing and connection problems," Other publications TiSEM b0f08a17-4734-4d57-ad66-f, Tilburg University, School of Economics and Management.
    10. repec:ems:eureir:1796 is not listed on IDEAS
    11. Michel Grabisch, 2011. "Ensuring the boundedness of the core of games with restricted cooperation," Annals of Operations Research, Springer, vol. 191(1), pages 137-154, November.
    12. Nunez, Marina & Rafels, Carles, 2003. "Characterization of the extreme core allocations of the assignment game," Games and Economic Behavior, Elsevier, vol. 44(2), pages 311-331, August.
    13. 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.
    14. Padilla Tinoco, Silvia Valeria & Creemers, Stefan & Boute, Robert N., 2017. "Collaborative shipping under different cost-sharing agreements," European Journal of Operational Research, Elsevier, vol. 263(3), pages 827-837.
    15. Grabisch, Michel & Sudhölter, Peter, 2014. "On the restricted cores and the bounded core of games on distributive lattices," European Journal of Operational Research, Elsevier, vol. 235(3), pages 709-717.
    16. Dietzenbacher, Bas, 2018. "Bankruptcy games with nontransferable utility," Mathematical Social Sciences, Elsevier, vol. 92(C), pages 16-21.
    17. Brânzei, R. & Dimitrov, D.A. & Tijs, S.H., 2002. "Convex Fuzzy Games and Participation Monotonic Allocation Schemes," Discussion Paper 2002-13, Tilburg University, Center for Economic Research.
    18. Dutta, Bhaskar & Mishra, Debasis, 2012. "Minimum cost arborescences," Games and Economic Behavior, Elsevier, vol. 74(1), pages 120-143.
    19. Bergantiños, Gustavo & Navarro, Adriana, 2019. "Characterization of the painting rule for multi-source minimal cost spanning tree problems," MPRA Paper 93266, University Library of Munich, Germany.
    20. Cortés, Pablo & Muñuzuri, Jesús & Guadix, José & Onieva, Luis, 2013. "Optimal algorithm for the demand routing problem in multicommodity flow distribution networks with diversification constraints and concave costs," International Journal of Production Economics, Elsevier, vol. 146(1), pages 313-324.
    21. Hark‐Chin Hwang & Wilco van den Heuvel, 2012. "Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 244-253, April.

    More about this item

    Keywords

    Stability Core Network Concavity;

    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:matsoc:v:58:y:2009:i:1:p:121-131. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/505565 .

    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.