ISSUE 179, article 2


Kibern. vyčisl. teh., 2015, Issue 179, pp 20-34.

Dotsenko Sergey I., PhD (Phys. & Math.), Associate Professor, Department of Operations Research, Faculty of Cybernetics of the Taras Shevchenko National University of Kyiv, Ave. Acad. Glushkov, 4 D, Kyiv, 03187, Ukraine, e-mail:


Introduction. Cooperative game theory is integral part of modern economics. The founder of this theory is Lloyd Shapley, who became Nobel prize winner in economics in 2012. In classical cooperative game theory the characteristic function of the game is rigidly defined and remains unchanged.. The extra players don’t participate in the game immediately, but they provide the connection between the origin players and so, may change the characteristic function of the game. For the extended game the Shapley values are calculated for origin and extra players equally well.

The purpose of this research is aimed at so-called extended games, when the extra players may be inducted into the game.

Results. The Shapley values for extended communication games, based on both forces, coordination game and secretary problem are obtained in explicit form. As accessory result, the theorem on stochastic inequality for Shapley values in the case of player’s non-uniform joining times to coalition is proved and then illustrated by vivid example.

Conclusions. The considered examples vividly illustrate winnings increment effect, stipulated by extra agent induction. This agent is aimed to provide the connection between the other players and is called a connector. Connector’s Shapley value characterizes his fair salary for connection provision. A linear extension function’s method provides the analysis of Shapley value calculation for problems of more sophisticated structure, than delivered above.

Keywords: cooperative game, communicative extension, Shapley value, stochastic inequality, optimal choice problem.

Download full text (ru)!

1 Tijs S. Introduction to game theory. Hindustan book agency. 2003.

2 Owen G. Multilinear Extensions of Games. Management Science. 1972, pp. 64–79.

3 Owen G. Values of Graph-Restricted Games. SIAM J Alg. Disc. Math. 1986, pp. 210–220.

4 Myerson R. Graphs and Cooperation in Games. Math. Op. Res. 1977, pp. 225–229.

5 Shapley L. A value for n-person games. Contributions to the Theory of Games. Princeton University Press. 1953, pp. 307–317.

6 Mazalov V.V. Mathematical game theory and it’s applications. Saint Petersburg: “Lan” 2010, 446 p. (in Russian).

Received 30.09.2014