Stable families of coalitions for network resource allocation problems - Vladimir Gurvich; Sergei Schreider (Statistics, Optimization & Information Computing, 2014)
A very common question appearing in resource management is: what is the optimal way of behaviour of the agents and distribution of limited resources. Is any form of cooperation more preferable strategy than pure competition? How cooperation can be treated in the game theoretic framework: just as one of a set of Pareto optimal solutions or cooperative game theory is a more promising approach? This research is based on results proving the existence of a non-empty K -core, that is, the set of allocations acceptable for the family K of all feasible coalitions, for the case when this family is a set of subtrees of a tree. A wide range of real situations in resource management, which include optimal water, gas and electricity allocation problems, can be modeled using this class of games. Thus, the present research is pursuing two goals: 1. optimality and 2. stability.Firstly, we suggest to players to unify their resources and then we optimize the total payoff using some standard LP technique. The same unification and optimization can be done for any coalition of players, not only for the total one.  However, players may object unification of resources. It may happen when a feasible coalition can guarantee a better result for every coalitionist.  Here we obtain some stability conditions which ensure that this cannot happen for some family K. Such families were characterized by Boros, Gurvich and Vasin [4] as Berge’s normal hypergraphs.  Thus, we obtain a solution which is optimal and stable. From practical point of view, we suggest a distribution of profit that would cause no conflict between players.