A probabilistic approach to the game of guessing in a random environment

A. P. Kovalevskii

Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 1, pp. 35-51

Résumé

The following game of two persons is formalized and solved in the paper. Player 1 is asked a question. Player 2 knows the correct answer. Moreover, both players know all possible answers and their a priori probabilities. Player 2 must choose a subset of the given cardinality of deception answers. Player 1 chooses one of the proposed answers. Player 1 wins one from Player 2 if he/she guessed the correct answer and zero otherwise. This game is reduced to a matrix game. However, the game matrix is of large dimension, so the classical method based on solving a pair of dual linear programming problems cannot be implemented for each individual problem. Therefore, it is necessary to develop a method to radically reduce the dimension. The whole set of such games is divided into two classes. The superuniform class of games is characterized by the condition that the largest of the a priori probabilities is greater than the probability of choosing an answer at random, and the subuniform class corresponds to the opposite inequality — each of the a priori probabilities when multiplied by the total number of answers presented to Player 1 does not exceed one. For each of these two classes, the solving the extended matrix game is reduced to solving a linear programming problem of a much smaller dimension. For the subuniform class, the game is reformulated in terms of probability theory. The condition for the optimality of a mixed strategy is formulated using the Bayes theorem. For the superuniform class, the solution of the game uses an auxiliary problem related to the subuniform class. For both classes, we prove results on the probabilities of guessing the correct answer when using optimal mixed strategies by both players. We present algorithms for obtaining these strategies. The optimal mixed strategy of Player 1 is to choose an answer at random in the subuniform class and to choose the most probable answer in the superuniform class. Optimal mixed strategies of Player 2 have much more complex structure. Bibliogr. 7.

Détail

Mots-clés : matrix game, equiprobable distribution
Keywords: Bayes' theorem, guessing probability, solution in pure strategies, solution in mixed strategies.

Bibliographie

[1] Borovkov A. A., Mathematical statistics, Gordon and Breach, New York, 1998, 570 pp. | MR | Zbl

[2] Bradley S. P., Hax A. C., Magnanti T. L., Applied mathematical programming, Addison-Wesley, Boston, 1977, 716 pp. | MR

[3] Hörner J., Rosenberg D., Solan E., Vieille N., “On a Markov game with one-sided information”, Oper. Res., 58:4-2 (2010), 1107–1115 | DOI | MR | Zbl

[4] Li S., Chen M., Wang Y., Wu Q., “A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making”, Inf. Sci., 594 (2022), 305–321 | DOI

[5] Lipton R. J., Young N. E., “Simple strategies for large zero-sum games with applications to complexity theory”, Proc. 26th Annu. ACM Symp. Theory of Computing (Montreal, Canada, May 23–25, 1994), ACM, New York, 1994, 734–740 | Zbl

[6] Neumann J., Morgenstern O., Theory of games and economic behavior. Princeton: Princeton Univ. Press, 2007, 776 pp. | MR

[7] Wei Ch.-Y., Lee Ch.-W., Zhang M., Luo H., “Last-iterate convergence of decentralized optimistic gradient descent-ascent in infinite-horizon competitive Markov games”, Proc. Mach. Learn. Res., 134 (2021), 4259–4299