Заранее определенную последовательность ходов игрока, выбранную им в зависимости от информации о ходах другого игрока и ходах игрока О (природы), будем называть чистой стратегией этого игрока.
В том случае, если в игре нет случайных ходов (игрок О в игре не участвует), выбор игроком А и игроком В чистых стратегий однозначно определяет исход игры — приводит к окончательной позиции, где игрок А. и получает свой выигрыш. Это обстоятельство позволяет сводить позиционную игру к матричной игре.
Процесс сведения позиционной игры к матричной называется нормализацией позиционной игры.
Покажем на нескольких примерах, как это делается.
Пример 13 (продолжение). Опишем стратегии игроков.
Стратегию игрока А можно задать одним числом х, показывающим, какую альтернативу, первую или вторую, выбрал игрок.
Тем самым, у игрока А две чистых стратегии:
А1 —выбрать х = 1, А2 — выбрать х = 2.
Стратегию игрока В, принимая во внимание, что выбор игрока А на 1-м ходе ему известен, удобно описывать упорядоченной парой
[y1, y2].
Здесь y1 (y1 = 1, 2) — альтернатива, выбираемая игроком В при условии, что игрок А выбрал первую альтернативу, х = 1, a y2 (y2 = 1, 2) — альтернатива, выбираемая игроком В при условии, что игрок А выбрал вторую альтернативу, х = 2.
Например, выбор игроком В стратегии [2, 1] означает, что если на 1-м ходе игрок А выбрал х = 1, то игрок В на своем ходе должен выбрать у = 2. Если же на 1-м xoде игрок А выбрал х = 2, то согласно этой стратегии игрок В на своем ходе должен выбрать у = 1.
Таким образом, у игрока В четыре чистых стратегии:
В1 — [1,1], у = 1 при любом выборе х;
В2 — [1, 2], у = х при любом выборе х;
В3 — [2,1], у ≠ х при любом выборе х;
В4 — [2, 2], у = 2 при любом выборе х.
Покажем теперь, как рассчитываются выигрыши игрока А в зависимости от примененных стратегий.
Пусть, например, игрок А выбрал стратегию А1 — (1), а игрок В — стратегию В2 — [1, 2]. Тогда х = 1, а из стратегии [1, 2] вытекает, что у = 1. Отсюда
W(х, y) = W(1, 1) = 1.
Остальные выигрыши рассчитываются совершенно аналогично.
Результаты расчетов записывается обычно или в виде таблицы выигрышей игрока А
| В1 | В2 | В3 | В4 | ||
| [1, 1] | [1, 2] | [2, 1] | [2, 2] | ||
| А1 | х = 1 | W(1, 1) | W(1, 1) | W(1, 2) | W(1, 2) |
| А2 | х = 2 | W(2, 1) | W(2, 2) | W(2, 1) | W(2, 2) |
или в вида матрицы игры
,
где, как обычно, строки соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В,
Полученная матрица имеет седловую точку. Оптимальные стратегии игроков: А1 — (1) и В3 — [2, 1]. Тем самым, игрок А на 1-м ходе выбирает х = 1, а игрок В на 2-м ходе выбирает у = 2. Цена игры v = -1.
Пример 14 (продолжение). Опишем стратегии игроков.
У игрока А они те же, что и в предыдущем примере
А1 – выбрать х = 1, А2 — выбрать х = 2.
Так как игроку В выбор игрока А неизвестен, то есть игрок В не знает, в какой именно из двух позиций он находится (см. рис. 4), то у него те же две стратегии:
В1 — выбрать у = 1, В2 — выбрать у = 2.
Соответствующие таблица выигрышей игрока А и матрица игры имеют следующий вид
| В1 | В2 | ||
| Y = 1 | y = 2 | ||
| А1 | х = 1 | W(1, 1) | W(1, 2) |
| А2 | х = 2 | W(2, 1) | W(2, 2) |
Полученная матрица седловой точки не имеет. Оптимальные смешанные стратегии игроков: Р = {2/3, 1/3} и Q = {1/2, 1/2}. Цена игры v = 0.
Замечание 1. На этих двух примерах хорошо видно, что результат сведения позиционной игры к матричной напрямую зависит от степени информированности игроков. В частности, отсутствие у игрока В сведений о выборе, сделанном игроком А приводит к уменьшению количества его возможных стратегий. Сравнивая, ответы, полученные в примерах 13 и 14, замечаем, что, снижение уровня информированности игрока (в данном случае — игрока В) делает для него исход игры менее, благоприятными.
Замечание 2. Приведенные выше примеры не исчерпывают всех возможных вариантов даже в этом, самом простом, случае двухходовых позиционных игр.
Рассмотрим теперь несколько примеров сведения к матричным играм позиционных игр, состоящих из трех ходов, сосредоточив при этом основное внимание на одном из наиболее ответственных шагов нормализации — описании стратегий игроков.
Пример 15.
1-й ход делает игрок А: он выбирает число х из множества двух чисел {1, 2}.
2-й ход делает игрок В: зная выбранное игроком А число х, он выбирает число у из множества двух чисел {1, 2}.
3-й ход делает игрок А: не зная о выбранном игроке В числе у на 2-м ходе и забыв выбранное им самим на 1-м ходе число х, он выбирает число z из множества двух чисел {1, 2}.
После этого игрок А получает вознаграждение W(x, у, z) за счет игрока В, например, такое:
W(1, 1, 1) = -2 W(2, 1, 1) = 3
W(1, 1, 2) = 4 W(2, 1, 2) = 0
W(1, 2, 1) = 1 W(2, 2, 1) = -3
W(1, 2, 2) = -4 W(2, 2, 2) = 5
На рис.5 показаны дерево игры и информационные множества.
Рис. 5
Нормализуем эту игру.
Поскольку игроку В выбор игрока А на 1-м ходе известен, то у игрока В те же четыре стратегии, что и в примере 13:
В1 – [1, 1], В2 – [1, 2], В3 – [2, 1], В4 – [2, 2].
Игрок А на 3-м ходе не знает предыдущих выборов — ни значения х, ни значения у. Поэтому каждая его стратегия состоит просто из пары чисел (х, z), где x (х = 1, 2) — альтернатива, выбираемая игроком А на 1-м ходе, а z (z = 1, 2) — альтернатива, выбираемая игроком А на 3-м ходе.
Например, выбор игроком А стратегии (2, 1) означает, что на 1-м ходе он выбирает x = 2, а на 3-м ходе — z = 1.
Таким образом, у игрока А четыре стратегии:
A1 – [1, 1], A2 – [1, 2], A3 – [2, 1], A4 – [2, 2].
Покажем теперь, как рассчитываются выигрыши игрока А в зависимости от стратегий, применяемых в данной игре. Пусть, например, игрок А выбрал стратегию A2 — (1, 2), а игрок В — стратегию В3 — (2, 1]• Тогда х = 1, откуда вытекает, что у = 2. Значение z = 2 выбрано игроком А независимо от выбора игрока В. Вычисляя значение функции выигрышей для этого набора, получаем
W(x, y, z) = W(1, 2, 2) = -4.
В результате подобных рассуждений получаются и остальные пятнадцать выигрышей. Это позволяет построить таблицу выигрышей игрока А. Имеем
| В1 | В2 | В3 | В4 | ||
| [1, 1] | [1, 2] | [2, 1] | [2, 2] | ||
| А1 | (1, 1) | W(1, 1, 1) | W(1, 1, 1) | W(1, 2, 1) | W(1, 2, 1) |
| А2 | (1, 2) | W(1, 1, 2) | W(1, 1, 2) | W(1, 2, 2) | W(1, 2, 2) |
| А3 | (2, 1) | W(2, 1, 1) | W(2, 2, 1) | W(2, 1, 1) | W(2, 2, 1) |
| А4 | (2, 2) | W(2, 1, 2) | W(2, 2, 2) | W(2, 1, 2) | W(2, 2, 2) |
или
.
Пример 16.
1-й ход делает игрок А: он выбирает число х из множества двух чисел {1, 2}.
2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число у из множества двух чисел {1, 2}.
3-й ход делает игрок А: он выбирает число z из множества двух чисел {1, 2}, не зная ни значения х, ни значения у.
После этого игроки расплачиваются по правилу, указанному в примере 15.
Графическое представление этой игры показано на рис. 6.
Рис. 6
Ясно, что у игрока А те же четыре стратегии, что и в примере 15:
A1 – [1, 1], A2 – [1, 2], A3 – [2, 1], A4 – [2, 2].
У игрока В всего две стратегии:
B1 – выбрать y = 1, B2 – выбрать y = 2
В этом случае (весьма слабой информированности игроков) таблица выигрышей игрока A и соответствующая матрица строятся совсем просто. Имеем
| В1 | В2 | ||
| y = 1 | y = 2 | ||
| А1 | (1, 1) | W(1, 1, 1) | W(1, 1, 1) |
| А2 | (1, 2) | W(1, 1, 2) | W(1, 2, 2) |
| А3 | (2, 1) | W(2, 1, 1) | W(2, 2, 1) |
| А4 | (2, 2) | W(2, 1, 2) | W(2, 2, 2) |
Оптимальные смешанные стратегии игроков и цена игры соответственно равны:
В следующем примере информационные множества выглядят немного иначе.
Пример 17.
1-й ход делает игрок А: он выбирает число х из множества двух чисел {1, 2}.
2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число у из множества двух чисел {1, 2}.
3-й ход делает игрок А: он выбирает число z из множества двух чисел {1, 2}, зная выбор у игрока В на 2-м ходе, но не помня собственного выбора х на 1-м ходе.
После этого игроки расплачиваются по правилу, указанному в примере 15.
Графическое представление этой игры показано на рис. 7.
Рис. 7
Поскольку игроку В неизвестен выбор игрока А на 1-м ходе, то, выполняя свой ход, он не знает, в какой именно из двух возможных позиций он находится. Поэтому у игрока В всего две стратегии:
B1 – выбрать y = 1, B2 – выбрать y = 2
При описании стратегий игрока А нужно исходит из того, что к 3-му ходу игрок А утратил сведения о собственном выборе на 1-м ходе, но ему известен выбор игрока В на 2-м ходе. Поэтому выбор числа z игроку А следует связать с известным ему к 3-му xоду значением у. Удобнее всего это сделать по аналогии с расчетом стратегий игрока В в примерах 13 и 15, т. е. при помощи упорядоченной пары
[z1, z2]
Здесь z1 (z1 = 1, 2) — альтернатива, выбираемая игроком А при условии, что игрок В выбрал первую альтернативу, у = 1, a z2 (z2 — 1, 2) — альтернатива, выбираемая игроком А при условии, что игрок В выбрал вторую альтернативу, у = 2.
Чистую стратегию игрока А в данной игре можно записать так
(x, [z1, z2]).
Здесь х (х = 1, 2) — альтернатива, которую игрок А выбирает на 1-м ходе, z1 (z1 = 1, 2) — альтернатива, которую игрок А выбирает на 3-м ходе, если на 2-м ходе игрок В выбрал выбрал первую альтернативу (у = 1) и z2 (z2 — 1, 2) — альтернатива, которую игрок А выбирает на 3-м ходе, если на 2-м ходе игрок В выбрал вторую альтернативу (у = 2).
Например, выбор игроком А стратегии (2, [2, 1]) означает, что на 1-м ходе игрок А выбирает x = 2, а на 3-м z = 2, если игрок В выбрал у = 1, и z = 1, если игрок В выбрал у = 2.
Тем самым, у игрока А восемь чистых стратегий:
A1 — (1, [1, 1]), A2 — (1, [1, 2]), A3 — (1, [2, 1]), A4 — (1, [2, 2]),
A5 — (2, [1, 1]), A6 — (2, [1, 2]), A7 — (2, [2, 1]), A8 — (2, [2, 2]),
Покажем теперь, как в зависимости от применяемых стратегий определяются элементы таблицы выигрышей игрока А.
Пусть, например, игрок А выбрал стратегию A3 — (1, [2, 1]), а игрок В — стратегию В2 — (2). Тогда x = 1, у = 2, а из [2, 1] вытекает, что z = 1. Отсюда
W(x, y, z) = W(1, 2, 1) = 1.
По этой же схеме вычисляются и остальные элементы таблицы.
В результате получаем
| В1 | В2 | |||
| (1) | (2) | |||
| А1 | (1, [1, 1]) | W(1, 1, 1) | W(1, 2, 1) | |
| А2 | (1, [1, 2]) | W(1, 1, 1) | W(1, 2, 2) | |
| А3 | (1, [2, 1]) | W(1, 1, 2) | W(1, 2, 1) | |
| А4 | (1, [2, 2]) | W(1, 1, 2) | W(1, 2, 2) | |
| А5 | (2, [1, 1]) | W(2, 1, 1) | W(2, 2, 1) | |
| А6 | (2, [1, 2]) | W(2, 1, 1) | W(2, 2, 2) | |
| А7 | (2, [2, 1]) | W(2, 1, 2) | W(2, 2, 1) | |
| А8 | (2, [2, 2]) | W(2, 1, 2) | W(2, 2, 2) | |
Оптимальные смешанны* стратегии игроков и цена игры соответственно равны:
Рассмотрим позиционную игру со случайным ходом.
Пример 18.
1-й ход производится случайно: игрок О выбирает число х, равное 1, с вероятностью 0,5 и равное 2 с такой же вероятностью.
2-й ход делает игрок А: он выбирает число у из множества двух чисел {1, 2}, не зная результатов случайного выбора на 1-м ходе.
3-й ход делает игрок В: он выбирает число z из множества двух чисел {1, 2}, зная о том, какое именно число х случайно выбрано игроком О на 1-м ходе и не зная выбора у игрока А на 2-м ходе.
После этого игроки расплачиваются, используя функцию W(x, y, z), ту же. что и в предыдущих примерах.
Графическое представление этой игры показано на рис.8.
Рис. 8
Опишем стратегии игроков
Поскольку игроку А исход случайного испытания неизвестен, то он имеет всего две стратегии:
А1 – (1), А2 – (2),
При построении своих стратегий игроку В естественно воспользоваться имеющейся у него информацией о результате 1-го хода. Это позволит ему описать свою стратегию упорядоченной парой
[z1, z2].
Здесь z1 (z1 = 1, 2) — альтернатива, выбираемая игроком В при условии, что х = 1, a z2 (z2 = 1, 2) — альтернатива, выбираемая игроком В при условии, что х = 2. Тем самым, у игрока В четыре стратегии:
В1 — [1, 1], В2 — [1, 2], В3 — [2, 1], В4 — [2, 2].
Покажем теперь, как определяются элементы таблицы выигрышей игрока А.
Пусть, например, игрок А выбрал стратегию А1 — (1), а игрок В — стратегию В3 — [2, 1].
Различаются два случая
1) х = 1 и 2) х = 2.
Если х = 1, то стратегия В3 указывает игроку В3 его Выборг z = 2. А так как у = 1, то в результате имеем
W(x, y, z) = W(1, 1, 2) = 4.
Если х = 2, то стратегия В3 указывает игроку В его выбор z = 1. А так как у = 1, то в результате
W(x, y, z) = W(2, 1, 1) = 3.
Поскольку первая и вторая альтернативы на 1-м ходе выбираются с вероятностями 0,5 и 0,5, то и вышеуказанные выигрыши появляются с теми же вероятностями и, следовательно, средний выигрыш игрока А при этих стратегиях определяется так
4 x 0,5 + 3 x 0,5 = 3,5.
Аналогичным образом рассчитывая остальные средние выигрыши, получаем при х = 1
| В1 | В2 | В3 | В4 | ||
| [1, 1] | [1, 2] | [2, 1] | [2, 2] | ||
| А1 | (1) | W(1, 1, 1) | W(1, 1, 1) | W(1, 1, 2) | W(1, 1, 2) |
| А2 | (2) | W(1, 2, 1) | W(1, 2, 1) | W(1, 2, 2) | W(1, 2, 2) |
или
,
при х = 2
| В1 | В2 | В3 | В4 | ||
| [1, 1] | [1, 2] | [2, 1] | [2, 2] | ||
| А1 | (1) | W(2, 1, 1) | W(2, 1, 1) | W(2, 1, 2) | W(2, 1, 2) |
| А2 | (2) | W(2, 2, 1) | W(2, 2, 2) | W(2, 2, 2) | W(2, 1, 1) |
или
.
Искомая матрица игры имеет следующий вид
.
Наконец, рассмотрим пример позиционной игры со случайным разыгрыванием права первого хода.
Пример 19.
1-й ход делает игрок О, выбирая число х, равное 1 с вероятностью 2/3 и равное 2 с вероятностью 1/3.
Если х = 1, то на 2-м ходе игрок А выбирает число у из множества двух чисел {1, 2}, зная результат случайного выбора на 1-м ходе, а на 3-й ходе игрок В выбирает число z из множества двух чисел {1, 2}, зная х, но не зная у.
Если x = 2, то на 2-м ходе игрок В выбирает число у из множества двух чисел {1, 2}, зная результат случайного выбора на 1-м ходе, а на 3-м ходе игрок А выбирает число z из множества двух чисел {1, 2}, зная х, но не зная у.
После этого игроки расплачиваются, используя функцию W(x, y, z), ту же, что и в предыдущих примерах.
Графическое представление этой игры показано на рис. 9.
Рис. 9
Чистую стратегию игрока А в данной игре можно описать упорядоченной парой
где у (у = 1, 2) — выбор игрока А на 2-м ходе, если на 1-м ходе выбрано х = 1, а z (z = 1, 2) — выбор игрока А на 3-м ходе, если на 1-м ходе выбрано х = 2.
Например, стратегия |1, 2| означает, что на 2-м хода игрок А выбирает у = 1, а на 3-м ходе — z = 2.
Тем самым, у игрока А четыре стратегии:
А1 — |1, 1|, А 2 — |1, 2|, А 3 — |2, 1|, А 4 — |2, 2|.
У игрока В те же четыре стратегии:
В1 — |1, 1|, В2 — |1, 2|, В3 — |2, 1|, В4 — |2, 2|.
Покажем теперь, как находятся элементы матрицы выигрышей игрока А.
Пусть, например, игрок А применяет стратегию А2 — |1, 2|, а игрок В — стратегию В3 — |2, 1|.
Различаются два случая
1) х = 1 и 2) х = 2.
По условию при х = 1 игрок А имеет возможность сделать только 2-й ход (выбрать у), а игрок В — только 3-й (выбрать 2). При х = 2 их возможности меняются местами: игроку В предоставлено право 2-го хода (выбрать у), а игроку А — 3-го (выбрать z). .
Если х = 1, то стратегия А2 указывает игроку А при 2-м ходе взять у = 1, а стратегия В3 указывает игроку В при 3-м ходе взять z = 1. В результате
W(x, y, z) = W(1, 1, 1) = -2.
Если х = 2, то стратегия B3 указывает игроку В при 2-м ходе взять у = 2, а стратегия А2 указывает игроку А при 3-м ходе взять z = 2. В результате
W(x, y, z) = W(2, 2, 2) = 5.
Поскольку первая и вторая альтернативы на 1-м ходе выбираются соответственно с вероятностями 2/3 и 1/3, то и найденные выигрыши появляются с теми же вероятностями. Следовательно, математическое ожидание выигрыша игрока А при таких стратегиях рассчитывается так
.
Итак,
при х = 1
| В1 | В2 | В3 | В4 | ||
| |1, 1| | |1, 2| | |2, 1| | |2, 2| | ||
| А1 | |1, 1| | W(1, 1, 1) | W(1, 1, 2) | W(1, 1, 1) | W(1, 1, 2) |
| А2 | |1, 2| | W(1, 1, 1) | W(1, 1, 2) | W(1, 1, 1) | W(1, 1, 2) |
| А3 | |2, 1| | W(1, 2, 1) | W(1, 2, 2) | W(1, 2, 1) | W(1, 2, 2) |
| А4 | |2, 2| | W(1, 2, 1) | W(1, 2, 2) | W(1, 2, 1) | W(1, 2, 2) |
или
,
при х = 2
| В1 | В2 | В3 | В4 | ||
| |1, 1| | |1, 2| | |2, 1| | |2, 2| | ||
| А1 | |1, 1| | W(2, 1, 1) | W(2, 1, 1) | W(2, 2, 1) | W(2, 2, 1) |
| А2 | |1, 2| | W(2, 1, 2) | W(2, 1, 2) | W(2, 2, 2) | W(2, 2, 2) |
| А3 | |2, 1| | W(2, 1, 1) | W(2, 1, 1) | W(2, 2, 1) | W(2, 2, 1) |
| А4 | |2, 2| | W(2, 1, 2) | W(2, 1, 2) | W(2, 2, 2) | W(2, 2, 2) |
или
.
Отсюда получаем искомую матрицу игры
.
Замечание. Графическое представление и функция выигрышей полностью определяют позиционную игру. В рассмотренных выше примерах 16-19 мы пользовались одной и той же функцией и одним и тем же деревом. Отличие было только в маркировке вершин дерева и информационных множествах. При построении последних необходимо соблюдать два правила:
1) в одно информационное множество могут входить позиции только одного игрока,
2) цепь, определяющая партию игры, может иметь с информационным множеством не более одной общей позиции.
Рис. 10
Как показывает рис. 10, и при таких ограничениях информационные множества могут выглядеть довольно необычно.
Дата: 2016-10-02, просмотров: 287.
