Основная теорема антагонистических игр Джона фон Неймана и седловая точка функции выигрыша

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

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

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

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

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

Если, то такая игра называется игрой с седловой точкой, элемент матрицы

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

15.Аналитическое решение игры 2×2 в смешанных стратегиях для игрока A. (из лекции)

16.Аналитическое решение игры 2×2 в смешанных стратегияхдля игрока B.

Первый случай. Решение игры 2х2

Рассмотрим игру () с матрицей без седловой точки. Решением игры являются смешанные стратегии игроков и . Очевидно, что

Использование игроком А своей оптимальной стратегии гарантирует ему получение среднего выигрыша не меньшего, чем цена игры ν. При этом, если игрок В использует свою оптимальную стратегию, то средний выигрыш игрока будет равен ν, если игрок В не использует свою оптимальную стратегию, то средний выигрыш игрока А будет больше ν.

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

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

Чтобы найти оптимальную смешанную стратегию игрока В: и соответствующую цену игры ν, решаем систему уравнений:

(3.14)

Получим:

(3.15)

Цена игры общая для обоих игроков.

(3.13)

17. Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока A.

В точках , оси О х восстановим перпендикуляры и обозначим их и – в соответствии со стратегиями игрока А (рис 3.1).

Рис. 3.1. Графическая интерпретация игры для игрока А

Изобразим стратегию . На прямой отложим , а на прямой отложим . Соединим эти точки и получим прямую . Аналогично изобразим стратегию , отложив на прямой значение , а на прямой - значение .

Каждой точке на отрезке [0; 1] соответствует смешанная стратегия игрока А, причем – расстояние от этой точки до нуля, а – расстояние от этой точки до точки 1 (рис. 3.1).

Ломанная (на рис. 3.1 выделена полужирно) определяет минимальные возможные средние выигрыши игрока А при использовании им своих смешанных стратегий. Точка М (самая высокая точка ломанной) – определяет наилучший средний выигрыш игрока А из всех минимальных. Она соответствует оптимальной смешанной стратегии игрока А. При этом:

если , то

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

с учетом того, что прямую определяют точки и а прямую - точки и .

18.Геометрический метод нахождения цены игры 2×2 и оптимальных стратегий игрока B.

Для игрока В оптимальная смешанная стратегия находится аналогично, но точка М определяется не самой высокой точкой нижней ломанной, а самой низкой точкой высокой ломанной – полужирная ломанная на рис. 3.2.

Рис. 3.2. Графическая интерпретация игры для игрока В

Найдя координаты точки , как точки пересечения прямых и , компоненты оптимальной смешанной стратегии игрока В и цену игры, ν, можно найти по следующим формулам:

19.Геометрический метод нахождения цены игры 2× n и оптимальных стратегий игрока A.

В парной игре у каждого противника есть определенный набор стратегий. Назовем их условно для первого игрока: А1, А2; для второго игрока: В1, В2,…Вn (n количество стратегий игрока B – игра 2 × n).

В результате выбора игроками любой пары стратегий А(i) и B(j) однозначно определяется исход игры – выигрыш a(i,j) игрока А (положительный или отрицательный) и проигрыш –a(i,j) игрока В. Значения a(i,j) известны для любой пары стратегий А(i), B(j). На основе этих данных можно построить платежную матрицу (матрицу игры), элементами которой являются выигрыши. Строки таблицы соответствуют стратегиям игрока A, столбцы – стратегиям игрока В.

При решении данной задачи необходимо определить то, с какими вероятностями игрок А будет выбирать свои стратегии (А1 и А2), при оптимальном решении. Оптимальным для игрока А будет являться такое решение, при котором он получит максимальный выигрыш. Обозначим вероятность выбора первой стратегии для первого игрока p₁ и p₂ соответственно для второй стратегии.

В декартовой системе координат на оси абсцисс отложим единичный отрезок A₁ A_2. Точка A₁(х=0) изображает стратегию A₁, а все промежуточные точки этого отрезка — смешанные стратегии S_A первого игрока, причем расстояние от S_A до правого конца отрезка — это вероятность p₁ стратегии A₁, расстояние до левого конца — вероятность p₂ стратегии A₂. По оси ординат будет откладываться цена игры. На перпендикулярах к отрезку А₁А₂ в точках 0 и 1 отложим выигрыши при стратегиях А₁ и А₂ соответственно. Соединим значения выигрышей игрока А при различных стратегиях игрока В (a_{1j1 –} a_2j1 и т. Д.). Найдем нижнюю огибающую (линию, проходящую через минимальные выигрыши игрока А при каждой смешанной стратегии). Точка N будет являться максимальным гарантированным выигрышем игрока А, а следовательно, смешанная стратегия игрока А в этой точке будет оптимальной. Опустим перпендикуляр из точки N на ось абсцисс, чтобы найти вероятности стратегий А₁ и А₂, а также на ось ординат, чтобы найти значение выигрыша.

20.Геометрический метод нахождения цены игры m ×2 и оптимальных стратегий игрока B.

В парной игре у каждого противника есть определенный набор стратегий. Назовем их условно для первого игрока: А1, А2,…Аm; для второго игрока: В1, В2 (m, n количество стратегий игроков – игра m × 2).

В результате выбора игроками любой пары стратегий А(i) и B(j) однозначно определяется исход игры – выигрыш a(i,j) игрока А (положительный или отрицательный) и проигрыш -a(i,j) игрока В. Значения a(i,j) известны для любой пары стратегий А(i), B(j). На основе этих данных можно построить платежную матрицу (матрицу игры), элементами которой являются выигрыши. Строки таблицы соответствуют стратегиям игрока A, столбцы – стратегиям игрока В.

При решении данной задачи необходимо определить то, с какими вероятностями игрок В будет выбирать свои стратегии (В1 и В2), при оптимальном решении. Оптимальным решением для игрока В,в этом случае, будет являться такое решение, при котором он понесет минимальные потери. Обозначим вероятность выбора первой стратегии для первого игрока q1 и q2 соответственно для второй стратегии.

В декартовой системе координат на оси абсцисс отложим единичный отрезок B₁ B₂. Точка B1(х=0) изображает стратегию B₁, а все промежуточные точки этого отрезка — смешанные стратегии S_B первого игрока, причем расстояние от S_B до правого конца отрезка — это вероятность q1 стратегии B1, расстояние до левого конца — вероятность q2 стратегии B2. По оси ординат будет откладываться цена игры. На перпендикулярах к отрезку B₁B₂ в точках 0 и 1 отложим выигрыши при стратегиях B₁ и B₂ соответственно. Соединим значения выигрышей игрока B при различных стратегиях игрока A (a_i11 – a_i12 и т. д.). Найдем верхнюю огибающую (линию, проходящую через максимальные проигрыши игрока B при выборе каждой смешанной стратегии). Точка M будет являться минимальным гарантированным проигрышем игрока B, а следовательно, смешанная стратегия игрока B в этой точке будет оптимальной. Опустим перпендикуляр из точки M на ось абсцисс, чтобы найти вероятности стратегий B1 и B2, а также на ось ординат, чтобы найти значение выигрыша.

21. Доминирование смешанных стратегий для игрока A.

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

где p_i ≥ 0 - вероятность применения игроком А чистой стратегии A_i, и p₁ +...+ p_i +...+ р_т = 1, как сумма вероятностей несовместных событий (состоящих в выборе одной из чистых стратегий) полной группы, а смешанная стратегия Q характеризуется законом распределения

где q_j ≥ 0 - вероятность выбора игроком В чистой стратегии B_j, q₁ +...+ q_j +...+ q_n = 1.

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

			…
			…
			…
…	…	…	…	…
			…

Между множеством смешанных (в том числе и чистых) стратегий игрока А и выпуклыми комбинациями

строк ( матрицы А, представляющими собой строки выигрышей , j=1,2,…,n, игрока А в ситуациях , j=1,2,…,n, устанавливается взаимно-однозначное соответствие

из которого ясно, что, в частности, каждой чистой стратегии игрока А ставится во взаимно-однозначное соответствие k-я строка матрицы А.

Если для двух выпуклых комбинаций строк матрицы А

и

выполняются неравенства

то говорят, что строка (2) доминирует строку (1), а строка (1) доминирует строкой (2). Если каждое неравенство (3) является равенством, то строки (1) и (2) называют дублирующими. Если же каждое неравенство (3) является строгим, то говорят, что строка (2) строго доминирует строку (1), а строка (1) строго доминируется строкой (2).

Аналогичная терминология используется и для соответствующих стратегий игрока А. А именно, если строка (2) доминирует, соответственно дублирует, соответственно строго доминирует строку (1), то говорят, что стратегия доминирует, соответственно дублирует, соответственно строго доминирует стратегию .

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

22. Доминирование смешанных стратегий для игрока B.

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

где p_i ≥ 0 - вероятность применения игроком А чистой стратегии A_i, и p₁ +...+ p_i +...+ р_т = 1, как сумма вероятностей несовместных событий (состоящих в выборе одной из чистых стратегий) полной группы, а смешанная стратегия Q характеризуется законом распределения

где q_j ≥ 0 - вероятность выбора игроком В чистой стратегии B_j, q₁ +...+ q_j +...+ q_n = 1.

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

			…
			…
			…
…	…	…	…	…
			…

Между смешанными (в том числе и чистыми) стратегиями игрока В и выпуклыми комбинациями

^T,

столбцов ^T , j=1,2,…,n, матрицы А (Т- значок транспонирования), представляющими собой столбцы ^T

проигрышей Н(, i=1,2,…,m, игрока В в ситуациях (, i=1,2,…,m, устанавливается взаимно-однозначное соответствие

^T ,

из которого видно, что, в частности, каждой чистой стратегии , l =1,2,…,n, игрока В ставится во взаимно-однозначное соответствие l -й столбец ^T матрицы А.

Если для двух выпуклых комбинаций столбцов матрицы А

^T

и

^T

выполняются неравенства

то говорят, что столбец (4) (стратегия доминирует столбец (5) (стратегию , а столбец (5) (стратегия ) доминируется столбцом (4) (стратегией ). Если каждое неравенство (6) является равенством, то столбцы (4) и (5) (стратегии и ) называют дублирующими друг друга. Если же каждое неравенство (6) является строгим, то говорят, что столбец (4) (стратегия ) строго доминирует столбец (5) (стратегию ), а столбец (5) (стратегия ) строго доминируется столбцом (4) (стратегией ).

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

23. Решение матричной игры m×n сведением к задаче линейного программирования для игрока A.

			…
			…
			…
…	…	…	…	…
			…

Пусть дана матричная игра с матрицей А порядка m х n.

P^o=(p1^o,p2^o,…,pm^o)

,

Если игрок А применяет любую смешанную стратегию P=(p1,p2,…,pm) против любой чистой стратегии B_j игрока В, то он получает выигрыш

F(P,B_j)=a₁jp₁+a₂jp₂+…+a_njp_m, j=1,2,…,n

.

Разделим каждое неравенство на V>0 и введем

x1=p1/v, x2=p2/v,…,xm=pm/v

Разделив на V>0 равенство , получим выражение x1+x2+…+xm=1/v

Получаем задачу линейного программирования для игрока А:

x1+x2+…+xm->min(поскольку первый игрок стремится найти такие значения хi и, следовательно, pi, чтобы цена игры v была максимальной)

P^o=(p1^o=x₁^o*V, p₂^o=x₂^o*V,…,p_m^o=x_m^o*V)

24. Решение матричной игры m×n сведением к задаче линейного программирования для игрока B.

Пусть дана матричная игра с матрицей А порядка m х n.

			…
			…
			…
…	…	…	…	…
			…

Q^o=(q1^o,q2^o,…,qn^o)

Если игрок В применяет любую смешанную стратегию Q=(q1,q2,…,qm) против любой чистой стратегии A_i игрока A, то он получает проигрыш

F(P,B_j)=a₁jq₁+a₂jq₂+…+a_njq_m, j=1,2,…,n

.

Разделим каждое неравенство на V>0 и введем

y1=q1/v, y2=q2/v,…,ym=qm/v

Разделив на V>0 равенство , получим выражение y1+y2+…+ym=1/v

Получаем задачу линейного программирования для игрока В:

y1+y2+…+ym->max (поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры v была наименьшей)

Q^o=(q1^o=y₁^o*V, q₂^o=y₂^o*V,…,q_m^o=y_m^o*V)

25. Основные понятия и определения теории игр с природой.

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

В любой момент времени природа П может находиться только в одном (но неизвестно, в каком) из n состояний П 1, П 2, …, П_n, то есть состояния природы разделены между собой во времени. Совокупность состояний природы П формируется либо на основе имеющегося опыта анализа состояний природы, либо в результате предположений и интуиции экспертов.

Для описания игры с природой необходимо также множество стратегий игрока A: .

Результаты реализации стратегий при различных состояниях природы могут быть описаны матрицей V:

.

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

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

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

Поиск по сайту: