Игровые модели. Классификация игр. Теория игр

1. 9. Игровые модели

2.

9.1 Классификация игр.
Антагонистические игры.

3.

4.

5.

6.

7.

Таким образом, в игровых задачах всегда известен
набор стратегий (вариантов решений), доступный ЛПР. В
качестве единственного критерия для оценки принятого
решения выступает выигрыш. Основная сложность такого
рода задач заключается в том, что принятое игроком решение
может привести к различным значениям выигрыша, в
зависимости от того, какие решения будут приняты другими
игроками, что, конечно, усложняет
процедуру сравнения
различных решений между собой.

8.

9. Кроме игр с нулевой и ненулевой суммой в которых участвуют не менее двух игроков, преследующих собственные интересы, можно

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

10.

11.

12.

13.

14. Пусть имеются два игрока - А и B, каждый из которых может выбрать одну из трех стратегий поведения. Выигрыши игрока A для всех

вариантов развития
событий приведены в таблице (матрице)
выигрышей

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

41.

42.

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

44.

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

45. В зависимости от того, разрешено или запрещено сотрудничество игроков, биматричные игры делятся на некооперативные и

кооперативные.
Обозначим, как и прежде, набор стратегий
одного игрока вектором p=(p1, p2, ...),
а набор стратегий второго - вектором
q=(q1, q2, ...).

46. В некооперативной игре при выборе стратегии игроки руководствуются принципом максимальной осторожности. Если условия игры

позволяют смешивать
стратегии, игроки могут построить свои
оптимальные смешанные стратегии.

47. Рассмотрим в качестве примера некооперативной игры задачу «Дилемма заключенных». Двое преступников попали в тюрьму. Если оба

будут молчать,
их осудят за незначительное преступление, и они получат
по одному году, если оба сознаются - по восемь лет, если
один сознается, а другой - нет, сознавшегося отпустят, а
его подельника посадят на 10 лет. Матрицы выигрыша
для игроков выглядят следующим образом (у игрока А
выигрыши для каждой стратегии записываются в строчку,
у игрока B - в столбик) :

48. Согласно принципу максимальной осторожности в некооперативной игре оба игрока должны сознаться. Данное решение является точкой

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

49. Выбранные стратегии игроков образуют равновесие Нэша, если ни одному из игроков не выгодно отклоняться от равновесной стратегии

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

50.

Пример. Рассмотрим в качестве примера игру
«студент-преподаватель». Студент (игрок A) готовиться
к зачету, который принимает преподаватель (игрок B).
У студента есть всего две стратегии (A1 и A2) –
готовиться или не готовиться к зачету. Аналогично
преподаватель может поставить (B1) или не поставить
зачет (B2). Матрицы выигрыша для игроков приведены
ниже. Необходимо найти точки равновесия Нэша.
Студент:
Преподаватель:
A1
A2
B1
B2
2
1
-1
0
B1
B2
A1
1
-3
A2
-2
-1

51.

Решение.
Во-первых,
рассмотрим
действия
игроков,
продиктованные принципом максимальной осторожности, т.е.
поместим их в условия, когда им известна только собственная
матрица выигрыша. В этом случае студент должен выбрать
стратегию A2 (гарантированный выигрыш равен 0) а
преподаватель - стратегию B1. (гарантированный выигрыш
равен -2) – если он выбирает в качестве решения чистую
стратегию. Данный набор стратегий не является равновесием
Нэша, поскольку отклонившись от него в одиночку, студент
может максимизировать свой выигрыш до 1 (получить не только
отметку о зачете, но и знания). Преподаватель, в свою очередь,
выбрав другую стратегию при той же стратегии студента, может
увеличить свой выигрыш до -1 (не поставив незаслуженный
зачет).

52.

Отметим, что поскольку верхняя и нижняя цена игры
для матрицы выигрышей преподавателя не совпадают, он
может увеличить гарантированный выигрыш до –1.4 (вместо –
2), применив смешанную стратегию (1/4; 3/4), тогда как для
студента остается оптимальной чистая стратегия A2, однако
данное решение также не будет равновесием по Нэшу.

53.

Легко проверить, что равновесие по Нэшу в этой
задаче обеспечивают наборы чистых стратегий (A1, B1) с
выигрышем (2, 1) и (A2, B2) с выигрышем (0, -1). Кроме того,
при неоднократной игре равновесие Нэша может быть
достигнуто путем применения игроками смешанных
стратегий, рассчитанных на основе матрицы выигрышей
соперника. Это связано с тем, что, применив определенную
смешанную стратегию, каждый из игроков может поставить
другого в положение, в котором никакими действиями нельзя
изменить свой выигрыш. Так, если студент смешает свои
стратегии в соотношении (1/5, 4/5), то он гарантирует
преподавателю ожидаемый выигрыш, который не зависит от
выбора стратегии преподавателем и составляет -1.4. Если
преподаватель смешает стратегии в пропорции (1/2, 1/2), то
он гарантирует ожидаемый выигрыш для студента, равный
1/2 при любой стратегии студента.

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

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

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

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

56. Если переговорное множество состоит из парето-оптимальных решений (доминирующих решений нет) и договориться о выборе той или

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

57. На рисунке T1 и T2 - точки гарантированного минимального выигрыша для игроков 1 и 2 в непрерывной игре. Точка T называется

точкой
угрозы. Точки дуги AB образуют переговорное
множество. Точка N (точка Нэша) соответствует
максимуму функции Нэша

58. В теории игр доказано, что если множество возможных выигрышей выпукло, замкнуто и ограничено сверху, то точка Нэша существует

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

59. Принцип Нэша можно применить и для решения  биматричных игр. Просто здесь  множество возможных решений ограничено несколькими

Принцип Нэша можно применить и для
решения биматричных игр. Просто здесь множество
возможных решений ограничено несколькими точками
на плоскости возможных выигрышей с координатными
осями V1 и
V2. Рассмотрим следующий пример.
Кооперативная игра задается матрицей выигрышей
Выигрыши
игроков
в
имеющихся
стратегиях игроков изображены
точками A, B, C, D. Парето-оптимальное
множество - отрезок AD, переговорное - участок
от p1 до p2.

60.

61. Чтобы найти решение, максимизирующее функцию Нэша f(x,y)=max(x-4)(y-4), выразим y через x, записав уравнение прямой AD

(y-8)/(8-2)=(x-2)/(2-8),
откуда y=10-x. Легко проверить, что функция
f(x)=10x-x2-24 максимальна в точке x=5, т.е. точка
Нэша в этой задаче имеет координаты (5, 5).
Если игроки применят первую стратегию и
поделят выигрыш поровну, они достигнут точки
Нэша.

62. В данной игре кооперация будет выгодна обоим игрокам только при условии, что они смогут поделить суммарный выигрыш. Игры, в

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

63. В общем случае, решение биматричной игры может основываться на различных критериях, среди которых: 1. Стремление каждого игрока

гарантировать
себе максимальный возможный выигрыш
2. Стремление игроков достичь равновесия
3. Стремление игроков увеличить общую сумму
выигрыша
4. Стремление игрока добиться максимального
превосходства над противником (максимальной
разности между своим и его выигрышем).

64.

65.

66. 9.3 Игры с природой

67.

68.

69.

70.

71.

72.

73.

74.

75.

76.

77.

78.

79.

80.

81.

82.

83.

84.

85.

86.

87.

88.

89.

90.

91.

92.

93.

94.

95.

96.

97.

98.

99.

100.

101.

102.

103.

104.

105.

106.

107.

108.

9.4 Позиционные игры

109.

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

110.

Кружками изображаются положения, в которых
игроком выбирается ход, отрезками – возможные ходы
(альтернативы). Латинская буква в кружке показывает, кто
из игроков выбирает ход (буква O обычно служит для
обозначения случайного хода)

111.

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

112.

Нормальная форма позиционной игры
Все игры, которые мы рассматривали ранее, были представлены
в так называемой, «нормальной форме». Данное представление
предполагает, что:
1) задано множество всех игроков;
2) задано множество стратегий каждого игрока;
3) для каждой игровой ситуации (состояния, когда игроки
выбрали свои стратегии), заданы значения выигрышей для
каждого из игроков.

113.

Пример. Пусть имеется два игрока, причем у каждого есть
всего две стратегии – назвать число 1 или назвать число 2 –
и известно, сколько выигрывает игрок A (за счет игрока B) в
каждой игровой ситуации. Необходимо представить игру в
нормальной форме.
Решение.
1) Множество игроков можно описать как {A, B}.
2) Множества стратегий игроков – как
{A1: x=1, A2: x=2} и {B1: y=1, B2: y=2}.
3) Нам остается задать выигрыши для каждой игровой
ситуации. Зададим значения функции выплат W(x, y)
игроку A за счет игрока B следующим образом:
W(A1, B1)= W(1, 1)= 1; W(A1, B2)= W(1, 2)= –1
W(A2, B1)= W(2, 1)= –2; W(A2, B2)= W(2, 2)= 2

114.

В рассмотренном примере мы построили нормальную форму
для антагонистической игры с матрицей выигрышей:
A1
A2
B1
B2
1
-2
-1
2
Решением игры являются смешанные стратегии игроков.
Для A это
p = (2/3, 1/3).
Для B это
q = (1/2, 1/2).

115.

Двухходовая позиционная игра с неполной информацией.
Используя данные рассмотренного примера, попробуем
построить позиционную игру (с последовательными ходами
игроков), представить ее в нормальной форме и найти ее
решение.
Пусть так же, как и в рассмотренном примере, игроки во время
хода должны назвать одно из двух чисел (1 или 2). В
зависимости от названных обоими игроками чисел
осуществляются те же выплаты, что и ранее. Однако теперь
игрок B может совершить ход только после того, как реализует
свою стратегию игрок А.

116.

Как уже говорилось, все позиционные игры можно разделить
на игры с полной и неполной информацией. Предположим, что
игрок B не знает, какую стратегию выбрал игрок A, т.е. мы
имеем игру с неполной информацией. В этом случае дерево
игры выглядит, как показано на рисунке

117.

Пунктиром на этом рисунке выделены информационные
множества игроков A и B. Информационное множество
игрока в позиционной игре – это множество позиций, в
которых, как известно игроку, он может с ненулевой
вероятностью находиться на данном этапе игры. Например,
игрок A на первом ходу вполне осведомлен о своем положении
в игре, поэтому его информационное множество состоит всего
из одной позиции. Для игрока B на втором этапе игры такое
множество включает две позиции, поскольку он не знает, какой
ход произвел игрок A, а значит не может сказать, в какой из
двух позиций он сам находится.

118.

Очевидно , что игрок А, совершая ход, может
выбрать одну из двух стратегий {A1: x=1, A2: x=2}. Игрок B
также может выбирать лишь между стратегиями {B1: y=1,
B2: y=2}. Это означает, что рассмотренная позиционная игра
фактически
эквивалентна
рассмотренной
выше
антагонистической игре, то есть у нас уже есть и ее
представление в нормальной форме и ее решение.

119.

Двухходовая позиционная игра с полной информацией.
Рассмотрим вариант, когда игрок B принимает решение, зная,
какую стратегию выбрал игрок A. В этом случае дерево игры
выглядит, как показано на рисунке:

120.

Игрок A по-прежнему имеет те же две стратегии
{A1: x=1, A2: x=2}.
Однако с игроком B дело обстоит иначе. Он может
сформировать заранее целых четыре стратегии, которые будут
определять его реакцию на ход игрока A. Эти стратегии удобно
описывать векторной величиной
y = [y1, y2].
Каждая компонента y может принимать два разных значения (1
или 2), при этом компонента y1 показывает, что будет делать
игрок B, если игрок A выберет свою первую стратегию
(назовет число 1), а компонента y2 - реакцию на выбор второй
стратегии игрока А (игрок A называет число 2).

121.

Так, стратегия [1, 1] означает, что независимо от хода
игрока A игрок B назовет 1, а стратегия [2, 2] - выбор
игроком B при любом решении игрока A числа 2.
Оставшиеся две стратегии соответствуют случаю, когда
выбор игрока B совпадает с выбором A (стратегия [1, 2])
или противоположен ему (стратегия [2, 1]). В частности,
стратегия [2, 1] означает, что при выборе игроком A его
первой стратегии (x=1) игрок B выберет 2, а при выборе
второй (x=2) - единицу.

122.

Результирующую матрицу выплат можно представить в
следующем виде:
B1
B2
B3
B4
[1, 1]
[1, 2]
[2, 1]
[2, 2]
A1
W(1, 1)
W(1, 1)
W(1, 2)
W(1, 2)
A2
W(2, 1)
W(2, 2)
W(2, 1)
W(2, 2)
С учетом конкретных значений W (x, y1(2)) получим матрицу, в
которой перечислены выигрыши игрока A (равные проигрышам
игрока B) для всех стратегии игроков и, таким образом,
завершим построение нормальной формы для данной
двухходовой позиционной игры с полной информацией.

123.

B1
B2
B3
B4
[1, 1]
[1, 2]
[2, 1]
[2, 2]
A1
1
1
-1
-1
A2
-2
2
-2
2
В теории игр доказывается следующее утверждение:
Любая позиционная игра с полной информацией эквивалентна
некоторой матричной игре, в которой существует седловая
точка в чистых стратегиях.
Действительно, полученная матрица игры с полной
информацией имеет седловую точку (решение в чистых
стратегиях), которое состоит в выборе игроком A стратегии a
A1, а игроком B – стратегии B3.
* Шахматы – игра с полной информацией

124.

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

125.

Обозначим переменными x и z выбор игрока A на первом и
третьем ходу, а переменной y –выбор игрока B и зададим
выигрыши игрока A в результате всех возможных партий W(x, y,
z) следующим образом:
W(1, 1, 1)=a, W(1, 1, 2)=b, W(1, 2, 1)=c, W(1, 2, 2)=d,
W(2, 1, 1)=e, W(2, 1, 2)=f, W(2, 2, 1)=g, W(2, 2, 2)=h.

126.

Рассмотрим сначала возможные действия игрока B. С точки
зрения его возможных стратегий игра ничем не отличается от
двухходовой позиционной игры с полной информацией,
рассмотренной выше. Чтобы перечислить свои стратегии, ему
по-прежнему достаточно указать все возможные наборы из
двух чисел [y1, y2], описывающие его предполагаемую реакцию
на выбор, сделанный игроком A.
Игрок A свой первый ход выбирает по своему
усмотрению, а значит, множество его возможных стратегий
можно разделить на две группы – с x=1 и x=2. Кроме того,
игрок A должен заранее рассмотреть вопрос о том, как
реагировать на ход игрока B. Его возможные стратегии можно
описать с помощью переменной z = [z1, z2], компоненты
которой показывают, какое решение он примет после выбора
игроком B числа 1 или числа 2.

127.

Платежная матрица трехходовой позиционной игры с
полной информацией.
Если подставить в нее заданные значения выплат,
получим матрицу :

128.

129.

Позиционная игра в три хода с неполной информацией.
Пусть в описанной выше игре в три хода игроки не всегда
владеют полной информацией о своих позициях.
Рассмотрим несколько вариантов такой игры.
Вариант 1. Пусть на третьем ходе игрок A не имеет
информации о выборе игрока B и не помнит о том, какой
выбор он сам сделал во время первого хода. Дерево такой
игры и соответствующая матрица выплат приведены на
рисунках

130.

131.

Вариант 2. Пусть игрок A на третьем этапе игры по-прежнему не
помнит своего первого хода и не знает, что за выбор сделал игрок B.
Однако теперь и игрок B ничего не знает о выборе игрока A на
первом ходу.

132.

Вариант 3. Пусть игрок A на третьем этапе игры знает, какую
альтернативу выбрал игрок B, но не помнит свой первый ход. Игрок
B совершает ход, не имея информации о выборе игрока A.

133.

Позиционная игра в три хода с неполной информацией и
случайным выбором первого хода.
Пусть первый ход осуществляется случайным образом, причем
обе альтернативы равновероятны. Затем свой ход делает игрок
A, не зная, какая из альтернатив была выбрана ранее, после
чего ход делает игрок B, которому результаты случайного
выбора при первом ходе известны, но неизвестен выбор игрока
A.
Поскольку игрок A не знает о результатах первого хода, у него в
любом случае есть только две стратегии {A1: y=1, A2: y=2}.
Игрок B должен описывать свои стратегии упорядоченной
парой z=[z1, z2], где z1 - вариант, который он выберет, если при
первом ходе будет выбрано значение x=1 , z2 – реакция на
вариант x=2.

134.

135.

B1
x=1
x=2
B2
B3
B4
[1, 1]
[1, 2]
[2, 1]
[2, 2]
A1
W(1, 1, 1)
W(1, 1, 1)
W(1, 1, 2)
W(1, 1, 2)
A2
W(1, 2, 1)
W(1, 2, 1)
W(1, 2, 2)
W(1, 2, 2)
A1
W(2, 1, 1)
W(2, 1, 2)
W(2, 1, 1)
W(2, 1, 2)
A2
W(2, 2, 1)
W(2, 2, 2)
W(2, 2, 1)
W(2, 2, 2)

136.

Если учесть вероятности выбора альтернатив на первом ходу
(p1=0.5 и p2=0.5), можно построить результирующую
платежную матрицу, в которой каждый выигрыш
рассчитывается как математическое ожидание вариантов x=1 и
x=2. Например, для набора стратегий A1 и B1 имеем
V11= p1 W(1, 1, 1) + p2 W(2, 1, 1),
для A2 и B1 аналогично
V21= p1 W(1, 2, 1) + p2 W(2, 2, 1) и. т. д.

137.

Прежде чем завершить этот раздел, ответим еще на один
вопрос - чему равно число возможных стратегий игрока B в 4хходовой позиционной игре с полной информацией? Очевидно,
каждая из 4-х стратегий после первого хода A должна быть
дополнена одной из 4-х аналогичных стратегий после второго
хода A, то есть у игрока B появится 16 возможных стратегий.