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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$$V=xA{y}^T$$

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

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

$$\begin{gathered} V_a=\underset{x}{min}\underset{y}{max}xA{y}^T \\ {V}_b=\underset{y}{max}\underset{x}{min}xA{y}^T \end{gathered}$$

Утверждение: $V_a=V_b$.

Доказательство. Запишем матрицу $A^{\prime }$, приписав к $A$ справа единичную матрицу:

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

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

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

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

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

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

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

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

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

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