Component efficient solutions in line-graph games with applications

Recently, applications of cooperative game theory to economic allocation problems have gained popularity. We investigate a class of cooperative games that generalizes some economic applications with a similar structure. These are the so-called line-graph games being cooperative TU-games in which the players are linearly ordered. Examples of situations that can be modeled like this are sequencing situations and water distribution problems. We define four properties with respect to deleting edges that each selects a unique component efficient solution on the class of line-graph games. We interpret these solutions and properties in terms of dividend distributions, and apply them to economic situations. © 2006 Springer-Verlag.