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. This research has been done while the third author was visiting Tinbergen Institute at the Free University, Amsterdam. The research is part of the Research Programme “Strategic and Cooperative Decision Making” at the Department of Econometrics. Financial support from the Netherlands Organization for Scientific Research (NWO) in the framework of the Russian-Dutch programme for scientific cooperation, is gratefully acknowledged. The third author also appreciates partial financial support from the Russian Leading Scientific Schools Fund (grant 80.2003.6) and Russian Humanitarian Scientific Fund (grant 02-02-00189a). We thank three anonymous referees for their valuable comments.