- •4. Максиминный и минимаксный принципы игроков. Показатели эффективности и неэффективности чистых стратегий.
- •5. Максимин и минимакс игры. Максиминные и минимаксные стратегии. Нижняя и верхняя цена игры в чистых стратегиях. Соотношение между ними.
- •Критерий решения игры в чистых стратегиях.
- •Доказательство утверждения .
- •Теорема об удовлетворительности игровой ситуации для игрока a.
- •Теорема об удовлетворительности игровой ситуации для игрока b
- •Равновесие в антагонистической игре.
- •Смешанные стратегии. Функция выигрыша и цена игры в смешанных стратегиях.
- •Теорема о существовании показателей эффективности и неэффективности смешанных стратегий в антагонистической игре.
- •Теорема о существовании нижней и верхней цен игры в смешанных стратегиях.
- •Теорема о соотношении нижней и верхней цен игры в чистых и смешанных стратегиях.
- •Основная теорема матричных игр Джона фон Неймана и седловая точка функции
- •Аналитическое решение игры 2×2 в смешанных стратегиях.
- •Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока a.
- •Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока b.
- •Геометрический метод нахождения цены игры 2×n и оптимальных стратегий игрока a.
- •Геометрический метод нахождения цены игры m×2 и оптимальных стратегий игрока b.
- •2)В общем случае схема решения игры 2xn или nx2 графическим методом состоит в следующем.
- •Доминирование смешанных стратегий для игрока a.
- •Доминирование смешанных стратегий для игрока b.
- •Решение матричной игры m×n сведением к задаче линейного программирования для игрока a.
- •Решение матричной игры m×n сведением к задаче линейного программирования для игрока b.
- •Основные понятия и определения теории игр с природой.
- •Игры с природой. Показатель благоприятности состояния природы. Риск игрока, принимающего решение. Матрица рисков. Принятие решений в условиях риска и неопределённости.
- •Критерий Байеса оптимальности чистых стратегий относительно выигрышей.
- •Критерий Байеса оптимальности чистых стратегий относительно рисков.
- •Критерий Лапласа оптимальности чистых стратегий относительно выигрышей.
- •Критерий Лапласа оптимальности чистых стратегий относительно рисков.
- •Критерий (крайнего пессимизма) Вальда оптимальности чистых стратегий.
- •Максимаксный критерий (крайнего оптимизма) оптимальности чистых стратегий.
- •Критерий пессимизма – оптимизма Гурвица оптимальности чистых стратегий относительно выигрышей.
- •Определение показателей оптимизма и пессимизма игрока, принимающего решения по критерию Гурвица относительно выигрышей.
- •Учёт выигрышей по критерию Гурвица крайним пессимистом, крайним оптимистом и нейтралом.
- •Критерий Севиджа
- •Миниминный критерий.
- •Критерий пессимизма – оптимизма Гурвица оптимальности чистых стратегий относительно рисков.
- •Критерий Гермейера оптимальности чистых стратегий
- •Критерий Ходжа – Лемана оптимальности чистых стратегий относительно выигрышей.
- •Основные понятия и определения в теории неантагонистических (бескоалиционных) игр. Способы задания неантагонистической игры.
- •Стратегическая форма игры. Чистые и смешанные стратегии игроков в неантагонистических (бескоалиционных) играх. Доминирование стратегий.
- •Равновесие по Нэшу в чистых стратегиях.
- •Семейная пара принимает решение о месте куда они могут пойти в свободное время. Так он предлагает футбол, а она балет
- •Равновесие по Нэшу в смешанных стратегиях.
- •46. Аналитическое решение биматричных игр 2×2.
- •Аналогичный анализ можно провести для второго игрока.
- •47. Геометрическое решение биматричных игр 2×2
- •48. Модель дуополии по Курно.
- •49. Модель дуополии по Бертрану.
- •50. Модель «Проблема общего».
- •51. Оптимальность по Парето в неантагонистических (бескоалиционных) играх.
- •52. Позиционная форма игры.
- •53. Понятие о конечных играх с совершенной информацией.
- •54. Стратегическая форма позиционной игры с совершенной информацией.
- •55. Равновесие по Нэшу в позиционной игре с совершенной информацией.
- •56. Обратная индукция и позиционные игры с совершенной информацией.
- •57. Модель дуополии по Штакельбергу.
- •58. Модель последовательного торга.
- •59. Модель «инвесторы и банк».
Теорема о существовании показателей эффективности и неэффективности смешанных стратегий в антагонистической игре.
12. Теорема о существовании показателей эффективности и неэффективности смешанных стратегий в антагонистической игре.
Для каждой смешанной стратегии игрока существует ;(4.1)
Для каждой смешанной стратегии игрока существует . (4.2)
Доказательство:
Для проведения доказательства введём понятие симплекса
Стандартным n-симплексом называется подмножество пространства действительных чисел, определяемое как
.
Его вершинами являются точки:
,
,
…
.
Сначала покажем, что симплекс является ограниченным замкнутым множеством, т.е. компактом.
Рассмотрим симплекс
в евклидовом пространстве . Так как норма векторав пространствеопределяется следующим образом:
,то для любой точки симплексасправедливо неравенство
,означающее ограниченность симплекса .
Пусть последовательность точек
, ,
сходится к точке при. Так как сходимость вявляется покоординатной, тоозначает, что,. Поскольку, то и.
Так как для каждогоk, то
.
Таким образом, предельная точка принадлежит симплексу, что доказывает его замкнутость.
Аналогично и симплекс – компакт в пространстве.
Если зафиксировать произвольную смешанную стратегию , то функция выигрышабудет функцией одного векторного аргумента, определённой на симплексе. Из аналитического выражения
,
видно, что она непрерывна по аргументу Q на множестве , которое, как мы только что установили, является компактом, а непрерывная на компакте функция достигает своей нижней и верхней граней. Поэтому для любогосуществует (4.1), т.е. для любогонайдётся хотя бы одна точкатакая, что
.
Аналогично доказывается и существование (4.2).
Теорема доказана.
Теорема о существовании нижней и верхней цен игры в смешанных стратегиях.
Нижней ценой (или максимином) матричной игры в смешанных стратегиях называется величина
Верхней ценой (или минимаксом) матричной игры в смешанных стратегиях называется величина
Докажем существование нижней и верхней цен в смешанных стратегиях, т.е. достижимость максимума в (1) и минимума в (2). Необходимость этого доказательства возникает по причине бесконечности множеств SA в (1) и SB в (2).
Сначала докажем вспомогательные предложения.
Лемма 1. Соответствие, сопоставляющее каждой смешанной стратегии Р SA игрока А показатель ее эффективности α(Р), является числовой функцией, определенной на симплексе SA, аналитическое выражение которой задается равенством
Аналогично, соответствие β(Q), задаваемое формулой
является числовой функцией, определенной на симплексе SB и ставящей в соответствие каждой смешанной стратегии Q SB игрока В показатель ее неэффективности β(Q).
Доказательство. Для каждой смешанной стратегии PSA в силу теоремы 1 - для каждой смешанной (в частности, чистой) стратегии Р SA игрока А существует (достигается)
для каждой смешанной (в частности, чистой) стратегии QSB игрока В существует (достигается)
существует число которое по определению минимума является единственным. Следовательно,α(Р) - числовая функция векторного аргумента Р, определенная на симплексе SA.
Аналогичной аргументацией обосновывается, что
является числовой функцией векторного аргумента Q, определенного на симплексе SB.
Лемма 2. Функции α(Р) и β(Q) непрерывны в своих областях определения SA и SB.
Оставим без доказательства. Теперь докажем следующую теорему.
Теорема 2. Для любой конечной матричной игры существуют нижняя и верхняя цены игры в смешанных стратегиях. Доказательство. Так как функция α(Р) по лемме 2 непрерывна на компакте SA, то она достигает на этом множестве своего максимума, т.е. существует нижняя цена игры в смешанных стратегиях:
Аналогичным образом обосновывается существование и верхней цены игры в смешанных стратегиях:
Смешанная стратегия PОSA, максимизирующая показатель эффективности α(Р) (существование которой доказано в теореме 2), назовем максиминной смешанной стратегией игрока А. Таким образом, нижняя цена игрыесть (см. 1) показатель эффективности максиминной смешанной стратегииPО:
В частном случае PО =Аi0 является максиминной чистой стратегией игрока A.
Аналогично, смешанная стратегия QО SB (существование которой доказано в теореме 2), минимизирующая показатель неэффективности β(Q), назовем минимаксной смешанной стратегией игрока В. Показатель неэффективности минимаксной смешанной стратегии QО равен верхней цене игры (см. 2)):
Если QО =Bj0, то Bj0является минимаксной чистой стратегией.