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.
References
- 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
- V. Mazalov. Mathematical theory of games and its applications. Saint Peterburg: Lan, 2010, 446 p. (in Russian).
Received 30.03.2015