Нормализация позиционной игры.

Заранее определенную последовательность ходов игрока, выбранную им в зависимости от информации о ходах другого игрока и ходах игрока О (природы), будем называть чистой стратегией этого игрока. В том случае, если в игре нет случайных ходов (игрок О в игре не участвует), выбор игроком А и ифоком В чистых стратегий однозначно определяет исход игры — приводит к окончательной позиции, где игрок А и получаст свой выигрыш. Это обстоятельство позволяет сводить позиционную игру к матричной игре. Процесс сведения позиционной игры к матричной называется нормализацией позиционной игры. Покажем на нескольких примерах, как это делается. Пример 13 (продолжение). Опишем стратегии игроков. Стратегию игрока А можно задать одним числом х, показывающим, какую альтернативу, первую или вторую, выбрал игрок. Тем самым, у игрока А две чистых стратегии: А | — выбрать i=l, Aj — выбрать х = 2. Стратегию игрока В, принимая во внимание, что выбор игрока А на 1-м ходе ему известен, удобно описывать упорядоченной парой Здесь г/i (yt = 1,2) — альтернатива, выбираемая игроком В при условии, что игрок А выбрал первую альтернативу, — альтернатива, выбираемая игроком В при условии, что игрок А выбрал вторую альтернативу, х = 2. Например, выбор игроком В стратегии (2, 1) означает, что если на 1-м ходе игрок А выбрал х = 1, то игрок В на своем ходе должен выбрать у = 2. Если же на 1-м ходе игрок А выбрал х = 2, то согласно этой стратегии игрок В на своем ходе должен выбрать у = 1. Таким образом, у игрока В четыре чистых стратегии: У - 1 при любом выборе х; Покажем теперь, как рассчитываются выигрыши игрока А в зависимости от примененных стратегий. Пусть, например, игрок А выбрал стратегию А у — (1), а игрок В — стратегию В2 — 11, 2]. Тогда х = 1, а из стратегии [1,2] вытекает, что у = I. Отсюда ИЧ*,у) = W(!,l) = l. Остальные выигрыши рассчитываются совершенно аналогично. ов записываются обычно или в виде таблицы выигрышей игрока А или в виде матрицы игры Нормализация позиционная игра где, как обычно, строки соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В. Полученная матрица имеет седловую точку. Оптимальные стратегии игроков: А\ — (1) и By — (2, 1]. Тем самым, игрок А на 1-м ходе выбирает х = I, а игрок В на 2-м ходе выбирает у = 2. Цена Пример 14 (продолжение). Опишем стратегии игроков. У игрока А они те же, что и в предыдущем примере: — выбрать г = 1, Ai — выбрать х = 2. Так как игроку В выбор игрока А неизвестен, то есть игрок В не знает, в какой именно из двух позиций он находится (см. рис. 4), то у него те же две стратегии: В] — выбрать у = 1, В} — выбрать у = 2. Соответствующие таблица выигрышей игрока А и матрица игры имеют следующий вид Полученная матрица седловой точки не имеет. Оптимальные смешанные стратегии игроков: Р = Цена игры и = 0. Замечание 1. На этих двух примерах хорошо видно, что результат сведения позиционной игры к матричной напрямую зависит от степени информированности игроков. В частности, отсутствие у игрока В сведений о выборе, сделанном игроком А, приводит к уменьшению количества его возможных стратегий. Сравнивая ответы, полученные в примерах 13 и 14, замечаем, что снижение уровня информированности игрока (в данном случае — игрока В) делает для него исход игры менее благоприятным. Замечание 2. Приведенные выше примеры не исчерпывают всех возможных вариантов даже в этом, самом простом, случае двухходовых позиционных игр. Рассмотрим теперь несколько примеров сведения к матричным играм позиционных игр, состоящих из трех ходов, сосредоточив при этом основное внимание на одном из наиболее ответственных шагов нормализации — описании стратегий игроков. Пример 15. 1'йход долает игрок А : он выбирает число х из множества двух чисел {1,2}. 2-й ход делает игрок В: зная выбранное игроком А число х, он выбирает число у из множества двух чисел {1,2}. 3-й ход делает игрок А: не зная о выбранном игроке В числе у на 2-м ходе и забыв выбранное им самим на I -м ходе число х, он выбирает число z из множества двух чисел {1,2}. После этого игрок А получает вознаграждение W(x, у, z) за счет игрока В, например, такое:. На рис. 5 показаны дерево игры и информационные множества. Результаты расчет Нормализуем эту игру. Поскольку игроку В выбор игрока А на 1-м ходе известен, то у игрока В те же четыре стратегии, что и в примере 13: Игрок А на 3-м ходе не знает предыдущих выборов — ни значения х, ни значения у. Поэтому каждая его стратегия состоит просто из пары чисел (z, z), где х (ж = 1, 2) — альтернатива, выбираемая игроком А на 1-м ходе, a z (г = 1, 2) — альтернатива, выбираемая игроком А на 3-м ходе. Например, выбор игроком А стратегии (2, I) означает, что на 1-м ходе он выбирает х = 2, а на 3-м ходе — 2 = 1. Таким образом, у игрока А четыре стратегии: Нормализация позиционная игра Покажем теперь, как рассчитываются выигрыши игрока А в зависимости от стратегий, применяемых в данной игре. Пусть, например, игрок А выбрал стратегию Ai — (1, 2), а игрок В — стратегию Вз — |2, 1). Тогда х = I, откуда вытекает, что у = 2. Значение z — 2 выбрано игроком А независимо от выбора игрока В. Вычисляя значение функции выигрышей для этого набора, полумаем В результате подобных рассуждений получаются и остальные пятнадцать выигрышей. Это позволяет построить таблицу выигрышей игрока А. Имеем или Пример 16. 1-й ход делает игрок А: он выбирает число х из множества двух чисел {1,2}. 2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число у из множества двух чисел {1,2}. 3-й ход делает игрок А : он выбирает число z из множества двух чисел {I, 2}, не зная ни значения х, ни значения у. После этого игроки расплачиваются по правилу, указанному в примере 15. Графическое представление этой игры показано на рис. 6. Ясно, что у игрока Л те же четыре стратегии, что Рис.6 и в примере 15: У игрока В всего две стратегии: В\ — выбрать у = 1, В] — выбрать у = 2. В этом случае (весьма слабой информированности игроков) таблица выигрышей игрока А и соответствующая матрица строятся совсем просто. Имеем В следующем примере информационные множества выглядят немного иначе. Пример 17. 1-й ход делает игрок А : он выбирает число х из множества двух чисел {1,2}. 2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число у из множества двух чисел {1,2}. 3-й ход делает игрок А: он выбирает число z из множества двух чисел {1, 2}. зная выбор у игрока В на 2-м ходе, но не помня собственного выбора г на 1-м ходе. После этого игроки расплачиваются по правилу, указанному в примере 15. Графическое представление этой игры показано на рис. 7. Поскольку игроку В неизвестен выбор игрока А на 1-м ходе, то, выполняя свой ход, он не знает, в какой именно из двух возможных позиций он находится. Поэтому у игрока В всего две стратегии: В\ — выбрать у = 1, В2 — выбрать у = 2. Нормализация позиционная игра При описании стратегий игрока А нужно исходить из того, что к 3-му ходу игрок А утратил сведения о собственном выборе на 1 -м ходе, но ему известен выбор игрока В на 2-м ходе. Поэтому выбор числа z игроку А следует связать с известным ому к 3-му ходу значением у. Удобнее всего это сделать по аналогии с расчетом стратегий игрока В в примерах 13 и 15, т.е. при помощи упорядоченной пары Здесь z\ (z\ = 1,2) — альтернатива, выбираемая игроком А при условии, что игрок В выбрал первую альтернативу, у = 1, a z2 (z2 — 1, 2) — альтернатива, выбираемая игроком А при условии, что игрок В выбрал вторую альтернативу, у = 2. Чистую стратегию игрока А в данной игре можно записать так Здесь х (х - I, 2) — альтернатива, которую игрок А выбирает на 1-м ходе, z\ (z, = 1,2) — альтернатива, которую игрок А выбирает на 3-м ходе, если на 2-м ходе игрок В выбрал выбрал первую альтернативу (у = 1) и z2 (г2 = 1, 2) — альтернатива, которую игрок А выбирает на 3-м ходе, если на 2-м ходе игрок В выбрал вторую альтернативу (у = 2). Например, выбор игроком А стратегии (2,(2, 1]) означает, что на 1-м ходе игрок А выбирает х - 2, а на 3-м z — 2, если игрок В выбрал у = I, и z = 1, если игрок В выбрал у — ?. Тем самым, у игрока А восемь чистых стратегий: Покажем теперь, как в зависимости от применяемых стратегий определяются элементы таблицы выигрышей игрока А. Пусть, например, игрок А выбрал стратегию >4} — (I, |2, 1)). а игрок В — стратегию В2 — (2) Тогда х = I, у = 2, а из |2, I) вытекает, что z = I. Отсюда По этой же схеме вычисляются и остальные элементы таблицы. Оптимальные смешанные стратегии игроков и цена игры соответственно равны: Рассмотрим позиционную ифу со случайным ходом. Пример 18. 1-й ход производится случайно: игрок О выбирает число х. равное 1, с вероятностью 0,5 и равное 2 с такой же вероятностью. 2-й ход делает игрок А: он выбирает число у из множества двух чисел {1, 2}, не зная результатов случайного выбора на 1-м ходе. 3-й ход делает игрок В: он выбирает число z из множества двух чисел {1,2}, зная о том, какое именно число х случайно выбрано игроком О на 1-м ходе и не зная выбора у игрока А на 2-м ходе. После этого игроки расплачиваются, используя функцию W(z, у, г), ту же, что и в предыдущих примерах. Графическое представление этой игры показано на рис. 8. Опишем стратегии игроков Поскольку игроку А исход случайного испытания неизвестен. то он имеет всего две стратегии: При построении своих стратегий игроку В естественно воспользоваться имеющейся у него информацией о результате 1-го хода. Это позволит ему описать свою стратегию упорядоченной парой Здесь — альтернатива, выбираемая игроком В при условии, что х = \,а z2 (z2 = 1,2)-— альтернатива, выбираемая игроком В при условии, что х = 2. Тем самым, у игрока В четыре стратегии: Покажем теперь, как определяются элементы таблицы выигрышей игрока А. Пусть, например, игрок А выбрал стратегию А\ — (1). а игрок В — стратегию By — |2, 1 ]. Различаются два случая Если х = 1, то стратегия By указывает игроку В его выбор z = 2. А так как у — 1, то в результате имеем Если х = 2. то стратегия By указывает игроку В его выбор z = I. А так как у = 1, то в результате имеем В результате получаем Поскольку первая и вторая альтернативы на 1-м ходе выбираются с вероятностями 0,5 и 0,5, то и вышеуказанные выигрыши появляются с теми же вероятностями и, следовательно, средний выигрыш игрока А при этих стратегиях определяется так Аналогичным образом рассчитывая остальные средние выигрыши, получаем при х = 1 Нормализация позиционная игра /303 [-3 5-3 Искомая матрица игры имеет следующий вид или при х = 2 ( -I Наконец, рассмотрим пример позиционной игры со случайным разыгрыванием права первого хода. Пример 19. 1-й ход делает игрок О. выбирая число х, равное I с вероятностью 2/3 и равное 2 с вероятностью 1/3. Если х = 1, то на 2-м ходе игрок А выбирает число у из множества двух чисел {1,2}, зная результат случайного выбора на 1-м ходе, а на 3-м ходе игрок В выбирает число z из множества двух чисел {1,2}, зная х, но не зная у. Если х = 2, то на 2-м ходе игрок В выбирает число у из множества двух чисел {1,2}, зная результат случайного выбора на 1-м ходе, а на 3-м ходе игрок А выбирает число z из множества двух чисел {1, 2}, зная х, но не зная у. После этого игроки расплачиваются, используя функцию W(x, y,z), ту же, что и в предыдущих примерах. Графическое представление этой игры показано на рис. 9. Чистую стратегию игрока А в данной игре можно описать упорядоченной парой где у (у = 1, 2) — выбор игрока А на 2-м ходе, если на 1-м ходе выбрано х = 1, a z (z = 1, 2) — выбор игрока А на 3-м ходе, если на 1-м ходе выбрано х — 2. Например, стратегия |1, 2| означает, что на 2-м ходе игрок А выбирает у = 1, а на 3-м ходе — Тем самым, у игрока А четыре стратегии: У игрока В те же четыре стратегии: Покажем теперь, как находятся элементы матрицы выигрышей игрока А. Пусть, например, игрок А применяет стратегию Л2 — |1, 2|, а игрок В — стратегию Bj — J2, 1|. Различаются два случая l)i=l и 2) х = 2. По условию при х = 1 игрок А имеет возможность сделать только 2-й ход (выбрать у), а игрок В — только 3-й (выбрать г). При х = 2 их возможности меняются местами: игроку В предоставлено право 2-го хода (выбрать у), а игроку А — 3-го (выбрать г). Если х — 1, то стратегия Л 2 указывает игроку А при 2-м ходе взять у = 1, а стратегия By указывает игроку В при 3-м ходе взять z — 1. В результате Если х = 2. то стратегия By указывает игроку В при 2-м ходе взять у = 2, а стратегия А2 указывает игроку А при 3-м ходе взять г — 2. В результате Поскольку первая и вторая альтернативы на 1-м ходе выбираются соответственно с вероятностями 2/3 и 1/3, то и найденные выигрыши появляются с теми же вероятностями. Следовательно, математическое ожидание выигрыша игрока А при таких стратегиях рассчитывается так Отсюда получаем искомую матрицу игры Замечание. Графическое представление и функция выигрышей полностью определяют позиционную игру. В рассмотренных выше примерах 16-19 мы пользовались одной и той же функцией и одним и тем же деревом. Отличие было только в маркировке вершин дерева и информационных множествах. При построении последних необходимо соблюдать два правила: 1) в одно информационное множество могут входить позиции только одного игрока, 2) цепь, определяющая партию игры, может иметь с информационным множеством не более одной общей позиции. Как показывает рис. 10, и при таких ограничениях информационные множества могут выглядеть довольно необычно.

Биматричные игры.