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

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

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

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

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

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

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

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

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

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

Рассмотрим пример, в котором имеются два про­давца, продающие определенный товар на рынке. Оба из них знают, что чем выше цена, тем меньше общий объем продаж. Для простоты предположим, что каждый из них может продать либо 400 единиц не­которого товара, либо 100 единиц. Известно, что при продаже 800 единиц на рынке складывается цена равная 100 фунтам, при 500 еди­ницах — 200 фунтов, а при объеме продаж 200 единиц — 500 фунтов. Матрица выигрышей продавцов показана в нижеследующей табли­це 7.5.

Таблица 7.5 – Матрица игры

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

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

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

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

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

и (7.5)

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

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

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

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

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

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

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

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

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

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

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

7.5. Элементы теории игр п лиц

Во многих реальных ситуациях в процессе принятия решений участвует более двух игроков. Рассмотрим случай, когда участников игры трое или более. Пусть N= {1, 2,..., п }— мно­жество игроков, х _i — стратегия i -го игрока, X_i — множество стратегий i -го игрока; f_i (x ₁, …, x _n) — функция выигрыша i -го игрока в зависимости от выбранных стратегий x ₁, …, x _n (ситуация игры). Такую игру на­зывают игрой п лиц. Введем определения характеристической функции.

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

(7.6.)

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