Теория игр

стратегий в играх.

Под игрой понимается процесс, в котором участвуют

две и более сторон, ведущих борьбу за реализацию своих интересов.
Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков.
Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.
Теория игр — это раздел прикладной математики, точнее — исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике и других.

Важное значение теория игр имеет для искусственного интеллекта и кибернетики.

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

2.2 Нормальная форма
2.3 Характеристическая функция
3 Применение теории игр
3.1 Описание и моделирование
3.2 Нормативный анализ (выявление наилучшего поведения)
4 Типы игр
4.1 Кооперативные и некооперативные
4.2 Симметричные и несимметричные
4.3 С нулевой суммой и с ненулевой суммой
4.4 Параллельные и последовательные
4.5 С полной или неполной информацией
4.6 Игры с бесконечным числом шагов
4.7 Дискретные и непрерывные игры
4.8 Метаигр
5 Литература

экономики.
Впервые математические аспекты и приложения теории были изложены в

классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior).
Одним из основателей математической теории игр является Джон Нэш. В своих трудах Дж. Нэш разработал принципы «управленческой динамики». Первые концепции теории игр анализировали антагонистические игры, когда есть проигравшие и выигравшие за их счет игроки.
Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу», или «некооперативное равновесие», в ситуации стороны используют оптимальную стратегию, что и приводит к созданию устойчивого равновесия.
Игрокам выгодно сохранять это равновесие, так как любое изменение ухудшит их положение. Работы Дж. Нэша сделали серьёзный вклад в развитие теории игр, были пересмотрены математические инструменты экономического моделирования.
Дж. Неш показывает, что классический подход к конкуренции А.Смита, когда каждый сам за себя, неоптимален. Более оптимальны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других.

объекты. Игра образуется игроками, набором стратегий для каждого игрока и

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

форме
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного

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







На рисунке слева — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами.
Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.

форме игра описывается платёжной матрицей.
Каждая сторона (точнее, измерение) матрицы — это

игрок, строки определяют стратегии первого игрока, а столбцы — второго.
На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. В примере (см. рис. ниже), если игрок 1 выбирает первую стратегию, а второй игрок — вторую стратегию, то на пересечении видим (−1, −1), это значит, что в результате хода оба игрока потеряли по одному очку.




Ы

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

подходов в прикладной математике, применяется для изучения поведения человека и

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

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

у игроков будут равны, то есть иметь одинаковые платежи. Иначе

говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные.
Примерами симметричных игр являются: «Дилемма заключённого», «Охота на оленя», «Ястребы и голуби». В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор»
В примере ниже игра может показаться симметричной из-за похожих стратегий, но это не так — выигрыш второго игрока при профилях стратегий (А, А) и (Б, Б) будет больше, чем у первого.

с нулевой суммой — особая разновидность игр с постоянной суммой, то

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





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

одновременно, или, они не осведомлены о выборе других до тех

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

игр составляют игры с полной информацией.
В такой игре участники

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

в них конечное число игроков, ходов, событий, исходов и т. п.

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

Метаигры
Это игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом). Цель метаигр — увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов.
Литература
Петросян Л. А. Зенкевич Н.А., Семина Е.А. Теория игр: Учеб. пособие для ун-тов. — М.: Высш. шк., Книжный дом «Университет», 1998. — С. 304. — ISBN 5-06-001005-8, 5-8013-0007-4