Tag: Dotsenko S.I.

ISSUE 180, article 2

DOI:https://doi.org/10.15407/kvt180.02.015

Kibern. vyčisl. teh., 2015, Issue 179, pp 15-24.

Dotsenko Sergey I., PhD (Phys. & Math.), Senior Researcher, Associate Professor, Department of Operations Research, Faculty of Cybernetics of the Taras Shevchenko National University of Kyiv, Pr. Glushkov, 4 D, Kyiv, 03187, Ukraine, e-mail: sergei204@ukr.net

SOLUTION OF THE PROBLEM OF OPTIMAL CHOICES WITH A GROUP BROWSING BY A GAME-THEORETIC APPROACH

Introduction. The problem of optimal choice in the case when the objects are divided into groups and carried out the simultaneous viewing of candidates in each group was considered by Bruss T. If watching the group of candidates is similar to the classical problem and the group is presented by the best candidate among all previously viewed items (such an element is called a maximum) to make a decision — choose this candidate and finish viewing or reject it and continue — the returning to the previously rejected candidates prohibited.

In this case, the optimal rule for selecting the best candidate is based on the so-called «choice theorem» (or «Bruss theorem»).

For the particular case of two groups the search strategy is trivial — namely to ignore the smaller group and to view the bigger one. However, if this case is considered as two person game, the problem appeared to be intriguing.

The purpose of the article is to find Nash equilibrium for two persons game, associated to group search secretary problem at the following set of rules.

1)  Each player makes his choice at his own set of elements.

2)  At the beginning the set of searched elements are divided at random into two subsets according to uniform distribution.

3)  Each of two players searches the best element (i.e. solve the secretary problem for two groups). After that, the prize is paid to one or two players according to the following rules. If one of the players made his lucky choice and the other one not, then the first one got 1. If the both players made their lucky choice at the same group then they share the price and got 1/2 each. If one of the players got his lucky choice at the first group, and another one at the second group, then the first one got 1, and the second one got nothing.

Results. For the considered game the Bayes-Nash equilibrium is obtained for three different cases. Equilibrium points are shown at two-dimensional diagram. Depending on the problem statement, Nash equilibrium area may take different shapes — either single point (cases 1 and 2) or family of points inside the closed curve (case 3). In first two cases, the slight effect of anarchy is observed.

Conclusion. The general principle, that the game situation solutions are based on even trivial optimization problems, makes these solutions to be complicated. The equilibrium situations of the game were found based on the concept of a complex rational behavior for each of the cases.

Keywords: problem of optimal choice, threshold strategy, group search, Bayes-Nash equilibrium, the price of anarchy.

Download full text (ru)!

References

1. Thomas Bruss. Sum the odds to one and stop. The annals of probability, 2000, vol. 28, no. 3, pp. 1384–1391. https://doi.org/10.1214/aop/1019160340
2. V. Mazalov. Mathematical theory of games and its applications. Saint Peterburg: Lan, 2010, 446 p. (in Russian).

Received 30.03.2015

ISSUE 179, article 2

DOI:https://doi.org/10.15407/kvt179.01.020

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: sergei204@ukr.net

ON GAME-THEORETICAL APPROACH IN ACTION COORDINATION PROBLEMS WITH INFORMATION EXCHANGE

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)!

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

2 Owen G. Multilinear Extensions of Games. Management Science. 1972, pp. 64–79. https://doi.org/10.1287/mnsc.18.5.64

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