Общие вопросы теории игр
дата публикации: 2016-07-17

Рассмотрение теории игр начнем с простого классического примера: задачи о двух заключенных. Два друга украли из квартиры одного богатого человека чемодан с деньгами, который спрятали, но тут им на хвост села полиция, и они были вынуждены угнать машину, чтобы скрыться, однако скрыться не удалось, и они попали в отделение. Следователь был ушлым человеком и посадил двух друзей по разным камерам, затем начал допрос. Обоим заключенным он назвал возможные сроки отсидки в случае, если их признают виновными, не забыл и о благодарности, если они будут сотрудничать с полицией, ведь доказательств того, что это именно они украли чемодан с деньгами, не было. Вот если докажут, что они оба украли чемодан, получат оба по 6 лет. Если один другого "сольет", то тот, кого сольют, получит 6 лет, а второго освободят за сотрудничество. А вот не сознаются, то получат по два года каждый за угон автомобиля. Как же будет развиваться ситуация, как будут мыслить заключенные? Попробуем предположить. Перед каждым заключенным дилемма: сливать или не сливать своего "друга". Первый думает: если не сливать, то возможны два варианта: он тоже будет молчать, тогда получу 2 года, а если он сольет, то получу 6 лет, то есть среднее 4 года, да еще и он выйдет, наверняка деньги, которые припрятали, украдет и растратит, пока я сижу, а вот если его слить, то тоже два варианта: он будет молчать, тогда сразу освобожусь, заберу деньги и потрачу, а если он сольет, то получим по 6 лет, то есть среднее 3 года. Получается выгоднее сливать. Так же будет рассуждать и второй, и получат оба по 6 лет. А ведь если бы договорились и верили друг другу, то получили бы по 2 года всего. Теперь запишем все наши рассуждения в нормальной форме.

  заключенный 1
не сливает
заключенный 1
сливает
заключенный 2
не сливает
(2,2) (0,6)
заключенный 2
сливает
(6,0) (6,6)

 

Вышеприведенная задача является простейшей игрой. Для дальнейших рассуждений рассмотрим некоторые важные определения.

Кооперативные (некооперативные) игры – это игры, в которых участники договариваются (не договариваются) относительно совместных действий. В результате участники игры могут разбиваться на коалиции. В качестве примера кооперативной игры может выступать процесс голосования акционерами какого-либо предприятия за конкретное решение. Если акционеров много, то они начинают объединяться в коалиции.

Симметричные (несимметричные) игры – это игры, в которых соответствующие стратегии игроков будут (не будут) равны. То есть, если два игрока поменяются местами, и выполнят те же самые стратегии, то результат в случае симметричной игры будет такой же. Примером симметричной игры выступает рассмотренная ранее задача о заключенных ввиду того, что при выборе одинаковых стратегий выигрыши обоих заключенных идентичны (2,2) и (6,6).

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

Игры с нулевой (не нулевой) суммой – это игры, в которых сумма выигрышей всех участников равна (не равна) нулю. Примером игры с нулевой суммой является орлянка.

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

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

Экстенсивная форма записи игры

Расширенная форма записи позволяет рассмотреть более полно процесс игры. Пусть все три игрока действуют в рамках своих интересов и пытаются максимизировать свою прибыль, тогда третий игрок будет выбирать из пары конечных исходов (1,2) исход 2, из пары (3,4) исход 4, из пары (5,6) исход 6, из пары (7,8) исход 7. Второй игрок, понимая это, будет рассчитывать на исходы 4 и 6, именно они дадут максимальную прибыль ему. Первый игрок все понимая будет рассчитывать на исход 4. В итоге 4 исход является разумным для всех трех игроков, то есть действуя разумно и сугубо в личных интересах, результат будет один и тот же. При этом, если первый игрок захочет выбрать другую стратегию, а остальные игроки будут действовать разумно, то вместо прибыли 3, он получит прибыль 0. Если второй игрок будет действовать не разумно, то его результат будет не 4, а 0. Третий игрок действуя не разумно получит 0 вместо 2. То есть, если один из игроков отступит от разумной стратегии, то он потерпит поражение. Данное умозаключение лежит в основе равновесия Нэша.

С математической точки зрения равновесие Нэша определяется следующей формулой:

H_i(x^*) \ge H_i(x_{i}, x_{-i}^*),

где i \in (1..n) - игроки, x_i \in S - стратегии игроков, S - множество стратегий, H_i \in H - выигрыш конкретного игрока, H - множество выигрышей, x^* \in S - равновесие Нэша, x_{-i}^* - набор стратегий, равносильный равновесию Нэша за исключением стратегии x_{i}^*.