Geodesic
Stable Families of Coalitions for Network Resource Allocation Problems
Contributions to game theory and management, Tome 4 (2011), pp. 223-230.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 in Boros et al. (1997) 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. 
@article{CGTM_2011_4_a16,
     author = {Vladimir Gurvich and Sergei Schreider},
     title = {Stable {Families} of {Coalitions} for {Network} {Resource} {Allocation} {Problems}},
     journal = {Contributions to game theory and management},
     pages = {223--230},
     publisher = {mathdoc},
     volume = {4},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2011_4_a16/}
}
TY  - JOUR
AU  - Vladimir Gurvich
AU  - Sergei Schreider
TI  - Stable Families of Coalitions for Network Resource Allocation Problems
JO  - Contributions to game theory and management
PY  - 2011
SP  - 223
EP  - 230
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2011_4_a16/
LA  - en
ID  - CGTM_2011_4_a16
ER  - 
%0 Journal Article
%A Vladimir Gurvich
%A Sergei Schreider
%T Stable Families of Coalitions for Network Resource Allocation Problems
%J Contributions to game theory and management
%D 2011
%P 223-230
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2011_4_a16/
%G en
%F CGTM_2011_4_a16
Vladimir Gurvich; Sergei Schreider. Stable Families of Coalitions for Network Resource Allocation Problems. Contributions to game theory and management, Tome 4 (2011), pp. 223-230. http://geodesic.mathdoc.fr/item/CGTM_2011_4_a16/

[1] North-Holland, Amsterdam, 1973 | Zbl

[2] Berge C., “Minimax theorems for normal hypergraphs and balanced hypergraphs — a survey”, Annals of Discrete Mathematics, 21 (1984), 3–19 | MR | Zbl

[3] Blair C. E., Jeroslow R. G., “The value function of a mixed integer program, 1”, Mathematical programming, 19 (1977), 121–138 | MR | Zbl

[4] Boros E., Gurvich V., Vasin A., “Stable families of coalitions and normal hypergraphs”, Mathematical Social Sciences, 34 (1997), 107–123 | DOI | MR | Zbl

[5] Boros E., Gurvich V., “Stable effectivity functions and perfect graphs”, Mathematical Social Sciences, 39 (2000), 175–194 | DOI | MR | Zbl

[6] Dixon P., Schreider S., Wittwer G., “Combining engineering-based water models with a CGE model”, Quantitative Tools in Microeconomic Policy Analysis, Chapter 2, ed. Pincus J., Australian Productivity Commission, Canberra, 2005, 17–30

[7] Egging R., Gabriel S. A., Holz F., Zhuang J., “A complimentary model for the European natural gas market”, Energy policy, 36 (2008), 2385–2414 | DOI

[8] Gabriel S. A., Zhuang J., Kiet S., “A large-scale complimentary model of the North American natural gas market”, Energy economics, 27 (2005), 639–665 | DOI

[9] Gomory R. E., Johnson E. L., “The group problem and subadditive functions”, Mathematical Programming, eds. Hu T. C., Robinson S. M., Academic Press, New York, 1973, 157–184 | MR

[10] Gurvich V., Vasin A., “Reconciable sets of coalitions”, Questions of applied math., Siberian Energetic Institute, Irkutsk, 1977, 20–30 (in Russian) | MR

[11] Gurvich V., Vasin A., “Reconcilable sets of coalitions for normal form games”, Numerical methods in optimization theory (Applied math.), Siberian Inst. of Energy, Irkutsk, 1978, 27–38 (in Russian) | MR

[12] Gurvich V., Schreider S., Network supply systems, stable families of coalitions for superadditive TU-games and Berge's normal hypergraphs, RUTCOR preprint, RRR 20-2010, November, Rutgers University, 2010, 22 pp.

[13] Hu X., Ralph D., “Using EPECs to model bilevel games inrestructured electricity markets with locational prices”, Operations research, 55:5 (2007), 809–827 | DOI | Zbl

[14] Jeroslow R. G., “Cutting plane theory: Disjunctive methods”, Annals of discrete mathematics, 1 (1977), 293–330 | DOI | Zbl

[15] Jeroslow R. G., “Cutting plane theory: Algebraic methods”, Discrete mathematics, 23 (1978), 121–150 | DOI | Zbl

[16] Jonson E. L., “Cyclic groups, cutting planes and shortest paths”, Mathematical Programming, eds. Hu T. C., Robinson S., Academic Press, 1973, 185–211

[17] Perera B. J. C., James B., Kularathna M. D. U., “Computer Software Tool for Sustainable Water Allocation and Management — REALM”, Journal of Environmental Management, 77:4 (2005), 291–300 | DOI

[18] Ralph D., “Mathematical programs with complementarity constraints in traffic and telecommunications networks”, Royal Society of London, Philosophical Transactions. Mathematical, Physical and Engineering Sciences, 366(1872) (2008), 1973–1987 | DOI | Zbl

[19] Schreider S., Zeephongsekul P., Abbasi B., Game theoretic approach for fertiliser application: propensity to cooperate, how important is it?, MODSIM2011, 2011, submitted

[20] Schrijver A., “On cutting planes”, Annals of Discrete mathematics, 9 (1980), 291–296 | DOI | Zbl