Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Биматричные игры

Государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный технологический институт (Технический университет)

Кафедра: Экономики и логистики

Факультет: 5

Курс: 2

Группа: 588

Учебная дисциплина: Статистика

КУРСОВАЯ РАБОТА

Тема: Теория игр. Биматричные игры.

Студент: Подпись ________ Степанова О. В.

Руководитель: Подпись_________ Межевич К. Г.

Оценка: ________ Подпись руководителя _________

Санкт-Петербург

2010

Содержание

1. Введение

2. Общее введение в теорию игр

3. Биматричные игры

4. Оптимальность по Парето

5. Равновесие по Нэшу

6. Решение биматричных игр

7. Биматричные игры 2х2 и их решение

7.1. «Семейный спор»

7.2. «Дилемма заключенного»

7.3. «Зачет»

8. Почти антагонистические игры

8.1. «Борьба за рынки»

9. Заключение

10. Список литературы

Введение.

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

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

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

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

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

Общее введение в теорию игр.

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

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

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

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

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

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

В теории игр участников конкурирующего взаимодействия называют игроками, каждый из них имеет непустое множество допустимых действий, совершаемых им по ходу игры, которые называются ходами или выборами. Набор всех возможных ходов по одному из списка возможных ходов каждого игрока (участвующих в парах, тройках и т.д. ходов) называется стратегией. Грамотно построенные стратегии взаимно исключают друг друга, т.е. взаимно исчерпывают все способы поведения игроков. Исходом игры называется реализация игроком выбранной им стратегии. Каждому исходу игры соответствует определяемое игроками значение полезности (выигрыша), называемое платежом.

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

1. В зависимости от количества игроков различают парные игры и игры n игроков. Математический аппарат реализации парных игр наиболее проработан. Игры трёх и более игроков исследовать сложнее из-за трудностей технической реализации алгоритмов решения.

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

3. По характеру взаимодействия игры делятся на:

· бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

· коалиционные (кооперативные) – игроки могут вступать в коалиции.

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

4. По характеру выигрышей игры делятся на:

· игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю);

· игры с ненулевой суммой.

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

Матричная игра – это конечная парная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

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

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

Целью любой игры является максимизация каждым игроком своей выгоды. Смысл математической теории игр, построенной на приведенной выше классификации, состоит в формализации (упрощении) и облегчении оптимального выбора. Множество всех возможных стратегий игр составляет большое число, растущее тем сильнее, чем больше игроков и набор доступных каждому ходов. Так для пары игроков, если условия игры позволяют каждому совершить по n ходов, в игре существует 2ⁿ стратегий.

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

· Минимаксная стратегия (выбор из максимальных (наихудших) проигрышей минимальных (наилучших).

· Максиминная стратегия (выбор из минимальных (наихудших) выигрышей максимальных (наилучших).

Развитием теории игр с использованием методов вероятностного анализа является математическая теория принятия решений. Эта теория оперирует не действительным (актуальным) решением, а средним, которое есть ожидаемое решение игры в течение ее многократного повторения. Данное свойство актуально для решения правовых задач, поскольку нормативный характер права означает, что оно ориентировано на неопределенного субъекта и предполагает многократное повторение правоотношений. Чтобы не вдаваться в глубокие математические выкладки, отметим лишь, что теория принятия решений предлагает систему критериев (например, критерий Гурвица, Хаджи-Лемана, критерий ожидаемого значения), которые с помощью вероятностного анализа исходов игр позволяют осуществить выбор оптимального решения в условиях риска и неопределенности.

Биматричные игры.

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

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

игрок А может выбрать любую из стратегий A₁,…,A_m,

игрок В может выбрать любую из стратегий B₁,…,B_n.

При этом всякий раз их совместный выбор оценивается вполне определенно: если игрок A выбрал i-ю стратегию А₁, а игрок В — k-ю стратегию B_k, то выигрыш игрока А равен некоторому числу a_ik, а выигрыш игрока В некоторому, вообще говоря, другому числу b_ik.

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

Последовательно перебирая все стратегии игрока А и все стратегии игрока B мы сможем заполнить их выигрышами две таблицы

B₁

…

B_k

…

B_n

B₁

…

B_k

…

B_n

A₁

a₁₁

…

a_1k

…

a_1n

A₁

b₁₁

…

b_1k

…

b_1n

…

….

…

….

…

A_i

a_i1

…

a_ik

…

a_in

A_i

b_i1

…

b_ik

…

b_in

…

A_m

a_m1

…

a_mk

…

a_mn

A_m

b_m1

…

b_mk

…

b_mn

Первая из таблиц описывает выигрыши игрока А, вторая — выигрыши игрока B. Обычно эти таблицы записывают в виде матриц

Здесь А — платежная матрица игрока А, а В — платежная матрица игрока В.

При выборе игроком А i-й стратегии, а игроком В — k-й стратегии их выигрыши находятся в матрицах выплат на пересечении i-x строк и k-х столбцов: в матрице А это элемент a_ik, а в матрице В — элемент b_ik.

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

Замечание, Рассматриваемые ранее матричные игры можно рассматривать, разумеется, и как биматричные, где матрица выплат игроку В противоположна матрице выплат игроку А:

или

Однако в общем случае биматричная игра — это игра с ненулевой суммой.

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

Существует ещё и алгебраическое представление биматричной игры:

Задача нахождения ситуаций равновесия бескоалиционной игры Г формата (m₁,…m_n) фактически состоит в решении системы m₁ + . .. … + m_n неравенств вида с m₁,…,m_n ограничениями неотрицательности и n ограничениями нормирования. Математически это сложно и громоздко. Лишь для отдельных сравнительно простых классов бескоалиционных игр ход решения этой задачи поддается элементарному описанию.

Именно одним из таких классов являются конечные бескоалиционные игры⁶ двух лиц. Пусть в такой игре игрок 1 имеет m чистых стратегий, а игрок 2 — n стратегий, и в каждой ситуации (i,j) игрок 1 получает выигрыш a_ij , а игрок 2 — выигрыш b_ij. Тогда значения обеих функций выигрыша игроков естественно расположить в виде пары матриц:

Поэтому такие игры называются биматричными. Биматричная игра с матрицами выигрышей А и В обозначается через Г (А , В) или через Г_{А ,В}.

Смешанные стратегии⁷ в биматричных играх, как и в матричных играх, естественно понимать как векторы, составляющие фундаментальный симплекс. Если X и Y — соответственно векторы, описывающие смешанные стратегии игроков 1 и 2, то, как легко видеть,

H₁(X,Y)=XAY^T, H₂(X,Y) = XBY^T.

Определение ситуации равновесия⁸ для случая биматричной игры приобретает следующую формулировку. Ситуация (X, Y) в биматричной игре с матрицами выигрышей А и В является равновесной, если

(1)

(2)

Очевидно, при В = -A биматричная игра превращается в матричную, а соотношения (1) и (2) – соответственно в

(3)

Последнее неравенство равносильно XAY^T и XА_j , что вместе с (3) дает нам известное определение седловой точки⁹ в матричной игре.

Оптимальность по Парето

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

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

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

Один вариант устойчивости ситуации, отражающий черты ее выгодности, состоит в ее оптимальности по Парето.

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

и будем, как обычно, полагать

Н_I(х)<Н_I(у), если при всех i є I;

H_I(x)≤H_I(y) если H_i(x)≤H_i(x) при всех i є I, но Н_I(х)≠ Н_I(у);

Н_I(х)≤ Н_I(у), если .

Определение. Ситуация х° в биматричной игре

Г =

называется оптимальной по Парето, если не существует ситуации xєx, для которой имеет место векторное неравенство.

Множество всех ситуаций в игре Г, оптимальных по Парето, обозначается через ζ^P(Г). Иными словами, в оптимальной по Парето ситуации игроки не могут совместными усилиями увеличить выигрыш кого-либо из них, не уменьшив при этом выигрыш кого-либо другого.

Формальное различие ситуации равновесия от ситуации, оптимальной по Парето: в первой ни один игрок, действуя в одиночку, не может увеличить своего собственного выигрыша; во второй — все игроки, действуя совместно, не могут (даже нестрого) увеличить выигрыш каждого.

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

ϑ (Г) = {H_I(x): xєx}

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

Так, в изображенном на рис.1 примере оптимальным по Парето ситуациям будут соответствовать все точки ϑ (Г), принадлежащие выделенными жирными линиями участкам "северо-восточной" границы ϑ (Г) .

В частности, для существования в игре Г оптимальной по Парето ситуации достаточно компактности множества ϑ (Г). Для этого же, в

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

Равновесие по Нэшу

Ситуация х называется ситуацией равновесия, если для любого игрока i є I и любой его стратегии x_i є х_i - выполняется неравенство .

Множество всех ситуаций равновесия в игре Г будем обозначать через ζ(Г). Очевидно,

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

Равновесной стратегией игрока в бескоалиционной игре называется такая его стратегия, которая входит хотя бы в одну из ситуаций равновесия игры.

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

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

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

Процесс нахождения ситуаций равновесия в биматричной игре часто называется решением игры.

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

Теорема. В каждой биматричной игре

Г =

существует хотя бы одна ситуация равновесия (в смешанных стратегиях).

Доказательство. Если игрок i имеет в игре Г m_i чистых стратегий, то множество X_i всех его смешанных стратегий, как уже неоднократно отмечалось, можно представлять как (m_i — 1) -мерный симплекс. Поэтому всякую ситуацию

Х = (Х_1,...,Х_n)

в смешанных стратегиях можно рассматривать как точку в декартовом произведении X = Х₁ x . . . x Х_n симплексов смешанных стратегий. Это декартово произведение, очевидно, является выпуклым и компактным подмножеством евклидова пространства размерности m₁ + ... + m_n - n.

Положим теперь для произвольной ситуации X и любой чистой стратегии

,- игрока i

. (4)

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

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

Составим теперь для всевозможных i=1, …, n и j=1, …, m_j числа вида

(5)

Все эти дроби, очевидно, неотрицательны, а каждая сумма вида

равна единице.

Следовательно, при фиксированных X и i дроби (5) можно понимать

как вероятности соответствующих чистых стратегий игрока i. Тем

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

Так как дроби (5) составляются для каждого игрока i є I, их совокупность определяет систему смешанных стратегий всех игроков, т.е. некоторую ситуацию в игре Г. Эта ситуация зависит от исходной ситуации X, являясь ее функцией. Будем обозначать ее поэтому через ψ(Х). Очевидно, что функция ψ осуществляет преобразование замкнутого выпуклого и ограниченного множества всех ситуаций X в себя.

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

Второе слагаемое, как видно из (4), есть комбинация из линейных функций H_i (X) и, постоянной 0 и операции взятия максимума (то, что функция шах { 0, х }является непрерывной, легко усмотреть из ее графика на рис.2. Следовательно, также является непрерывной функцией X.

Рисунок 2

Значит, числитель дроби (5) есть непрерывная функция X. Наконец, знаменатель этой дроби непрерывен и притом не может приближаться к нулю (его значения не меньше единицы). Таким образом, функция ψ является непрерывной.

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

6. Решение биматричных игр

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

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

Пусть Г=Г(А,В)- m x n биматричная игра с матрицами выигрышей игроков:

(6)

Множество ζ₁(Г) всех ситуаций, приемлемых для игрока 1 в этой игре, состоит из всех ситуаций (X, У), для которых выполняется система неравенств:

(7)

Далее я буду рассматривать случаи, соответствующие тому или иному спектру стратегии¹² X.

Пусть. Тогда в (7) для по свойству дополняющей нежесткости¹³ должно выполняться точное равенство. Отсюда следует, что для любых двух смешанных стратегий X’ и Х'' обладающих одним и тем же спектром и дающих в паре с одной и той же стратегией Y приемлемые ситуации, должно быть X'AY^T = X»AY^T.

Таким образом, на множестве X(s_x) всех стратегий игрока 1 со спектром s_x величина ХАY^T не зависит от X.