Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - методы и модели в технике и экономике, Кулаго - файл ВВЕДЕНИЕ В ТЕОРИЮ ИГР.doc


Лекции - методы и модели в технике и экономике, Кулаго
скачать (3095.1 kb.)

Доступные файлы (5):

ВВЕДЕНИЕ В ТЕОРИЮ ИГР.doc449kb.05.11.2002 06:47скачать
методы и модели 1_2.doc536kb.11.11.2002 09:44скачать
методы и модели 4_6.doc2396kb.25.10.2002 05:55скачать
методы и модели игры 32.doc1022kb.23.10.2002 11:07скачать
методы и модели игры 3.doc2582kb.23.10.2002 07:23скачать

содержание

ВВЕДЕНИЕ В ТЕОРИЮ ИГР.doc

БИМАТРИЧНЫЕ ИГРЫ
Предыдущие рассмотрения касались игр двух лиц, в которых интересы игроков
были прямо противоположны (антагонистические, или матричные игры), а также
позиционных игр, сводимых к матричным. Однако ситуации, в которых интересы
игроков хотя и не совпадают, но уже не обязательно являются противоположными,
встречаются значительно чаще.

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

игрок А — может выбрать любую из стратегий А1, ... , Am,

игрок В — любую из стратегий В1,..., Вn.

При этом всякий раз их совместный выбор оценивается вполне определенно:

если игрок А выбрал i-ю стратегию Ai, а игрок Вk-ю стратегию Вk, то в итоге выигрыш игрока А будет равен некоторому числу aik, а выигрыш игрока В некоторому, вообще говоря, другому числу bik.

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

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




B1



Bk



Bn

A1

a11



a1k



a1n



………………………………….

Ai

ai1



aik



ain



………………………………….

Am

am1



amk



amn







B1



Bk



Bn

A1

b11



b1k



b1n



………………………………….

Ai

bi1



bik



bin



………………………………….

Am

bm1



bmk



bmn

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

,

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

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

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

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

bik.= -aik

или

,

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

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

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

^ Пример 20. «Борьба за рынки. Небольшая фирма (игрок А) намерена сбыть партию товара на одном из двух рынков, контролируемое другой, более крупной фирмой (игрок В) Для этого фирма А готова предпринять но одном из рынков соответствующие приготовления (например, развернуть рекламную компанию). Господствующая на рынках фирма В может пытаться воспрепятствовать этому, приняв на одном из рынков предупредительные меры (разумеется, в рамках закона). Не встречая противодей­ствия на рынке, фирма А захватывает его; при наличии препятствий — терпит поражение.

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

Что же касается второго рынка, то при поражении фирмы А ее потери будут не столь разорительны, но и победа принесет немного.

Таким образом, у фирмы А два стратегии:

^ А1 — выбор первого рынка, А2 — выбор второго рынка.

Такие же стратегии и у фирмы В:

В1 — выбор первого рынка, В2 — выбор второго рынка.

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

,

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

То, что в ситуации (А1, В1) выигрыш игрока В равен 5, а в ситуации (А2, В2) — 1, подчерки­вает, что первый рынок более выгоден (удобно расположен, хорошо посещаем и т.п.), чем второй. Выигрыш (-10) игрока А в ситуации (А1, В1) (а точнее, проигрыш) в сопоставлении с его выигры­шем (-1) в ситуации (А2, В2) выглядит, разумеется, вполне сокрушительно. Что же касается ситуации, когда фирмы уделяют основное внимание разным рынкам (А1, В2) и (А2, В1), то здесь фирму А ждет настоящий выигрыш, больший на более выгодном рынке. Потери, которые при этом несет фирма В, оказываются прямо противоположными.


Замечание. Ясно, что точно рассчитать выгоду и ущерб сторон в этом конфликте заранее довольно трудно. А дот в следующей конфликтной ситуации размеры выигрышей игроков известны со всей определенностью.

^ Пример 21. «Дилемма узников. Игроками являются два узника, находящихся в предварительном за­ключении по подозрению в совершении преступления. При отсутствии прямых улик возможность их осуждения в большой степени зависит от того; заговорят они или будут молчать.

Если оба будут молчать, то наказанием будет лишь срок предварительного заключения (потери каждого из узников составят (-1)). Если сознаются, то получат срок, учитывающий признание как смягчающее обстоятельство (потери каждого из узников составят в атом случае (-6)). Если же заго­ворит только один из узников, а другой будет молчать, то в этом случае заговоривший будет выпущен на свободу (его потери равны 0), а сохраняющий молчание получит максимально возможное наказание (его потери будут равны (-9)).

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

Выигрыши игроков А и В соответственно описываются так:





(М)

(Г)

(М)

-1

-9

(Г)

0

-6




(М)

(Г)

(М)

-1

-9

(Г)

0

-6



^ Пример 22. «Семейный спор». Два партнера договариваются о совместном проведении одного из двух действий, (1) и (2), каждое из которых требует их совместного участия.

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

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




(1)

(2)

(1)

2

0

(2)

0

1







(1)

(2)

(1)

1

0

(2)

0

2


Пояснение. Довольно понятно, что различные конфликтные ситуации могут иметь одну и ту же формализацию. В частности, рассмотренная биматричная игра часто интерпретируется, как одновременный выбор супругами совместного развлечения: посещение оперного спектакля или хоккейного матча. При этом в посещении оперного театра жена заинтересована в большей степени, чем муж, а при посещении стадиона наблюдается обратная картина. В случае же непреодоления разногласий, возникших при выборе, день оказывается вообще испорченным. Отсюда и название, вынесенное в заголовок.
^ Пример 23. «Студент — Преподаватель. Рассмотрим следующую ситуацию. Студент (игрок А) готовится к зачету, который принимает Преподаватель (игрок В), Можно считать, что у Студента две стратегии — подготовиться к сдаче зачета (+) и не подготовиться (-). У Преподавателя также две стратегии — поставить зачет [+] и не поставить зачета [-].

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

Выигрыш Студента




[+]

[-]

(+)

оценка заслужена

очень обидно

(-)

удалось обмануть

оценка заслужена




Выигрыш Преподавателя




[+]

[-]

(+)

все нормально

был неправ

(-)

дал себя обмануть

опять придет



Количественно это можно выразить, например, так





[+]

[-]

(+)

2

-1

(-)

1

0







[+]

[-]

(+)

1

-3

(-)

-2

-1



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

Попробуем ответить на это вопрос так:

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

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

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

А1, … , Аm, B1, … , Bn.

Естественно ожидать, что в более сложном случае биматричной игры дело вряд ли обстоит проще.

Однако при расширении матричной игры путем перехода к смешанным стратеги­ям, т. е. к такому поведению игроков, при котором они чередуют (чистые) стратегии с определенными частотами: игрок А — стратегии А1, … , Аm с частотами р1, … , рm, где



а игрок B — стратегии B1, … , Bn с частотами q1, … , qn, где



выяснилось, что в смешанных стратегиях равновесная ситуация всегда существует. Иными словами, любая матричная игра в смешанных стратегиях разрешима.

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

В матричном случае смешивание стратегий приводило к расширению возможно­сти выплат в том смысле, что расчет строился из вычисления средних выигрышей игроков А и В, которые определялись по элементам платежной матрицы А и вероят­ностям рi, и qk:



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


^ 2 X 2 биматричные игры, Ситуация равновесия

Мы предполагаем уделить основное внимание случаю, когда у каждого из игроков имеется ровно две стратегии, т. е. случаю m = n = 2. Поэтому нам кажется уместным выписать приведенные выше формулы именно для такого случая.

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



вероятности



а средние выигрыши вычисляются по формулам



где



Сформулируем основное определение.

Определение. Будем говорить, что пара чисел



определяет равновесную ситуацию, если для любых р и q, подчиненных условиям одновременно выполнены следующие неравенства

(#)

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

Но может ли быть подобная ситуация равновесия в биматричной игре? Ответ на по­ставленный вопрос дает следующее утверждение.

^ Теорема 4 (Дж. Наш). Всякая биматричная игра имеет хотя бы одну равновесную ситуацию (точку равновесия) в смешанных стратегиях.

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

Итак, равновесная ситуация существует. Но как ее найти?

Если некоторая пара чисел (р*, q*) претендует на то, чтобы определять ситуа­цию равновесия, то для того, чтобы убедиться в обоснованности этих претензий, или, наоборот, доказать их необоснованность, необходимо проверить справедливость не­равенств (#) для любого р в пределах от 0 до 1 и для любого q в пределах от 0 до 1.

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

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

(#)

равносильно выполнению неравенств

(##)
Иными словами, для того, чтобы убедиться в обоснованности претензий пары (р*, q*) на то, чтобы определять равновесную ситуацию, достаточно проверить справедливость неравенства



только для двух чистых стратегий игрока, A (p = 0 и р = 1) и неравенства



только для двух чистых стратегий игрока В (q = 0 и q = 1).

Четыре неравенства (##) позволяют провести поиск точки равновесия уже вполне конструктивно.

Запишем средние выигрыши игроков А и В в более удобной форме. Имеем



Обратимся к первой из полученных формул. Полагая в ней сначала р = 1, а потом р = 0, получаем, что



Рассмотрим разности



Полагая



получим для них следующие выражения



В случае, если пара (р, q) определяет точку равновесия, эти разности неотрицательны



Поэтому окончательно получаем



Из формул для функции при q = 1 и q = 0 соответственно имеем



Разности

и

с учетом обозначений



приводятся к виду



совершенно так же, как соответствующие разности для функции НА.

Если пара (р, q) определяет точку равновесия, то эти разности неотрицательны



Поэтому



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

Для того, чтобы в биматричной игре



пара (р, q) определяла равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств

(*)

где

(**)
^

Поиск равновесных ситуаций


Геометрический смысл условий (*) рассмотрим на примерах описанных выше биматричных игр.

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

,

Заменяя в неравенстве (*) величины С, α, D и β их конкретными значениями



получаем



Рассмотрим сначала левую пару неравенств (l)



Возможны следующие три случая



1. Полагая р = 1, получаем


Откуда




и, значит,



2. Полагая р = 0, получаем



Откуда



и, значит,



3. Наконец, положив 0 < р < 1, получим



что возможно лишь в случае, если



т.е.



Сформулируем результат наших рассмотрений:



Перенесем теперь полученные сведения на чертеж.

Введем на плоскости прямоугольную систему координат (р, q) и выделим на ней единичный ква­драт, соответствующий неравенствам



(рис. 1).


Рис. 1 Рис. 2 Рис. 3

Нанесем на этот чертеж то множество точек, которое описывается условиями 1°, 2° и 3°. Это множество (на рис. 2 его точки выделены жирной линией) состоит из трех прямолинейных участков — двух вертикальных лучей и одного горизонтального отрезка — и представляет собой «зигзаг». Нас будет интересовать только та его часть, которая попала в заштрихованный на рис. 2 единичный квадрат.

Оставив на время полученные результаты в покое, обратимся к правой части неравенств (r):



Три интересных для нас случая



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


Перенося его на чертеж, получим второй «зигзаг», но уже горизонтальный (рис. 3). Теперь остается только объединить полученное на рис. 4.

Общая точка построенных зигзагов – точка равновесия – имеет координаты

.

Соответствующие смешанные стратегии игроков имеют следующий вид



а средние выигрыши игроков таковы



Замечание. Попробуем разбить рассмотренную биматричную игру на две матричные игры с нулевой суммой.

1. Игра с матрицей А.



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



цену этой игры



а затем и оптимальную смешанную стратегию для игрока В



2. Игра с матрицей В.



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



цену этой игры



а затем и оптимальную смешанную стратегию для игрока А



Сравнивая полученные результаты с решением биматричной игры, можно заметить следующее: если каждый игрок будет применять свои стратегии в этой игре, исходя только из матрицы своих вы­игрышей, то его оптимальный средний выигрыш совпадет с его выигрышем при равновесной ситуации; кстати, по своей матрице игрок может найти и оптимальную смешанную стратегию другого игрока (но не свою!).
^ Пример 21. «Дилемма узников» (продолжение). Выигрыши игроков А и В описываются соответствующи­ми матрицами выплат

,

Проведем необходимые вычисления. Имеем



Отсюда



получим, что



Полученные зигзаги изображены на рис. 5.



Рис. 5
Единственная равновесная ситуация — (0, 0). Это ситуация, в ко­торой каждый из игроков выбирает вторую чистую стратегию — со­знаться — и теряет 6.

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

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

Совершенно ясно однако, что в рассматриваемых обстоятельствах ситуация (0, 0) неустойчива — любой из узников, изменяя свою стра­тегию, увеличивает свой выигрыш (избегает наказания).

^ Пример 22. «Семейный спор» (продолжение). Выигрыши игроков А и В в этой биматричной игре зада­ются так:

, .

Проводя необходимые вычисления



и рассуждения



получаем, что



Геометрически полученный результат выглядит так (рис.6).



Рис. 6
Данная игра имеет три точки равновесия. Две из них отвечают чистым стратегиям игроков,



одна — смешанная,



Признаться, полученные результаты ставят больше вопросов, чем дают ответов.

Ситуации (1, 1) и (0, 0) соответствуют одновременному выбору игроками своих первых или, соответственно, вторых стратегий, то есть определенной договоренности о совместных действиях.

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

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

Если бы игроки договорились играть оба, скажем, первую чистую стратегию, причем игрок ^ А за по­лучение большего выигрыша, чем игрок В, заплатил бы ему 1/2, то выигрыш каждым полутора единиц можно было бы считать и выгодным и справедливым. Однако в рамках теории бескоалиционных игр такого рода дележи не рассматриваются.

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

Наконец, обратимся к последнему из приведенных выше примеров биматричных игр — «Студент — Преподаватель».
^ Пример 23. «Студент — Преподаватель» (продолжения). Впечатления у каждого из них относительно результатов общения в матричном виде выглядят следующим образом

, .

Проводя необходимые вычисления



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






Рис. 7

(рис. 7).

Число точек пересечения у зигзагов (равновесных ситуаций) рав­но трем. Две из них отвечают чистым стратегиям игроков,



одна — смешанная,



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

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

^

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


Содержательные представления об устойчивости, выгодности и справедливости мно­гообразны. Выше мы рассматривали проявление устойчивости через равновесие. Существует и иной вариант устойчивости ситуации, в большей степени, чем равновесность, отражающий черты ее выгодности. Это оптимальность по Парето.
^ 5.1. Множество Парето

Рассмотрим на плоскости (U, V) множество Ω (рис. 8). Каждая его точка облада­ет одним из следующих свойств: либо все точки, ближайшие к ней, принадлежат множеству Ω (такая точка называется внутренней точкой множества Ω), либо сколь угодно близко от нее расположены как точки множества Ω, так и точки, множеству Ω не принадлежащие (такие точки называются граничными точками множества Ω). Гра­ничная точка может как принадлежать множеству Ω, так и не принадлежать. Здесь мы будем рассматривать только такие множества, которым принадлежат все точки границы. Множество всех граничных точек множества называется его границей. Обо­значение: дΩ.



Рис. 8 Рис. 9
Пусть М — произвольная точка множества Ω, внутренняя или граничная, и (U, V) —ее координаты. Поставим следующий вопрос: можно ли, оставаясь во мно­жестве Ω, переместиться из точки М в близкую точку так, чтобы при этом увеличились обе ее координаты. Если М — внутренняя точка, то это бесспорно возможно. Если же М — граничная тонка, то такое возможно не всегда (рис. 9). Из точек М1, М2, М3 это сделать можно, но уже из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата U при этом остается неизменной). Пе­ремещая точку горизонтального отрезка PQ вправо, мы увеличиваем координату U (при этом координата V сохраняет свое значение). Что же касается дуги BQ, то пере­мещение вдоль нее способно увеличить лишь одну из координат при одновременном уменьшении другой.

Тем самым, точки множества Ω можно разбить на три класса:

  • в первый класс относятся точки, которые, оставаясь во множестве и, можно сдвинуть так, чтобы одновременно увеличились обе координаты (в этот класс попадают все внутренние точки множества Ω и часть его граничных точек),

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

  • в третий класс попадут точки, перемещение ко­торых по множеству Ω способно лишь уменьшить либо одну из координат, либо обе (дуга BQ грани­цы дΩ) (рис. 10).

Множество точек третьего класса называется мно­жеством Парето, или границей Парето данного множе­ства Ω (выделено на рис. 10).



Рис. 10



Рис. 11


^ 5.2. Метод идеальной точки

Пусть на плоскости (х, у) задано множество ω (рис. 11) и в каждой точке этого множества определены две не­прерывные функции

U = Ф(х, у) и V = ψ(х, у)

Рассмотрим следующую задачу.

Во множестве ω найти точку (х*, у*), в которой

и

Обычно это записывается так

Ф(х, у) → max и ψ(х, у) → max



Сразу же отметим, что в общем случае поставленная задача решения не имеет. В самом деле, нарисуем на плоскости (U, V) все точки, координаты которых вы­числяются по формулам

U = Ф(х, у) и V = ψ(х, у),

Из рис. 12 видно, что наибольшее значение U - Umax — и наибольше значение V - Vmax — достигаются в разных точках, а точка с координатами

(Umax , Vmax)

лежит вне множества Ω.

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

Опишем один из путей, использующий множество Парето.



Рис. 12 Рис. 13
Сначала на плоскости (U, V) задается целевая точка, в качеств координат которой часто выбирается сочетание наилучших значений обоих критериев U и V.

В данном случае это точка (Umax , Vmax).

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

Затем строится множество Парето и на нем ищется точка, ближайшая к точке утопии — идеальная точка (рис. 13).


5.3. Оптимальность по Парето в биматричной игре
^

Рассмотрим биматричную игру с 2 х 2-матрицами




Пусть и — средние выигрыши игроков А и В.

Ситуация (р*, q*) в биматричной игре А и В наказывается оптимальной по Парето, если из того, что

и

вытекают равенства



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

Различие ситуации равновесия от ситуации, оптимальной по Парето, состоит в сле­дующем:

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

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

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


Рис. 14

Напомним, что соответствующие платежные матрицы в этой игре имели следующий вид



Тем самым, на единичном квадрате



(рис. 14) возможных значений вероятностей р и q заданы две функции



Точки с координатами (U, V), вычисленными по приведенным формулам, на плоскости (U, V) заполняют четырехугольник с вершинами К(-1, -1), L(-9, 0), М(-6, -6) и N(0, -9) (рис. 15). Граница Парето этого множества — ломаная NKL.


Рис. 15 Рис. 16
Каждый из игроков заинтересован в наибольшем значении своего среднего выигрыша



Нетрудно заметить, что в данном случае

Umax = 0 и Vmax = 0.

Тем самым, точкой утопии в этой задаче является начальная точка О (0, 0). Ближайшая к ней точка множества Парето — К (-1, -1) (рис. 16).

Идеальная точка К (-1, -1) — точка с наибольшими выигрышами для каждого из игроков — оказывается лучше, чем равновесная точка М(-6, -6), и ей соответ­ствуют чистые стратегии обоих игроков

p = 1, q = 1.


§ 6. Несколько слов в заключение
На анализе полученных результатов стоит остановиться чуть подробнее.

Из приведенных примеров видно, что числа С и D из соотношений (**) могут быть как положительными, так и отрицательными. Они могут, в частности, даже обращаться в нуль.

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

CD ≠ 0.

Тогда, как нетрудно видеть, точка равновесия определяется парой



Эти формулы являются весьма примечательными: в равновесной ситуации выбор игрока ^ А полностью определяется элементами платежной матрицы игрока В,



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



(и не зависит от элементов его собственной платежной матрицы).

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Будем считать, что если игрок А добился превосходства на одном из рынков (на другом превосходства автоматически добивается игрок В), то он вытесняет про­тивника с этого рынка и получает выигрыш, пропорциональный избытку вложенных средств с коэффициентом, характеризующим важность рынка (этот коэффициент ра­вен k1 для первого рынкам k2 Для второго). Тогда функция выигрыша H (x, у) игрока А определяется формулой



Ясно, что функция выигрыша игрока В равна -Н(х, у).

Дуэль


Два дуэлянта (игроки А и В) начинают сходиться в момент времени t = 0. У каждого пистолет заряжен одной пулей. Они встретятся в момент времени t = 1 (если только ни один из них не застрелит другого раньше). Каждый из дуэлянтов может выстрелить, когда пожелает. Если при этом одному из них удастся поразить противника, а самому остаться невредимым, то он становится победителем (его выигрыш равен 1) и дуэль тут же прекращается. Если оба промахнутся, дуэль закончится вничью (выигрыш каждого из игроков равен 0). Если оба выстрелят одновременно и каждый поразит противника, то дуэль также считается окончившейся вничью.

Если игрок ^ А произведет выстрел в момент времени х (), то его выстрел будет успешным с вероятностью р(х). Подобным же образом, выстрел игрока В в момент времени у () будет успешным с вероятностью q(y). При условии х < у игрок А выиграет с вероятностью р(х), а проиграет с вероятностью (1 - р(х))q(y). Тем самым, его средний выигрыш при х < у будет равен



С другой стороны, если х > у, его средний выигрыш будет равен



При х = у средний выигрыш



Таким образом, функция выигрыша Н(х, у) игрока А имеет вид



и антагонистическая игра задана. В частности, если игроки стреляют без промаха, - р(х) = q(y) = 1,



^

Дифференциальная игра поиска


Ищущий (игрок А) стремится обнаружить уклоняющегося (игрока В). Оба игрока перемешаются с постоянными скалярными скоростями (α и β соответственно) по плоскости внутри некоторой поисковой области Ω. В любой момент времени каждый из игроков управляет своим перемещением, задавая направление вектора скорости. Пусть (хА, уА) и (хB, уB) — координаты игроков. Тогда имеем



Игра поиска заканчивается в тот момент, когда игроки сблизятся на расстояние l > 0, иными словами, когда будет выполнено неравенство



В случае успешного обнаружения выигрыш игрока А считается равным 1.

Построение решения в этой игре существенно зависит от характера и степени информированности игроков.

* * *

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

Другой важный класс составляют кооперативные игры, в которых разрешены са­мые разнообразные формы сотрудничества. Возможность соглашений между игро­ками оказывает существенное влияние на исход игры. Если допустить, например, в игре «Дилемма узников» совместный выбор стратегий, то исход игры может оказать­ся совсем иным. При наличии побочных платежей по-иному окончится и «Семей­ный спор».

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

^ Задачи к разделу

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

a) б)
2. Найдите решения следующих матричных игр:

а) б) в)
г) д)

3. Найдите точные и приближенные решения следующих матричных игр:
а) б)
4. Дайте графическое представление, приведите к нормальной форме и найдите точное решение позиционной игры со следующей функцией выигрышей W(x, y, z)
W(1, 1, 1) = 2 W(2, 1, 1) = -1

W(1, 1, 2) = -2 W(2, 1, 2) = 3

W(1, 2, 1) = 1 W(2, 2, 1) = 0

W(1, 2, 2) = 0 W(2, 2, 2) = -3
а) 1-й ход делает игрок А: он выбирает число х из множества двух чисел {1, 2}. 2-й ход делает игрок В: не зная о выборе игрока А на 1 -м ходе, он выбирает число у из множества двух чисел {1, 2}. 3-й ход делает игрок А: он выбирает число z из множества двух чисел {1, 2}, зная значение у, выбранное игроком В на 2-м ходе, но не помня собственного выбора х на 1-м ходе.

б) 1-й ход делает игрок A: он выбирает число х из множества двух чисел {1, 2}. 2-й ход делает игрок B: зная выбор игрока А на 1-м ходе, он выбирает число у из множества двух чисел {1, 2}. 3-й ход делает игрок А: он выбирает число z из множества двух чисел {1, 2}, не зная значения у, выбранного игроком В на 2-м ходе, но помня собственный выбор х на 1-м ходе.

в) 1-й ход производится случайно: игрок О выбирает число х, равное 1 с вероятностью 0,3 и равное 2 с вероятностью 0,7. ^ 2-й ход делает игрок А: он выбирает число у из множества двух чисел {1, 2}, зная результат случайного выбора на 1-м ходе. 3-й ход делает игрок В: он выбирает число z из множества двух чисел {1, 2}, зная выбор у игрока А на 2-м ходе, но не зная случайного выбора х на 1-м ходе.

5. Найдите решение биматричной игры:
а) .

б) .

в) .

г) «ястреб-голубь»

Найдите ситуации равновесия в каждом из двух случаев: 1) a > b, 2) a < b.

Ответы







Скачать файл (3095.1 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации