imperfect-information.md

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

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

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

• Если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет).

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

• Если оба свидетельствуют друг против друга, они получают по 2 года.

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

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

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

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

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

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

• Если партнёр молчит, то лучше его предать и выйти на свободу (иначе — полгода тюрьмы).

• Если партнёр свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе — 10 лет) тюрьмы.

Стратегия «свидетельствовать» строго доминирует над стратегией «молчать», то есть свидетельствовать всегда лучше вне зависимости от действия другого узника. Оба узника приходят к этому выводу и в итоге получают по 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$. Задача