Лекция 6 Ситуация равновесия по Нэшу в информационном расширении игры

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

Подчеркнем, что ценность полученной информации определяется не ее объемом, а полезностью. Для одних задач (целей) полезная информация одна, для других – другая. Таким образом, оценка получаемой информации определяется через функцию выигрыша.

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

Информационное расширение игры

Пусть задана исходная игра Г=<X₁, X₂, M₁, M₂>, тогда игра

I=<X1,X2,π,M1(x1,x2),M2(x1,x2)называется информационным расширением игры , если существует проекция π: × X₁×X_2, обладающая следующими свойствами:

1) Каждой паре стратегий ( , ) × ставит в соответствие пару управлений (исходов) (x₁, x₂) X₁×X₂

2) Множество стратегий содержит стратегии , т.е. стратегии – управления, не использующие информации.

3) Функции выигрыша в игре вычисляются по правилу:

_i( , ) = M_i(π ( , ))

Не для любых множеств стратегий выполняется свойство (1), а следовательно и свойства (2) и (3).

Например, возьмем пару { }. В этом случае игрок 1 знает о выборе второго, а игрок 2 одновременно знает выбор первого - противоречие. Следовательно, пара { } «физически» не реализуема.

Свойство (2) заключается в следующем:

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

Выигрыши в игре определяются по свойству (3) равенством:

_i( , ) = M_i( π ( , ))

Т.е. сначала стратегии ( , ) проектируются во множество управлений (исходов) - (x₁, x₂) X₁×X₂, а затем вычисляются значения _i( , ), как и в игре Г.

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

Пример 1:

Пусть , т.е. ,

, т.е.

Тогда ( , ) .

Фиксируем для примера:

X1=x(x2)=x2^2

X2=x2=1/2.

Тогда эти стратегии проектируются так:

( x 1, x 2 ) ( x 1 (x 2 ) , x 2 ) (x 2/2, ½) =(1/4,1/2)

Пример 2:

Пусть x1: x 2  X 1 т.е. ,

x 2 : x 1X 2, т.е. - игрок 2 принимает решение в зависимости от стратегии первого игрока. Например,

Проектируем:

,

так как

.

Ситуация равновесия по Нэшу в информационном расширении игры

Пусть задана игра:

Г = < , , , >

и ее информационное расширение:

Определение.

( ⁰, ⁰)- ситуация равновесия в информационном расширении игры, если M₁⁰ =M₁(π( ⁰, ⁰))= M₁(π( , ⁰))

M₂⁰= M₂(π( ⁰, ⁰))= M₂(π( ⁰, )

Заметим ,что

( ⁰, ⁰) π (х₁⁰, х₂⁰) – равновесный исход, но не ситуация равновесия!

Таким образом, ситуация равновесия может реализоваться на стратегиях

( º, º) є

но ее проекция

( хº₁, хº₂) є

не обязательно равновесная по Нэшу.

Напомним, что стратегия ^а = х₁^а(х₂) называется абсолютно оптимальной стратегией, если справедливо равенство:

M₁(x₁^а(x₂), x₂)= M₁(x₁, x₂)

Определим x₂= х₂^а - оптимальный ответ второго игрока из условия:

M₂(x₁^а(x₂), x₂) = M₂(x₁^а(x₂^а), x₂^а )

Положительные свойства стратегий:

Свойство 1.

Ситуация равновесия всегда существует на классе стратегий

( , )=(x₁(x₂), x₂)

Доказательство: Достаточно выбрать абсолютно оптимальную стратегию ^а = хª₁(x₂), и оптимальный ответ на нее ^а = х₂^а

По определению:

M₁(x₁^а(x₂), x₂) = M₁(x₁, x₂),

M₂(x₁^а(x₂^а), x₂^а ) = M₂(x₁^а(x₂), x₂).

Тогда, если = х₂^а, то

M₁(π( ,x^2^а))= M₁(x₁(xª₂), xª₂) = M₁(x₁^а(x₂^а), x₂^а ).

Если = ^а ( ), то M₂(x₁^а(x₂), x₂ )= M₂(x₁^а(x₂^а), x₂^а), что соответствует определению ситуации равновесия в информационном расширении игры.

Свойство 2.

Если , то и – увеличение информации приводит к возможности увеличения выигрыша.т

Доказательство:

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

Свойство 3.

Пусть игрок 1 знает х_{2 .}

Определим взаимовыгодное множество для этого случая:

₁₂={(х₁, х₂) M₁( х₁, х₂) ≥ M₁(х₁, х₂);

M₂( х₁, х₂) ≥ M₂(х₁, х₂)}.

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

{х₁(х₂), х₂[х₁(х₂)]}

Аналогичное утверждение верно и в симметричном случае, когда игрок 2 знает х_1.

Здесь взаимовыгодное множество определяется следующим образом:

₂₁={(х₁, х₂) M₁( х₁, х₂) ≥ M₁(х₁, х₂);

M₂( х₁, х₂) ≥ M₂(х₁, х₂)}.

А класс использованных стратегий имеет вид:

{ х₁ [х₂(х₁)], х₂ (х₁)}.

Для иллюстрации сделанных выводов рассмотрим следующий

Пример. [1]

Исследуем биматричную игру:

М₁= M₂=

Сначала найдем равновесные ситуации в исходной игре.

Для этого определим:

x₁^a(x₂) –абсолютно оптимальную стратегию первого игрока и

х₂ = x₂^a – оптимальный ответ второго.

Напомним, что:

x₁^a(x₂): M₁(x₁^a(x₂), x₂) = M₁(x₁, x₂)x₂^a:

M₂(x₁^a(x₂^а), x₂^a) = M₂(x₁^a(x₂^а), x₂).

Итак:

3, если x₂ = 1

x₁^a(x₂) = 2, если x₂ = 2

2, если x₂ = 3

Аналогично: 3, если x₁ = 1

x₂^a(x₁) = 2, если x₁ = 2

2, если x₁ = 3

Единственная ситуация равновесия в исходной игре определяется из условия пересечения оптимальных стратегий в точке (x₁^a(x₂^а) , x₂^a(x₁^a)) (2,2).

В этой ситуации выигрыши игроков равны (4,4).

Построим П-множество Парето на классе исходных управлений.

Напомним, что

(x₁^п, x₂^п) П

если не существует (x₁^', x₂^')єХ₁*Х₂, такой что:

M_i(x₁^', x₂^') ≥ M_i(x₁^п, x₂^п), i=1, 2 (дизъюнкция)

M_i(x₁^', x₂^') > M_i(x₁^п, x₂^п), i=1 либо i=2 (конъюнкция)

В пространстве выигрышей множество возможных решений имеет вид:

M₂

П

7

6 П

4 (4, 4) с.р.

3

2 П

0 2 3 4 6 7 M₁

рис.1

Как видно из рис.1:

П = {( 1,1); (1,3); (3,1)},

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

МП = {(6,6); (2,7); (7,2)}.

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

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

{ х₁(х₂), х₂[х₁(х₂)]}, {х₁[х₂(х₁)], х₂(х₁)}.

Имеем для игрока 1:

M₁(x₁, x₂) = 0

M₁(x₁, x₂) = 3

Определим: х₂ = х₂^H - стратегия наказания первого игрока вторым, из условия

M₁(х₁, х₂) = M₁(х₁, х₂^H)

В данном случае имеем х₂^H= .

Далее для игрока 2 имеем: M₂(x₁, x₂) = 0

M₂(x₁, x₂) = 3

Определим х₁^H (х₂) - стратегию наказания второго игрока первым.

2, если х₁ = 1

х₁^H (х₂)= 1, если х₂ = 2

3 (2), если х₃ =3

Покажем, что равновесные стратегии можно выбрать на классе стратегий {x₁(x₂), x₂ [x₁(x₂)]} .Действительно , пусть

x₁⁰ (x₂) = 1, х₂=1 ⁰ = х₂⁰ [х₁(х₂)] = 1, =

х₁^н (х₂), х₂ 1 , х₂^н = 3,

Очевидно, эти стратегии проектируются в точку (х₁ = 1, х₂=1). В этой точке M₁ = 6, M₂ = 6.

Если от этих стратегий отклонится игрок 1, то есть , то он получит не больше, чем

M₁(π( , ⁰))= M₁(π ( , 3) = M₁(2, 3) = 3 < 6.

Таким образом, игроку 1 не выгодно отклоняться от точки ( , ⁰).

Если же при = , игрок 2 выберет , то его выигрыш оценивается величиной

M₂[π( ⁰, )].

Если т.ч. х₂ 1, при = , то

M₂[π( ⁰, )] = M₂(х₁^H(х₂), х₂) = 0 < 6

Итак, игроку 2 также не выгодно отклоняться от точки ( , ⁰), то есть ( , ⁰) – ситуация равновесия в игре .

Замечание. Точку из множества Парето можно сделать равновесной, если выигрыши игроков в ней оцениваются величиной не меньшей, чем их максимально гарантированные результаты, соответствующие их информированности. Этому условию удовлетворяют также точка (7,2) на классе стратегий {x₁(x₂), x₂ [x₁(x₂)]} и точка (2,7) на классе стратегий {x₂(x₁), x₁ [x₂(x₁)]}.

Упражнение.

Точку (7,2) можно сделать ситуацией равновесия на классе

{x₁(x₂), x₂ [x₁(x₂)]}

Точку (2,7) можно сделать ситуацией равновесия на классе

{x₂(x₁), x₁ [x₂(x₁)]}.

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

1. Вычислить гарантированные (минимальные или максимальные, в зависимости от информированности ) результаты игроков.

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

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

4. Путем переговоров выбирается точка из этого множества, устраивающая обоих партнеров.

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

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

Проведем анализ рассмотренных ранее иллюстративных игр, но уже на классе стратегий.

Игра «продавец – покупатель»

В этой игре на классе исходных управлений не существует равновесной ситуации.

Пусть теперь например, покупатель имеет информацию о действиях продавца. Тогда его абсолютно оптимальная стратегия заключается в доверии (без затрат на проверку в случае честного поведения продавца. Если же продавец обманул, то оптимальное поведение покупателя – проверить и наказать продавца. Оптимальный выбор продавца в этой ситуации –честно взвесить товар. Что приводит к исходу – (честно взвеситл, поверил). Подчеркнем, что эта ситуация не является ситуацией равновесия в исходной игре! Ситуация равновесия реализуется только на классе стратегий.

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

Заметим, что различные варианты информированности приводят к различным ситуациям равновесия.

Игра «семейный спор»

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

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

Игра «реклама»

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