Игры с неполной информацией

Игры с неполной информацией

Рассмотрим следующую ситуацию, известную как дилемма заключённого:

Двое преступников — А и Б — попались примерно в одно и то же время на сходных преступлениях. Полиция предполагает, что они действовали по сговору, и, изолировав их друг от друга, предлагает им одну и ту же сделку:

Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?

Игры, в которых у игроков (в данном случае — узников) есть некоторая неопределенность относительно действий других игроков (например, из-за одновременности действий), называются играми с неполной информацией.

Данную «игру» можно представить в виде следующей табилцы:

                                   | Б хранит молчание | Б даёт показания |
А хранит молчание | (1, 1) | (10, 0) |
А даёт показания | (0, 10) | (2, 2) |

Пары чисел в ячейках означают сроки, которые получают заключенные А и Б соответственно.

Предположим, что оба преступника заботятся только о минимизации собственного срока заключения. Тогда рассуждения каждого узника будут следующими:

Стратегия «свидетельствовать» строго доминирует над стратегией «молчать», то есть свидетельствовать всегда лучше вне зависимости от действия другого узника. Оба узника приходят к этому выводу и в итоге получают по 2 года каждый.

С точки зрения группы лучше всего хранить молчание и получить по году, так как это уменьшит срок заключения каждого. Такие состояния называются Парето-эффективными, но, как мы видим, они не всегда являются стабильными.

Игры с нулевой суммой

Рассмотрим другой пример игры с неполной информацией: «камень-ножницы-бумага». Эта игра в каком-то смысле более «человечная»: игроки явно соревнуются друг с другом, и им не нужно делать сделки с совестью и предавать друг друга.

Определение. Игра называется с нулевой суммой, если один игрок выигрывает столько, сколько второй проигрывает.

Примечание. Дилемма заключенного — пример игры с ненулевой суммой.

В играх с нулевой суммой исходы можно записывать разницей между выгодой первого и второго игрока:

    | К2 | Н2 | Б2|
К1 | 0 | +1 | -1|
Н1 | -1 | 0 | +1|
Б1 | +1 | -1 | 0 |

Каждая фиксированная стратегия (в данном случае выбор действия — камень, ножницы или бумага), которую может выбрать игрок, называется его чистой стратегией.

Смешанной стратегией игрока называется набор чистых стратегий, задаваемый вероятностями (относительными частотами) выбора соответствующих чистых стратегий. Задача обоих игроков — выбрать смешанную стратегию, максимизирующую свой выигрыш.

Понятно, что в этой игре любая чистая стратегия может быть доминирована (то есть, если всегда делать один и тот же ход, то оппонент сообразит, как побеждать).

Обозначим смешанную стратегию первого игрока за \(x\), а второго игрока за \(y\). Тогда ожидаемый счёт можно записать так:

\[ V = xAy^T \]

Действительно, эта формула раскрывается в \(\sum A_{ij} \cdot x(i) \cdot y(j)\).

Минимаксная теорема. Первый игрок хочет минимизировать это значение, а второй — максимизировать. Обозначим за \(V_a\) и \(V_b\) оптимальные значения, которые удаётся достичь игрокам вне зависимости от действий оппонента, то есть:

\[ V_a = \min_x \max_y xAy^T \\ V_b = \max_y \min_x xAy^T \]

Утверждение: \(V_a = V_b\).

Доказательство. Запишем матрицу \(A'\), приписав к \(A\) справа единичную матрицу:

Будем доказывать от противного: покажем, что ситуация \(V_a < 0 < V_b\) невозможна, а значит для любого \(t\) ситуация невозможна.

Рассмотрим выпуклую оболочку \(C\) её столбцов.

Предположим, что \(\vec{0} \in C\).

Тогда существуют \(z_1, z_2, \ldots z_{n+m}\) такие что \(0 \leq z_i \leq 1\) и \(\sum z_i = 1\) (то есть вероятностное распределение).

$sum_{j=1}^n a_{ij} z_{ij} $

В этой игре оптимальной

Несимметричные игры

Минимаксная теорема

Докажем очень частный случай. Это утверждение оказывается верно, и даже в случае многопользовательских игр и игр с ненулевой суммой, но доказательства этих фактов содержат слишком много матана, чтобы добавлять их навключать сайт по программированию.

Пусть имеется матрица \(A\) размера \(n \times m\). Задача