Теория игр_10.05.2013.pptx

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

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

применив против игрока B стратегию, соответствующую максимальному элементу столбца

.
Доказано [Вентцель Е.С. Исследование операций: Задачи, принципы, методология.
Учебное пособие- М.: Дрофа, 2004. ], что при многократно повторяемой игре без седловой точки игроку A, для обеспечения среднего выигрыша, большего, чем α , следует чередовать свои стратегии .
Игроку B для улучшения результата также целесообразно чередовать свои стратегии
Для многократно повторяемых игр без седловой точки вводится следующее определение.
• В играх, которые повторяются многократно, каждая из стратегий
называется чистой стратегией.
• Стратегия игрока A, обозначаемая


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

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

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

утверждающая, что каждая игра имеет, по крайней мере, одно решение,

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

Следствие1. Любая игра имеет цену.

Следствие2. Цена игры удовлетворяет неравенству

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

2
Рассмотрим игру без седловой точки типа 2 x 2

с платежной матрицей


и найдем оптимальную стратегию


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

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




решение которой имеет вид






Аналогичным образом можно найти оптимальную стратегию



игрока B. В этом случае неизвестные удовлетворяют системе урав-нений

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

× и 2 m ×
Рассмотрим игру типа 2 n ×

с платежной матрицей


и проведем через точку (1; 0) координатной плоскости Oxy прямую l, перпендикулярную оси абсцисс.
После этого для каждой из стратегий проведем прямую

соединяющую точку на оси Оу с точкой на прямой l. Ось Оу отвечает за стратегию , а прямая l − за стратегию

× и 2 m ×








Если игрок А применяет смешанную стратегию

применяет чистую стратегию
равен

и этому выигрышу соответствует точка М на прямой

с абсциссой

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

× и 2 m ×
Выигрыш игрока А, если он придерживается

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



Частоты в оптимальной стратегии


игрока В определяются из соотношения

× и 2 m ×
Пример . Пусть игра задана матрицей


Найти

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

Следовательно, , и оптимальной стратегией игрока В является стратегия

× и 2 m ×


Цена игры V = 7,2.
Полезными

стратегиями игрока А являются стратегии .
Найдем их частоты

стратегии
Пример. Рассмотрим игру с платежной матрицей, показанной в таблице 1.

Платежная матрица не имеет седловой точки, т. к. в этой игре ни один из участников игры не может выбрать один план в качестве своей оптимальной стратегии.
Следовательно, каждый игрок должен найти некоторую «смешан­ную стратегию» для максимизации своего выигрыша или минимизации своего проигрыша.
Таблица 1
Допустим, например, что А решает играть половину времени по плану Р, а половину по плану Q. Если В при этом будет все время играть по плану S, то ожидаемый выигрыш для А будет

а если В будет все время играть по плану Т, то ожидаемый выигрыш игрока А будет

стратегии
Допустим далее, что В также применяет смешанную стратегию и в

половине случаев выбирает план S, а в половине Т, причем каждый выбор определяет случайно. В этом случае ожидаемый выигрыш игрока А будет

Подобным образом можем подсчитать, каков ожидаемый выигрыш А при других смешанных стратегиях. Например, если А играет в четверти случаев план Р, a Q — в трех четвертях, в то время как В играет одну треть раз S, а две трети Т, то ожидаемый выигрыш А будет

Возникает вопрос: какова оптимальная смешанная стратегия для игро­ков? Из приведенных примеров видим, что выигрыш А меняется от 1,5 долларов до 4 долларов. Хотим узнать, не может ли игрок А обес­печить себе некоторый минимум выигрыша и каков он?
Подобным образом, может ли В застраховаться от проигрыша больше некоторого максималь­ного?
На эти вопросы можно ответить положительно. Математическая теория игр дает доказательство того, что всегда существуют оптимальные стра­тегии и способы их нахождения.

стратегии
Рассмотрим теперь, как могут быть найдены оптимальные стратегии этой игры

и каковы ожидаемые значения выигрыша и проигрыша для игроков.
Пусть А играет Р с частотой х, a Q с частотой 1 — х. Тогда, если В будет играть все время S, выигрыш А будет

Если В будет все время играть Т, выигрыш А будет


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


В результате получаем

стратегии
Таким образом, независимо от частот, с которыми В играет S

или Т, А всегда выигрывает 3 доллара. (Если, например, В играет S с частотой и Т с частотой
то ожидаемый выигрыш для А будет

и так же при любом выборе частот для В.) Следовательно, выбором частот 1/3 и 2/3
А получает обеспеченный выигрыш в 3 доллара.
Тот же самый метод можно применить к игроку В. Обозначим частоту выбора плана S буквой y, тогда частота выбора Т будет 1 - y . Для оптимальной стратегии имеем:



Заметим, что для игры с нулевой суммой.
Полным решением данной игры будет: (1) А следует играть Р и Q соответственно с
частотами 1/3 и 2/3; (2) В следует играть S и T с частотами 2/5 и 3/5; (3) цена игры — 3 доллара.

игр всегда могут быть заданы в виде матрицы
m x

n где игрок А имеет m возможных планов, В имеет п возможных планов и платежная матрица есть матрица (см. табл. 2).
Таблица 2
Математически можно показать, что (1) каждой прямоугольной игре соответствует определенное значение цены g; это значение единственно; (2) существует оптимальная стратегия игрока А, т. е., существуют частоты такие, что
и если игрок А
играет, применяя план I с частотой х1, план II с частотой х2 …., план m c частотой Хm , то он может обеспечить себе средний выигрыш не менее g, где g — цена игры; (3) также и для игрока В существует оптимальная стра­тегия


такая, что, если он применяет планы I, II, . . . , п с частотами y1,y2,…yn он обеспечивает себе проигрыш не больше g

матрица которой имеет седловую точку ( i0 , j0),

имеем следующее решение

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


Соотношение (3) в действительности представляет собой п неравенств, по одному неравенству для каждого j. Соотношение (4) представляет собой n неравенств. Таким образом, имеем m+n+1 неизвестных с m+n+2 соотношениями (с дополнительными ограничениями так как отрицательные частоты не имеют смысла).

гарантируют существование решения, удовлетворяющего этим соотношениям.
Они гарантируют также единственность

g. Однако для игра может иметь несколько или даже бесконечное множество решений.
Пример. Для игры, представленной в таблице 1, неизвестными будут
и g. Соотношения следующие
(5)
(6)
(7)
(8)
(9)
(10)
Такие задачи могут быть решены при помощи «обычной алгебры», графиче­ским способом, применением матричной алгебры или итеративным мето­дом.

нахождения неизвестных из соотношений (1), (2), (3) и (4).
Решение

осно­вано на указанном ранее факте: каждая прямоугольная игра имеет цену, а именно цену g, которая существует и единственна.
Необходимо найти одну такую цену g, которая удовлетворяет нашим соотношениям.
Для этого строим процедуру поиска цены g, опираясь на то, что она единственна.
Пер­вый шаг — предположить, что соотношения (3) и (4) суть равенства.
В этом случае получается следующая система уравнений:

шесть уравнений.
Поэтому решим только пять уравнений и проверим, удовлетворяет

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

Если неизвестные удовлетворяют всем этим условиям, то они составляют полное решение.

равенствам

Следовательно, (13), (14) и (15) переходят в следующие уравнения:




Складывая

уравнения (17) и (18), находим т.е. х1=1/3 так что из уравнений (17), (18) и (11) получаем:

Подставляя эти значения в уравнение (16), получаем откуда


Поскольку имеем полное решение, а именно:

Что называется матричной игрой?
3. Что называется матричной игрой типа

m n × ?
4. Какая игра называется игрой с нулевой суммой?
5. Что называется чистой стратегией?
6. Что называется нижней ценой игры?
7. Что называется верхней ценой игры?
8. Что называется ценой игры?
9. В чем состоит принцип минимакса?
10. Какая игра называется игрой с седловой точкой?
11. Что называется седловой точкой?
12. Что называется смешанной стратегией?
13. Что называется решением игры в смешанных стратегиях?
14. Что называется полезной стратегией?
15. Что утверждает основная теорема теории игр?
16. В чем состоит схема аналитического решения игры типа 2 2 × ?
17. В чем состоит схема графического решения игры типа 2 n × ?
18. В чем состоит схема графического решения игры типа 2 m × ?