Элементы теории игр

Содержание

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

Кремер Н.Ш. Теория вероятностей и  математическая статистика / Н.Ш. Кремер. – М. : ЮНИТИ, 2006.

 

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

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

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

 http://ru.wikipedia.org/wiki/%D2%E5%EE%F0%E8%FF_%E8%E3%F0

 

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

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

http://knowledge.allbest.ru/mathematics/3c0b65635a3ac78b5d43b88421306d27_0.html

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

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

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

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

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

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

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

http://vtit.kuzstu.ru/books/shelf/book1/doc/gl%2013.html#p13.1

 

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

 

Кремер Н.Ш. Теория вероятностей и математическая статистика / Н.Ш. Кремер. – М. : ЮНИТИ, 2006.

 

 

 

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

 
 
Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая  абстрактная игра двух игроков. 
 
Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию. 
 
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2 – свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму | аij | ). На этом игра заканчивается. 
 
Каждая стратегия игрока i= ; j =   часто называется чистой стратегией. 
 
Если рассмотреть матрицу 
 
 
А =   
 
 
то проведение каждой партии матричной игры с матрицей ^ А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.

http://www.km.ru/referats/F59274E3C6AE4790AAB97F9BDC96C6BA# 
 
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i = ) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2 
 
аij (i =  ) 
 
т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится 
 
аij =  =   (1). 
 
Определение. Число  , определённое по формуле (1) называется нижней чистой ценой игры и показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2. 
 
Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается  
 
аij 
 
т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает такую свою j = j1стратегию, при которой игрок 1 получит min выигрыш, т.е. находит 
 
aij =  =   (2). 
 
Определение. Число  , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1. 
 
Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше  , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем  . 
 
Определение. Если в игре с матрицей А  = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры 
 
u =  = . 
 
Седловая точка – это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство   =  . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе: 
 
   
 
где i, j – любые чистые стратегии соответственно игроков 1 и 2; (iо,jо) – стратегии, образующие седловую точку. 
 
Таким образом, исходя из (3), седловой элемент   является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий (iо,jо) игроков 1 и 2, образующая седловую точку и седловой элемент  , называется решением игры. При этом iо и jоназываются оптимальными чистыми стратегиями соответственно игроков 1 и 2.