Критерии Гурвица, Вальда, Сэвиджа, миниминный, максимаксный.

Вопросы для самоконтроля.

1. Какой принцип выбора оптимальной стратегии лежит в основе обобщенного критерия пессимизма-оптимизма Гурвица относительно выигрышей?
2. Какие показатели в обобщенном критерии Гурвица относительно выигрышей используются для выражения количественной меры пессимизма и оптимизма?
3. В каком случае обобщенный критерий Гурвица относительно выигрышей превращается в критерии: Байеса относительно выигрышей, Лапласса относительно выигрышей, Вальда, максимаксный?
4. Какой критерий выбора оптимальной стратегии использует самую полную информацию об игре?
5. В чем состоит принцип «невозрастающих (неубывающих) средних выигрышей» при выборе коэффициентов обобщенного критерия Гурвица?
6. Какой принцип выбора оптимальной смешанной стратегии лежит в основе обобщенного критерия пессимизма-оптимизма Гурвица относительно выигрышей?
7. В каком случае обобщенный критерий Гурвица относительно рисков превращается в критерии: Байеса относительно рисков, Лапласса относительно рисков, Сэвиджа, миниминный?
8. Перечислите критерии, по которым стратегии, оптимальные среди чистых стратегий, являются оптимальными и среди всех смешанных стратегий.

 

Упражнение 1

Определите оптимальную чистую стратегию и оцените выигрыш игрока А в игре «Планирование посева» (см.упр.2.4.2), используя следующие критерии относительно выигрышей: Вальда, максимаксный, Гурвица в опасной и безопасной ситуациях, обобщенный критерий Гурвица в опасной и безопасной ситуациях.

 

Упражнение2

Оцените выигрыш игрока А и определите оптимальную чистую стратегию в игре «Строительство электростанции», используя следующие критерии относительно выигрышей: Вальда, максимаксный, Гурвица в опасной и безопасной ситуациях, обобщенный критерий Гурвица в опасной и безопасной ситуациях.

 

Упражнение 3

Оцените выигрыш игрока А и определите оптимальную чистую стратегию в игре «Поставка товара», используя следующие критерии относительно выигрышей: Вальда, максимаксный, Гурвица в опасной и безопасной ситуациях, обобщенный критерий Гурвица в опасной и безопасной ситуациях.

 

Упражнение 4

Оцените риск игрока А и определите оптимальную чистую стратегию в игре «Планирование посева», используя следующие критерии относительно рисков: Сэвиджа, миниминный, обобщенный критерий Гурвица в опасной и безопасной ситуациях.

 

Упражнение 5

Оцените риск игрока А и определите оптимальную чистую стратегию в игре «Строительство электростанции», используя следующие критерии относительно рисков: Сэвиджа, миниминный, обобщенный критерий Гурвица в опасной и безопасной ситуациях.

 

Упражнение 6

Оцените риск игрока А и определите оптимальную чистую стратегию в игре «Поставка товара», используя следующие критерии относительно рисков: Сэвиджа, миниминный, обобщенный критерий Гурвица в опасной и безопасной ситуациях.

 

Тема 5. Кооперативные игры

Пример. «Нахождение С-ядра игры трех лиц».

Рассмотрим игру трех лиц с характеристической функцией v (S): v ({l}) = v ({2}) = v ({3}) = 0, v ({l,2}) = 0.5, v ({l,3}) = 0.6, v ({2,3}) = 0.7, v(N) = l. Условие на дележи, принадлежащие С-ядру, задается системой неравенств:

Множество дележей игры трех лиц можно изобразить на симплексе (см. рисунок 9), то есть на треугольнике, задаваемом в неравенствами x_i,>0, i=1,3, и равенством

(изображен на рисунке 9 серым цветом).

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

Рис. 9. С-ядро в игре с тремя игроками

 

Тема 6. Иерархические игры.

Борьба за лидерство.

Определение. Исход игры (9.1) называется индивидуально рациональным, если

для всех . (1)

Лемма. Все NE-исходы индивидуально рациональны.

Доказательство. Для всех i справедливы неравенства

.

Взяв супремум по в этих неравенствах, получаем (1.

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

Пример: игра «перекресток».

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

Остановиться
Ехать
	Остановиться	Ехать

 

Оба NE-исхода {(остановиться, ехать), (ехать, остановиться)} оптимальны по Парето. Тем не менее они не взаимозаменяемы. Для каждого игрока оптимальной стратегией является остановка, если другой игрок решил проехать перекресток, и проезд, если другой остановился. Высказав решимость придерживаться неосторожной стратегии «ехать», игрок выигрывает, поскольку он заставляет другого остановиться и получает максимальный выигрыш, равный 2.

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

Рассмотрим детальнее понятие борьбы за лидерство, используя необходимые дополнительные понятия.

Для игры двух лиц обозначим через график отображения наилучших ответов i-го игрока на любую стратегию j-го игрока:

(симметричное определение для ).

Определение. Пара называется i-равновесием по Штакельбергу в игре , если

и , (2)

где .

Можно интерпретировать 1-равновесие по Штакельбергу на основе следующего сценария: игрок 1 (лидер) знает обе функции выигрыша и и использует эту информацию для предсказания реакции игрока 2. Игрок 2 (ведомый) воспринимает стратегию игрока 1 как заданную извне и максимизирует собственный выигрыш, полагая, что стратегия игрока 1 фиксирована. Таким образом, игрок1, имея первый ход и предвидя, что игрок 2 использует один из своих наилучших ответов на , находит оптимальное решение задачи (2).

Определение. В игре двух лиц назовем i-выигрышем по Штакельбергу выигрыш игрока при любом i-равновесии по Штакельбергу:

, .

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

, . (3)

Лемма. Пусть игра G имеет по крайней мере два оптимальных по Парето NE-исхода , с различными векторами выигрышей:

. (4)

Тогда в G имеет место борьба за лидерство.

Доказательство. Заметим, что . Тогда по определению

, .

Если в G нет борьбы за лидерство, то найдется исход x, для которого справедливо (3), что означает

, ,

, .

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

Справедлива следующая (примем ее без доказательства)

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

Обратное утверждение отнюдь не верно: NE-стратегия может быть доминируемой. Этот неожиданный факт можно проиллюстрировать следующим примером.

Пример.

	L	C	R
T
M
B

 

Это игра двух лиц в нормальной форме, в которой каждый игрок имеет по три стратегии. Здесь – единственный NE-исход. Тем не менее, для игрока 1 (выбирающего строки), стратегия T доминируется стратегией B, а для игрока 2 (выбирающего столбцы) стратегия L доминируется стратегией R.

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

Напомним, что действительная функция f вогнута, если для всех и любых x, y выполнено

.

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

Тогда множество NE(Г) равновесий по Нэшу игры не пусто и компактно.

Теорема Нэша позволяет утверждать, что множество NE(Г) пусто. Чтобы его вычислить, требуется решить следующую систему уравнений :

.

Если – внутренняя точка множества и функция индеференцируема по , то условия (4) эквивалентны условию

для всех .

Пример: олигополия с назначением выпуска.

Пусть имеется n производителей с нулевыми затратами, поставляющих на рынок некоторый товар в количествах . Общее предложение есть , а цена равна , , , , т.е. p – убывающая функция на положительной полуоси.

Эту ситуацию можно представить как следующую

, , .

Из условий на p получается, что функция вогнута по . Поскольку – не компактные множества, положим , где – предложение, порождающее нулевую цену: . Для усеченной игры применима теорема Нэша, позволяющая утверждать существование NE-исхода x в усеченной игре. На самом деле исход x есть равновесие по Нэшу и в исходной игре. Действительно, гарантированный выигрыш каждого игрока в усеченной игре есть 0, поэтому по лемме 9.5

для .

В силу вогнутости и дифференцируемости на множестве NE-исход x удовлетворяет системе (9.13):

.

Таким образом, игра имеет единственный NE-исход на диагонали , где .

Пример: устойчивость в дуополии Курно.

Два игрока поставляют на рынок некоторые количества и одного и того же товара, цена на который определяется следующим образом:

.

Рассмотрим два различных предположения о функции затрат:

а) постоянные затраты на выпуск единицы продукции при увеличении масштабов производства: затраты на производство y единиц оцениваются величиной для обоих игроков;

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

Наконец, максимальные производственные возможности обоих игроков равны 0,5 (поэтому цена и затраты неотрицательны).

В случае а) получаем следующую игру:

, ,

 

Легко вычислить наилучший ответ игрока i на стратегию y_j игрока j, поскольку u_i вогнута по x_i:

Единственный NE-исход таков:

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

где α(y)=0,25-0,5y.

На рис. (5, а) изображены две такие последовательности. Изобразив самостоятельно ещё несколько последовательностей, читатель убедится, что из любой начальной позиции () последовательности () сходятся к NE-исходу (1/6,1/6). Говорят, что (1/6,1/6) является устойчивым NE-исходом.

 

Обратимся теперь к случаю б). получается следующая игра в нормальной форме:

По-прежнему функция u_i вогнута по x_i и кривые наилучших ответов имеют вид

где

Теперь имеются три NE-исхода:

Из рис. 5, б видно, что, начиная с любого исхода последовательность всегда сходится к или за конечное число шагов. Это справедливо даже в том случае, когда точка сколь угодна близка к точке (но не совпадает с ней). Говорят, что это неустойчивый NE-исход, а - локально устойчивые.

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

 

Антагонuстuческuе игры – игры в нормальной форме, в которых сумма выигрышей игроков при любом исходе равна нулю.

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

Верхняя цена игры (минимакс)

Гарантирующее равновесие – это исход игры, при котором каждый игрок выбирает действие , где . Это решение игры называют также максиминным.

Гипотеза рационального поведения – это предположение, что игрок стремится максимизировать свою целевую функцию с учетом всей имеющейся у него информации, т.е. выбирает одну из альтернатив y^*, на которых достигается максимум его целевой функции y^* = arg f (y).

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

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

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

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

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

Игра Г₁ – это иерархическая игра, в которой игрок, выбирающий стратегию вторым (агент) не ожидает информации о действии центра, тогда реализация права первого хода центра может состоять в сообщении центром агенту функции . Такое сообщение может рассматриваться, как обещание выбрать действие при выборе агентом действия x ₂. Тогда стратегия агента состоит в выборе действия в зависимости от сообщения центра, . Если при этом агент доверяет сообщению центра, он должен выбрать действие , реализующее .

Иерархическая игра – игра с фиксированной последовательностью ходов.

Иерархия представлений – с овокупностьпредставлений агентов о параметрах иерархической игры и их представления о представлениях других агентов и т.д.

Классификация игр. Существует несколько оснований классификаций игр.

- по числу участников (два или несколько);

- по ограничению на выигрыш (игры с нулевой суммой или антагонистические и игры с произвольной суммой);

- по информированности сторон (с полной и неполной информированностью);

- по количеству повторений (однократные и динамические (с дискретным временем – повторяющиеся, с непрерывным – дифференциальные);

- по мощности множеств стратегий (дискретные и непрерывные игры);

- по возможности совместных действий (некооперативные и кооперативные игры);

- по последовательности ходов (одновременные и иерархические);

и др.

Критерий Байеса относительно выигрышей (рисков)– максимум ожидаемого выигрыша (минимум ожидаемого риска) в игре с природой при заданных вероятностях ее состояний.

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

Критерий Вальда (критерий крайнего пессимизма) есть частный случай обобщенного критерия Гурвица отно­сительно выигрышей со специальными коэффициентами λ₁=1,λ₂=0…= λ_n=0.

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

Kpumepuu Cэвиджa (кpumepuu кpaйнего neccuмизмa) представляет собой частный случай обобщенного критерия Гурвица относительно рисков с коэффициентами λ₁=1,λ₂=0…= λ_n=0.

Максимаксный критерий (критерий крайнего оптимизма) представляет собой частный случай обобщенного кри­терия Гурвица относительно выигрышей, когда коэффициенты λ₁,λ₂,…, λ_n выби­раются следующим образом: λ₁=…=λ_n-1=0, λ_n=1.

Muниминный кpumepuй (кpumepuu кpaйнего oоптимизма). представляет собой частный случай обобщенного критерия Гурвица относительно рисков, когда коэффициенты выбираются в виде λ₁=…=λ_n-1=0, λ_n=1.

Нижняя цена игры (максимин)

Обобщенный критерий пессимизма-оптимизма Гурвица относительно выиг­рышей с коэффициентами λ₁,λ₂,λ₃,…λ_n.

Переставим выигрыши а_i1,а_i2,...,а_in при каждой стратегии A_i, (т.е. элементы каждой строки матрицы), расположив их в неубывающем порядке, и обо­значим элементы полученной матрицы через b_ij, пусть числа λ₁,λ₂,λ₃,…λ_n, удовлетворяют условиям и . Показателем эффективности стратегии А_i по рассматриваемому критерию назовем число

Обобщенным критерием пессимизма-оптимизма Гурвица относительно вы­игрышей с коэффициентами назовем критерий, по которому опти­мальной среди чистых стратегий считается стратегия . с максимальным пока­зателем эффективности Обстановка игры для i-го игрока есть вектор действий всех игроков, кроме i-гo.

Обобщенный критерий пессимизма – оптимизма Гурвица относительно рисков с коэффициентами это критерий, по которому оптимальной среди чистых стратегий считается стратегия c минимальным показателем неэффективности, т.e.

.

Обстановка игры в смешанных стратегиях для i-гo игрока, есть распределение вероятности (с плотностью ) появления заданной обстановки при использовании игроками смешанных стратегий .

Пассивная стратегия игрока – чистая стратегия, входящая в оптимальную смешанную стратегию с нулевой вероятностью

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

Равновесие в доминантных стратегиях (РДС) есть совокупность доминантных стратегий всех игроков (если таковые существуют).

Равновесие в игре Г₁ отличается от равновесия Штакельберга тем, что при определении оптимальной стратегии первого игрока вычисляется минимум по множеству .

Равновесия Нэша : , то есть для любого игрока и для любого допустимого его действия выбор им равновесного по Нэшу действия дает ему выигрыш не меньший, чем при выборе любого другого действия при условии, что остальные игроки играют равновесные по Нэшу стратегии. Отличие между РДС и равновесием Нэша заключается в том, что в формулировке РДС фигурирует произвольная обстановка, равновесии Нэша – конкретная «нэшевская» обстановка.

Равновесие Штакельберга в игре Г₁ есть такая пара действий , что , , то есть – функция наилучшего ответа агента на действие центра. Рефлексивная игра Г_I - это игра, описываемая следующим кортежем:

Г_I = { N,(X_i) _{i Î N}, f_i (×) _{i Î N}, W, I },

где N – множество реальных агентов, X_i – множество допустимых действий i -го агента, f_i (×):W ´ X’ ®Â¹ – его целевая функция, i Î N, W – множество возможных значений неопределенного параметра, I – структура информированности.

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

В настоящее время в теории игр не существует единой концепции решения, одинаково подходящей для всех классов игр.

Седловая точка матрицы А антагонистической игры – это элемент , что .

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

Смешанная стратегиея i-гo игрока для игры в нормальной форме есть распределение вероятности на множестве действий с плотностью , где .

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

Строго домuнuруемая стратегия игрока i: это cтратегия , если существует стратегия такая, что для произвольной обстановки выполняется неравенство

Cтрого недомuнuруемой стратегией игрока i: это cтратегия , если для произвольной стратегии найдется обстановка такая, что

Структура информированности I_i i -го агента задается набором всевозможных значений вида , где l пробегает множество целых неотрицательных чисел, j ₁, …, j_l Î N, а Î W.

Структура информированности I игры в целом – набор значений , где l пробегает множество целых неотрицательных чисел, j ₁, …, j_l Î N, а Î W. Структура информированности I «недоступна» наблюдению агентов, каждому из которых известна лишь некоторая ее часть (а именно – I_i). Таким образом, структура информированности – бесконечное n -дерево (то есть тип структуры постоянен и является n -деревом), вершинам которого соответствует конкретная информированность реальных и фантомных агентов.

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

Формальная модель конфликта (игры) есть следующий кортеж: {множество игроков, множество стратегий, множество исходов, множество функций выигрыша}

Функция выигрыша или целевая функция или функция предпочтения или функция полезности , описывающая предпочтения субъекта (игрока), отображает множество его допустимых действий (альтернатив) A на числовую ось Â ¹. Значения этой функции позволяют сравнивать разные альтернативы (действия). Если есть два варианта – два элемента из множества допустимых действий, то лучшим будет тот, который приводит к большему значению функции.

Чистая стратегия игрока в игре в нормальной форме есть выбор им одного из элементов множества своих действий.

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

 

 

[1] Публикации, отмеченные здесь и далее значком «*», имеются в свободном доступе в электронной библиотеке сайта www.mtas.ru.

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