IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v191y2021ics0022053120301617.html

Hyperadditive games and applications to networks or matching problems

Author

Listed:
  • Bahel, Eric

Abstract

For the class of cooperative games with transferable utility, we introduce and study the notion of hyperadditivity, a new cohesiveness property weaker than convexity and stronger than superadditivity. It is first established that every hyperadditive game is balanced: we propose a formula allowing to compute some core allocations; and this leads to the definition of a single-valued solution that satisfies core selection for hyperadditive games. This new solution coincides with the Shapley value on the subclass of convex games. Furthermore, we prove that the bargaining set of a hyperadditive game is equal to its core. It is shown that many well-known economic applications satisfy hyperadditivity. Our work extends (and gives a unifying explanation for) various results found in the literature on network games, assignment games and convex games. In addition, some new results are derived for these respective families of games.

Suggested Citation

  • Bahel, Eric, 2021. "Hyperadditive games and applications to networks or matching problems," Journal of Economic Theory, Elsevier, vol. 191(C).
    • Handle: RePEc:eee:jetheo:v:191:y:2021:i:c:s0022053120301617
    DOI: 10.1016/j.jet.2020.105168
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053120301617
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2020.105168?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Muto, S. & Nakayama, M. & Potters, J.A.M. & Tijs, S.H., 1988. "On big boss games," Other publications TiSEM 488a314a-179c-4628-91e6-7, Tilburg University, School of Economics and Management.
    2. TamÂs Solymosi, 1999. "On the bargaining set, kernel and core of superadditive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 28(2), pages 229-240.
    3. Trudeau, Christian & Vidal-Puga, Juan, 2017. "On the set of extreme core allocations for minimal cost spanning tree problems," Journal of Economic Theory, Elsevier, vol. 169(C), pages 425-452.
    4. Shapley, Lloyd S. & Shubik, Martin, 1969. "On market games," Journal of Economic Theory, Elsevier, vol. 1(1), pages 9-25, June.
    5. Shapley, Lloyd S & Shubik, Martin, 1969. "On the Core of an Economic System with Externalities," American Economic Review, American Economic Association, vol. 59(4), pages 678-684, Part I Se.
    6. Roger B. Myerson, 1977. "Graphs and Cooperation in Games," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 225-229, August.
    7. Bahel, Eric & Trudeau, Christian, 2019. "Stability and fairness in the job scheduling problem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 1-14.
    8. Eric Bahel & Christian Trudeau, 2017. "Minimum incoming cost rules for arborescences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(2), pages 287-314, August.
    9. Marina Núñez & Carles Rafels, 1998. "On extreme points of the core and reduced games," Annals of Operations Research, Springer, vol. 84(0), pages 121-133, December.
    10. Juan J. Vidal-Puga, 2004. "Bargaining with commitments," International Journal of Game Theory, Springer;Game Theory Society, vol. 33(1), pages 129-144, January.
    11. Rosenthal, Edward C., 2013. "Shortest path games," European Journal of Operational Research, Elsevier, vol. 224(1), pages 132-140.
    12. Herings, P.J.J. & van der Laan, G. & Talman, A.J.J. & Yang, Z., 2010. "The average tree solution for cooperative games with communication structure," Games and Economic Behavior, Elsevier, vol. 68(2), pages 626-633, March.
    13. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    14. Robert Wilson, 2005. "Information, efficiency, and the core of an economy," Studies in Economic Theory, in: Dionysius Glycopantis & Nicholas C. Yannelis (ed.), Differential Information Economies, pages 55-64, Springer.
    15. Bergantinos, Gustavo & Vidal-Puga, Juan J., 2007. "A fair rule in minimum cost spanning tree problems," Journal of Economic Theory, Elsevier, vol. 137(1), pages 326-352, November.
    16. Dutta, Bhaskar & Mishra, Debasis, 2012. "Minimum cost arborescences," Games and Economic Behavior, Elsevier, vol. 74(1), pages 120-143.
    17. Crawford, Vincent P & Knoer, Elsie Marie, 1981. "Job Matching with Heterogeneous Firms and Workers," Econometrica, Econometric Society, vol. 49(2), pages 437-450, March.
    18. Gul, Faruk, 1989. "Bargaining Foundations of Shapley Value," Econometrica, Econometric Society, vol. 57(1), pages 81-95, January.
    19. Tijs, Stef & Borm, Peter & Lohmann, Edwin & Quant, Marieke, 2011. "An average lexicographic value for cooperative games," European Journal of Operational Research, Elsevier, vol. 213(1), pages 210-220, August.
    20. Morton Davis & Michael Maschler, 1965. "The kernel of a cooperative game," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 12(3), pages 223-259, September.
    21. Bahel, Eric & Trudeau, Christian, 2014. "Stable lexicographic rules for shortest path games," Economics Letters, Elsevier, vol. 125(2), pages 266-269.
    22. Bahel, Eric & Trudeau, Christian, 2014. "Stable lexicographic rules for shortest path games," Economics Letters, Elsevier, vol. 125(2), pages 266-269.
    23. Bahel, Eric & Trudeau, Christian, 2019. "A cost sharing example in which subsidies are necessary for stability," Economics Letters, Elsevier, vol. 185(C).
    24. Montez, João, 2014. "One-to-many bargaining when pairwise agreements are non-renegotiable," Journal of Economic Theory, Elsevier, vol. 152(C), pages 249-265.
    25. 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.
    26. Casajus, André & Yokote, Koji, 2017. "Weak differential marginality and the Shapley value," Journal of Economic Theory, Elsevier, vol. 167(C), pages 274-284.
    27. Casajus, André & Huettner, Frank, 2014. "Weakly monotonic solutions for cooperative games," Journal of Economic Theory, Elsevier, vol. 154(C), pages 162-172.
    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. Ata Atay & Eric Bahel & Tamás Solymosi, 2023. "Matching markets with middlemen under transferable utility," Annals of Operations Research, Springer, vol. 322(2), pages 539-563, March.
    2. Ata Atay & Marina N'u~nez & Tam'as Solymosi, 2024. "A many-to-one job market: more about the core and the competitive salaries," Papers 2404.04847, arXiv.org.
    3. Pongou, Roland & Tondji, Jean-Baptiste, 2024. "The reciprocity set," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    4. Atay, Ata & Núñez, Marina & Solymosi, Tamás, 2026. "A note on the non-coincidence of the core and the bargaining set in many-to-one assignment markets," Games and Economic Behavior, Elsevier, vol. 156(C), pages 58-63.
    5. Bahel, Eric & Trudeau, Christian & Wang, Haoyu, 2026. "Preconvex games," Games and Economic Behavior, Elsevier, vol. 155(C), pages 250-266.

    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. Trudeau, Christian & Vidal-Puga, Juan, 2017. "On the set of extreme core allocations for minimal cost spanning tree problems," Journal of Economic Theory, Elsevier, vol. 169(C), pages 425-452.
    2. 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.
    3. Bahel, Eric & Gómez-Rúa, María & Vidal-Puga, Juan, 2020. "Stability in shortest path problems," MPRA Paper 98504, University Library of Munich, Germany.
    4. Grabisch, Michel & Sudhölter, Peter, 2018. "On a class of vertices of the core," Games and Economic Behavior, Elsevier, vol. 108(C), pages 541-557.
    5. Bahel, Eric & Gómez-Rúa, María & Vidal-Puga, Juan, 2024. "Stable and weakly additive cost sharing in shortest path problems," Journal of Mathematical Economics, Elsevier, vol. 110(C).
    6. Funaki, Yukihiko & Núñez, Marina, 2024. "Some advances in cooperative game theory: Indivisibilities, externalities and axiomatic approach," Journal of Mathematical Economics, Elsevier, vol. 115(C).
    7. 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.
    8. Bergantiños, Gustavo & Vidal-Puga, Juan, 2020. "Cooperative games for minimum cost spanning tree problems," MPRA Paper 104911, University Library of Munich, Germany.
    9. Bahel, Eric & Trudeau, Christian, 2019. "A cost sharing example in which subsidies are necessary for stability," Economics Letters, Elsevier, vol. 185(C).
    10. 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.
    11. Eric Bahel & María Gómez-Rúa & Juan Vidal-Puga, 2025. "Merge-proofness and cost solidarity in shortest path games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 65(2), pages 475-485, September.
    12. Gustavo Bergantiños & Juan Vidal-Puga, 2021. "A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 12(1), pages 73-100, March.
    13. Takaaki Abe & Satoshi Nakada, 2023. "Core stability of the Shapley value for cooperative games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 60(4), pages 523-543, May.
    14. Xu Lang & Zaifu Yang, 2021. "Reduced-Form Allocations for Multiple Indivisible Objects under Constraints," Discussion Papers 21/04, Department of Economics, University of York.
    15. Eric Bahel & Christian Trudeau, 2016. "From spanning trees to arborescences: new and extended cost sharing solutions," Working Papers 1601, University of Windsor, Department of Economics.
    16. Atay, Ata & Núñez, Marina & Solymosi, Tamás, 2026. "A note on the non-coincidence of the core and the bargaining set in many-to-one assignment markets," Games and Economic Behavior, Elsevier, vol. 156(C), pages 58-63.
    17. Bahel, Eric & Trudeau, Christian, 2019. "Stability and fairness in the job scheduling problem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 1-14.
    18. Alexander Kovalenkov & Myrna Wooders, 2003. "Advances in the theory of large cooperative games and applications to club theory; the side payments case," Chapters, in: Carlo Carraro (ed.), The Endogenous Formation of Economic Coalitions, chapter 1, Edward Elgar Publishing.
    19. Eric Bahel & Christian Trudeau, 2017. "Minimum incoming cost rules for arborescences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(2), pages 287-314, August.
    20. Robert P. Gilles & Lina Mallozzi, 2025. "Gately values of cooperative games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 79(3), pages 723-758, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    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:jetheo:v:191:y:2021:i:c:s0022053120301617. 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/622869 .

    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.