Теория игр двух лиц или двух групп лиц

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

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

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

Теория игр двух лиц или двух групп лиц

План

• Введение в теорию игр
• Предмет теории игр
• Неформальное описание игры
• Игры двух лиц с нулевой суммой
• Игры с седловой точкой
• Смешанные стратегии
• Нахождение смешанной стратегии
• Геометрическое решение игры
• Игры двух лиц с ненулевой суммой
• Некооперативная игра двух лиц
• Кооперативная игра двух лиц. Переговорное множество
• Пример
• Список литературы

Введение в теорию игр

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

В художественной литературе этому столкновению интересов уделялось не меньше внимания, чем любви и Богу. Это столкновение интересов является предметом целого ряда наук, психологии, социологии, политологии. Даже экономическая наука по большому счету изучает столкновение интересов, так как конкуренция является именно таким столкновением. Но лишь в 40-е годы двадцатого века это столкновение интересов стало предметом математического исследования, прежде всего в области экономики. Первая значительная книга по теории игр ? книга Дж. фон Неймана и С. Моргенштерна, изданная в 1944 году так и называлась - “Теория игр и экономическое поведение”.

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

Предмет теории игр

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

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

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

По выигрышу:

1. Антагонистические игры;

2. Игры с нулевой суммой.

По характеру получения информации:

1. Игры в нормальной форме (игроки получают всю информацию до начала игры);

2. Динамические игры (информация поступает в процессе игры).

По количеству стратегий:

1. Конечные игры;

2. Бесконечные игры.

По составу игроков:

1. Бескоалиционные игры;

2. Коалиционные игры.

Неформальное описание игры

Всякая игра предполагает следующее:

1. Наличие некоторого числа n участвующих в ней лиц (игроков). Могут быть игры с одним игроком (пасьянс), двумя игроками (шахматы, муж с женой, две конкурирующие фирмы), тремя игроками (преферанс, три фирмы на рынке) и т.д. По числу игроков и идёт классификация игр ? игры двух лиц, трёх лиц и т.д.;

2. Конечный выигрыш (или проигрыш) каждого игрока. Когда игра кончается, каждый игрок получает доход (если значит, игрок проиграл), зависящий от его поведения и поведения других игроков.

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

,

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

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

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

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

2. Игры двух лиц с нулевой суммой

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

Итак, пусть имеется два игрока. В распоряжении первого игрока имеется всего n возможных ходов i=1,2,3,...,n; в распоряжении второго игрока имеется m возможных ходов j=1,2,3,...,n. Эти возможные ходы называются чистыми стратегиями игроков.

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

то первый игрок получает выигрыш, равный .Очевидно, что выигрыш второго игрока равен .

Эти данные можно записать в виде матрицы

,

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

Как же должны действовать игроки в такой ситуации? Какие ходы они должны делать?

3. Игры с седловой точкой

Рассмотрим с этих позиций игру со следующей платёжной матрицей

.

Попробуем порассуждать с точки зрения первого игрока. Если он сделает ход i=1, то наихудшей для него будет ситуация, когда второй игрок сделает ход j=3, так как в этом случае он получит 0. Если первый игрок сделает ход i=2, то в наихудшем случае (при ходе второго игрока j=1) он также получит 0. Аналогично, при i=3 он в наихудшем случае получит 4 (при j=2), при i=4 , 2 (при j=3 ) и, наконец, при i=5 он в наихудшем случае получит 0 (при j=3).

Стремясь сделать свой гарантированный выигрыш как можно больше, первый игрок должен выбрать ход i=3, так как в этом случае он гарантирует себе выигрыш, равный 4 (правда, и его максимальный выигрыш невелик , всего 5).

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

Если он выберет ход j=1, то его максимальный проигрыш будет равен 18 (если первый игрок сделает ход i=1). Аналогично, при j=2 его максимальный проигрыш будет равен 4, при j=3, 8, и, наконец, при j=4 его максимальный проигрыш будет равен 25. Стремясь сделать свой максимальный проигрыш как можно меньше, второй игрок должен выбрать ход j=2, так как в этом случае его максимальный проигрыш, равный 4, самый маленький.

Итак, мы пришли к выводу, что первый игрок должен ходить i=3, а второй j=2. Допустим теперь, что второй игрок, как говорят, “открывает карты” и заявляет первому игроку: “Я буду делать ход j=2”. Есть ли первому игроку необходимость менять свой ход? Нет, так как в этом случае его наилучший ход всё равно i=3.

Аналогично, если первый игрок заявит второму, что он будет ходить i=3, то второму игроку также нет смысла менять свой ход, так как наилучшим ответом будет всё равно j=2. Пара i=3, j=2 является, как говорят, уравновешенной парой, так как “открытие карт” игроками не даёт поводов противнику менять свою стратегию. Как говорят, пара i=3, j=2 есть решение игры, а величина выигрыша при этом первого игрока (и одновременно величина проигрыша второго) ? 4 ? это цена игры.

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

.

Стремясь сделать свой минимальный выигрыш максимальным, он выбирает свой ход из условия

.

Такая стратегия называется максиминной.

Аналогично, второй игрок, выбирая ход j, в наихудшей для себя ситуации проигрывает

.

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

.

Такая стратегия называется минимаксной.

Каково же соотношение между

и ?

Теорема 1. Пусть имеются два числовых множества и ; есть вещественная функция двух переменных при и . Тогда

,если и существуют.

Доказательство

По определению минимума, имеем

.

Аналогично, по определению максимума,

.

Следовательно

.

Но заметим, что правая часть этого неравенства не зависит от x . Поэтому

.

Аналогично, левая часть не зависит от y. Поэтому

,

что и требовалось доказать.

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

.

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

Определение. Пусть есть действительная функция, определённая

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

1. ;

2..

Теорема 2. Пусть ? действительная функция, определённая для всех и существует и . Тогда для того, чтобы

необходимо и достаточно, чтобы имела седловую точку.

Кроме того,если есть седловая точка функции ,то

.

Доказательство

Достаточность.

Пусть есть седловая точка функции .

,

откуда следует, что

.

Аналогично,

,

откуда следует, что

.

Сводя всё вместе, получаем

.

Но так как

,

,

то отсюда следует, что

.

Сравнивая это с результатом теоремы 1, где было доказано обратное неравенство, получаем, что

.

Необходимость.

Пусть

.

Пусть ? это тот элемент множества , при котором принимает своё максимальное значение, то есть

.

Аналогично, пусть ? это тот элемент множества , при котором принимает своё минимальное значение, то есть

.

Покажем, что <- седловая точка функции . В силу предположения о том, что , имеем

.(1)

По определению минимума, имеем

,

и поэтому из (1) следует, что

.

Отсюда следует, что

.(2)

Аналогично, по определению максимума,

,

и поэтому из (1) следует, что

.

Отсюда следует, что

.(3)

Объединяя вместе (2) и (3), получаем

,

что соответствует тому, что седловая точка функции .

Замечание. На основании интерпретации матрицы как функции двух переменных отсюда следует, что седловая точка платёжной матрицы определяется условием

,

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

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

Ответим еще на некоторые вопросы, касающиеся седловых точек.

1. Может ли у матрицы быть несколько седловых точек?

Ответ положительный да, может. Так, в матрице

две седловых точки (i=1, j=1) и (i=1, j=3).

2. Если седловых точек несколько, то не возникает ли каких-то противоречий между ними?

Ответ отрицательный. Более того, если () и () две седловые точки , то () и () тоже седловые точки и .

Докажем это для произвольной функции . Пусть и две седловые точки этой функции. Тогда имеем

,

,

и мы имеем следующую цепочку

,

откуда следует, что на самом деле

.

Отсюда же следует, например, что

,

то есть также седловая точка.

3. Все ли матрицы имеют седловую точку? Ответ отрицательный. У матрицы седловых точек нет.

4. Смешанные стратегии

Седловая точка в матричных играх всё-таки скорее исключение, чем правило. А что же может гарантировать себе игрок, если седловой точки нет?

Давайте снова рассмотрим игру с платёжной матрицей

.

теория игра математическая модель

Здесь , и между и образуется “дыра” Как можно её заполнить и чем?

Представим себя в позиции первого игрока. Он имеет гарантированный выигрыш (скорее, проигрыш), равный (-1). Как он может его повысить?

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

В такой ситуации единственный выход , выбирать свой ход случайным образом. Например, взять и подбросить монету. Упадёт она кверху орлом , делать ход i=1, выпадет решка , делать ход i=2. Что же это даст?

Выигрыш станет случайной величиной и оценивать его надо по математическому ожиданию. Пусть второй игрок делает ход j=1. Тогда математическое ожидание выигрыша первого игрока будет

.

Если второй игрок делает ход j=2, то математическое ожидание выигрыша первого игрока равно

.

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

Аналогично, второй игрок, бросая монету и выбирая ход в соответствии с её “указанием”, гарантирует себе в среднем проигрыш, равный 0. Это тоже лучше, чем проигрыш, равный 1.

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

Конечно, с обычных житейских позиций, случайный выбор хода не всегда приемлем. Вообразите себе военачальника, который выиграл сражение. Он даёт интервью по TV и на вопрос о том, как же он принял правильное решение, говорит: “Ну, я бросил монету, она упала орлом кверху, и поэтому я … ”. Как посмотрит на него телезритель? А если он проиграл битву, то как отнесётся к такому ответу его начальство?

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

6. Геометрическое решение игры

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

Рассмотрим идею этого решения на случае n=m=2, когда платёжная матрица имеет вид

.

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



Рассмотрим прямоугольную систему координат, где по оси абсцисс откладывается величина p (она занимает отрезок ), а по оси координат величина среднего выигрыша первого игрока.

Пусть второй игрок выбирает ход j=1. Тогда средний выигрыш первого игрока будет равен

,

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

,

что является отрезком прямой, соединяющей точки и .

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



и оптимальная смешанная стратегия первого игрока есть .

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

и равен также .

Таким образом, мы нашли и цену игры и оптимальные смешанные стратегии каждого игрока.

На рисунке приведен лишь самый интересный и стандартный случай. Возможны и другие варианты, два из который приведены ниже.



В варианте, приведенном на рис. 2, оптимальной для первого игрока является чистая стратегия с p=1, то есть первый игрок всегда должен выбирать первый ход; для второго игрока оптимальным является выбор второго хода, то есть i=1, j=2 является седловой точкой платёжной матрицы.

В ситуации, приведённой на рис. 3, есть целый отрезок оптимальных значений =, то есть оптимальная смешанная стратегия неоднозначна.

Эта методика легко переносится на случай, когда n=2, а m>2. Тогда платёжная матрица имеет вид

и мы должны нарисовать m отрезков прямых

,

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

которая даёт значение .

Рассмотрим это на примере. Пусть платёжная матрица имеет вид

.

Тогда мы должны построить три отрезка прямых

Они изображены на рис. 4, где также жирной линией

выделен минимальный выигрыш первого игрока.

Легко видеть, что максимальное значение этого минимального выигрыша определяется пересечением прямых, соответствующих j=2 и j=3, то есть определяется из условия

,

откуда следует, что , так что оптимальная смешанная стратегия

первого игрока есть .

Цена игры

.

Что касается второго игрока, то в образовании цены игры участвуют только j=2 и j=3. Поэтому ход j=1 он вообще не должен делать; считая, что , , получим

,

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

7. Игры двух лиц с ненулевой суммой

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

Здесь , выигрыш первого игрока и выигрыш второго, если первый игрок делает ход i, а второй j. Однако в данном случае

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

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

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

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

8. Некооперативная игра двух лиц

Пусть задана игра двух лиц с матрицей

.

В теории рассматриваются в основном две стратегии поведения игроков - это максиминная стратегия и так называемая стратегия угрозы.

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

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

.

Считая все ( как этого можно добиться говорилось выше), перейдём к величинам . Тогда имеем

,

.

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

,

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

Решение этой задачи и определяет максиминную стратегию первого игрока, так как

, .

Вторая стратегия - это так называемая стратегия угрозы или минимаксная стратегия. При её использовании игрок ставит своей задачей не выиграть самому, а “наказать” второго игрока, действуя по принципу: “пусть у меня две коровы сдохнут, лишь бы у соседа корова сдохла”.

Встанем снова на позицию первого игрока. Пусть он снова применяет смешанную стратегию . Но, применяя её, он считает не свой выигрыш, а выигрыш второго игрока. Если второй игрок делает ход j, то его средний выигрыш составит величину

.

Первый игрок действует по принципу

,

то есть он минимизирует максимальный выигрыш второго игрока.

Если обозначить максимальный выигрыш второго игрока через , то мы имеем

.

Считая все , что даёт , введём величины . Тогда получим

,

и желание минимизировать приводит нас снова к задаче линейного программирования

Решая эту задачу и находя , мы найдём и и смешанную стратегию первого игрока

Рассмотрим подробнее случай n=m=2. Тогда платёжная матрица игры имеет вид

.

Найдём геометрически максиминную стратегию и стратегию угрозы первого игрока.

Начнём с максиминной стратегии. Пусть первый игрок выбирает ход i=1 с

вероятностью .Тогда .Если второй игрок делает ход j=1, то средний выигрыш первого игрока будет равен ,что даёт отрезок прямой, соединяющий точки и .

Если второй игрок делает ход j=2, то средний выигрыш первого игрока будет равен , что даёт отрезок, соединяющий точки и . Минимум из этих двухвыигрышей на рисунке нарисован жирной линией, из которой ясно, как определяется гарантированный выигрыш

первого игрока и оптимальное значение :

.

Чему равен и в других случаях расположения этих двух прямых сообразите сами.

Теперь рассмотрим стратегию угрозы первого игрока. Пусть он снова применяет смешанную стратегию . Если второй игрок делает ход j=1, то средний выигрыш второго игрока будет равен , что даёт отрезок прямой, соединяющий точки и . Если второй игрок делает ход j=2, то его средний выигрыш будет равен .

Напомним, что первый игрок считает сейчас не свой выигрыш, а выигрыш второго игрока. Его задача - минимизировать его максимальный выигрыш. Максимальный выигрыш второго игрока изображен на рис. 6 жирной

линией; из рисунка же ясно, как находятся и :

.

Проиллюстрируем эти понятия на примере игры, которая имеет платёжную матрицу



и которая получила название “семейный спор”. Название возникло из-за следующей её интерпретации. Муж (игрок 1) и жена (игрок 2) могут выбирать одно из двух вечерних развлечений ? футбол (i=1, j=1) или театр (i=2, j=2). Согласно обычному стандарту, мужчина предпочитает футбол, а женщина ? театр. Однако им гораздо важнее идти вместе, чем смотреть своё предпочтительное зрелище. И если они поругаются и пойдут в разные стороны (i=1, j=2 или i=2, j=1), то оба проиграют, получая (-1,-1).

Найдём стратегии первого игрока (очевидно, что в силу симметричности платёжной матрицы стратегии второго игрока точно такие же).

Рассматривая максиминную стратегию первого игрока, когда он выбирает ход i=1 с вероятностью p, получим, что его выигрыш будет равен

при ,

при .

Соответствующие прямые изображены на рис. 7. Величина находится из условия

,

откуда имеем ,так что смешанная стратегия первого игрока есть и его гарантированный выигрыш равен

.

Применяя стратегию угрозы, он считает выигрыш второго игрока, который будет равен

при ,

при .

Соответствующие прямые изображены на рис. 8. Величина находится из условия

откуда следует, что p=3/5, так что смешанная стратегия первого игрока есть (3/5,2/5). При этом выигрыш второго игрока будет в любом случае равен

.

Таким образом, применяя максиминную стратегию первый игрок может гарантировать себе выигрыш, равный 1/5; применяя стратегию угрозы он может быть уверен, что второй игрок получит не более 1/5.

9. Кооперативная игра двух лиц. Переговорное множество

Прежде, чем говорить о кооперативных играх, вернёмся еще раз к последнему примеру - игре “семейный спор”. Пусть первый игрок использует смешанную стратегию (p,1-p), второй , стратегию (q,1-q). Тогда средние выигрыши игроков будут равны

,

.

Тем самым пара (p, q) превращается в пару .

Рассмотрим плоскость . Перебирая все возможные значения пар (p, q) мы получим на плоскости некоторую область, которая изображена на рис. 9. Она ограничена прямыми, проходящими через пары точек ( 1, 1), (1, 2) и ( 1, 1), (2, 1), а также куском параболы . В ней есть “провал”, ограниченный именно этой параболой.

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

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

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

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

Раньше ход номер i первого игрока выбирался с вероятностью и ход номер j второго игрока с вероятностью и ходы обоих игроков были независимы так что комбинация (i, j) появлялась с вероятностью . Сейчас ходы выбираются совместно и поэтому комбинация ходов появляется с некоторой совместной вероятностью . Совместная игра сводится таким образом к выбору совместной смешанной стратегии . При этом, очевидно,

.

При такой совместной смешанной стратегии средние выигрыши первого и второго игроков равны соответственно

. (9)

Представим себе плоскость .Какую область заполняют в ней значения и , получаемые по формулам (9)?

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

Так в игре типа “семейный спор” область R есть выпуклая оболочка точек (-1,-1), (2, 1) и (1, 2) (см. рис. 11).

Сравните эту область с той, которая изображена на рис. 9. Мы видим, что применение совместных стратегий позволило заполнить ту “впадину”, которая была при некооперативной игре.

О чем же теперь могут договориться наши игроки? Пусть и есть максиминные выигрыши первого и второго игроков соответственно. Нанесём на наше множество R точку с координатами . Эта точка называется точкой status quo. Очевидно, что ни один из игроков не согласится получать в результате совместной игры меньше, чем даёт ему максиминная стратегия ? зачем ему такая договорённость, если он может гарантировать себе или без всяких договорённостей.



Поэтому из нашего множества R сразу исчезает область, где или .

Рассмотрим теперь оставшуюся область, где и .

Определение 1. Точка называется подчинённой точке если одновременно и , причем хотя бы одно из этих неравенств строгое.

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

Определение 2. Множество точек из R, которые не подчинены никаким другим точкам и для которых выполняется условие , называется переговорным множеством или множеством Парето.

Легко догадаться, что переговорное множество это та часть правой верхней (или, как еще говорят, северо-восточной) границы множества R, для которой выполнены условия .

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

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

1. На плоскости нанести точки , , .

2. Построить выпуклую оболочку этих точек.

3. Найти максиминные выигрыши обеих игроков и построить точку status quo.

4. Нарисовать северо-восточную границу построенного множества, удовлетворяющую условиям

На этом работа математика заканчивается. А дальше , торгуйтесь, ребята!

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

Пример

Цель работы

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

Задание

Для заданной игры:

1. Сделать формальную постановку задачи.

2. Определить множество возможных стратегий игроков, при этом по возможности исключить эквивалентные стратегии.

3. Выписать матрицу игры.

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

Описание игры

Упрощенный покер.

Первый игрок получает одну из карт Ст и Мл с равными вероятностями, а затем может или "сделать ставку" или "спасовать". Если первый делает ставку, то второй может "спасовать" и потерять или "уравнять игру", и выиграть или потерять в зависимости от того, имеется ли на руках у первого игрока карта Мл или Ст. Если первый игрок пасует, то второй может также пасовать, что дает выигрыш 0, или сделать ставку, выигрывая , если у первого игрока карта Мл, и теряя , если у первого игрока старшая карта.

Решить задачу при ,

Математическая постановка.

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

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

Делать ставку (в дальнейшем ставить) вне зависимости от того, какая карта ему пришла (старшая или младшая).

Пасовать также вне зависимости от пришедшей карты.

Ставить, если пришла старшая карта, и пасовать, если пришла младшая.

Ставить, если пришла младшая, а пасовать, если пришла старшая.

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

Ставить вне зависимости от заявки первого игрока.

Пасовать вне зависимости от заявки первого игрока.

Ставить в ответ на ставку первого игрока, и пасовать, в ответ на пас.

Ставить в ответ на пас, и пасовать в ответ на ставку.

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

Зная, что вероятность прихода первому игроку любой из карт равна 1/2 , мы можем выписать платежную матрицу игры - A. Элемент этой матрицы равен ожидаемому выигрышу первого игрока при использовании им стратегии , и использовании вторым игроком стратегии . Так:

(1)

Здесь - размер выигрыша первого игрока, если он сделал заявку З¹ при наличии у него карту достоинства К, а второй игрок сделал заявку З². Вычислим, аналогично (1) все остальные элементы матрицы:

Т.о. получили следующую матрицу:

(2)

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

Нижняя цена игры равна

. (3)

Верхняя цена игры - (4)

Т.е. верхняя и нижняя цена игры не совпадает, следовательно, оптимального решения в чистых стратегиях не существует.

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

В этом случае цена игры будет равна

. (5)

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

Введем величину

, (6)

тогда, очевидно,

, (7)

и получаем следующие неравенства:

.(8)

Тогда из (6-8) получаем следующую задачу линейного программирования:

 (9)

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

Исходя из (3) и (4) положим цену игры - , и введем новые переменные:

(10).

Отысканию максимума величины , очевидно, будет соответствовать поиск максимума , откуда получаем:

.

Разделим теперь систему неравенств из (9) на , и получим новую задачу линейного программирования:

(11)

Решив задачу (11), получим ее решение(x^*₁..x^*₄),

(1/2,1,1,0) исходя из (10), цену игры найдем как:

(12),

а компоненты вектора смешанной стратегии первого игрока:

.(13)

(14).

Видим, что

Найдем, также оптимальную смешанную стратегию для второго игрока, являющуюся решением задачи л.п., двойственной к (11):

(15)

Как, видно:

Т.е. в ходе решения получили следующие результаты:

1.Оптимальная смешанная стратегия первого игрока:

2.Оптимальная смешанная стратегия второго игрока:

3. Цена игры:

. (16)

Таким образом, из (3),(4),(16) получили, что выполняется соотношение .

Будем считать задачу решенной.

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

1. Вавилов В.А., Змеев О.А., Змеева Е.Е. Исследование операций.

2. Оуэн Г.Теория игр. М.:Мир,1971.

3. Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.?М.: Наука, 1981.?336 с.

4. Коваленко А. А. Сборник задач по теории игр. Львов,1974.

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