Материал: Экономико-математические методы и модели. Гасилов В.В., Околелова Э.Ю

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

m

xi≥0, i=1, …, m, ∑xi =1, (5.3)

i=1

n

yj≥0, j=1, …, n, ∑y j =1, (5.4)

j=1

а второй игрок выбирает стратегию, обеспечивающую

Эти величины определяются соответственно как среднеожидаемые максиминные и среднеожидаемые минимаксные платежи.

Если х* i и у* j — оптимальные решения для обоих игроков, каждому элементу платежной матрицы aij соответствует вероятность xi* y*j . Следова-

m n

тельно, оптимальное ожидаемое значение игры v* = ∑∑aij xi* y*j .

i=1 j=1

Как и в случае чистых стратегий, выполняется соотношение:

минимаксный ожидаемый проигрыш ≥ максиминный ожидаемый выигрыш.

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

Справедлива следующая основная теорема теории матричных игр с нулевой суммой (теорема фон Неймана).

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

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

Так же, как и для вполне определенных игр, стратегия х* Игрока 1 называется максиминной, стратегия y* Игрока 2 – минимаксной, значение v – ценой игры.

В случае, когда v=0, игра называется справедливой.

Очевидным следствием из теоремы о минимаксе является соотноше-

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

86

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

5.5. Игры с ненулевой суммой и кооперативные игры

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

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

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

Один из подходов к решению некооперативных игр состоит в определении точек равновесия игры. Понятие равновесия в теории игр шире понятия оптимальности в теории оптимизации и включает последнее в качестве частного случая. В общем случае пара стратегий X, Y для Игрока 1 и Игрока 2 называется точкой равновесия по Нэшу, если ни одному из игроков невыгодно отклоняться от своей стратегии в одиночку, если выигрыш при этом не увеличивается.

Рассмотрим пример, когда матрица выигрышей игры имеет следующий вид:

(4;1) (0;0)

(0;0) (1;4) .

Легко видеть, что в данной игре пары стратегий х = (1, 0), у = (1, 0) и х=(0,1), у = (0,1) являются равновесными, т.е. Игроку 2 (1) невыгодно отклоняться от 1-й (2-й) стратегии, если Игрок 1 (2) придерживается 1-й (2-й) стратегии. Отметим также, что выигрыши в равновесных точках различны.

87

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

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

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

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

Рассмотрим пример, в котором имеются два продавца, продающие определенный товар на рынке. Оба из них знают, что чем выше цена, тем меньше общий объем продаж [5].

Для простоты предположим, что каждый из них может продать либо 400 единиц некоторого товара, либо 100 единиц. Известно, что при продаже 800 единиц на рынке складывается цена, равная 100 денежным единицам (д.е.), при 500 единицах — 200 д.е., а при объеме продаж 200 единиц — 500 д.е. Матрица выигрышей продавцов показана в табл. 5.5.

Таблица 5.5

Матрица выигрышей

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

Предположим теперь, что по каким-либо причинам они принимают решения независимо друг от друга. Каковы оптимальные стратегии для игроков в этом случае? Пара стратегий (400,100) не является ситуацией равновесия, так как в этом случае второму игроку выгодно изменить свою стратегию на 400 и тем самым увеличить свой выигрыш с 20000 до 40 000 д.е.

Если рассмотреть пару стратегий (100,100), то она также не является ситуацией равновесия, поскольку каждому отдельному игроку выгодно по-

88

менять свою стратегию на 100 и получить вместо 50 000 д.е. выигрыш в 80 000 д.е. Если же мы рассмотрим пару стратегий (400,400), то отклонение каждого отдельного игрока является для него невыгодным. Эта ситуация на-

зывается ситуацией некооперативного равновесия.

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

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

А1= aij1 — платежная матрица первого игрока, а А2 = aij2 — платежная

матрица второго игрока.

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

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

1. Оптимальность по Парето. Пусть имеется несколько целевых функций F1(z),..., Fn(z), каждую из которых хотят максимизировать. Вектор решения z называется оптимальным по Парето (или эффективным), если не существует другого вектора z*, для которого значения всех функций Fi(z)≥Fi(z*), и хотя бы одно неравенство строгое.

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

Множество эффективных векторов называется множеством Парето, а любой вектор этого множества — оптимумом по Парето.

89

В случае биматричной игры z = (x, у), а в качестве целевых функций рассматриваются функции V(x,y) и W(х,у), заданные соотношениями (5.6).

2. Ситуации равновесия по Нэшу. Это такая пара смешанных страте-

гий (х*, у* ), что для любых произвольных стратегий х и у выполняются нера-

венства V(x*, у*) ≥ V(х, у* ) и W (x*, у*) ≥ W(x*, у).

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

Справедлива следующая основная теорема теории биматричных игр. Теорема Нэша. Существует хотя бы одна ситуация равновесия в любой

биматричной игре.

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

5.6. Введение в теорию игр п лиц

Во многих реальных ситуациях в процессе принятия решений участвует более двух игроков. Рассмотрим случай, когда участников игры трое или более. Пусть N= {1, 2,..., п} — множество игроков; хi — стратегия i-го игрока; Xi — множество стратегий i-го игрока; fi (x1,…, xn) — функция выигрыша i-го игрока в зависимости от выбранных стратегий x1,…, xn (ситуация игры). Такую игру называют игрой п лиц. Введем определение характеристической функции [5].

Определение. Функцию v(S) называют характеристической функцией для игры п лиц, если для любого подмножества S множества игроков N (S N), v(S) — максимальный суммарный гарантированный выигрыш игроков подмножества S при условии их оптимальных совместных действий. Или в математическом виде

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

5.7. Позиционные игры

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

90