 |
Глава 2. Бескоалиционные игры
|
|
|
|
ТЕОРИЯ ИГР ДЛЯ ЭКОНОМИСТОВ
Кострома
УДК
ББК
Скаржинская Е.М., Илюхина А.С., Метелькова К.С. Теория игр: конспект лекций с методическими указаниями: Учебное пособие. – Кострома. 2008. –90с.
Рецензенты:
Землякова И.В., доктор технических наук, профессор
Цуриков В.И., доктор экономических наук, профессор
Настоящее учебное пособие разработано доктором экономических наук, профессором Скаржинской Е.М. и сотрудниками кафедры «Математические методы в экономике». Пособие предназначено для аспирантов и студентов экономических специальностей.
Содержание
Глава 1. Введение.
§1.1. Предмет теории игр 4
§1.2. Формальное описание игры. 10
§1.3. Классификация игр 11
Глава 2. Бескоалиционные игры
§2.1. Антагонистические игры
§2.1.1. Понятие антагонистической игры. Матричная игра 13
§2.1.2. Доминирование стратегий. Редукция игры. 14
Решение игры в доминирующих стратегиях
§2.1.3. Решение игры в чистых стратегиях 16
§2.1.4. Смешанное расширение игры 22
§2.1.5. Решение игры в смешанных стратегиях 28
§2.1.6. Игра против природы 31
§2.1.7. Критерии оптимальности решения в
условиях неопределённости 32
§2.1.8 Критерий Лапласа 33
§2.1.9. Критерий Вальда (максиминный критерий) 34
§2.1.10. Критерий Гурвица (критерий взвешенного
оптимизма /пессимизма) 35
§2.1.11. Критерий Сэвиджа (критерий наименьших
сожалений) 36
§2.1.12. Решение игры против природы в смешанных
стратегиях 37
§ 2.2 Неантагонистические игры
§2.2.1. Понятие неантагонистической игры 40
§2.2.2. Биматричные игры 42
§2.2.3. Равновесие Нэша 44
§2.2.4. Эффективность по Парето 48
§2.2.5. Повторяющиеся игры. Применение к микроэкономике 49
§2.2.6. Последовательные игры 54
|
|
|
Глава 3. Кооперативные решения
§3.1. Понятие коалиционной игры 62
§3.2. Определение решения игры 65
§3.3. Эффективность обмена. Ящик Эджворта 66
§3.4. Арбитражное решение 72
Практикум 79
Литература 93
Введение
Предмет теории игр
Любой процесс в экономике происходит при активном взаимодействии людей, стремящихся реализовать собственные цели, имеющих собственные интересы, оценивающих результаты процесса с точки зрения своих интересов. Интересы участников экономического взаимодействия часто не совпадают. Результаты, которые выгодны одним участникам, могут быть не выгодны другим. Так, например, продавцы заинтересованы в увеличении выручки, а покупатели заинтересованы в понижении цены; наемные работники заинтересованы в повышении заработной платы, что снижает прибыль нанимателей. Перечисленные ситуации имеют общее свойство – наблюдается конфликт интересов участников, т.е. лиц, от которых зависит конечный результат экономического процесса.
Конфликт присутствует в принятии решений даже в том случае, когда решение принимает одно лицо. Например, человек собирается купить квартиру и руководствуется четырьмя критериями: квартира должна быть недорогой, удобно расположенной, иметь хорошее качество, быть удачно спланированной. При выборе из множества предлагаемых вариантов покупатель видит, что одни варианты лучше других по критерию цены, но уступают по критерию расположения, и т.д. В данном случае выбор варианта осложняется конфликтом целей, которые ставит покупатель при покупке жилья.
Принятие решений еще более усложняется, если результат, который получает некоторое лицо, зависит не только от принимаемого им решения, но и от решений, которые принимают другие лица. Например, цена товара на рынке, где предложение поступает от нескольких продавцов, зависит от того, какую рыночную стратегию (объем предложения и назначенная цена) выберет каждый продавец. Таким образом, каждый участник, выбирая те или иные действия (т.е. выбирая свою стратегию), воздействует на конечный результат, т.е. на цену и объем реализации, и в конечном итоге на выручку всех продавцов.
|
|
|
Многообразие ситуаций принятия решений в экономике и в других сферах имеет три общие черты, которые можно сформулировать в виде трех принципов:
1. Конечный результат зависит от выбора решений несколькими лицами (которых мы будем называть участниками игры). Этот принцип носит название «совместность действий».
2. Принцип, согласно которому возникает конфликт между участниками какого-либо общего процесса из-за несовпадения их интересов, носит название «конфликт интересов».
3. Участник экономического процесса стоит перед выбором решения, которое в наибольшей степени должно соответствовать его интересам Для выбора разумного (т.е. рационального) решения, участник должен осознавать, что другие участники имеют собственные интересы, а значит, будут выбирать решения, которые выгодны им. Принцип, согласно которому каждый участник конфликта принимает наиболее эффективные для достижения своих интересов решения, учитывая возиможные действия других участников, называется принципом рациональности.
Легко заметить, что эти три принципа характерны для любой конфликтной ситуации не только в экономике. Примерами конфликтов служат спортивные состязания, политическая борьба, карточные игры, трудовые отношения, рыночное ценообразование, конкуренция, цена акций и т.п. Все эти разнообразные конфликтные ситуации допускают общие формализованные описания и анализ с помощью математических методов. Формализованное описание конфликта (т.е. его математическая модель) называется игрой (The Game). Теория игр является разделом математики, в котором изучаются математические модели конфликтов.
Конфликты и возможности математического анализа вариантов их разрешения, предсказания их исходов давно привлекают внимание математиков. Зарождение теории игр как математической дисциплины можно отнести к письму Б. Паскаля к П. Ферма от 29 июля 1654 года, которое принято считать началом математической теории вероятностей. В дальнейшем отдельные математические вопросы, которые можно отнести к теоретико-игровым, рассматривались многими учеными. Объектом изучения вначале были азартные и карточные игры. Вальдеграв нашел оптимальные смешанные стратегии в игре «проходящий туз» (1712 год), Д. Бернулли проанализировал «петербургскую игру» (1732 год), П. Лаплас рассмотрел принципы оптимальности (1814 год), Ж. Бертран представил теоретико-игровой подход к игре в баккара (1888 год), в 1911 году Э. Цермело описал теоретико-игровой подход к шахматной игре.
|
|
|
Систематическое изучение матричных игр началось с работы Э. Бореля (1921 г.), содержащей доказательство существования оптимальных смешанных стратегий для некоторых случаев игры..
В XX веке теория игр получила энергичное развитие, вызванное не только теоретическим интересом математиков, но и запросами прикладных задач экономики и техники. По сути, математическая теория игр была детально разработана американскими учеными Дж. Нейманом и О. Моргенштерном в известной работе «Теория игр и экономическое поведение» (1944 год) как средство математического подхода к явлениям конкурентной экономики.
Вторая половина XX века отмечена важнейшими результатами в теории игр и ее применением в самых разнообразных сферах, прежде всего в экономике, политике и военном деле. Понятие равновесия, имеющее центральное значение в теории игр, сформулировано выдающимся математиком и экономистом Дж. Нэшем, им же доказана теорема существования равновесия в бескоалиционной игре (теорема Нэша). Дж. Нейман и О. Моргенштерн получили первое из решений для коалиционных игр, Н-М решение. Современная теория коалиционных игр, на основе которых моделируются политические и экономические процессы, сложилась благодаря работам Л.С. Шепли. Р. Аумана, А.И. Соболева. Общее определение игры и исчерпывающую классификацию игр впервые дал выдающийся российский математик Н.Н. Воробьев. Значительный вклад в развитие теории игр внесли российские Е.Б. Яновская, Ю.Б. Гермейер, Э. Вилкас, Г.Н. Дюбин и В.Г. Суздаль.
|
|
|
В ходе своего развития теория игр превратилась в общую математическую теорию конфликтов. В рамках теории игр поддаются математическому описанию военные и правовые конфликты, спортивные состязания, а также явления, связанные с биологической борьбой за существование. Теория игр позволяет формализовать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии. Проблемы управления, планирования и прогнозирования также часто решаются с помощью сценарного подхода, разрабатываемого с применением теории игр.
Как всякая математическая модель, игра создается с определенными целями, для того, чтобы ответить на определенные вопросы. Формулировка некоторых вопросов, на которые должен ответить анализ игры, очевидна – например, как должен действовать участник игры, стремящийся получить наибольший выигрыш? Или – как должен действовать игрок, стремящийся обезопасить себя от наибольших потерь? На языке теории игр вопросы подобного рода формулируются следующим образом. И чем (каким исходом) закончится игра, если все участники выберут свои оптимальные стратегии? Имеют ли игроки оптимальные стратегии? Существуют ли в данной игре исходы, которые выгодны всем игрокам? Будут ли все участники стремиться именно к этим исходам?
Заметим, что анализ игры способен дать ответы далеко не на все вопросы. Так, например, часто нет ответа на «детский» вопрос – чем закончится данная игра, или кто будет победителем? Дело в том, что, во-первых, исход игры может зависеть от случайных факторов, во-вторых, некоторые игры имеют несколько решений, в-третьих, реальные участники игры могут действовать не вполне рационально, т.е. не принимать оптимальные решения.
Покажем на популярных примерах игровых задач, как с помощью математической модели можно получить ответы на некоторые вопросы.
Пример. «Орел - решка».
Два участника игры подбрасывают по монетке достоинством в 1 рубль. Если на обеих монетах выпадут одинаковые значения (орел-орел или решка-решка), то обе монеты достаются первому игроку. Если значения на монетах различны, то обе монеты достаются второму игроку. Сформулируем вопрос: может ли игрок максимизировать свой выигрыш?
Для ответа на вопрос представим данную конфликтную ситуацию в виде таблицы (Таблица 1), записывая выигрыш первого игрока со знаком «+», а второго со знаком «-».
Таблица 1
| стратегии второго игрока | |||
| стратегии первого игрока | орел | решка | ||
| орел | +1 | -1 | ||
| решка | -1 | +1 | ||
Решение. Каждый из четырех исходов в таблице 1 является результатом двух случайных событий – выпадения на двух монетах «орла» или «решки». В силу равновозможности исходов, вероятность каждого из них равна ¼. Выбор стратегии также является случайным и не зависит от воли игрока. В данной игре результат зависит от случая, игроки не имеют возможности влиять на свой выигрыш.
|
|
|
Пример. «Запиши число».
Среди нескольких игроков разыгрывается приз (например, 100 рублей). По правилам игры каждый участник записывает некоторое число от 0 до 10, затем определяется среднее арифметическое всех чисел и делится на 3, полученное число обозначим r. Приз получает тот игрок, чье число имеет наименьшее абсолютное отклонение от r. Если несколько игроков назвали числа, дающие наименьшее отклонение от r. То приз делится между ними поровну. Вопрос: может ли каждый игрок обеспечить себе ненулевой выигрыш? Чем закончится игра, если все игроки будут действовать оптимальным образом?
Решение. Рассмотрим сначала случай, когда число участников игры равно 2. Покажем, что игрок, записавший число 0, получит выигрыш не меньший 50.
Действительно, если другой игрок также запишет 0, то 100 делится пополам, каждый получает 50. Если же другой игрок запишет число x>0, то r=x/6. Для игрока, записавшего 0, абсолютное отклонение r от 0 составит x/6, а для игрока, записавшего x, отклонение составит |(x- r)/6|=5x/6. Приз в 100 рублей получит игрок, записавший 0. Если оба игрока абсолютно рациональны, то они выберут свои оптимальные стратегии[1], т.е. запишут 0, тогда исходом игры будет получение каждым игроком 50 рублей.
Если число игроков равно 3, то число 0 не будет оптимальной стратегией. Например, если первый игрок запишет 0, второй 1, а третий 9, то выигрыш получит второй игрок. Точно также оптимальными не будут все остальные числа, т.к. против любого числа x, записанного первым игроком, найдутся числа y и z, записанные другими игроками, для которых абсолютное отклонение x от r будет больше чем отклонение от r числа y или z. Следовательно, исход игры является неопределенным.
Пример. «Дилемма заключенных».
Два человека совершили общее преступление, т.е. являются сообщниками. Их задержали по подозрению, но следствие не имеет явных доказательств их вины, поэтому им предложили помогать следствию. Они получат по 4 года заключения, если оба сознаются в совершении преступления. Они получат по 2 года заключения, если ни один из них не сознается (предполагается, что в этом случае следствие не сможет им предъявить полноценного обвинения, но в некоторых правонарушениях их все же обвинят). Если один из них сознается, а другой не сознается, то сознавшийся получит 1 год заключения за содействие правосудию, а не сознавшийся - 7 лет. Подозреваемые не имеют возможности передавать друг другу информацию. Какие решения склонны принимать заключенные, если они стремятся получить наименьший срок заключения, и при этом не принимают в расчет этические принципы, такие как солидарность, честность и взаимное доверие.
Решение. Представим данную конфликтную ситуацию в виде таблицы, где каждый возможный исход находится в клетке на пересечении стратегий 1-го и 2-го заключенного, и характеризуется «выигрышами» обоих заключенных. (Таблица 2). и в виде дерева решений (Таблица 3). «Выигрыши» игроков обозначим как количество лет заключения, взятое по очевидным причинам со знаком «-».
Таблица 2
| стратегии второго заключенного | ||||
| стратегии первого заключенного |  2
| сознаться | не сознаться | |
| сознаться | -4; -4 | -1; -7 | ||
| не сознаться | -7; -1 | -2; -2 | ||
Ту же информацию можно представить в виде «дерева решений» (Таблица 3).
Таблица 3
| 1 заключенный | 2 заключенный | Оценка выигрыша | |||
| 1 заключенный | 2 заключенный | ||||
| сознаться | 
| сознаться | - 1 исход | -4 | -4 |
| не сознаться | - 2 исход | -1 | -7 | ||
| не сознаться | сознаться | - 3 исход | -7 | -1 | |
| не сознаться | - 4 исход | -2 | -2 |
Анализ Таблицы 2 и Таблицы 3 показывает, что при любой стратегии 2-го заключенного для 1-го заключенного выбор стратегии «сознаваться» дает лучший результат, чем выбор альтернативной стратегии («не сознаваться»). Как мы покажем позднее, такая стратегия называется доминирующей. То же справедливо и для 2-го заключенного. Следовательно, исходом, оптимальным выбором обоих заключенных будет стратегия «сознаться», следствием чего будет исход, при котором они получат по 4 года заключения. В то же время, лучший результат они получили бы при одновременном выборе стратегии «не сознаться». Однако, несогласованность действий мешает реализации этого исхода: каждому заключенному в отдельности хочется сократить срок заключения и они отказываются от стратегии «не сознаваться», которую они выбрали бы при условии согласованности действий. Заметим, что условие, мешающее им общаться, не очень существенно. Даже, если бы заключенные могли переписываться и договориться, что они не будут сознаваться, это не гарантировало бы выбор стратегии «не сознаваться», потому что каждому в отдельности выгоднее лот нее отказаться. Чтобы оба участника следовали этой стратегии, в правила игры надо ввести изменения: либо предполагать, что заключенные абсолютно доверяют друг другу, либо ввести штрафные санкции за отказ от стратегии «не сознаваться», либо (как это будет сделано в последующих главах), предполагать, что игровая ситуация разыгрывается неограниченное число раз. Но это, разумеется, потребует построения другой математической модели.
Пример. «Красный тигр».
Число участников равно 2. Первый игрок называет одного из двух животных – «тигр» или «обезьяна». Второй участник называет один из трех цветов – «желтый», «красный», «черный». Выигрыши игроков для всех возможных исходов указаны в Таблице 4 (первое число – выигрыш 1-го, второе число – выигрыш 2-го игрока).
Таблица 4
| 2-й 1-й | «желтый» | «красный» | «черный» |
| «обезьяна» | -2; 2 | -1; 1 | 2; -2 |
| «тигр» | 2;-2 | 0;0 | 1; -1 |
Попытаемся ответить на вопрос, имеют ли игроки стратегии, которые обеспечивают им значение выигрыша, которое не может стать меньше при любых действиях соперника.
Решение. Анализ таблицы 4 показывает, что среди стратегий 2-го игрока есть стратегия, которой ему невыгодно пользоваться. В самом деле, сравним стратегии «красный» и «черный». Если первый игрок применит стратегию «обезьяна», то стратегия «черный» окажется хуже, чем стратегия «красный (-2 против 1). Если первый игрок применит стратегию «тигр», будет иметь место тот же вывод (-1 против 0). Предполагая, что 2-й игрок рационален, 1-й игрок поймет, что стратегия «черный» не будет применяться, следовательно, останется таблица из двух строк и двух столбцов. Сравним стратегии 1го игрока «тигр» и «обезьяна» по первым двум столбцам. При использовании 2-м игроком стратегии «желтый», стратегия «тигр» лучше стратегии «обезьяна» (2 против -2). То же при стратегии «красный» (1 против 0).
Формальное описание игры.
Для формального описания игры (конфликта) необходимо зафиксировать следующие моменты:
1. Множество участников, т.е. тех сторон, которые участвуют в конфликте, имеют свои интересы и принимают решения, от которых зависит исход конфликта; будем считать, что число участников счётное (может быть пронумеровано). Иногда заинтересованные лица и лица, принимающие решения могут не совпадать. В дальнейшем будем называть каждого, кто принимает решения, влияющие на исход игры, игроком.
2. Возможные действия участников – стратегии. Каждый участник (игрок) может выбирать своё действие (стратегию или ход) из некоторого множества доступных ему действий.
Будем обозначать: 
– множество стратегий 1-го участника;
– множество стратегий 2-го участника;
– множество стратегий n -го участника.
Первый участник, независимо от остальных, выбирает стратегию 
второй – 
…, n -ый – 
. Результат этих независимых выборов можно истолковать как определенную ситуацию x={s1, s2,…sn}, называемую исходом игры.
Обозначим всё множество исходов 
. Очевидно, что это множество исходов будет равно декартову произведению множеств 
.
= 
3. Каждый исход 
приводит к определённым 
последствиям для каждого участника. Будем считать, что эти последствия можно выразить количественно и будет называть соответствующее число выигрышем участника, т.о. будет соответствовать набор чисел: 
– выигрыш 1-го участника; 
– выигрыш 2-го участника;
– выигрыш n -го участника.
Всё множество выигрышей можно описать следующим образом:
– множество выигрышей (проигрышей), т.е. результат игры 1-го участника;
– результат игры дл 2-го участника;
– результат игры n -го участника.
Итак, для формального описания игры необходимо:
§ задать множество игроков – 
§ задать для каждого из них множество стратегий – 
§ задание функций выигрышей (проигрышей) игроков для каждого из возможных исходов игры (платёжная функция).
Классификация игр
Игры можно разделить на классы по множеству различных признаков. Например, по количеству игроков: игры с 2-мя участниками, игры с 3-мя участниками, и т.д. Очевидно, что игра с двумя участниками является самой простой моделью. Принципиальные различия между играми производятся по следующим признакам:
1) Могут ли участники игры объединяться в группы для выработки совместных решений. Если участники игры могут объединяться в группы, принимающие совместные решения, то игра называется коалиционной или кооперативной. В противном случае – бескоалиционной или некооперативной. Нетрудно понять, что в коалиционной игре набор возможных решений каждого участника намного шире, чем в бескоалиционной игре. Следовательно, более сложной является модель конфликта между участниками.
2) На основании какой информации принимают решения участники игры. Наиболее простым является случай, когда все участники, во-первых, знают все множество возможных исходов игры, т.е. ситуаций, к которым приводят все допустимые комбинации стратегий игроков, и, во-вторых, знают количественные значения индивидуальных полезностей всех игроков для каждого исхода. Формальное описание такой игры с полной информацией приведено в §1.2., в данном пособии рассматриваются только такие игры. Но в реальных конфликтах участники не всегда располагают такой информацией, или одни участники являются более информированными, чем другие. Такие конфликты моделируются играми с неполной информацией, более сложными в смысле нахождения решения, чем игры с полной информацией.
3) Однократно или многократно производится розыгрыш игры. Если одна и та же игровая ситуация воспроизводится множество раз (многократное разыгрывание), то игра называется повторяющейся. Такие игры описаны в §2.2.5. данного пособия.
4) Действуют ли участники игры одновременно, или действия одних участников следуют за действиями других. В последнем случае игра называется последовательной. Такие игры описаны в §2.2.6. данного пособия.
5) Отдельный класс игр представляют собой динамические (или дифференциальные) игры. Эти игры являются моделями конфликтных задач управления динамическими объектами, движение которых описывается дифференциальными уравнениями. В данном пособии такие игры не рассматриваются.
Имеются также другие признаки выделения игр в отдельные классы, например, различия игровых возможностей игроков, или их переговорных сил, игры, в которых отдельные игроки могут изменять правила игры и т.д. Эти игры, представляющие большой практический интерес, не входят в данное пособие, ознакомиться с ними можно в монографии Гермейер Ю.Б. Игры с непротивоположными интересами.
В данном пособии игры классифицируются на коалиционные и бескоалиционные, последние с свою очередь разделяются на игры с противоположными интересами (антагонистические) и игры с непротивоположными интересами (неантагонистические).
Глава 2. Бескоалиционные игры
Антагонистические игры
|
|
|
