Теория игр

Министерство образования и науки Украины и АР Крыма

Реферат

По дисциплине: «Математическое программирование»

На тему: «Теория игр»

Выполнил:

Студент группы МО-21-09

Абибуллаев Ленур

Проверил преподаватель:

Гапонов А.И.

Симферополь, 2010

Введение

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

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

1 История

Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение»[2] (англ. Theory of Games and Economic Behavior).

Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу[3] о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума». Некоторые американские телевизионные шоу, например, «Friend or Foe», «Alias» или «NUMB3RS», периодически ссылаются на теорию в своих эпизодах.

Большой вклад в применения теории игр стала работа Томаса Шеллинга, нобелевского лауреата по экономике 2005 г. «Стратегия конфликта». Т.Шеллинг рассматривает различные «стратегии» поведения участников конфликта. Эти стратегии совпадают с тактиками управления конфликтами и принципами анализа конфликтов в конфликтологии (это психологическая дисциплина) и в управлении конфликтами в организации (теория менеджмента). В психологии и других науках используют слово «игра» в других смыслах, нежели чем в математике. Некоторые психологи и математики скептически относятся к использованию этого термина в других смыслах, сложившихся ранее. Культурологическое понятие игры было дано в работе Йохана Хёйзинга «Homo ludens» (статьи по истории культуры), автор говорит об использовании игр в правосудии, культуре, этике.. говорит о том, что игра старше самого человека, так как животные тоже играют. Понятие игры встречается в концепции Эрика Бёрна «Игры, в которое играют люди, люди, в которые играют люди». Это сугубо психологические игры, основанные на трансакционном анализе. Понятие игры у Й.Хёзинга отличаться от интерпретации игры в теории конфликтов и математической теории игр. Игры также используются для обучения в бизнес-кейсах, семинарах Г. П. Щедровицкого, основоположника организационно-деятельностного подхода. Во время Перестройки в СССР Г. П. Щедровицкий провел множество игр с советскими управленцами. По психологическому накалу ОДИ (организационно-деятельностные игры) были так сильны, что служили мощным катализатором изменений в СССР. Сейчас в России сложилось целое движение ОДИ. Критики отмечают искусственную уникальность ОДИ. Основой ОДИ стал Московский методологический кружок (ММК).Математическая теория игр сейчас бурно развивается, рассматриваются динамические игры. Однако, математический аппарат теории игр -- затратен. Его применяют для оправданных задач: политика, экономика монополий и распределения рыночной власти и т. п. Например, с помощью теории игр делегация США моделировала поведение участников торговых переговоров с СССР, а потом с Россией. Результатом этих переговоров стали договоры крайне выгодные американцам и невыгодные России. Великолепный пример с играми мы видели в 2007--2008 годы в Украине при формировании и развале в Верховной Раде Украине коалиций. Пока ещё культурологические и бизнес-игры не интерпретируются с помощью математической теории игр по многим причинам, одна из которых -- это дело будущего.

Нобелевскими лауреатами по экономике за достижения в области теории игр стали: Роберт Ауманн, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Томас Шеллинг.

2 Представление игр

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

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

Игра «Ультиматум» в экстенсивной форме

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

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

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

Нормальная форма

В нормальной, или стратегической, форме игра описывается платёжной матрицей.[5] Каждая сторона (точнее, измерение) матрицы -- это игрок, строки определяют стратегии первого игрока, а столбцы -- второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. В примере справа, если игрок 1 выбирает первую стратегию, а второй игрок -- вторую стратегию, то на пересечении мы видим (?1, ?1), это значит, что в результате хода оба игрока потеряли по одному очку.

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

3 Характеристическая формула

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

Основания такого подхода можно найти ещё в книге фон Неймана и Моргенштерна. Изучая нормальную форму для коалиционных игр, они рассудили, что если в игре с двумя сторонами образуется коалиция C, то против неё выступает коалиция N \ C. Образуется как бы игра для двух игроков. Но так как вариантов возможных коалиций много (а именно 2N, где N -- количество игроков), то выигрыш для C будет некоторой характеристической величиной, зависящей от состава коалиции. Формально игра в такой форме (также называемая TU-игрой[6]) представляется парой (N, v), где N -- множество всех игроков, а v : 2N > R -- это характеристическая функция.

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

4 Типы игр

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

Часто предполагают, что кооперативные игры отличаются именно возможностью общения игроков друг с другом. В общем случае это неверно. Существуют игры, где коммуникация разрешена, но игроки преследуют личные цели, и наоборот.

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

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

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

Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков -- симметричные. В частности, таковыми являются: «Дилемма заключённого», «Охота на оленя», «Ястребы и голуби».[7] В качестве несимметричных игр можно привести «Ультиматум» или «Диктатор».

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

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

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

Многие изучаемые математиками игры, в том числе уже упоминавшаяся «Дилемма заключённого», иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме -- это делается введением фиктивного игрока, который «присваивает себе» излишек или восполняет недостаток средств.[8]

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

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

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

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

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

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

В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки, го, манкала и другие.

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

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

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

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

Дискретные и непрерывные игры

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

5 Метаигры

Это такие игры, результатом которых является набор правил для другой игры (называемой целевой или игрой-объектом). Цель метаигр -- увеличить полезность выдаваемого набора правил. Теория метаигр связана с теорией оптимальных механизмов (англ.).

Основные понятия теории игр

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

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

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

1. множество заинтересованных сторон (игроков);

2. возможные действия каждой из сторон (стратегии или ходы);

3. интересы сторон, представленные функциями выигрыша (платежа) для каждого из игроков.

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

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

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

6 Классификация игр

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

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

Дадим формальное описание перечисленных элементов конфликта. Множество всех игроков, обозначаемое I, в случае конечного их числа может задаваться простым перечислением игроков. Например, I = {1, 2} при игре в орлянку, I = {Продавец, Покупатель} в ситуации монополия-монопсония, I = {1, 2, ..., n} в случае анализа результатов голосования в парламенте.

Множество стратегий игрока i обозначим через Xi. При игре в орлянку каждый игрок располагает двумя стратегиями: Xi = {Орел, Решка}; каждый участник голосования имеет выбор на множестве стратегий {За, Против}. В случае взаимодействия на рынке как Продавец, так и Покупатель могут назначать некоторую неотрицательную цену на продаваемый (покупаемый) товар, т.е. множество стратегий каждого из них Xi: Рi > 0.

В каждой партии игрок выбирает некоторую свою стратегию xi Xi , в результате чего складывается набор стратегий x = {x1, x2, ..., xn}, называемый ситуацией. Так, ситуацию в Парламенте описывает список {За, За, Против, За, ...}, полученный в итоге проведенного голосования.

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

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

Например, в случае игры в орлянку каждый из игроков имеет по две стратегии, именуемые Орел и Решка. Если игроки выбирают одинаковые стратегии, т.е. в случаях, если оба говорят «Орел» или оба говорят «Решка», 1-й игрок выигрывает 1 рубль, а второй игрок проигрывает 1 рубль. В ситуациях, когда оба игрока выбирают различные стратегии, 1_й игрок проигрывает 1 рубль, а 2_й игрок соответственно этот 1 рубль выигрывает.

В итоге матрица выигрышей 1_го игрока Н1 выглядит следующим образом:

Соответственно матрица выигрышей 2_го игрока Н2 имеет вид:

Для антагонистических игр, в которых выигрыш одного игрока равен проигрышу другого (игр с нулевой суммой), выполняется соотношение Н1 = -Н2. Игра в орлянку, очевидно, является примером такой игры.

Часто для наглядности матрицы выигрышей для обоих игроков совмещают в одну, которая дает полное представление о всей игре:

В каждой клетке этой матрицы слева указаны значения выигрыша 1_го игрока, справа - значения выигрыша 2_го игрока.Рассмотрим пример задания матрицы выигрышей для игры с нулевой суммой, называемой в литературе по теории игр Дилемма Заключенного. Содержание игры следующее: два преступника ожидают приговора суда за совершенное злодеяние. Адвокат конфиденциально предлагает каждому из преступников облегчить его участь (и даже освободить!), если он сознается и даст показания против сообщника, которому грозит угодить в тюрьму за совершенное преступление на 10 лет. Если никто не сознается, то обоим угрожает заключение на определенный срок (скажем, 1 год) по обвинению в незначительном преступлении. Если сознаются оба преступника, то, с учетом чистосердечного признания, им обоим грозит попасть в тюрьму на 5 лет. Каждый заключенный имеет на выбор 2 стратегии: не сознаваться или сознаваться, выдав при этом сообщника. В итоге можно получить следующую матрицу «выигрышей» для обоих игроков:

Приведем пример записи функции выигрыша для бесконечной игры. В случае дуополии каждый из игроков может объявить цену р, по которой он хотел бы продать некоторое количество товара. При этом предполагается, что потребители приобретут товар у фирмы, объявившей меньшую цену, или распределяет свой спрос поровну между фирмами в случае, если они назначили одинаковую цену. Если функцию спроса в зависимости от цены на товар обозначить как d(p), то функция выигрыша 1_й фирмы П1(р1, р2) будет иметь вид

{ р1d(p1), если p1 < p2,

П1(р1, р2) = { если p1 = p2,

{ 0, если p1 > p2.

Аналогично выглядит функция выигрыша 2-й фирмы П2(р1, р2).