теория игр, угадывание числа

[mustitz]

Geen в сообщении #991168 писал(а):

Тогда, скажем для $n=4$ полная матрица игры (при рациональных в первом приближении стратегиях отгадывающего) будет такая:

$$\begin{array}{c|cccccccccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 3 & 2 & 2 & 3 & 3 & 4 \\ 2 & 2 & 2 & 3 & 3 & 4 & 1 & 1 & 3 & 2 & 3 & 4 & 2 & 4 & 3 \\ 3 & 3 & 4 & 2 & 4 & 3 & 2 & 3 & 1 & 1 & 4 & 3 & 3 & 2 & 2 \\ 4 & 4 & 3 & 3 & 2 & 2 & 3 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 \end{array}$$

Что-то слишком много стратегий... В силу симметрии для загадывающего можно выделить две стратегии: (1) загадать с вероятностью 50% либо 1, либо 4; (2) загадать с вероятностью 50% либо 2, либо 3. Для отгадывающего получаем такие стратегии
1/4 - 4 Называем с вероятностью 50% либо 1, либо 4. Потом называем 4 (либо 1, если на первом шаге названа 4). На следующем шаге, в силу соображений симметрии, нам все равно, что называть 2 или 3.
1/4 - 3 Называем с вероятностью 50% либо 1, либо 4. Потом называем 3 (либо 2, если на первом шаге названа 4). Этим исчерпываются стратегии, которые начинаются с 1/4, потому как называть вторым шагом 2 нецелесообразно, стратегия будет находится под доминацией стратегии 1/4 - 3.
2/3 - 3 Расшифровывать не буду
2/3 - 4

Соответственно матрица

           1/4       2/3
==============================
1/4 - 4    1.5       3.5
1/4 - 3     2        2.5
2/3 - 3     3        1.5
2/3 - 4     2         2

Мы видим, что стратегия 1/4 - 3 под доминацией стратегии 2/3 - 4, что в общем случае можно попытаться оформить в виде теоремы, типа стратегия, которая начинается с $1/n - (n-1)$, всегда будет под доминацией стратегии, которая начинается с $2/(n-1) - n$.

[vito]

Игра тривиальная.
Входные установки.
1. Игра антагонистическая.
2. Игрок А (загадывающий) имеет только один личный ход.
3. Игрок В (угадывающий) имеет от 1 до n (размерность игры) ходов.

Пусть n =3. Понятно, что А имеет всего 3 стратегии.
Составим матрицу игры.

        A1   A2   A3
B1    3      2       1
B2    2      3       2
B3    1      2       3

Пусть А загадал 1, В назвал 1. Выигрыш В 3.
Пусть А загадал 2, В назвал 1. А говорит что число больше. Игрок В увеличивает значение на единицу и получает выигрыш 2. И т.д.
Стратегия увеличения/уменьшения не имеет никакого значения. Приращение или уменьшение на 1 эквивалентно любой другой (доказать самостоятельно). Имеет значение насколько близко мы оказались к загаданному числу.

Решение.


B=A= {p1= 0.49, p2 = 0.8881784197e-15, p3= 0.49}
V(цена игры) = 2.

То есть мы должны равновероятно выбирать крайние значения, и крайне редко средние.
При этом цена игры будет 2.
Объяснение. Понятно, что стратегия 2 для игрока А невыгодна и он должен ее избегать. Игрок В зная это тоже не будет выбирать эту стратегию. Но в этом случае игра сведется к угадыванию двух крайних чисел. Поэтому игрок А крайне редко, но должен выбирать средние значения.
Подобный принцип распределения стратегий сохраняется для задач любой размерности.