A Probabilistic Approach to the Game of Guessing in a Random Environment

The following game of two persons is formalized and solved in the paper. Player 1 is askeda question. Player 2 knows the correct answer. Moreover, both players know all possible answersand their a priori probabilities. Player 2 must choose a subset of the given cardinality of deceptionanswers. Player 1 chooses one of the proposed answers. Player 1 wins one from Player 2 if he/sheguessed 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 duallinear programming problems cannot be implemented for each individual problem. Therefore, it isnecessary to develop a method to radically reduce the dimension.

The whole set of such games is divided into two classes. The superuniform class ofgames is characterized by the condition that the largest of the a priori probabilities is greater thanthe probability of choosing an answer at random, and the subuniform class corresponds to theopposite inequality—each of the a priori probabilities when multiplied by the total numberof answers presented to Player 1 does not exceed one. For each of these two classes, the solvingthe extended matrix game is reduced to solving a linear programming problem of a much smallerdimension. For the subuniform class, the game is reformulated in terms of probability theory. Thecondition for the optimality of a mixed strategy is formulated using the Bayes theorem. For thesuperuniform class, the solution of the game uses an auxiliary problem related to the subuniformclass. For both classes, we prove results on the probabilities of guessing the correct answer whenusing optimal mixed strategies by both players. We present algorithms for obtaining thesestrategies. The optimal mixed strategy of Player 1 is to choose an answer at random in thesubuniform class and to choose the most probable answer in the superuniform class. Optimalmixed strategies of Player 2 have much more complex structure.