История развития теории игр

Размещено на http://www.allbest.ru/

История развития теории игр

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

Анализ математической стороны и основных принципов ТИ был дан Дж. фон Нейманом в 1928 году. В 1944 фон Нейман и Моргенштерн опубликовали известную работу «Теория игр и экономического поведения», положившую начало бурному развитию математического исследования игр. Эта работа явилась основным толчком для развития линейного программирования и теории статистических решений Вальда. Она открыла также новый подход к задачам выбора решений в конкурентных ситуациях.

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

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

Большой вклад в применения теории игр стала работа Томаса Шеллинга, нобелевского лауреата по экономике 2005 г. «Стратегия конфликта». Т.Шеллинг рассматривает различные «стратегии» поведения участников конфликта. Эти стратегии совпадают с тактиками управления конфликтами и принципами анализа конфликтов в конфликтологии (это психологическая дисциплина) и в управлении конфликтами в организации (теория менеджмента). В психологии и других науках используют слово «игра» в других смыслах, нежели чем в математике.

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

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

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

конфликтный матричный игра стратегия

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

Как утверждал Г.Лейбниц, "...и игры заслуживают изучения; и если какой-нибудь проницательный математик посвятит себя их изучению, то получит много важных результатов, ибо нигде человек не показывает столько изобретательности, как в игре ".

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

Остановимся на классификации игр.

Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называется антагонистической.

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

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

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

Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой.

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

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

В природе и обществе часто возникают конфликтные ситуации, в которых участвуют стороны с различными или даже противоположными интересами. Конфликтные ситуации возникают при операциях типа купли-продажи (особенно при наличии конкуренции), в судопроизводстве, в спорте и т.д.

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

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

Игра - это упрощенная формализованная модель реальной конфликтной ситуации.

Для математического описания игры необходимо четко сформулировать:

· правила игры, в которых должны быть описаны возможные варианты действий игроков;

· объем информации каждой стороны о поведении другой;

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

Игрок - это одна из сторон в игровой ситуации.

Стратегия игрока - это его правила действия в каждой из возможных ситуаций игр.

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

Основная задача ТИ состоит в выявлении оптимальных стратегий игроков.

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

· по количеству игроков. В игре может участвовать любое конечное число игроков. Если игроки объединяются в две группы, преследующие противоположные цели, то имеет место игра двух «лиц» (парная игра). Например: шахматы - игра двух партнеров с конечным числом возможных ходов; покер - игра многих партнеров с конечным числом возможных ходов.

· В зависимости от взаимоотношений участников различают игры некооперативные и кооперативные.

Некооперативные игры в сравнении с кооперативными

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

Пример кооперативной игры: торг между покупателем и продавцом относительно цены ковра. Если издержки производства ковра составляют 100$, и покупатель оценивает его в 200$, возможна кооперативная игра, потому что соглашение о продаже ковра по цене между 101$ и 199$ максимизирует сумму излишка покупателя и прибыли продавца, улучшая положение обоих сторон.

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

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

Решение матричных игр в чистых стратегиях

Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 - свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию, 2 - свою j-ю стратегию, после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij | ). На этом игра заканчивается.

Каждая стратегия игрока i=; j = часто называется чистой стратегией.

Если рассмотреть матрицу

то проведение каждой партии матричной игры с матрицей ^ А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.

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

Определение. Число, определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

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

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

Определение. Число, определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше, а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем .

Определение. Если в игре с матрицей ,то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

Седловая точка - это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство Размещено на http://www.allbest.ru/

= Размещено на http://www.allbest.ru/

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

где i, j - любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) - стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент, называется решением игры. При этом iо и jоназываются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

Пример 1

Седловой точкой является пара (iо = 3; jо = 1), при которой.

Заметим, что хотя выигрыш в ситуации (3;3) также равен, она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

Из анализа матрицы выигрышей видно, что Размещено на http://www.allbest.ru/

, т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

Матричные игры в смешанных стратегиях

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

1. Решение игры через систему уравнений.

2. Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2, то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.

3. Решение игры графическим методом.

В случаях, когда n=2 или m=2, матричную игру можно решить графически.

4. Решение матричной игры симплекс-методом.

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

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

В данном случае Размещено на http://www.allbest.ru/

=3, а Размещено на http://www.allbest.ru/

=6. Таким образом, игрок А может выиграть не менее 3, а игрок В может ограничить свой проигрыш (выигрыш игрока А) шесть единицами. Область между 3 и 6 остается как бы нейтральной, и каждый игрок может попытаться улучшить свой результат за счет этой области. Но как это сделать? Если игроки применяют свои наиболее предпочтительные стратегии А2 и В1, то игрок А выигрывает, а игрок В проигрывает 6 единиц. Это, конечно, устраивает игрока А, но невыгодно игроку В. Поэтому, если игрок В заметит, что игрок А предпочтительно использует свою стратегию А2, то он может перейти на свою стратегию В2 и понизить выигрыш игрока А до 2 единиц. В свою очередь игрок А может в ответ перейти на свою первую стратегию и выиграть уже 9 единиц. В свою очередь, узнав об этом, игрок В может снова сменить стратегию и понизить выигрыш игрока А до 2 единиц.

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

Обозначим через p1, …, pm вероятности, с которыми игрок А использует в ходе игры свои чистые стратегии А1, ….Am, а через q1, …, qn аналогичные величины для игрока В. Очевидно, должны выполняться условия неотрицательности:

И условия нормировки:

Упорядоченные множества P1, …, pm и Q1, …, qn полностью определяют характер действий игроков и называются смешанными стратегиями игроков А и В соответственно. Очевидно, игроки располагают бесконечным множеством смешанных стратегий.

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

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо I-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта I-Я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Пример

Задержание подозреваемого.

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

Вариант, при котором оперативник пойдет один и своими силами сможет задержать преступника, оценивается им как выигрыш в 3 единицы (очень хорошо). Также оценивается и тот случай, когда преступник окажет сопротивление и решение вызова группы захвата окажется вполне своевременным. Если оперативник предпримет попытку задержания в одиночку, не рассчитав свои силы, и данная попытка не увенчается успехом ввиду сопротивления задерживаемого, то оперуполномоченный проигрывает 1 единицу. Т.е. его выигрыш составит -1. При неэффективном вызове группы захвата оперативник выигрывает всего 1 единицу.

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

Платежная матрица в этом случае будет такова:

Наибольшее значение минимумов строк равно 1. Это соответствует второй стратегии оперативника. Наименьшее значение максимумов столбцов - 3 (впрочем, максимумы столбцов в этой матрице совпадают). Мы видим, что нижняя и верхняя цена игры не равны друг другу. Значит, платежная матрица не имеет седловую точку и конфликт не может быть разрешен в чистых стратегиях. Рассмотренный выше способ решения игры уже не применим. Если оперуполномоченный применит вторую стратегию, то это гарантирует ему выигрыш в 1 единицу. Но взять эту стратегию в качестве чистой, т.е. всякий раз при задержании подозреваемого вызывать группу захвата, было бы, безусловно, неэффективно. Это означало бы «стрельбу из пушки по воробьям». Как интуитивно понятно, оперативник должен применять обе стратегии в зависимости от предполагаемой ситуации. Естественно, что в каждом конкретном случае он реализует какую-то одну из них. И теория игр не дает рецепта по поводу того, как поступать оперативнику в отдельном случае. Она, как мы увидим дальше, лишь определяет вероятности применения стратегий игроками. Эти вероятности зависят от условий задачи, т.е. тех платежей, которые были заданы изначально.

Связь между теорией игр и линейным программированием

Первоначально развитие теории стратегических матричных игр осуществлялось параллельно и независимо от линейного программирования. Позже было установлено, что стратегическая матричная игра может быть сведена к паре двойственных задач линейного программирования. Решив одну из них, получаем оптимальные стратегии игрока 1; решив другую, получаем оптимальные стратегии игрока 2. Математическое соответствие между стратегическими матричными играми и линейным программированием было установлено Дж. Б. Данцигом, сформулировавшим и доказавшим в 1951 г. основную теорему теории игр

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число v и такие стратегии U* и W* игроков 1 и 2 соответственно, что выполняются неравенства:

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

Размещено на Allbest.ru