Cooperative Games in Graph Structure

P.J.J. Herings, G. van der Laan, A.J.J. Talman

Research output: Working paperDiscussion paperOther research output

285 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationTilburg
PublisherMicroeconomics
Number of pages33
Volume2000-90
Publication statusPublished - 2000

Publication series

NameCentER Discussion Paper
Volume2000-90

Keywords

  • cooperative games
  • graphs

Cite this

Herings, P. J. J., van der Laan, G., & Talman, A. J. J. (2000). Cooperative Games in Graph Structure. (CentER Discussion Paper; Vol. 2000-90). Tilburg: Microeconomics.
Herings, P.J.J. ; van der Laan, G. ; Talman, A.J.J. / Cooperative Games in Graph Structure. Tilburg : Microeconomics, 2000. (CentER Discussion Paper).
@techreport{bab3074501b4480ba8ac48a347ed9d9d,
title = "Cooperative Games in Graph Structure",
abstract = "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.",
keywords = "cooperative games, graphs",
author = "P.J.J. Herings and {van der Laan}, G. and A.J.J. Talman",
note = "Pagination: 33",
year = "2000",
language = "English",
volume = "2000-90",
series = "CentER Discussion Paper",
publisher = "Microeconomics",
type = "WorkingPaper",
institution = "Microeconomics",

}

Herings, PJJ, van der Laan, G & Talman, AJJ 2000 'Cooperative Games in Graph Structure' CentER Discussion Paper, vol. 2000-90, Microeconomics, Tilburg.

Cooperative Games in Graph Structure. / Herings, P.J.J.; van der Laan, G.; Talman, A.J.J.

Tilburg : Microeconomics, 2000. (CentER Discussion Paper; Vol. 2000-90).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Cooperative Games in Graph Structure

AU - Herings, P.J.J.

AU - van der Laan, G.

AU - Talman, A.J.J.

N1 - Pagination: 33

PY - 2000

Y1 - 2000

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

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

KW - cooperative games

KW - graphs

M3 - Discussion paper

VL - 2000-90

T3 - CentER Discussion Paper

BT - Cooperative Games in Graph Structure

PB - Microeconomics

CY - Tilburg

ER -

Herings PJJ, van der Laan G, Talman AJJ. Cooperative Games in Graph Structure. Tilburg: Microeconomics. 2000. (CentER Discussion Paper).