Шпаргалка по "Экономике"

 

                                     

Зная  числа  (свои выигрыши при применении всех стратегий и разумных ответах игрока II), первый игрок должен выбрать такую стратегию, для которой   максимально. Обозначив это максимальное значение как , (т.е.  ) и используя (1), получим:                                           

 

Таблица 13.2

III	1	2	. . .
1			. . .
2			. . .
. . .	. . .	. . .	. . .	. . .	. . .
			. . .
			. . .

 

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

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

Стратегия игрока II, обеспечивающая «выигрыш»  , является его минимаксной стратегией. Выбор минимаксной стратегии игроком II гарантирует ему проигрыш не больше .

В теории игр доказывается, что для  нижней и верхней цены игры всегда справедливо неравенство:  

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

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

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

Таблица 13.3.

					(минимумы строк)
	8	-2	9	-3	-3
	6	5	6	8	5
	-2	4	-9	5	-9
(максимумы столбцов)	8	5	9	8

 

Если компания A выбирает стратегию  , то, независимо от реакции компании B, наихудшим для нее результатом является потеря  3% рынка в пользу конкурента. Аналогично при выборе стратегии наихудшим исходом для компании A является увеличение рынка на 5% за счет компании B. Наконец, наихудшим исходом при выборе стратегии является потеря компанией A 9 % в пользу компании B. Чтобы достичь наилучшего результата из наихудших, компания A должна выбрать стратегию .

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

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

Решение, соответствующее седловой точке, гарантирует, что ни одной компании нет смысла пытаться выбрать другую стратегию. Действительно, если компания B перейдет к любой другой стратегии ( ), то компания A может сохранить свой выбор стратегии , что приведет к большей потери рынка компанией B (6 или 8 процентов). По тем же причинам компании A нет смысла использовать другую стратегию – если она использует, например, стратегию , то компания B может использовать свою стратегию и увеличить свой рынок на 9 %.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

11. Решение игр без седловых точек. Понятие о смешанных стратегиях и алгоритм определения средних выигрышей игроков.

 

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

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

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

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

Средний выигрыш  первого игрока равен математическому ожиданию

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

   

где вектор-строка задает вероятности применения различных чистых стратегий первым игроком, - платежная матрица и задает вероятности применения чистых стратегий вторым игроком:

По  формуле (13.6) легко найти выигрыши игроков в случае, когда один из них применяет чистую стратегию, а второй – смешанную.

Так, средний  выигрыш первого игрока при условии, что он применяет чистую стратегию , а игрок B – смешанную стратегию, получается заменой в формулах (13.6) или (13.7) вектор- строки   на :

Аналогично, средний выигрыш первого игрока при условии, что он применяет смешанную стратегию, а игрок В – некоторую чистую стратегию равен:

Приведем  алгоритм нахождения оптимальных смешанных  стратегий.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12. Определение оптимальных смешанных стратегий в играх без седловых точек.

 

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

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

Будем искать решение  игры в смешанных стратегиях:

;   .

Применение  игроком I оптимальной смешанной  стратегии  гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры  .

Пусть игрок II применяет свою активную чистую j-ю  стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен

 

Учитывая, что  не может быть меньше , запишем условия:

                    

Разделив левую  и правую части каждого из неравенств (10.3) на цену игры , получим:

                

При использовании обозначений    

                       

неравенства (10.5) примут вид:

 

 

 

где, очевидно, все  , так как .

Условие нормировки с учетом определения (13.13) дает следующее соотношение

Учитывая, что игрок I стремится максимизировать  , получаем линейную функцию

                            

 

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

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

 

     

Аналогично  можно показать, что оптимальная  стратегия второго игрока  определяется по формулам

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

 

,

а переменные

 

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

 

Исходная  задача	Двойственная  задача

Цена  игры и вероятности применения стратегий  игроками I  и II равны: