Stable families of coalitions for network resource allocation problems
Abstract
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.References
C. Berge, Graphs and Hypergraphs, Dumond, Paris, English translation, North-Holland, Amsterdam, (1970).
C. Berge, Minimax theorems for normal hypergraphs and balanced hypergraphs - a survey, Annals of Discrete Mathematics, 21, (1984) pp. 3-19.
C.E. Blair and R.G. Jeroslow, The value function of a mixed integer program 1, Mathematical programming, 19, (1977) pp. 121-138.
E. Boros, V. Gurvich and A. Vasin, A stable families of coalitions and normal hypergraphs, RUTCOR Research Report 23-1995, Rutgers University; Mathematical Social Sciences 34 (1997) pp. 107-123.
E. Boros and V. Gurvich, Stable effectivity functions and perfect graphs, Mathematical Social Sciences, 39 (2000) pp. 175-194.
P. Dixon, S. Schreider and G. Wittwer, Combining engineering-based water models with a CGE model, Chapter 2 in Quantitative Tools in Microeconomic Policy Analysis, Pincus, J. (editor), Publisher: Australian Productivity Commission, Canberra (2005) pp. 17 – 30.
R. Egging, S.A. Gabriel, F. Holz and J. Zhuang, A complimentary model for the European natural gas market, Energy policy, 36, (2008) pp. 2385-2414.
S.A. Gabriel, J. Zhuang and S. Kiet A large-scale complimentary model of the North American natural gas market, Energy economics, 27, (2005) pp.639-665.
R.E. Gomory and E.L.,Johnson, The group problem and subadditive functions. In Hu, T.C., Robinson, S.M. (eds), Mathematical Programming, Academic Press, New York, (1973) pp. 157–184.
V. Gurvich and A. Vasin Reconciable sets of coalitions. In: Questions of applied math. Siberian Energetic Institute, Irkutsk, (1977) pp. 20-30 (in Russian).
V. Gurvich and A. Vasin Reconcilable sets of coalitions for normal form games, In "Numerical methods in optimization theory(Applied math.)", Siberian Inst. of Energy, Irkutsk, (1978) pp. 27-38 (in Russian).
V. Gurvich. and S. Schreider, Network supply systems, stable families of coalitions for superadditive TU-games and Berge’s normal hypergraphs, RUTCOR preprint, RRR 20-2010, Rutgers University, (2010) 22 p.
X Hu. and D. Ralph, Using EPECs to model bilevel games inrestructured electricity markets with locational prices, Operations research, 55(5), (2007) pp. 809-827.
R.G. Jeroslow, Cutting plane theory: Disjunctive methods, Annals of discrete mathematics, 1, (1977) pp. 293-330.
R.G. Jeroslow, Cutting plane theory: Algebraic methods, Discrete mathematics, 23, (1978) pp. 121 -150.
E.L. Jonson, Cyclic groups, cutting planes and shortest paths, in Mathematical Programming, Hu, T.C. and Robinson, S. (eds.) Academic Press, (1973) pp. 185-211.
B.J.C. Perera, B. James and M.D.U. Kularathna, M.D.U. Computer Software Tool for Sustainable Water Allocation and Management - REALM. Journal of Environmental Management, 77(4), (2005) pp. 291-300.
D. Ralph, Mathematical programs with complementarity constraints in traffic and telecommunications networks." Royal Society of London, Philosophical Transactions. Mathematical, Physical and Engineering Sciences, 366(1872), (2008) pp. 1973-1987.
S. Schreider, P. Zeephongsekul, B. Abbasi, and M. Fernandes, Game Theoretic Approach for Fertilizer Application: Looking for the Propensity to Cooperate, Annals of Operations Research, 206 (1), (2013) pp. 385-400.
A. Schrijver, On cutting planes, Annals of Discrete mathematics, 9, (1980) pp. 291-296.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
