A Value for Games Defined on Graphs

Abstract

Given a graph <math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'> <mrow> <mi>g</mi><mo>=</mo><mrow><mo>(</mo> <mrow> <mi>V</mi><mo>,</mo><mi>A</mi></mrow> <mo>)</mo></mrow></mrow> </math>, we define a space of subgraphs <i>M</i> with the binary operation of union and the unique decomposition property into blocks. This space allows us to discuss a notion of minimal subgraphs (minimal coalitions) that are of interest for the game. Additionally, a partition of the game is defined in terms of the gain of each block, and subsequently, a solution to the game is defined based on distributing to each player (node and edge) present in each block a payment proportional to their contribution to the coalition.