IDEAS home Printed from
   My bibliography  Save this paper

Cooperative Games in Graph Structure


  • Herings P. Jean-Jacques
  • Laan Gerard van der
  • Talman Dolf



By a cooperative game in coalitional structure or shortly coalitional game we mean the standard cooperative non-transferable utility game described by a set of payoffs for each coalition that is a nonempty subset of the grand coalition of all players. It is well-known that balancedness is a sufficient condition for the nonemptiness of the core of such a cooperative non-transferable utility game. For this result any information on the internal organization of the coalition is neglected.In this paper we generalize the concept of coalitional games and allow for organizational structure within coalitions. For a subset of players any arbitrarily given structural relation represented by a graph is allowed for. We then consider non-transferable utility games in which a possibly empty set of payoff vectors is assigned to any graph on every subset of players. Such a game will be called a cooperative game in graph structure or shortly graph game. A payoff vector lies in the core of the game if there is no graph on a group of players which can make all of its members better off.We define the balanced-core of a graph game as a refinement of the core. To do so, for each graph a power vector is determined that depends on the relative positions of the players within the graph. A collection of graphs will be called balanced if to any graph in the collection a positive weight can be assigned such that the weighted power vectors sum up to the vector of ones. A payoff vector lies in the balanced-core if it lies in the core and the payoff vector is an element of payoff sets of all graphs in some balanced collection of graphs. We prove that any balanced graph game has a nonempty balanced-core and therefore a nonempty core. We conclude by some examples showing the usefulness of the concepts of graph games and balanced-core. In particular these examples show a close relationship between solutions to noncooperative games and balanced-core elements of a well-defined graph game. This places the paper in the Nash research program, looking for a unifying theory in which each approach helps to justify and clarify the other.

Suggested Citation

  • Herings P. Jean-Jacques & Laan Gerard van der & Talman Dolf, 2002. "Cooperative Games in Graph Structure," Research Memorandum 011, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
  • Handle: RePEc:unm:umamet:2002011

    Download full text from publisher

    File URL:
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    1. van der Laan, G. & Talman, A.J.J. & Yang, Z., 1994. "Intersection theorems on polytopes," Discussion Paper 1994-20, Tilburg University, Center for Economic Research.
    2. Nash, John, 1953. "Two-Person Cooperative Games," Econometrica, Econometric Society, vol. 21(1), pages 128-140, April.
    3. P. Jean-Jacques Herings, 1997. "An extremely simple proof of the K-K-M-S Theorem," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 10(2), pages 361-367.
    4. Doup, T.M. & Talman, A.J.J., 1987. "A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices," Other publications TiSEM 398740e7-fdc2-41b6-968f-4, Tilburg University, School of Economics and Management.
    5. Gerard van der Laan & Zaifu Yang & Dolf Talman, 1998. "Cooperative games in permutational structure," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 11(2), pages 427-442.
    6. Nowak Andrzej S. & Radzik Tadeusz, 1994. "The Shapley Value for n-Person Games in Generalized Characteristic Function Form," Games and Economic Behavior, Elsevier, vol. 6(1), pages 150-161, January.
    7. Jean Tirole, 1988. "The Theory of Industrial Organization," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262200716, January.
    8. Bouyssou, Denis, 1992. "Ranking methods based on valued preference relations: A characterization of the net flow method," European Journal of Operational Research, Elsevier, vol. 60(1), pages 61-67, July.
    9. Kamiya, K. & Talman, D., 1990. "Variable Dimension Simplicial Algorithm For Balanced Games," Papers 9025, Tilburg - Center for Economic Research.
    10. Ichiishi, Tatsuro & Idzik, Adam, 1991. "Closed Covers of Compact Convex Polyhedra," International Journal of Game Theory, Springer;Game Theory Society, vol. 20(2), pages 161-169.
    Full references (including those not matched with items on IDEAS)

    More about this item


    Economics ;

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    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:unm:umamet:2002011. 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: (Leonne Portz). General contact details of provider: .

    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.