Теория игр
Материал из Покер Вики
Материал из Poker-wiki.ru, свободной энциклопедии по покеру.
Теория игр (англ. Theory of Games) - математический метод изучения всех оптимальных стратегий процессов (игр), в которых участвует две или более сторон, которые ведут борьбу за реализацию своих целей и интересов посредством выбора и использования оптимальной стратегии, отталкиваясь от ожидаемой стратегии и поведения других сторон, участвующих в процессе. По сути это математический метод выбора оптимальной стратегии с учетом всей возможной информации и предположений о возможных ресурсах, моделях поведения и возможных стратегий всех участников игры. В современном своем виде включает принцип равновесия Нэша, который гласит, что задача каждого участника игры выбирать стратегию, которая приведет к результату, выгодному не только себе, но и остальным сторонам.
Теория игр в первоначальном виде была опубликована в 1944 году в научном труде "Теория игр и экономического поведения" (англ. Theory of Games and Economic Behavior) авторов Джона фон Неймана и Оскара Моргенштерна. В наши дни теория игр как раздел прикладной математики получила широкое распространение в огромном числе сфер человеческой жизнедеятельности. Чаще всего эта теория находит применение в экономике, однако в наши дни она используется гораздо шире - в социологии, этике, политологии, психологии, кибернетики, биологии - в теории эволюции, игорной сфере.
Одним из ярких примеров одного из типов игр, описанных теорией игр, может служить покер, который представляется в экстенсивной форме представления игр и является комбинированным типом не кооперативных игр с нулевой суммой с частично полной информацией.
Содержание |
[править] История
[править] Формы представления игр
Каждая игра - это строго описанный математической моделью объект. Эта математическая модель включает в себя представления сторон-участников, набор стратегических действий, доступных каждой стороне, формирующих стратегии или комбинации стратегий, а также результаты игры - то к чему каждая сторона должна стремиться, в конце концов.
Процессы, рассматриваемые теорией игр, могут быть представлены в трех основных формах. Если для кооперативных игр большей частью применяется характеристическая форма представления, то для всех остальных используют нормальную или экстенсивную форму.
[править] Нормальная форма представления
Это так называемая стратегическая форма представления процесса (игры), может быть описана так называемой платежной матрицей. В обобщенном виде это выглядит так: каждая сторона матрицы - это отдельная сторона-участник процесса (игрок), где строки это возможные стратегии одной стороны, а столбцы - стратегии второй стороны. Содержимое матрицы - пересечение решений о выборе каждой сторон одной из этих стратегий. Видно что, если игрок 1 выберет стратегию 2, а игрок 2 выберет стратегию 1, то для обоих это будет нулевым решением, то есть оба ничего не потеряют и ничего не приобретут. Игроки выбирают максимально выгодную для себя стратегию, но в отношении поведения оппонента в выборе его стратегии, это решение может не принести положительного результата. Это особенность такой формы представления игр с неполной информацией.
[править] Экстенсивная форма представления
Это расширенная форма представления игр. Саму форму наглядно можно изобразить в форме дерева решений, где каждая вершина соответствует ситуации выбора одной из сторон своей стратегии. Каждой стороне отделяется целый уровень вершин. Результат игры, после выбора обоими сторонами своих стратегий представлен снизу.
В данном примере игрок 1 ходит первым и выбирает стратегию F или U. После чего игрок 2 должен проанализировать ситуацию и выбрать оптимальную для себя стратегию, что приведет к конечному результату.
Это самая наглядная форма представления, ее особенность в том, что с ее помощью удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же стороны делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
[править] Характеристическая форма представления
Это форма представления кооперативных игр, то есть тех игр, в которых игра не между индивидуально обособленными сторонами (игроками), а между коалициями, образованными игроками. Тут используют характеристическую функцию, определяющую выигрыш каждой коалиции игроков, предполагая, что выигрыш пустой коалиции равен нулю.
Эта форма была основана на нормальной форме представления. Если в игре с двумя сторонами образуется коалиция, то против неё выступает коалиция
. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много -
, где
- количество игроков, то выигрыш для
будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме представляется парой
, где
— множество всех игроков, а
- это
— это характеристическая функция.
Эта форма применима для всех игр, то есть, есть возможность перевести любую игру из нормальной формы в характеристическую, однако в обратную сторону это не всегда доступно.
[править] Типы игр
[править] Кооперативные и не кооперативные
Кооперативная, либо коалиционная игра - это игра, в которой игроки могут объединяться в группы, накладывая на себя определенные обязательства перед другими участниками этой группы и координируя свои действия в выборе тактики приемлемой для достижения целей всей группы. Не кооперативная игра - это игра, где каждый игрок играет по принципу "каждый сам за себя".
Не кооперативные игры описывают игру на более низком уровне в мелких деталях, полученных от каждого участника игры. Кооперативные же игры описывают общую стратегию поведения групп и общую стратегию игры в целом. Равновесие Нэша - это попытка решения некоторых кооперативных игр как ситуации равновесия не кооперативных игр.
[править] С нулевой и с ненулевой суммой
Игры с нулевой суммой - так называются вид игр с постоянной суммой, то есть таких в которых участники игры не могут изменить имеющиеся ресурсы и фонд игры в целом. В этом случае сумма всех выигрышей равна сумме всех проигрышей. Примером такой игры может стать покер - один игрок выигрывает всю сумму, остальные участники проигрывают. Жизненный пример в общих чертах - воровство.
Игры с суммой отличной от нуля - игры с непостоянной суммой предполагают, что выигрыш одного игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть отличен нуля. Такие игры могут быть преобразованы к нулевой сумме — это делается введением фиктивного игрока, который "присваивает себе" излишек или восполняет недостаток средств. Примером игры с ненулевой суммой могут быть шашки, шахматы. Примером в жизни может служить обычная торговля, в которой каждый участник извлекает выгоду.
[править] С полной или неполной информацией
В игре с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры.
Большинство изучаемых в математике игр — с неполной информацией или частично не полной информацией, то есть когда достаточно знание всех доступных противникам стратегий, знание всех их ходов необязательно.
[править] Параллельные и последовательные
В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. Обычно представлены в нормальной форме представления.
Другой вид последовательные или динамические игры. В этих играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Эта информация может быть даже не совсем полной, например, игрок может узнать, что его оппонент из некоторого множества своих стратегий точно не выбрал какую-либо определенную, ничего не узнав о других. Они представлены в экстенсивной форме.
[править] Симметричные и не симметричные
Симметричная игра - это такая игра, при которой соответствующие линии стратегий у игроков будут равны, то есть иметь одинаковые результаты. Проще говоря, если игроки поменяются местами, то шансы на выигрыш останутся прежними. Большинство игр, особенно для двух игроков - симметричные.
В не симметричной игре стратегии могут походить друг на друга, однако результат применения их будет разный. При выборе одной из сторон любой из стратегий результат будет меньше, чем у второй стороны.
[править] Дискретные и непрерывные игры с бесконечным числом шагов
Большинство изучаемых игр дискретны: в них конечное число игроков, ходов, событий, исходов. Примерами таких игр может оказаться практически любой процесс, происходящий в реальном мире или изучаемый в экономике. Они, как правило, длятся конечное число ходов, дабы достигнуть результата. Соответственно и стратегия подбирается в расчете на определенные рамки (временные, или количеством итераций).
Есть игры, которые расширены на неопределенно число ходов, соответственно способные продолжаться бесконечно долго. Они обычно связываются с вещественной шкалой (обычно временной шкалой). Их называют дифференциальными, хотя происходящие в них события могут быть дискретными по природе. Тут вопрос выбора стратегии стоит по другому - необходимо найти не оптимальное решение, а хотя бы выигрышную стратегию, чтобы на длительной дистанции поддерживать положительный результат.