Теория игр
Лекция 3
Тема лекции 3: «Биматричные игры»
Разделы лекции:
1. Понятие биматричной игры. Примеры биматричных игр.
2. Биматричные игры 2x2. Ситуация равновесия.
3. Поиск равновесных ситуаций. Кооперативное поведение игроков.
РАЗДЕЛ 1. ПОНЯТИЕ БИМАТРИЧНОЙ ИГРЫ. ПРИМЕРЫ БИМАТРИЧНЫХ ИГР.
Предыдущие рассмотрения касались игр двух лиц, в которых интересы игроков были прямо противоположны – антагонистических игр. Однако ситуации, в которых интересы игроков хотя и не совпадают, но уже не обязательно являются противоположными, встречаются значительно чаще. Рассмотрим, например, конфликтную ситуацию, в которой каждый из двух участников имеет следующие возможности для выбора своей линии поведения: игрок A — может выбрать любую из стратегий А1, ..., Аm, игрок B – любую из стратегий В1, ..., Вn. При этом всякий раз их совместный выбор оценивается вполне определенно: если игрок A выбрал i-ю стратегию Ai, а игрок B – j-ю стратегию Вj, то в итоге выигрыш игрока А будет равен некоторому числу aij, а выигрыш игрока В некоторому, вообще говоря, другому числу bij. Иными словами, всякий раз каждый из игроков получает свой приз. Последовательно перебирая все стратегии игрока A и все стратегии игрока B, мы сможем заполнить их выигрышами две таблицы:
B1 ... Bj ... Bn
A1 a11 ... a1j ... a1n
... ... ... ... ... ...
Ai ai1 ... aij ... ain
... ... ... ... ... ...
Am am1 ... amj ... amn
B1 ... Bj ... Bn
A1 b11 ... b1j ... b1n
... ... ... ... ... ...
Ai bi1 ... bij ... bin
... ... ... ... ... ...
Am bm1 ... bmj ... bmn
Первая из таблиц описывает выигрыши игрока A, а вторая - выигрыши игрока В. Обычно эти таблицы записывают в виде двух матриц размера m x n: А = ||aij||, В = ||bij||. Здесь A – платежная матрица игрока A, а B – платежная матрица игрока В.
При выборе игроком A i-й стратегии Ai, а игроком B — j-й стратегии Bj их выигрыши находятся в матрицах выплат на пересечении i-х строк и j-х столбцов: в матрице A - это элемент aij, а в матрице B — элемент bij.
Таким образом, в случае, когда интересы игроков различны, но не обязательно противоположны, получаются две платежные матрицы: одна – матрица выплат игроку A, другая – матрица выплат игроку В. В конечной бескоалиционной игре двух игроков каждый из них делает один ход — выбирает одну стратегию из имеющегося у него конечного числа стратегий, и после этого он получает свой выигрыш согласно определенным для каждого из них матрицам выигрышей.
Другими словами, конечная бескоалиционная игра двух игроков полностью определяется двумя матрицами выигрышей для двух игроков. Поэтому совершенно естественно звучит название, которое обычно присваивается подобной игре — биматричная игра.
ЗАМЕЧАНИЕ. Рассматриваемые ранее матричные игры, разумеется, можно рассматривать и как биматричные, где матрица выплат игроку B противоположна матрице выплат игроку A:
B = -A. Тем не менее, в общем случае биматричная игра — это игра с ненулевой суммой. В дальнейшем мы будем сопоставлять наши рассмотрения с рассуждениями, проведенными нами ранее в лекции 2 для матричных игр (особенно при попытках разрешения схожих проблем). Подобные сопоставления часто оказываются одновременно и удобными и полезными. Конечно, класс биматричных игр значительно шире класса матричных (разнообразие новых моделируемых конфликтных ситуаций весьма заметно), а, значит, неизбежно увеличиваются и трудности, встающие на пути их успешного разрешения.
ПРИМЕРЫ БИМАТРИЧНЫХ ИГР.
Примеры этого раздела описывают некоторые типичные конфликтные ситуации, приводящие к биматричным играм. Сначала мы обсудим вопросы, связанные с формализацией рассматриваемых конфликтов (построение платежных матриц), а затем рассмотрим рекомендации по их разрешению.
ПРИМЕР 1. «БОРЬБА ЗА РЫНКИ». Небольшая фирма (игрок А) намерена сбыть партию товара на одном из двух рынков, контролируемых другой, более крупной фирмой (игрок В). Для этого фирма A готова предпринять на одном из рынков соответствующие приготовления (например, развернуть рекламную компанию). Господствующая на рынках фирма B может попытаться воспрепятствовать этому, приняв на одном из рынков предупредительные меры (разумеется, в рамках закона). Не встречая противодействия на рынке, фирма A захватывает его; при наличии препятствий — терпит поражение. Будем считать для определенности, что проникновение фирмы A на первый рынок более выгодно для нее, нежели проникновение на второй. Естественно также считать, что и борьба за первый рынок потребует вложения больших средств. Например, победа фирмы A на первом рынке принесет ей вдвое больший выигрыш, чем победа на втором, но зато и поражение при попытке освоиться на первом рынке полностью разорит ее, избавив фирму B от конкурента. Что же касается второго рынка, то при поражении фирмы A ее потери будут не столь разорительны, но и победа принесет немного. Таким образом, у фирмы A две стратегии: Α1 — «выбор первого рынка», Α2 — «выбор второго рынка». Такие же стратегии и у фирмы B: Β1 — «выбор первого рынка», B2 – «выбор второго рынка». Для того чтобы составить платежные матрицы игроков, нужны расчетные количественные показатели, которые мы приведем здесь в условных единицах:
A =
-10 2
1 -1
B =
5 -2
-1 1
Взглянем на выписанные матрицы выплат. Из сказанного выше ясно, что если оба игрока выберут один и тот же рынок, то победа останется за более сильной фирмой В. То, что в ситуации (Α1, Β1) выигрыш игрока B равен 5, а в ситуации (Α2, Β2) равен 1, подчеркивает, что первый рынок более выгоден (удобно расположен, хорошо посещаем и т.п.), чем второй. Выигрыш (- 10) игрока A в ситуации (Α1, Β1) (а точнее, проигрыш) в сопоставлении с его выигрышем (- 1) в ситуации (А2, В2) выглядит, разумеется, вполне сокрушительно. Что же касается ситуации, когда фирмы уделяют основное внимание разным рынкам (A1, В2) и (А2, Β1), то здесь фирму A ждет настоящий выигрыш, больший на более выгодном рынке. Потери, которые при этом несет фирма B, оказываются прямо противоположными. Ясно, что точно рассчитать выгоду и ущерб сторон в этом конфликте заранее довольно трудно. А вот в следующей конфликтной ситуации размеры выигрышей игроков известны со всей определенностью.
ПРИМЕР 2. «НЕФТЕДОБЫЧА».
Рассмотрим две нефтедобывающие страны, назовем их, скажем, A и В. Эти две страны могут кооперироваться (К), договариваясь об объемах ежедневной добычи нефти, «заморозив», например, добычу на уровне 2 млн. баррелей в день. С другой стороны, страны могут действовать «не кооперативно» (Н), добывая, например, по 4 млн. баррелей нефти в день. Прибыли стран в зависимости от их объемов добычи нефти следующие.
Если обе страны A и B ограничатся добычей 2 млн. баррелей нефти в день, то прибыль первой страны A составит 46 млн. долларов в день, а прибыль второй страны B составит 42 млн. долларов в день. Если обе страны A и B будут добывать по 4 млн. баррелей нефти в день, то прибыль первой страны A составит 32 млн. долларов в день, а прибыль второй страны B составит 24 млн. долларов в день. Если первая страна A будет ограничивать добычу нефти на уровне 2 млн. баррелей в день, а вторая страна B будет добывать 4 млн. баррелей в день, то прибыль первой страны A составит 26 млн. долларов в день, а прибыль второй страны B составит 44 млн. долларов в день. И наоборот, если первая страна A будет добывать 4 млн. баррелей нефти в день, а вторая страна B ограничит ежедневную добычу нефти до 2 млн. баррелей, то прибыль первой страны A составит 52 млн. долларов в день, а прибыль второй страны B составит 22 млн. долларов в день. Эта картина достаточно типична для картеля, когда у каждого из членов картеля есть стимул отклониться от договора, чтобы за счет увеличения объемов добычи получить дополнительную прибыль.
Эта конфликтная ситуация приводит к биматричной игре, в которой каждый из игроков имеет по две стратегии: «кооперироваться» (К) или «не кооперироваться» (Н).
Матрица выигрышей игрока A:
B
A (К) (Н)
(К) 46 26
(Н) 52 32
Матрица выигрышей игрока B:
B
A (К) (Н)
(К) 42 44
(Н) 22 24
Рассмотрим еще один гипотетический пример, показывающий, сколь велико многообразие ситуаций, изучение которых методами биматричных игр и интересно, и эффективно.
ПРИМЕР 3. «ЯСТРЕБ—ГОЛУБЬ».
Предположим, что в некоторой популяции соперничающие индивидуумы в общении между собой применяют только две стратегии – стратегию Ястреба и стратегию Голубя. Эти названия используются здесь в том смысле, в каком их обычно применяют к людям, и, вообще говоря, никак не связаны с особенностями биологии соответствующих птиц (в действительности голуби – довольно агрессивные птицы). Ястребы всегда дерутся неистово и безудержно, отступая лишь при серьезных ранениях. Голуби же ограничиваются угрозами, с достоинством соблюдая все условности, и никогда не наносят противнику повреждений. Если Ястреб сталкивается с Голубем, то Голубь быстро убегает, оставаясь, таким образом, невредимым. Если Ястреб дерется с Ястребом, то драка продолжается до тех пор, пока один из соперников не получит серьезных повреждений или не будет убит. Если же Голубь встречается с Голубем, то ни один из них не страдает. Голуби долго выступают друг перед другом, принимая разные позы, пока один из них не устанет или не решит, что ему не стоит продолжать противостояние, а лучше отступить. Будем исходить из предположения, что индивидуум не может заранее узнать, с кем ему предстоит драться (с Ястребом или с Голубем), и решить, какую стратегию из двух указанных (стратегию Ястреба или стратегию Голубя) он выберет для себя. Индивидуум обнаруживает это только в момент начала поединка и, следовательно, опытом прошлых встреч с определенными индивидуумами воспользоваться не может, так как попросту не помнит о них. Попробуем провести количественную оценку результатов конфликта, считая, что выигрыш приносит 50 очков (+50), проигрыш — 0 очков (0), серьезная рана приносит потерю 100 очков (-100), а затраты времени в поединке штрафуются 10 очками (-10). Отметим, что точные величины выигрышей не имеют для нашего анализа особенно большого значения, но помогают дельному размышлению над поставленной проблемой. Вычислим теперь средние выигрыши индивидуумов.
1. Предположим сначала, что рассматриваемая популяция состоит из одних Голубей. В их поединках пострадавших не бывает. Состязания представляют собой длительные парные турниры, которые заканчиваются только тогда, когда один из противников отступает. Победитель получает 50 очков – цена ресурса, явившегося причиной поединка, но он платит и штраф, равный 10 очкам, за потерю времени на длительный турнир, так что его выигрыш, в конечном счете, равен 40 очкам:
50 - 10 = 40.
Побежденный также платит штраф – 10 очков – за потерянное время.
Естественно ожидать, что каждый отдельный Голубь в среднем в половине турниров победит, а в половине проиграет. Тем самым, его средний выигрыш за один турнир равен среднему арифметическому между (+40) и (-10):
(40 - 10) /2 = 15, то есть получим (+15).
2. Допустим теперь, что в популяции появился Ястреб. Так как Ястребы всегда побеждают Голубей, то он будет получать 50 очков за каждый поединок и, тем самым, его средний выигрыш равен (+50). При драке Ястреба с Ястребом один из них получает тяжкие повреждения, оцениваемые как (-100), тогда как выигрыш победителя составляет +50. Каждый Ястреб в популяции Ястребов может рассчитывать на выигрыш в половине сражений, а в половине проиграть. Поэтому его ожидаемая средняя сценка за одну драку равна среднему арифметическому между (+50) и (-100):
(50-100)/2 = -25, то есть получим (-25).
3. Если в популяции Ястребов появился один Голубь, то он окажется побежденным во всех турнирах, но при этом будет оставаться невредимым. Тем самым, его средний выигрыш в популяции Ястребов равен 0.
Приведенные расчеты позволяют составить платежные матрицы участников A и B любого парного турнира, которые придерживаются в нем одной из двух выделенных стратегий – стратегии Ястреба или стратегии Голубя. Мы получаем следующие платежные матрицы:
A=
(Я) (Г)
(Я) - 25 50
(Г) 0 15
B=
(Я) (Г)
(Я) - 25 0
(Г) 50 15
СМЕШАННЫЕ СТРАТЕГИИ.
В приведенных примерах (позже мы вернемся к подробному рассмотрению каждого) описаны ситуации, в которых интересы игроков не совпадают. Естественно встает вопрос о том, какие рекомендации необходимо дать игрокам для того, чтобы моделируемая конфликтная ситуация разрешилась. Иными словами, что мы будем понимать под решением биматричной игры? Попробуем ответить на это вопрос так: вследствие того, что интересы игроков не совпадают, нам нужно построить такое (компромиссное) решение, которое бы в том или ином, но в одинаковом смысле удовлетворяло обоих игроков. Не пытаясь сразу выражать эту мысль совсем точно, сначала попробуем найти некую равновесную ситуацию, явное отклонение от которой одного из игроков уменьшало бы его выигрыш. Подобный вопрос мы ставили и при рассмотрении матричных игр. Напомним, что возникающее при разработке минимаксного подхода понятие равновесной ситуации приводило нас к поиску седловой точки, которая, как оказалось, существует далеко не всегда – конечно, если ограничиваться только чистыми стратегиями игроков A и B, то есть стратегиями A1, …, Am и B1, …, Bn. Естественно ожидать, что в более сложном случае биматричной игры дело вряд ли обстоит проще. Однако при расширении матричной игры путем перехода к смешанным стратегиям, то есть к такому поведению игроков, при котором они чередуют (чистые) стратегии с определенными частотами: игрок A чередует стратегии A1, …, Am, с частотами p1, …, pm, где pi ≥ 0, i= 1, …, m, ∑ pi = 1, а игрок B чередует стратегии Β1, ..., Вn с частотами q1, …, qn, где qj ≥ 0, j= 1, …,n, ∑ qj = 1, выяснилось, что в смешанных стратегиях равновесная ситуация всегда существует. Иными словами, любая матричная игра в смешанных стратегиях разрешима. Поэтому, рассматривая здесь биматричные игры, разумно попробовать сразу же перейти к смешанным стратегиям игроков (тем самым мы предполагаем, что каждая игра может быть многократно повторена в неизменных обстоятельствах). В матричном случае смешивание стратегий приводило к расширению возможности выплат в том смысле, что расчет строился из вычисления средних выигрышей H1 и H2 игроков A и B, соответственно, которые определялись по элементам платежной матрицы A и вероятностям pi, i= 1, …, m, и qj, j= 1, …, n, следующим образом.
H1=∑ aij piqj, H2= - ∑ aij piqj.
При смешанных стратегиях в биматричных играх также естественно возникают средние выигрыши H1 и H2 игроков A и B, соответственно, определяемые по правилам, в которых уже нет никакой дискриминации игрока B:
H1 =∑ aij piqj, H2= ∑ bij piqj.
РАЗДЕЛ 2. БИМАТРИЧНЫЕ ИГРЫ 2x2 . СИТУАЦИЯ РАВНОВЕСИЯ.
Здесь мы рассмотрим случай, когда у каждого из игроков имеется ровно две стратегии, то есть случай: m = n = 2. Поэтому выпишем приведенные выше формулы для вычисления средних выигрышей H1 и H2 игроков A и B именно для такого случая. В биматричной игре 2x2 платежные матрицы игроков имеют следующий вид:
А=
a11 a12
a21 a22
B=
b11 b12
b21 b22
Для вероятностей (p1, p2) и (q1, q2) имеем следующие соотношения: p1 = p, p2 = 1 – p; q1 = q, q2 =1 – q.
Средние выигрыши H1 и H2 игроков A и B, с учетом соотношений для вероятностей (p1, p2) и (q1, q2), вычисляются по формулам:
H1 (p,q) = a11 pq + a12 p(1-q) + a21(1-p)q + a22(1-p)(1 - q), (1)
H2 (p,q) = b11 pq + b12 p(1-q) + b21(1-p)q + b22(1-p)(1 - q), (2)
где 0 ≤ p ≤ 1, 0 ≤ q ≤ 1.
Сформулируем основное определение.
ОПРЕДЕЛЕНИЕ. Будем говорить, что пара чисел (p*, q*) определяет равновесную ситуацию, где 0 ≤ p* ≤ 1, 0 ≤ q* ≤ 1, если для любых p и q, подчиненных условиям 0 ≤ p ≤ 1, 0 ≤ q ≤ 1, одновременно выполнены следующие неравенства:
H1 (p,q*) ≤ H1 (p*,q*), H2 (p*,q) ≤ H2 (p*,q*) . (3)
ПОЯСНЕНИЕ. Выписанные неравенства (3) означают следующее: ситуация, определяемая смешанной стратегией (р*, q*), является равновесной, если отклонение от нее одного из игроков при условии, что другой сохраняет свой выбор, приводит к тому, что выигрыш отклонившегося игрока может только уменьшиться. Тем самым, получается, что если равновесная ситуация существует, то отклонение от нее невыгодно самому игроку. Но может ли быть подобная ситуация равновесия в биматричной игре? Ответ на поставленный вопрос дает следующее утверждение.
ТЕОРЕМА 1 (НЭША). Всякая биматричная игра имеет хотя бы одну равновесную ситуацию (точку равновесия) в смешанных стратегиях.
Заметим, что весьма похожее утверждение мы уже встречали при изучении вопроса разрешимости матричных игр. Напомним также, что в соответствующем разделе лекции 2 «Антагонистические игры» после формулировки аналогичного утверждения о существовании равновесной ситуации в матричной игре описывался и способ отыскания точки равновесия. Та же проблема встает перед нами и здесь: равновесная ситуация в биматричной игре существует, но как ее найти?
Если некоторая пара чисел (p*, q*) претендует на то, чтобы определять ситуацию равновесия в биматричной игре, то для того, чтобы убедиться в обоснованности этих претензий (или, наоборот, доказать их необоснованность), необходимо проверить справедливость неравенств (3) для любого p в пределах от 0 до 1 и для любого q в пределах от 0 до 1. В общем случае число таких проверок бесконечно, и, следовательно, действенный способ определения равновесной ситуации нужно искать по-другому. Для этого мы обопремся на следующий теоретический результат.
ТЕОРЕМА 2. Выполнение неравенств
H1 (p,q*) ≤ H1 (p*,q*), H2 (p*, q) ≤ H2 (p*,q*) (3)
равносильно выполнению неравенств
H1 (0,q*) ≤ H1 (p*,q*), H1 (1,q*) ≤ H1 (p*,q*),
H2 (p*,0) ≤ H2 (p*,q*), H2 (p*,1) ≤ H2 (p*,q*) . (4)
Иными словами, для того, чтобы убедиться в обоснованности претензий пары (р*, q*) на то, чтобы определять равновесную ситуацию, достаточно проверить справедливость неравенства H1 (p,q*) ≤ H1 (p*,q*) только для двух чистых стратегий игрока A (p = 0 и p =1) и проверить справедливость неравенства H2 (p*,q) ≤ H2 (p*,q*) только для двух чистых стратегий игрока B (q = 0 и q = 1).
Четыре неравенства (4) позволяют провести поиск точки равновесия уже вполне конструктивно. Запишем средние выигрыши игроков A и B в более удобной форме. Мы имеем следующие выражения. Преобразуя формулу (1), получим:
H1 (p,q) = (a11 + a22 – a12 – a21)pq + (a12 – a22)p + (a21 – a22)q + a22. (1’)
Аналогично, раскрывая скобки и группируя слагаемые в формуле (2), получим:
H2 (p,q) = (b11 + b22 – b12 – b21)pq + (b12 – b22)p + (b21– b22)q + b22. (2’)
Обратимся к первой из полученных формул (1’) . Полагая в ней сначала p = 1, а потом p = 0, получаем, что
H1 (1,q) = (a11 + a22 — a12 – a21) q + (a12 – a22) + (a21 – a22)q + a22 = (a11 + a22 — a12 – a21) q + (a21 – a22)q + a12 = (a11 – a12) q + (a21 – a22)q + a12,
H1 (0,q) = (a21 – a22)q + a22.
Теперь рассмотрим разности
H1 (p,q) – H1 (1,q) =(a11 + a22 – a12 – a21)pq + (a12 – a22)p + (a21 – a22)q + a22 – ((a11 – a12 ) q + a12) = (a11 + a22 – a12 – a21)pq + (a12 – a22)p – (a11 + a22 — a12 – a21) q + a22 — a12,
и
H1 (p,q) – H1 (0,q) = (a11 + a22 – a12 – a21)pq + (a12 – a22)p.
Введя следующие обозначения: С = a11 + a22 — a12 - a21 и α = a22 — a12, получим для выражений H1 (p,q) – H1 (1,q) и H1 (p,q) – H1 (0,q) следующие выражения:
H1 (p,q) – H1 (1,q) = Cpq — pα – Cq+α = Cq(p-1) — α(p-1) = (p – 1)(Cq – α) ,
H1 (p,q) – H1 (0,q) = Cpq — pα = p(Cq – α).
В случае, если пара (р, q) определяет точку равновесия, то в силу неравенств (4), сформулированных в теореме 2, эти разности неотрицательны. То есть для точки равновесия будут выполняться неравенства:
H1 (p,q) – H1 (1,q) ≥ 0, H1 (p,q) – H1 (0,q) ≥ 0.
Поэтому окончательно получаем следующие неравенства:
(p – 1)(Cq – α) ≥ 0 , p(Cq – α) ≥ 0. (5)
Из формулы (2’) для функции Н2 (р, q) при q = 1 и q = 0 соответственно имеем:
H2 (p,1) = (b11 + b22 – b12 – b21) p + (b12 – b22)p + (b21 – b22) + b22 = (b11 + b22 – b12 – b21)p + (b12 – b22)p + b21,
и
H2 (p,0) = (b12 – b22)p + b22.
Вычислим разности H2 (p,q) – H2 (p,1) и H2 (p,q) – H2 (p,0). Мы имеем:
H2 (p,q) – H2 (p,1) = (b11 + b22 – b12 – b21)pq + (b12 – b22)p + (b21– b22)q + b22 – ((b11 + b22 – b12 – b21)p + (b12 – b22)p + b12) = (b11 + b22 – b12 – b21)pq + (b21– b22)q –(b11 + b22 – b12 – b21)p + (b22 – b12),
H2 (p,q) – H2 (p,0) = (b11 + b22 – b12 – b21)pq + (b12 – b22)p + (b21– b22)q + b22 – ((b12 – b22)p + b22) = (b11 + b22 – b12 – b21)pq +(b21– b22)q.
Разности H2 (p,q) – H2 (p,1) и H2 (p,q) – H2 (p,0), с учетом обозначений
D = b11 + b22 – b12 – b21 и β = b22 – b21,
приводятся к виду
H2 (p, q) – H2 (p, 1) = Dpq – βq – Dp + β = (q – 1)(Dp – β) ,
H2 (p, q) – H2 (p, 0) = Dpq – βq = q(Dp – β).
Преобразования разностей H2 (p, q) – H2 (p,1) и H2 (p, q) – H2 (p,0) проводим аналогично преобразованиям соответствующих разностей для функции Н1.
Если пара (р, q) определяет точку равновесия, то в силу неравенств (4), сформулированных в теореме 2, эти разности неотрицательны. То есть
H2 (p, q) – H2 (p, 1) ≥ 0 , H2 (p, q) – H2 (p,0) ≥ 0.
Поэтому получим следующие неравенства:
(q – 1)(Dp – β) ≥ 0, q(Dp – β) ≥ 0 . (6)
Прежде чем приступать к последующим шагам, подведем некоторые итоги. Для того чтобы в биматричной игре
А=
a11 a12
a21 a22
B=
b11 b12
b21 b22
пара (p, q) определяла равновесную ситуацию, в силу теоремы 2 необходимо и достаточно одновременное выполнение следующих неравенств:
(p-1)(Cq - α) ≥ 0 , p(Cq - α) ≥ 0, (q-1)(Dp -β) ≥ 0, q(Dp -β) ≥ 0, 0 ≤ p ≤ 1, 0 ≤ q ≤ 1, (7)
где
С = a11 + a22 — a12 — a21, α = a22 — a12, D = b11 + b22 — b12 — b21, β = b22 — b21.
РАЗДЕЛ 3. ПОИСК РАВНОВЕСНЫХ СИТУАЦИЙ. КООПЕРАТИВНОЕ ПОВЕДЕНИЕ ИГРОКОВ.
Геометрический смысл условий (7) рассмотрим на примерах описанных выше биматричных игр.
ПРИМЕР 1. «БОРЬБА ЗА РЫНКИ» (ПРОДОЛЖЕНИЕ). Напомним, что ситуация сложившаяся в этой задаче, задается платежными матрицами следующего вида
A =
-10 2
1 -1
B =
5 -2
-1 1
Заменяя в неравенствах (5) и (6) величины C, α, D и β их конкретными значениями
С = -10 - 2 - 1 - 1 = -14, α = -1 - 2 = -3, D= 5 + 2 + 1 + 1= 9, β = 1 + 1= 2,
получаем:
(p-1)(-14q - (-3)) ≥ 0, p(-14q - (-3)) ≥ 0 (5’),
(q-1)(9p - 2) ≥ 0, q(9p - 2) ≥ 0 (6’).
Рассмотрим сначала первую пару неравенств (5’):
(p-1)(-14q +3) ≥ 0, p(-14q + 3) ≥ 0 .
Возможны следующие три случая:
1) р=1, 2) р = 0, 3) 0 < p < 1.
Разберем каждый из этих случаев подробно.
1. Полагая p = 1, получаем следующие неравенства: 0 ≥ 0, -14q + 3 ≥ 0 .
Откуда приходим к неравенству: 14q - 3 ≤ 0 и, значит, q ≤ 3/14.
2. Полагая p = 0, получаем следующие неравенства: – (– 14q +3) ≥ 0, 0 ≥ 0 .
Откуда 14q - 3 ≥ 0 и, значит, q ≥ 3/14.
3. Наконец, положив 0 < p < 1, получим неравенства: 14q - 3 ≤ 0, 14q - 3 ≥ 0, что возможно лишь в случае, если 14q - 3 = 0, то есть q = 3/14.
Сформулируем результаты наших рассмотрений:
1) при p = 1 имеем q ≤ 3/14 .
2) при p=0 имеем q ≥ 3/14.
3) при 0 < p < 1 имеем q= 3/14.
Перенесем теперь полученные сведения на чертеж. Введем на плоскости прямоугольную систему координат (p, q) и выделим на ней единичный квадрат, соответствующий неравенствам 0 ≤ p ≤ 1, 0 ≤ q ≤ 1, (рисунок 1).
Рисунок 1.
Нанесем на этот чертеж то множество точек, которое описывается условиями 1), 2) и 3). Это множество (на рисунке 2 его точки выделены жирной линией) состоит из трех прямолинейных участков — двух вертикальных лучей и одного горизонтального отрезка — и представляет собой «зигзаг». Нас будет интересовать только та его часть, которая попала в заштрихованный на рисунке 2 единичный квадрат.
Рисунок 2.
Оставив на время полученные результаты в покое, обратимся ко второй части неравенств (6’):
(q-1)(9p-2) ≥ 0, q(9p-2) ≥ 0 (6’).
Три интересных для нас случая 1) q =1, 2) q = 0, 3) 0< q < 1 приводят нас к следующим результатам.
1) q = 1, p ≥ 2/9 ,
2) q= 0 , p ≤ 2/9,
3) 0 < q < 1, p = 2/9 .
Перенося его на чертеж, получим второй «зигзаг», но уже горизонтальный (рисунок 3).
Рисунок 3.
Теперь остается только объединить полученные результаты на рисунке 4. Общая точка построенных зигзагов — точка равновесия (p*, q*) — имеет координаты (2/9, 3/14).
Рисунок 4.
Соответствующие смешанные стратегии игроков имеют следующий вид:
P = (p*, 1-p*) = (2/9, 7/9), Q = (q*, 1-q*) = (3/14, 11/14),
а средние выигрыши игроков в точке равновесия таковы:
Н1(2/9, 3/14) = - 4/7, H2(2/9, 3/14) = 1/3.
ЗАМЕЧАНИЕ. Попробуем разбить рассмотренную биматричную игру на две матричные игры с нулевой суммой.
1. Игра с матрицей А.
A =
-10 2
1 -1
Решая эту игру графическим методом, найдем оптимальную смешанную стратегию для игрока A: P = (p1, p2) = (1/7, 6/7), цену этой игры V1 = - 4/7, а затем и оптимальную смешанную стратегию для игрока В: Q = (q1, q2) = (3/14, 11/14).
2. Игра с матрицей В.
B =
5 -2
-1 1
Решая эту игру графическим методом, найдем оптимальную смешанную стратегию для игрока B: Q = (q1, q2) = (1/3, 2/3), цену этой игры V2 = 1/3, а затем и оптимальную смешанную стратегию для игрока A: P = (p1, p2) = (2/9, 7/9).
Сравнивая полученные результаты с решением биматричной игры, можно заметить следующее: если каждый игрок будет применять свои стратегии в этой биматричной игре, исходя только из матрицы своих выигрышей, то его оптимальный средний выигрыш совпадет с его выигрышем при равновесной ситуации.
Знакомство с биматричными играми мы завершим исследованием биматричной игры, построенной в примере «Ястреб – Голубь».
ПРИМЕР 3. «ЯСТРЕБ—ГОЛУБЬ» (ПРОДОЛЖЕНИЕ). Напомним, что ситуация сложившаяся в этой задаче, задается платежными матрицами следующего вида
A=
(Я) (Г)
(Я) - 25 50
(Г) 0 15
B=
(Я) (Г)
(Я) - 25 0
(Г) 50 15
После аффинных преобразований (деления всех элементов обеих матриц на 5) проведем необходимые вычисления:
С = -5-10- 0 + 3 = -12, α = 3 -10= -7,
D = -5- 0-10 + 3 = -12, β = 3-10= - 7.
Подставив полученные значения в неравенства (5’) и (6’), получим:
(р - 1)(-12q + 7) ≥ 0, р(-12q + 7) ≥ 0,
и
(q - 1)(-12р + 7) ≥ 0, q(-12р + 7) ≥ 0.
После несложных расчетов получаем, что
1) при p = 1 имеем q ≤ 7/12,
2) при p = 0 имеем q ≥ 7/12,
3) при 0 < p < 1 имеем q= 7/12.
1) при q = 1, p ≤ 7/12 ,
2) при q= 0 , p ≥ 7/12,
3) при 0 < q < 1, p = 7/12.
Геометрически полученный результат показан на рисунке 5. Рисунок 5.
Данная игра имеет три точки равновесия, две из которых отвечают чистым стратегиям игроков. Нас же в данном случае интересует смешанная стратегия, характеризующаяся следующими величинами:
p = 7/12, q = 7/12, H1 (7/12, 7/12) = H2 (7/12, 7/12) = 25/4. (7)
Полученные результаты допускают разные интерпретации. Рассмотрим две из них.
1. При многократном участии индивидуума в турнире (с заданной системой оценки выигрышей) наиболее разумной линией его поведения следует признать смешивание стратегии Ястреба и стратегии Голубя в отношении 7 к 5. При этом всякий раз выбор конкретной стратегии должен носить случайный характер, чтобы у противника не было возможности угадать, как он собирается вести себя в каждом конкретном состязании. Так, например, неразумно выступать в роли Ястреба семь раз подряд, а затем пять раз подряд в роли Голубя и так далее. Если какой-нибудь индивидуум примет такую простую последовательность, то противники быстро разберутся в его намерениях и несомненно воспользуются этим (например, разыгрывая роль Ястреба в тех случаях, когда индивидуум решил выступать в роли Голубя). При случайном выборе стратегии Ястреба с вероятностью 7/12 и стратегии Голубя с вероятностью 5/12 индивидуум может рассчитывать на средний выигрыш в турнире, равный 6,25. Изменение пропорции 7:5 может этот выигрыш только уменьшить.
2. Рассматривая популяцию, в которой каждый из индивидуумов выбрал одну из двух этих стратегий в качестве единственно допустимой для себя, и, тем самым, состоящую из Ястребов и Голубей, найденные числа (7) можно объяснить еще и так. Для используемой нами системы очков стабильное соотношение между Ястребами и Голубями в популяции составляет 7:5, и при этом средний выигрыш Ястреба оказывается в точности равным среднему выигрышу Голубя (+6,25). Если число Ястребов в популяции начнет возрастать так, что их доля станет выше 7/12, то у Голубей начнет возникать дополнительное преимущество и соотношение вернется к стабильному состоянию. Если же начнет изменяться доля Голубей, то и у Ястребов найдутся способы вновь вернуть соотношение к стабильному. Но 6,25 гораздо меньше среднего выигрыша для Голубя в популяции из одних Голубей (+15). Если бы все согласились быть Голубями, то каждому отдельному индивидууму это пошло бы только на пользу. Беда, однако, в том, что любой сговор, даже тот, который в конечном счете выгоден всем, не защищен от злоупотреблений — оказаться в группе из Голубей единственным Ястребом настолько хорошо (всегда +50), что появление Ястребов ничем не остановить. Найденная стабильная стратегия устойчива не тем, что она так уж хороша для участвующих в ней индивидуумов, а просто потому, что она гарантирует от измены в своих рядах. Один из возможных путей разработки модели Ястреб—Голубь состоит в расширении множества стратегий путем введения в него новых — стратегии «Отпорщика», стратегии «Задиры» и т. д. Приведенный пример — это всего лишь простая модель, помогающая как-то понять реальные события и факты. Ее можно, разумеется, и совершенствовать и усложнять. При удачном развитии сходство модели с реальным миром по мере ее усложнения возрастает.
КООПЕРАТИВНОЕ ПОВЕДЕНИЕ ИГРОКОВ.
Как отмечалось выше, равновесие является важнейшим принципом оптимальности в бескоалиционных играх, в которых не рассматривается образование коалиций. Коалиция является формой кооперации, направленной на увеличение персональных возможностей игроков, то есть на увеличение их выигрышей. В матричной игре кооперация игроков лишена смысла, так как в такой игре улучшение положения одного из них приводит к ухудшению положения другого. Ситуация меняется при переходе от матричной игры к биматричной игре, так как в биматричных играх кооперация может улучшить положение обоих игроков. В биматричной игре имеется лишь одна нетривиальная коалиция (коалиция, состоящая более чем из одного игрока) — коалиция обоих игроков. Для пояснения отличий между индивидуальным выбором решений обоими игроками и совместным принятием решения коалицией этих игроков рассмотрим следующий пример.
ПРИМЕР 4. «КОНКУРС НА РЕАЛИЗАЦИЮ ПРОЕКТА».
Две фирмы участвуют в конкурсе на реализацию проекта, причем доход от реализации проекта составит 10 у.е. Каждая фирма может либо подать простую заявку на участие в конкурсе (затраты равны 1 у.е.), либо представить программу реализации проекта (затраты составят 3 у.е.). По условиям конкурса, если обе фирмы выбирают одинаковый способ подачи заявки, то заказ (и доход) на реализацию проекта делится между ними пополам. Если же фирмы выбирают различные способы действий, то предпочтение отдается фирме, которая представит программу. Требуется разрешить эту конфликтную ситуацию.
РЕШЕНИЕ. Представим описанную конфликтную ситуацию в виде биматричной игры. Игроками A и B здесь выступают фирмы, стратегия A1 (B1) — подача заявки на участие в конкурсе, стратегия A2 (B2) — представление программы действий.
Количественно выигрыши игроков можно выразить следующим образом: A=
B1 B2
A1 4 – 1
A2 7 2
B=
B1 B2
A1 4 7
A2 – 1 2
Решив эту игру, найдем единственную равновесную ситуацию p = q = 0 , или (A2 , B2) с выигрышем H1(0, 0) = H2(0, 0) = 2. В этом случае каждая фирма получает прибыль, равную 2 у.е. Для этого обе фирмы должны представить программу действий и поделить пополам доход от реализации проекта. Ни одному из этих игроков невыгодно отклоняться от этой стратегии, так как это может только уменьшить его выигрыш. Но если игроки одновременно отклоняются от оптимальной (равновесной по Нэшу) стратегии, то возникает ситуация (A1,B1), которая очевидно является более выгодной для обоих из них с выигрышем H1(1,1)= H2(1,1) = 4. Однако переход к этой ситуации возможен только как результат договора между игроками, что осуществимо лишь при создании коалиции этих игроков.
Объединение игроков в коалицию требует как минимум возможности обмена информацией между ними. Если же игроки не могут обмениваться информацией, то каждый из них будет опасаться менять выбранную им чистую стратегию A2 (B2) на стратегию A1 (B1) , так как это приводит к уменьшению выигрыша отклонившегося игрока.
Рассмотренный пример демонстрирует важную особенность биматричных игр — возможность наличия противоречия между выгодностью и устойчивостью (положением равновесия). Действительно, ситуация (A2 , B2) является устойчивой, но невыгодной; а ситуация (A1 , B1) — выгодной, но неустойчивой. Поэтому если игроки заключают между собой договор — обоим придерживаться стратегии (A1 , B1) , то этот договор будет находиться под угрозой нарушения, так как каждому игроку выгодно его одностороннее нарушение.
При исследовании кооперативного аспекта в теории игр внимание обращается, как правило, не на ситуации игры, а на ее исходы. В соответствии с этим в основе оптимальности лежит идея выгодности.
Проанализируем, как может реализовываться идея выгодности в рамках неантагонистической игры двух лиц. Пусть {Ai}, i = 1, …, m, — множество стратегий первого игрока, а {Bj}, j = 1, …, n, — множество стратегий второго игрока. Если игроки образуют коалицию, то они могут создавать любую ситуацию (Ai , Bj), и, таким образом, реализовать любой исход игры. Возникает вопрос, какой исход игры следует считать в этом случае наиболее выгодным для коалиции, то есть оптимальным для нее.
Так, в рамках примера «КОНКУРС НА РЕАЛИЗАЦИЮ ПРОЕКТА» игроки, объединившись в коалицию, предпочтут исход (A1 , B1) исходу (A2 , B2). Однако исходы (A1, B2) и (A2, B1) также являются «кандидатами» на оптимальность.
В общем случае для биматричной игры рассмотрение вопроса о ее оптимальности с точки зрения коалиции удобно представить в геометрической форме. На координатной плоскости (Н1 , Н2) изобразим точки, координатами которых являются выигрыши игроков (aij , bij) для каждой возможной ситуации (Ai, Bj). При этом возникает «картинка», похожая на ту, что изображена на рисунке 6.
Так как коалиция может выбирать любой из представленных девяти исходов, то фактически получается задача двухкритериальной оптимизации, где первый игрок стремится максимизировать критерий H1 , а второй — критерий H2.
Анализ такой многокритериальной задачи можно провести в два этапа. На первом этапе мы проводим доминирование стратегий по Парето. Отбрасывая исходы, доминируемые по Парето, получаем множество Парето-оптимальных исходов. В примере, представленном на рисунке 6, Парето-оптимальными являются исходы {4, 5, 6, 8}.
Выбор оптимального исхода следует производить из множества Парето-оптимальных исходов. На втором этапе необходимо решить вопрос — какое из Парето-оптимальных решений следует считать оптимальным?
На первом этапе игроки выступают как союзники, так как этот шаг выгоден обоим из них. Однако на втором этапе, при сравнении любых двух Парето-оптимальных решений, игроки из союзников превращаются в противников: так как увеличение выигрыша одного из них влечет за собой уменьшение выигрыша другого.
H2
0 H1
Рисунок 6. Нахождение Парето-оптимальных решений.
Для решения задачи нахождения оптимального исхода в кооперативной игре сделаем еще одно допущение: возможно использование не только чистых, но и смешанных стратегий. Это приводит к тому, что вместе с двумя чистыми исходами (H1 , H2) и (H1’ , H2’) коалиция может реализовать также исход:
λ • (H1, H2) + (1-λ) • ( H1’, H2’) = (λ • H1 + (1-λ) • H1’, λ • H2 + (1-λ) • H2’),
где число λ удовлетворяет условию 0 ≤ λ ≤ 1.
С геометрической точки зрения, это означает, что множество исходов биматричной игры превращается в многоугольник D (рисунок 7), вершинами которого будут точки (aij, bij). При этом исходы, оптимальные по Парето, образуют «северо-восточную» границу этого многоугольника, а именно, это ломаная (8, 6, 4, 5).
H2
0 H1
Рисунок 7. Многоугольник исходов D.
Задача нахождения кооперативного решения биматричной игры сводится теперь к построению правила, которое для каждого такого многоугольника исходов D указывает единственный оптимальный исход, принадлежащий его «северо-восточной» границе.
Рассмотрим решение этой задачи, известное как АРБИТРАЖНОЕ РЕШЕНИЕ НЕША.
Арбитражное решение представляет собой некую систему требований (аксиом), с помощью которых для любой игры выделяется ее единственное решение — оптимальный исход этой игры.
Пусть νA и νB — цены матричных игр с матрицами A и B соответственно. Тогда в явном виде арбитражное решение Нэша для пары (H1, H2) — это точка (H1*, H2*), для которой произведение (функция полезности):
U = (H1 – νA) • (H2 – νB)
достигает своего наибольшего значения в той части области D возможных исходов биматричной игры, в которой выполняются условия:
H1 > νA, H2 > νB.
В заключение отметим, что большинство напоминающих игры ситуаций общественной жизни порождают как конфликтное, так и кооперативное поведение. В большинстве игр, возникающих из анализа социально-экономических ситуаций, интересы не являются ни строго антагонистическими, ни точно совпадающими. Действительно, продавец и покупатель согласны, что в их общих интересах договориться о продаже, конечно, при условии, что сделка выгодна обоим. Однако они энергично торгуются при выборе конкретной цены в пределах, определяющихся условиями взаимной выгодности сделки. А теория игр является полезным логическим аппаратом для анализа мотивов поведения участников в подобных ситуациях. И приложения теории игр преимущественно развивались в связи с исследованием экономики. Это соответствует установкам основоположников теории игр фон Неймана и Моргенштерна. Однако прочная репутация теоретико-игрового подхода утвердилась только после теоремы Дебре-Скарфа, позволяющей рассматривать конкурентное равновесие как результат кооперативных действий. С тех пор целые разделы экономической теории (такие, как теория несовершенной конкуренции или теория экономического стимулирования) развивались в тесном контакте с теорией игр.
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ.
[1] Вентцель Е.С. Элементы теории игр. М.: Физматгиз, 1961.
[2] Данилов В.И. Лекции по теории игр. М.: Российская экономическая школа, 2001.
[3] Печерский С.Л., Беляева А.А. Теория игр для экономистов. Вводный курс. Учебное пособие. СПб.: 2001.
[4] Фомин Г.П. Математические методы и модели в коммерческой дея¬тельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финан¬сы и статистика, 2005. — 616 с: ил.
[5] Шикин Е. В. От игр к играм. Математическое введение. Изд. 2-е, исправл. — М.: Едиториал УРСС, 2003. — 112 с.