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

x a_ij y^* < V < x^* a_ij y, (5.5)

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

Таблица 5.5

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

Продавец 1 / Продавец 2	400	100
400	40000/40000	80000/20000
100	20000/80000	50000/50000

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

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

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

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

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

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

и .(5.6)

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

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

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

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

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

2. Ситуации равновесия по Нэшу. Это такая пара смешанных стратегий (х^*, у^* ), что для любых произвольных стратегий х и у выполняются неравенства V(x^*, у^*) ≥ V(х, у^* ) и W (x^*, у^*) ≥ W(x^*, у).

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

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

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

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