Теория игр

Материал из Poker-wiki.ru, свободной энциклопедии по покеру.

Теория игр (англ. Theory of Games) - математический метод изучения всех оптимальных стратегий процессов (игр), в которых участвует две или более сторон, которые ведут борьбу за реализацию своих целей и интересов посредством выбора и использования оптимальной стратегии, отталкиваясь от ожидаемой стратегии и поведения других сторон, участвующих в процессе. По сути это математический метод выбора оптимальной стратегии с учетом всей возможной информации и предположений о возможных ресурсах, моделях поведения и возможных стратегий всех участников игры. В современном своем виде включает принцип равновесия Нэша, который гласит, что задача каждого участника игры выбирать стратегию, которая приведет к результату, выгодному не только себе, но и остальным сторонам.

Теория игр в первоначальном виде была опубликована в 1944 году в научном труде "Теория игр и экономического поведения" (англ. Theory of Games and Economic Behavior) авторов Джона фон Неймана и Оскара Моргенштерна. В наши дни теория игр как раздел прикладной математики получила широкое распространение в огромном числе сфер человеческой жизнедеятельности. Чаще всего эта теория находит применение в экономике, однако в наши дни она используется гораздо шире - в социологии, этике, политологии, психологии, кибернетики, биологии - в теории эволюции, игорной сфере.

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

Формы представления игр

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

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

Нормальная форма представления

Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.

Это так называемая стратегическая форма представления процесса (игры), может быть описана так называемой платежной матрицей. В обобщенном виде это выглядит так: каждая сторона матрицы - это отдельная сторона-участник процесса (игрок), где строки это возможные стратегии одной стороны, а столбцы - стратегии второй стороны. Содержимое матрицы - пересечение решений о выборе каждой сторон одной из этих стратегий. Видно что, если игрок 1 выберет стратегию 2, а игрок 2 выберет стратегию 1, то для обоих это будет нулевым решением, то есть оба ничего не потеряют и ничего не приобретут. Игроки выбирают максимально выгодную для себя стратегию, но в отношении поведения оппонента в выборе его стратегии, это решение может не принести положительного результата. Это особенность такой формы представления игр с неполной информацией.

Экстенсивная форма представления

Это расширенная форма представления игр. Саму форму наглядно можно изобразить в форме дерева решений, где каждая вершина соответствует ситуации выбора одной из сторон своей стратегии. Каждой стороне отделяется целый уровень вершин. Результат игры, после выбора обоими сторонами своих стратегий представлен снизу.

Экстенсивная форма игры с двумя игроками.

В данном примере игрок 1 ходит первым и выбирает стратегию F или U. После чего игрок 2 должен проанализировать ситуацию и выбрать оптимальную для себя стратегию, что приведет к конечному результату.

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

Характеристическая форма представления

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

Эта форма была основана на нормальной форме представления. Если в игре с двумя сторонами образуется коалиция , то против неё выступает коалиция . Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много - , где - количество игроков, то выигрыш для будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме представляется парой , где — множество всех игроков, а - это — это характеристическая функция.

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

Типы игр

Кооперативные и не кооперативные

Кооперативная, либо коалиционная игра - это игра, в которой игроки могут объединяться в группы, накладывая на себя определенные обязательства перед другими участниками этой группы и координируя свои действия в выборе тактики приемлемой для достижения целей всей группы. Не кооперативная игра - это игра, где каждый игрок играет по принципу "каждый сам за себя".

Не кооперативные игры описывают игру на более низком уровне в мелких деталях, полученных от каждого участника игры. Кооперативные же игры описывают общую стратегию поведения групп и общую стратегию игры в целом. Равновесие Нэша - это попытка решения некоторых кооперативных игр как ситуации равновесия не кооперативных игр.

С нулевой и с ненулевой суммой

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

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

С полной или неполной информацией

В игре с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры.

Большинство изучаемых в математике игр — с неполной информацией или частично не полной информацией, то есть когда достаточно знание всех доступных противникам стратегий, знание всех их ходов необязательно.

Параллельные и последовательные

В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. Обычно представлены в нормальной форме представления.

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

Симметричные и не симметричные

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

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

Дискретные и непрерывные игры с бесконечным числом шагов

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

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