Приближенный метод решения матричных игр mxn icon

Приближенный метод решения матричных игр mxn




Скачати 224.1 Kb.
НазваПриближенный метод решения матричных игр mxn
Дата08.09.2012
Розмір224.1 Kb.
ТипДокументи

  1. Приближенный метод решения матричных игр mxn


Рассмотрим приближенный метод решения матричных игр - метод Брауна-Робинсона (иначе - метод итераций). Идея его заключается в следующем. Разыгрывается эксперимент, в котором игроки А и В поочередно применяют друг против друга свои чистые стратегии. Каждый из игроков стремится увеличить свой выигрыш, предполагая, что будущее будет походить на прошлое; при этом считается, что ни один из них не знает своей оптимальной стратегии.

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

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

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

Объясним этот метод на примере игры 3x3, платежная матрица которой приведена ниже. Игра начинается с произвольно выбранной стратегии игрока А, - например стратегии А1 (выбранные стратегии обозначаются звездочкой). Платежные элементы этой строки переписываются под платежной матрицей. Игрок В, предполагая, что будущее будет походить на прошлое, выберет стратегию В2, при которой его проигрыш минимален. Соответствующий этой стратегии проигрыш обозначен звездочкой. Платежные элементы стратегии В2 переписываются справа от платежной матрицы. Игрок А, также предполагая, что будущее будет походить на прошлое, выбирает стратегию А2 (наибольшее число обозначено звездочкой). Платежные элементы, соответствующие стратегии А2, прибавляются поочередно с предыдущей строкой, записанной под матрицей. Далее выбирается наименьший элемент суммарной строки. Ему соответствует стратегия В3. Тогда к столбцу, записанному справа от платежной матрицы, поочередно прибавляются платежные элементы стратегии В3. Этот процесс продолжается до тех пор, пока разрыв между нижней и верхней оценками игры станет небольшим.


Bj
















1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20




Ai

B1

B2

B3







2

9

18

25

27

29

31

33

42

51*

60

62

64

66

75

84*

93

95

97*

99




A1

7

2

9

*




9*

11*

11

13

22

31*

40*

49*

49*

49

49

58

67*

76*

76*

76

76

87

96

105*




A2

2

9

0







0

9

20*

29*

29*

29

29

29

40

51

62*

62*

62

62

73

84

95*

95*

95

95




A3

9

0

11























































































































































1

7

2*

9



































































2

9*

11

9



































































3

11

20

9*



































































4

20*

20

20



































































5

29

20*

31



































































6

38

20*

42



































































7

40

29*

42



































































8

42

38*

42



































































9

44

47

42*



































































10

46

56

42*



































































11

53

58

51*



































































12

62

58*

62



































































13

71

58*

73



































































14

73

67*

73



































































15

75

76

73*



































































16

77

85

73*



































































17

84

87

82*



































































18

93

87*

93



































































19

102

87*

104



































































20

109

89*

113




































































В рассматриваемом примере сделано 20 шагов. За эти двадцать шагов игрок А применил свою первую стратегию (количество звездочек в суммарных выигрышах, соответствующей первой стратегии) 3 раза; вторую - 10 раз; третью - 7 раз. Игрок В применил стратегию В1 два раза; вторую - 11 раз; третью - 8 раз. Следовательно, приближенные оценки оптимальных стратегий, полученные за 20 итераций, равны:



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

Приближенную цену игры определяют как среднеарифметические между нижней оценкой игры , равной минимально накопленному выигрышу игрока А, деленному на число шагов k, и верхней оценкой игры , равной максимальному суммарному проигрышу игрока В, деленному на k:



В рассматриваемом примере



Точная цена игры v=5.

Разрыв между и отражает неточность оценок относительно оптимальных смешанных стратегий. В примере составляет 18% от цены игры v=5.

Увеличивая число итераций k, то можно найти более точные оценки оптимальных смешанных стратегий.

Преимуществом итерационного метода решения матричных игр является то, что объем вычислений с увеличением размерности игры mxn растет существенно медленнее, чем в методах линейного программирования (в частности симплекс - метода).


^ 2.10. Качественная оценка элементов платежной матрицы

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

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

Пусть, например, платежи оцениваются как плохие (п); удовлетворительные (у), хорошие (х) или отличные (о), а матрица игры имеет вид


Bj


Ai


B1


B2


B3


B4


B5


i

A1

п

у

х

о

х

п

A2

у

у

х

х

о

у*

A3

п

о

о

о

х

п

A4

у

о

у

п

п

п

j

у*

о

о

о

о





В этой игре ==y, т.е. игра решается в чистых стратегиях. Игрок А должен придерживаться своей второй стратегии, а игрок В - стратегии В1. Цена игры - удовлетворительно.

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





B1

B2

B3

B4

B5

B6

A1



















A2



















A3



















A4







*










A5



















A6



















A7




















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

Пример. Решить игру, платежная матрица которой имеет вид


Bj


Ai


B1


B2


B3

A1

п

о

у

A2

х

у

х

A3

п

х

п


Как видно стратегия В1 доминирует стратегию В3, стратегия А1 доминирует стратегию А3, а, следовательно, исходную игру можно свести к игре 2*2:


Bj


Ai


B1


B2


i

A1

п

о

п

A2

х

у

у*

j

х*

о





Таким образом, игрокам не следует использовать стратегии А3 и В3. Так как =у не равняется =х, то игра не имеет седловой точки и должна решаться в смешанных стратегиях.

Частоты применения своих стратегий игроком А равны:

;

;

Частоты применения своих стратегий игроком В равны:

;

;

Таким образом, частота применения стратегии А1 пропорциональна разности между “хорошо” и “удовлетворительно”, а стратегии А2 пропорциональна разности между “отлично” и “плохо”. Ясно, что стратегия А1 должна применяться реже, чем стратегия А2 независимо от того, какие упорядоченные числа будут приписаны этим понятиям.

Положение игрока В несколько более неопределенно. Он должен применять стратегию В1 с частотой пропорциональной разности между “отлично” и “удовлетворительно”, а стратегию В2 - с частотой, пропорциональной разности между “хорошо” и “плохо”. Здесь неясно, какая разность больше.

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



Схожі:

Приближенный метод решения матричных игр mxn icon2 Упрощение матричных игр
Решение матричных игр тем сложнее, чем больше размерность платежной матрицы. Поэтому для игр с платежными матрицами большой размерности...
Приближенный метод решения матричных игр mxn iconЛ. Ф. Василевич Решение нечётких матричных игр
Таким образом, возникает нечёткая матричная игра. В данной статье предлагается методика решения таких игр и анализа чувствительности...
Приближенный метод решения матричных игр mxn iconКонтрольные вопросы по курсу "Исследование операций и теория игр"
Теорема о активных стратегиях. Сведение матричных игр (2 Х n), (m Х 2) к матричной игре (2 Х 2)
Приближенный метод решения матричных игр mxn icon2 Графический метод решения задач линейного программирования
Графическое решение задач лп дает наглядное представление процесса нахождения оптимального решения, а также анализа полученного решения...
Приближенный метод решения матричных игр mxn icon2 Графический метод решения задач линейного программирования
Графическое решение задач лп дает наглядное представление процесса нахождения оптимального решения, а также анализа полученного решения...
Приближенный метод решения матричных игр mxn icon2 Графический метод решения задач линейного программирования
Графическое решение задач лп дает наглядное представление процесса нахождения оптимального решения, а также анализа полученного решения...
Приближенный метод решения матричных игр mxn iconП. И. Чайковский 3 основные понятия теории игр и их классификация 3 > Предмет и задачи теории игр 3 > Терминология и классификация игр 4 > Примеры игр 6 тесты
Книга содержит большое количество тестов и задач, которые можно использовать для проведения практических занятий, а также для самостоятельного...
Приближенный метод решения матричных игр mxn iconП. И. Чайковский 4 основные понятия теории игр и их классификация 4 > Предмет и задачи теории игр 4 > Терминология и классификация игр 7 > Примеры игр 12 тесты
Книга содержит большое количество тестов и задач, которые можно использовать для проведения практических занятий, а также для самостоятельного...
Приближенный метод решения матричных игр mxn icon1. основные понятия теории игр и их классификация предмет и задачи теории игр
Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке...
Приближенный метод решения матричных игр mxn icon1. основные понятия теории игр и их классификация предмет и задачи теории игр
Даже идея Руссо об эволюции от «естественной свободы» к «гражданской свободе» формально соответствует с позиций теории игр точке...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи