Irrigation game

Irrigation games are cooperative games which model cost sharing problems on networks (more precisely, on rooted trees). The irrigation game is a transferable utility game assigned to a cost-tree problem. A common example of this cost-tree problems are the irrigation networks. The irrigation ditch is represented by a graph, its nodes are water users, the edges are sections of the ditch. There is a cost of maintaining the ditch (each section has an own maintenance cost), and we are looking for the fair division of the costs among the users. The irrigation games are mentioned first by Aadland and Kolpin 1998, but the formal concept and the characterization of the game class is introduced by Márkus et al. 2011.

Mathematical definition

The definition of Márkus et al. 2011 is the following: A graph is a pair $G=(V;A)$, where the elements of $V$ are called vertices or nodes, and $A$ stands for the ordered pairs of vertices, called arcs or edges. A rooted tree is a graph in which any two vertices are connected by exactly one simple path, and one vertex has been designated the root, in which case the edges have a natural orientation, away from the root. The tree-order is the partial ordering on the vertices of a rooted tree with $i\leq j$, if the unique path from the root to $j$ passes through $i$. For any $e\in A,$ $e={\overline {ij}}$ means $e$ is an edge between vertices $i;j\in V$ such that $i\leq j$.

Let $c:A\rightarrow \mathbb {R} _{+}$. Then $c$ and $(G;c$) are called cost function and cost-tree respectively: for any $e\in A,$ $e={\overline {ij}},$ $c_{e}$ is the cost of joining player $j$ to player $i$.

Assume that the cost-tree problems have fixed, at least two, number of players ($\#V\geq 3,\#N\geq 2$). Let $(G;c)$ be a cost-tree, and $N$ be the set of the players (the vertices but the root). Consider an $S\subseteq N$ non-empty coalition, then the cost of connecting the players of $S$ to the root is given by the cost of the minimal rooted tree which covers coalition $S$. By this method for each cost-tree we can define a game, called irrigation game. Formally:

Definition (Irrigation game): For any cost-tree $(G;c)$, let $N=V\setminus \{root\}$ be the player set, and for any coalition $S$ (the empty sum is 0) let

$v_{(G;c)}(S)=\sum \limits _{e\in A_{s}}c(e).$

Example

The above graph represents a simple irrigation game played by three players. $G=(V,A)$ is as follows: $V=\{root,1,2,3\},A=\{{\overline {root1}},{\overline {root2}},{\overline {23}}\}$, and the cost function $c$ is defined as $c({\overline {root1}})=11,\ \ c({\overline {root2}})=5$ and $c({\overline {23}})=7$.

Then the irrigation game is the following: $v_{(G;c)}(\emptyset )=0$, $v_{(G;c)}(\{1\})=11$, $v_{(G;c)}(\{2\})=5$, $v_{(G;c)}(\{3\})=7$, $v_{(G;c)}(\{1,2\})=16$, $v_{(G;c)}(\{1,3\})=23$, $v_{(G;c)}(\{2,3\})=12$, $v_{(G;c)}(\{1,2,3\})=23.$

Properties and Results

Márkus et al. 2011 reported several important properties of the class of the irrigation games. First, the well-known class of the airport games is a proper subset of the class of irrigation games, since the airport games are defined on special rooted trees, on chains (see: Airport problem). Second, the class of irrigation games is a non-convex cone which is a proper subset of the finite convex cone spanned by the duals of the unanimity games, therefore every irrigation game is concave.

Márkus et al. 2011 also extended the Shapley and Young axiomatizations of the Shapley value to the class of irrigation games and showed that the Shapley value of an irrigation game is always in the core of the game.

References

Aadland D, Kolpin V (1998). Shared irrigation costs: An empirical and axiomatic analysis. Mathematica Social Sciences 35:203-218

Márkus J, Pintér M, Radványi A (2011). The Shapley value for airport and irrigation games. MPRA Paper No. 30031 http://mpra.ub.uni-muenchen.de/30031/