Теория игр
Содержание
Введение
Теория игр, обязанная своим происхождением так называемым салонным играм, имеет многочисленные экономические, социологические и военные приложения. Эти приложения поддерживают интерес к теории игр и питают её новыми задачами. Тем не менее, в ней сохранилась в значительной степени первоначальная терминология, относящаяся к играм в собственном смысле: партия, ход, выигрыш, игрок и другие. Первые серьёзные исследования по теории игр были выполнены в первой трети XX века такими выдающимися учеными, как Э. Борель, Дж. фон Нейман, но не породили сколько – нибудь заметных откликов. И только после публикации книги Дж. фон Неймана и О.Моргенштерна «Теория игр и экономическое поведение» началось интенсивное развитие теории игр и её приложений.
Для решения любой проблемы существенным всегда является вопрос: кто поставлен перед проблемой, или, как говорят, должно быть лицо принимающее решение (ЛПР). В реальной жизни ЛПР может быть некоторое ответственное лицо (директор, бухгалтер, коммерсант, про давец и т.д.), или некоторая группа лиц (комиссия, бригада, совет директоров и т.д.). То есть ЛПР – это реально существующий объект, который желает улучшить или ухудшить некоторые показатели, что с математической точки зрения принципиальной разницы не имеет, и имеет для этого полномочия.
Теория игр является частью большого и интенсивно развивающегося раздела математики – «Исследование операции» - теории математических моделей принятия оптимальных решений. Принятие решений осуществляется при различном уровне информированности принимающего решение субъекта о создавшейся ситуации. В полностью детерминизированном случае при возможности количественной оценки результата принятия того или иного решения (т.е. при заданной целевой функции) задача сводится, как правило к поиску экстремума функции нескольких переменных при заданных ограничениях. Типичным примером такого рода является классическая «транспортная задача».
В другом случае информированности субъекту необходимо принимать решение, когда имеется несколько вариантов условий, он не знает, какой из них может осуществиться в действительности, но ему известно априорное распределение вероятности появления каждого из вариантов. В этом случае дело сводится к поиску экстремума среднего значения (математического ожидания) целевой функции. При всей содержательной несхожести указанных случаев в принципе они сводятся к математически однотипным задачам.
В третьем случае информированности субъекту может быть известным только множество вариантов, а распределение вероятности на этом множестве неизвестно. Более того, выбор варианта может находится во власти другого (других) разумного субъекта (игрока), интересы которого не обязаны совпадать с интересами первого субъекта. Именно этим третьим случаем занимается теория игр. Поэтому её можно определить как теорию математических моделей принятия оптимальных решений в условиях конфликта или неопределенности.
Понятие «конфликт» подразумевает задание множества его участников, их возможностей и интересов. «Оптимальность» предусматривает задание системы предпочтений, позволяющих сравнивать между собой решения. Включение в определение теории игр «неопределенности» отражает возможность применения её методов к принятию решений в ситуации, когда разумный противоборствующий субъект отсутствует, но когда ничего не известно о шансах появления того или иного варианта условий, в которых необходимо принимать решение, и приходится, например ввиду большого риска или осторожности, рассчитывать на осуществление наихудшего варианта. Такого рода задачи объединяются термином «игры против природы».
Теория игр
Теория игр — математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.[1]
Экстенсивная форма
Экстенсивная форма игры
Игра «Ультиматум» в экстенсивной форме
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.
На рисунке слева — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
Нормальная форма
Игрок 2 |
Игрок 2 | |
Игрок 1 |
4, 3 |
–1, –1 |
Игрок 1 |
0, 0 |
3, 4 |
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии. | ||
Нормальная форма игры
В нормальной, или стратегической, форме игра описывается платёжной матрицей. Каждая сторона (точнее, измерение) матрицы — это игрок, строки определяют стратегии первого игрока, а столбцы — второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. В примере справа, если игрок 1 выбирает первую стратегию, а второй игрок — вторую стратегию, то на пересечении мы видим (−1, −1), это значит, что в результате хода оба игрока потеряли по одному очку.
Игроки выбирали стратегии с максимальным для себя результатом, но проиграли, из-за незнания хода другого игрока. Обычно в нормальной форме представляются игры, в которых ходы делаются одновременно, или хотя бы полагается, что все игроки не знают о том, что делают другие участники. Такие игры с неполной информацией будут рассмотрены ниже.
Характеристическая формула
Кооперативная игра (математика)
В кооперативных играх с трансферабельной полезностью, то есть возможностью передачи средств от одного игрока к другому, невозможно применять понятие индивидуальных платежей. Вместо этого используют так называемую характеристическую функцию, определяющую выигрыш каждой коалиции игроков. При этом предполагается, что выигрыш пустой коалиции равен нулю.
Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C, то против неё выступает коалиция N \ C. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2N, где N — количество игроков), то выигрыш для C будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой[6]) представляется парой (N, v), где N — множество всех игроков, а v : 2N → R — это характеристическая функция.
Подобная форма представления
может быть применена для всех
игр, в том числе без
Типы игр
Кооперативные и некооперативные
Кооперативная игра (математика), Некооперативная игра
Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя. Развлекательные игры редко являются кооперативными (за исключением некоторых сетевых игр, например, Counter-Strike), однако такие механизмы нередки в повседневной жизни.
Часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. В общем случае это неверно. Существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот.
Из двух типов игр,
некооперативные описывают
Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.
Симметричные и несимметричные
А |
Б | |
А |
1, 2 |
0, 0 |
Б |
0, 0 |
1, 2 |
Несимметричная игра | ||
Симметричная игра
Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные. В частности, таковыми являются: «Дилемма заключённого», «Охота на оленя», «Ястребы и голуби».[7] В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор».
В примере справа игра, на первый взгляд может показаться симметричной из-за похожих стратегий, но это не так — ведь выигрыш второго игрока при любой из стратегий (1, 1) и (2, 2) будет больше, чем у первого.
С нулевой суммой и с ненулевой суммой
А |
Б | |
А |
−1, 1 |
3, −3 |
Б |
0, 0 |
−2, 2 |
Игра с нулевой суммой | ||
Игра с нулевой суммой
Игры с нулевой суммой — особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. Посмотрите направо — числа означают платежи игрокам — и их сумма в каждой клетке равна нулю. Примерами таких игр может служить покер, где один выигрывает все ставки других; реверси, где захватываются фишки противника; либо банальное воровство.
Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме — это делается введением фиктивного игрока, который «присваивает себе» излишек или восполняет недостаток средств.
Ещё игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду. Сюда также относятся го, шашки и шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война.
Параллельные и последовательные
Последовательная игра
В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. В последовательных, или динамических, играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Эта информация может быть даже не совсем полной, например, игрок может узнать, что его противник из десяти своих стратегий точно не выбрал пятую, ничего не узнав о других.
Различия в представлении
С полной или неполной информацией
Игра с полной информацией
Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игр — с неполной информацией. Например, вся «соль» Дилеммы заключённого или Сравнения монеток заключается в их неполноте.
В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки, го, манкала и другие.
Часто понятие полной информации путают с похожим — совершенной информации. Для последнего достаточно лишь знание всех доступных противникам стратегий, знание всех их ходов необязательно.
Игры с бесконечным числом шагов
Детерминированность
Игры в реальном мире или изучаемые в экономике игры, как правило, длятся конечное число ходов. Математика не так ограничена, и в частности, в теории множеств рассматриваются игры, способные продолжаться бесконечно долго. Причём победитель и его выигрыш не определены до окончания всех ходов.
Задача, которая обычно ставится в этом случае, состоит не в поиске оптимального решения, а в поиске хотя бы выигрышной стратегии. Используя аксиому выбора, можно доказать, что иногда даже для игр с полной информацией и двумя исходами — «выиграл» или «проиграл» — ни один из игроков не имеет такой стратегии. Существование выигрышных стратегий для некоторых особенным образом сконструированных игр имеет важную роль в дескриптивной теории множеств.
Дискретные и непрерывные игры
Дифференциальные игры
Большинство изучаемых игр дискретны: в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно — шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры также рассматриваются в теории оптимизации, находят своё применение в технике и технологиях, физике.
Метаигры
Это такие игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом). Цель метаигр — увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов (англ.).
ОПРЕДЕЛЕНИЕ МАТРИЧНОЙ ИГРЫ
Описание игры включает перечень участников конфликта, задание множеств возможных действий и оценок эффективности этих действий для каждого из них. Участников конфликта принято называть игроками. Обозначим множество всех игроков через . Далее будем считать множество N конечным. Игроков принято различать по их номерам, т. е. считать ={1,2, ..., n}. Множество возможных действий i-го игрока обозначим через . Элементы этого множества принято называть стратегиями. Каждый игрок имеет не менее двух различных стратегий, в противном случае его действия заранее определены и фактически он не участвует в игре. В результате выбора i-м игроком стратегии складывается система стратегий , которая называется ситуацией. Эффективность возможных действий игроков мы будем оценивать теми выигрышами, которые игроки получают в каждой ситуации s. Выигрыш игрока i в ситуации s обычно обозначается через . Функция , определенная на множестве всех ситуаций, называется функцией выигрыша игрока i. Цель i-го игрока — максимизация своей функции выигрыша.
Данный способ описания
игры заключается в том, что рассматриваются
все возможные стратегии
Игра (17.1) называется антагонистической, если в ней участвуют два игрока и значения функций выигрыша в каждой ситуации равны по величине и противоположны по знаку.
Следовательно, для задания антагонистической игры достаточно указать функцию выигрыша только одного из игроков . Поэтому под антагонистической игрой понимается совокупность
Г = <А, В, Н>,
где А и В — соответственно множества стратегий игроков I и II, а Н — функция выигрыша игрока I.
Конечная антагонистическая игра в нормальной форме называется матричной игрой.
Это название можно объяснить следующей возможностью описания игр такого рода. Поскольку множество возможных действий каждого из игроков в этом случае конечно, можно положить А = {1, 2, ..., m}, В = {1, 2,..., n}, где m и n — соответственно число стратегий игроков I и II, а значения функции Н представить в виде следующей матрицы:
Здесь —выигрыш игрока I в ситуации (i, j), где i — номер строки (стратегия игрока I), j — номер столбца (стратегия игрока II). Матрица Н называется матрицей игры или матрицей выигрышей.
Матричная игра полностью определяется своей матрицей выигрышей. Поэтому часто вместо выражения “игра с матрицей выигрышей Н” употребляется выражение “игра Н”.
Преимущество представления игры в виде матрицы заключается в хорошей наглядности. Матричные игры являются самыми простыми из класса антагонистических игр.
РЕШЕНИЕ МАТРИЧНЫХ ИГР В ЧИСТЫХ СТРАТЕГИЯХ.
Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=
Каждая стратегия игрока i=
Если рассмотреть матрицу
А =
то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =
т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится
Определение. Число
Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается
т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1 стратегию, при которой игрок 1 получит min выигрыш, т.е. находит
Определение. Число
Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше
Определение. Если в игре с матрицей А
u =
Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство
где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку.
Таким образом, исходя из (3), седловой элемент
Пример 1
Седловой точкой является пара (iо = 3; jо = 1), при которой u =
Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 =
Пример 2
Из анализа матрицы выигрышей видно, что
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ИГР 2 x n И m x 2.
Поясним метод на примераx.
Пример 1.
Рассмотрим игру, заданную платёжной матрицей.
На плоскости xОy введём систему координат и на оси Оx отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (x, 1 - x). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.
В точкаx А1 и А2 восстановим перпендикуляр и на полученныx прямыx будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0x соответствуют точки В1, В2 и В3.
Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В'1, В2', В3' на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В'1, В2 и В'2, В3 и В'3 получим три прямые, расстояние до которыx от оси 0x определяет средний выигрыш при любом сочетании соответствующиx стратегий. Например, расстояние от любой точки отрезка В1В'1 до оси 0x определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами x и 1–x) и стратегией В1 игрока 2. Это расстояние равно
2x1 + 6(1 - x2) = u1
(Вспомните планиметрию и
Соответствующие два уравнения имеют вид
Следовательно Х = (
Оптимальные стратегии для игрока 2 можно найти из системы
и, следовательно, Y = (0;
Пример 2. Найти решение игры, заданной матрицей
Решение. Матрица имеет размерность 2 x 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная А1 K А'4 соответствует верxней границе выигрыша игрока 1, а отрезок N K –цене игры. Решение игры таково
U = (
Список литературы
Игры с непротивоположными интересами. Гермейер Ю.Б., Главная редакция физико-математической литературы издательства «Наука»,1976.
теория игр: Учебное пособие/Н.В. Мурзов, А.В.Дубовиков, Рязанская государственная радиотехническая академия, Рязань, 2001.
Решение матричных и кооперативных игр
на ЭВМ: Учебное пособие И.А. Цветков; Рязанская государственная ради отехническая академия, Рязань,2000.
Краткий курс теории игр для спецализированных школ с математическим уклоном/В.Н. Лагунов, Тверь,1994