Теория игр

Справедливы следующие утверждения:

1. H'(P', Q') = лH(P,Q) +µ, i= 1, 2, …., m; j = 1, 2, …, n

2. a'(P') = лa(P) + µ, P Ђ Sa

3. в'(Q') = лв(Q) + µ, Q Ђ Sb

4. Образы и прообразы оптимальных стратегий являются оптимальными V' = лV + µ



34. Аналитическое решение игры 2х2 с седловой точкой. Критерий седловой точки матрицы игры 22, основанный на принципе доминирования

Теорема. Пусть i,k € {1,2}, i?k - номера строк, j,l € {1,2}, j?l - номера столбцов матрицы А размера 2 х 2. Для того, чтобы элемент a_ij был седловой точкой матрицы А, необходимо и достаточно выполнение хотя бы одного из следующих условий:

1) Можно удалить k-ю строку как доминируемую i-й строкой, а затем в оставшейся i-й строке можно удалить l-й столбец как доминируемый j-м столбцом;

2) Можно удалить l-й столбец как доминируемый j-м столбцом, а затем в оставшемся j-м столбце удалить k-ю строку как доминируемую i-й строкой.

Доказательство: Необходимость: Пусть a_ij - седловая точка. Тогда элемент a_ij - наименьший в i-й строке и наибольший j-м столбце: a_ij ? a_il (1), a_ij ? a_kj. (2). При сравнении элементов a_il и a_kl. возможны случаи: a_il ? a_kl (3) или a_il ? a_kl (4)

Достаточность: Пусть выполняется условие 1 теоремы. Тогда i-я строка доминирует k-ю строку, откуда следует, что верно (2). Так как в i-й строке l-й столбец доминируется j-м столбцом, то имеет место (1). Неравенства (1) и (2) означают, что a_ij - седловая точка игры. Пусть выполняется условие 2 теоремы. Из того, что l-й столбец доминируется j-м столбцом, следует (1), а из того, что в j-м столбце i-я строка доминирует k-ю строку, вытекает неравенство (2). Поэтому a_ij - седловая точка игры.



35. Критерий существования седловой точки в игре 22 в терминах пассивных стратегий

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

Док-во: 1) Необходимость. Пусть , - номера чистых стратегий игрока А, а , номера чистых стратегий игрока В. Пусть - седловая точка. Тогда - оптимальная стратегия игрока А. Так как чистую оптимальную стратегию можно рассматривать как смешанную оптимальную стратегию, в которую чистая стратегия входит с вероятностью 1, а чистая стратегия - с нулевой вероятностью, то стратегия является пассивной, и необходимость доказана.

2) Достаточность. Пусть стратегия игрока А является пассивной. Тогда найдется оптимальная смешанная стратегия , в которую чистая стратегия входит с нулевой вероятностью и, следовательно, чистая стратегия входит с вероятностью, равной 1. Это означает, что , т.е. - оптимальная стратегия. Пусть - некоторая оптимальная стратегия игрока В, в которую чистые стратегии и входят соответственно с вероятностями и . Так как , то хотя бы одно из чисел и положительно. Если , то чистая стратегия является активной и тогда, по теореме об активных стратегиях . В то же время стратегия является оптимальной, тк в случае , имеет место , а - оптимальная стратегия. С учетом этого и из равенства следует, что - седловая точка. Если , то чистая стратегия является активной оптимальной стратегией и тогда из равенства , которое имеет место в силу теоремы об активных стратегиях, следует, что - седловая точка.



36. Признак существования седловой точки в игре 22 в терминах сумм элементов главной и побочной диагоналей матрицы игры

Теорема. Для того чтобы у матрицы А размером 2x2 существовала седловая точка, достаточно, чтобы сумма элементов главной диагонали матрицы А равнялась сумме элементов ее побочной диагонали: a11 + a22 = a12 + a21 (1)

Следствие: Для того чтобы у матрицы А размером 2Ч2 не существовало седловой точки, необходимо, чтобы сумма элементов главной диагонали матрицы А не равнялась сумме элементов ее побочной диагонали: а11+а22?а12+а21 (2)

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

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

Рассмотрим игру с матрицей наименьшего размера 2х2

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

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



а11+а22 ?а12+а21

Теорема: Пусть матрица А размером 2х2 не имеет седловой точки. Тогда каждый из игроков А и В обладает единственной оптимальной смешанной стратегией соответственно P^o = (p₁^O, p₂^O) и Q^o = (q₁^O_, q₂^O), где

P₁^O= ,

P₂^O= 1- P₁^O = ,

q₁^O = ,

q₂^O= 1- q₁^O =

А цена игры (в смешанных стратегиях) V определяется формулой

V =

Следствие: Если матрица игры А размером 2х2 симметрическая, т.е. a12=a21, и не имеет седловой точки, то чистые стратегии A1,B1 и A2,B2 входят в соответствующие оптимальные смешанные стратегии P^o = (p₁^O, p₂^O) и Q^o = (q₁^O, q₂^O) соответственно с равными вероятностями p₁^O = q₁^O, p₂^O= q₂^O.

Следствие: если матрица игры А размером 2х2 двоякосимметрическая, т.е. a12=a21 и a11=a22, и не имеет седловой точки, то каждая из чистых стратегий A1,A2,B1,B2 входит в соответствующую оптимальную стратегию P^o = (p₁^O, p₂^O) или Q^o = (q₁^O_, q₂^O) с вероятностью, равной Ѕ: p₁^O = q₁^O = p₂^O= q₂^O=1/2, и цена игры V = Ѕ (а11+а12)= Ѕ (а22+а21)



38. Геометрический метод нахождения цены игры 22 и оптимальных стратегий игрока А

1. Берем горизонтальный отрезок [0;1] на котором для определенности положено

2. В концах отрезка [0;1] проводим к нему два перпендикуляра: левый, соответствующий стратегии , и правый, соответствующий стратегии

3. На левом перпендикуляре от точки 0 его пересечения с отрезком [0;1] откладываем (как на вертикальной оси) элементы первой строки матрицы А

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0;1] откладываем (как на вертикальной оси) элементы и второй строки матрицы А

5. Соединяем точки, изображающие элементы с одинаковыми вторыми индексами, т.е. элементы, стоящие в одном и том же столбце матрицы А. В результате получаем отрезки и

6. Находим нижнюю огибающую отрезков и

7. Находим наивысшие точки нижней огибающей

8. Проектируем их ортогонально на горизонтальный отрезок [0;1]

9. Полученные проекции определяют оптимальные стратегии игрока А

10. Ордината наивысшей точки огибающей равна цене игры V

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

12. Нижний из двух верхних концов отрезков и есть верхняя цена игры в чистых стратегиях

39. Геометрический метод нахождения цены игры 22 и оптимальных стратегий игрока В

1. Берем горизонтальный отрезок [0,1].

2. В концах отрезка [0,1] проводим к нему 2 перпендикуляра: левый и правый

3. На левом перпендикуляре вертикальной числовой оси от точки 0 его пересечения с отрезком [0,1] откладываем все элементы матрицы А, за исключением а22

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все эл-ты матрицы А, за исключением а11

5. Каждый элемент на левом перпендикуляре соединим отрезком с каждым элементом на правом перпендикуляре, отличающимся от него только одним индексом. В результате получим отрезки a11a21, a12a22, a11a12 и a21a22

6. Находим нижнюю огибающую отрезов a11a21 и a12a22.

7. Находим аивысшую точку N нижней огибающей.

8. Находим абсциссу р0 наивысшей точки нижней огибающей.

9. Смешанная стратегия Р0=(1-р0, р0) является оптимальной стратегией игрока А.

10. Находим верхнюю огибающую отрезков a11a12 и a21a22.

11. Находим наинизшую точку М верхней огибающей.

12. Находим абсциссу q0 наинизшей точки верхней огибающей.

13. Смешанная стратегия Q0=(1-q0,q0) является оптимальной стратегией игрока В.

14. Ордината наивысшей точки нижней огибающей равна ординате наинизшей точки верхней огибающей и представляет собой цену игры V.

15. Т.о. найдено геометрическими средствами решение игры {P0,Q0,V}

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

17. Нижний из концов верхней огибающей (лежащий на перпендикулярах) есть верхняя цена игры в чистых стратегиях в



40. Геометрический метод решения игры 22 по алгоритму «А, В»

1. Берем горизонтальный отрезок [0, 1].

2. В концах отрезка [0, 1] проводим к нему два перпендикуляра левый и правый.

3. На левом перпендикуляре от точки 0 его пересечения с отрезком [0, 1] откладываем все элементы на матрицы A, за исключением элемента а22.

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0, 1] откладываем все элементы матрицы A, за исключением элемента a11.

5. Каждый элемент на левом перпендикуляре соединим отрезком с каждым элементом на правом перпендикуляре, отличающимся от него только одним индексом. В результате получим отрезки а11а21, а12а22, a11a12, a21а22

6. Находим нижнюю огибающую отрезков и a11a21 и а12а22.

7. Находим наивысшую точку N нижней огибающей.

8. Находим абсциссу наивысшей точки N нижней огибающей

9. Смешанная стратегия = (1-ро, ро) является оптимальной стратегией игрока А.

10. Находим верхнюю огибающую отрезков a11а12 и а21а22

11. Находим наинизшую точку M верхней огибающей.

12. Находим абсциссу нaинизшей точки М верхней огибающей.

13. Смешанная стратегия (1-qo, qo) является оптимальной стратегией игрока В.

14. Ордината наивысшей точки N нижней огибающей равна ординате наинизшей точки М верхней огибающей и представляет собой цену игры

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

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

1. Берем горизонтальный отрезок [0, 1]

2. Через концы отрезка [0,1] проводим к нему два перпендикуляра: левый и правый

3. На левом перпендикуляре от точки 0 его пересечения с отрезком [0,1] откладываем все элементы первой строки матрицы А.

4. На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем все элементы второй строки матрицы А.

!Масштабы на левом и правом перпендикулярах должны быть одинаковы, не обязательно совпадающие с масштабом горизонтального отрезка [0,1]

5. Каждую пару точек, изображающих элементы а_1j и a_2j, j=1,2,…,n, стоящие в j-том столбце матрицы А, соединяем отрезком a_1ja_2j. Таким образом, будут построены n отрезков, представляющих собой графики n линейных функций



H(P,B_j)=(a_2j-a_1j)p+a_1j,

6. Если все отрезки a_1ja_2j неубывающие(имеют неотрицательный наклон ), то стратегия А₂ доминирует стратегию А₁

Если все отрезки a_1ja_2j возрастающие (имеют положительный наклон (a_2j-a_1j>0)), то стратегия А₂ строго доминирует стратегию А₁.

7. Если все отрезки a_1ja_2j невозрастающие (имеют неположительный наклон ), то стратегия А₁ доминирует стратегию А_2.

Если все отрезки a_1ja_2j убывающие (имеют отрицательный наклон (a_2j-a_1j<0)), то стратегия А₁ строго доминирует стратегию А₂.

8. Если отрезок лежит ниже отрезка , то стратегия доминирует стратегию .Если отрезок лежит выше отрезка , то стратегия строго доминирует стратегию .

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

10. На нижней огибающей находим наивысшую точку

11. Абсцисса p^O этой точки является вероятностью выбора игроком А чистой стратегии А2 в оптимальной смешанной стратегии P^O=(1-p^O;p^O)

12. Ордината наивысшей точки нижней огибающей является ценой игры V

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

14. Нижний из верхних концов отрезков a_1ja_2j, есть верхняя цена игры в чистых стратегиях в.

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



42. Теорема об аналитическом методе нахождения цены игры 2 и оптимальных стратегий игрока А

Теорема. Если через max т-ку N нижней огибающей отрезков a_1ja_2j, j=1,…,n, порождаемых чистыми стратегиями В_j, j=1,…,n, игрока В, проходят два каких-либо отрезка a_1j1a_2j1 и a_1j2a_2j2, j₁j₂, j_1,j₂{1,…,n}, то абсцисса точки N и, следовательно, =1-p⁰ = , а цена игры V=.

Доказательство. Уравнения отрезков a_1j1a_2j1 и a_1j2a_2j2 имеют следующий вид: Н(Р,В_j1)=(а_2j1-а_1j1)р+а_1j1; Н(Р,В_j2)=(а_2j2-a_1j2)р+а_1j2, р[0,1]. Тк эти отрезки пересекаются в т-ке N, то абсцисса p⁰ этой точки является решением уравнения (а_2j1-a_1j1)p⁰+a_1j1 = (a_2j2-a_1j2)p⁰+a_1j2, отсюда получаем формулу для . Поскольку цены игры V представляет собой ординату точки N, то для вычисляется V достаточно в правую часть одного из равенств Н(Р,В_j1) или Н(Р,В_j2) подставить р абсциссу р⁰, выраженную в первой формуле для . Подставляя р=р⁰ в правую часть равенства, получим формулу для V.

43. Теорема об аналитическом методе нахождения цены игры 2 и оптимальных стратегий игрока В

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

Для того, чтобы смешанная стратегия игрока где



была оптимальной, необходимо и достаточно, чтобы отрезки имели разные наклоны.

44. Геометрический метод нахождения цены игры m2 и оптимальных стратегий игрока В

1) Берём горизонтальный отрезок [0,1].

2) Через концы отрезка [0,1] проводим к нему два перпендикуляра: левый и правый.

3) На левом перпендикуляре, лежащем на вертикальной числовой оси, от точки 0 его пересечения с отрезком [0,1] откладываем все элементы первой строки матрицы А.

4) На правом перпендикуляре от точки 1 его пересечения с отрезком [0,1] откладываем (как на вертикальной числовой оси) все элементы второй строки матрицы А.

5) Каждую пару точек, изображающих точки а_i1и а_i2,, стоящие в i-q строке матрицы А, соединяем отрезком а_i1 а_i2. Таким образом, будут построены m отрезков, представляющих собой графики m линейных функций Н(A_i,Q)=(а_i2 - а_i1)q+ а_i1, q€[0,1], i=1,…,m

6) Если все отрезки а_i1 а_i2, i=1,…,m - неубывающие(имеют неотрицательный наклон): а_1j а_2j, ? j=1,…,n, то стратегия B₁ доминирует стратегию B₂. Если все отрезки а_i1 а_i2, i=1,…,m - возрастающие (имеют положительный наклон): а_i1 а_i2, i=1,…,m, то стратегия B₁ строго доминирует стратегию B₂.

7) Если все отрезки а_i1 а_i2, i=1,…,m - невозрастающие(имеют неположительный наклон): а_1j а_2j, ? j=1,…,n, то стратегия B₂ доминирует стратегию B₁. Если все отрезки а_i1 а_i2, i=1,…,m - убывающие (имеют отрицательный наклон): а_i1 а_{i2 v}, i=1,…,m, то стратегия B₂ строго доминирует стратегию B₁.

8) Если отрезок а_i11 а_i12 лежит не ниже отрезка а_i21 а_i22, i₁?i₂, i₁,i₂€{1,…,m}, то стратегия A_i1 доминирует стратегию A_i2. Если отрезок а_i11 а_i12 лежит выше отрезка а_i21 а_i22, i₁?i₂, i₁,i₂€{1,…,m}, то стратегия A_i1 строго доминирует стратегию A_i2.

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

10) На верхней огибающей находим минимальную (наинизшую) точку (или точки).

11) Абсцисса q⁰ этой точки является вероятностью выбора игроком B чистой стратегии B2 в оптимальной смешанной стратегии Q⁰=(1-q⁰,q⁰).

12) Ордината минимальной точки верхней огибающей является ценой игры V.

13) Верхний из нижних концов отрезков а_i1 а_i2, i=1,…,m является нижней ценой игры в чистых стратегиях .

14) Нижний из концов верхней огибающей (лежащих на перпендикулярах) есть верхняя цена игры в чистых стратегиях .

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

45. Теорема об аналитическом методе нахождения цены игры m2 и оптимальных стратегий игрока В

Оптимальную стратегию Q⁰=(1-q⁰,q⁰) игрока В и цену игры V можно подсчитать и по формулам, которые даются в следующей теореме:

Если через минимальную точу М верхней огибающей отрезков a_i1a_i2, i=1,…,m, порождаемых чистыми стратегиями А_i, i=1,…,m, игрока А, проходят два каких-либо отрезка ai₁1ai₁2 и ai₂1ai₂2, i₁?i₂, i₁,i₂ принадлежит {1,…,m}, то абсцисса точки М.

(1)

и следовательно,

(2)

а цена игры



(3)

Доказательство: уравнения отрезков ai₁1ai₁2 и ai₂1ai₂2 имеют следующий вид

H(P,A_i1)=( - )q+, q принадлежит [0,1] (4)

H(P,A_i2)=( - )q+, q принадлежит [0,1] (5)

Так как эти отрезки пересекаются в точке М, то абсцисса p⁰ это точки является решением уравнения

(-

откуда получаем формулу (1)

Поскольку цена игра V представляет собой ординату M, то для вычисления V достаточно в правую часть одного из равенств (4) и (5) подставить вместо q абсциссу q⁰, выраженную формулой (1). Подставляя p=p⁰ в правую часть равенства (4), получим

Формула (3) доказана!

46. Принцип решения игры m n методом Шепли-Сноу. Теорема Шепли-Сноу о крайних оптимальных стратегиях

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

Пусть Р⁰= () и Q⁰=( - крайние оптимальные стратегии соответственно игроков А и В в игре с платёжной матрицей А_m*n и ценой игры V. Тогда найдутся натуральное число r, 1, номера строк i₁…,i_r и номера столбцов j₁…,j_r матрицы А такие, что крайняя оптимальная стратегия Р⁰=() удовлетворяет системе уравнений

А крайняя оптимальная стратегия Q⁰=( удовлетворяет системе уравнений

При этом если V, то матрица первой системы и транспонированная матрицы второй системы невырождены, т.е. их определители отличны от нуля

Доказательство

), предположим: )=, l=1,…,r , j откуда следует

Аналогично с следует

Тогда выполняется равенства и

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

Решение матричной игры mxn с матрицей А эквивалентно решению следующей пары двойственных друг другу стандартных задач линейного программирования: найти min _I при ограничениях x_i0, i=1,…,m, _Ijx_i?1, j=1,…,n; найти max _j при ограничениях y_j?0, j=1,…,n, _ijy_j?1, i=1,…,m. Точнее говоря, если x⁰=(x₁⁰,…,x_m⁰)-оптимальное решение задачи на нахождение min, а y⁰=(y₁⁰,…,y_m⁰)-оптимальное решение задачи на нахождение max, то V=(_I⁰)^-1=(_j⁰)^-1 - цена игры с матрицей А, Р⁰=Vx⁰=(p₁⁰=Vx₁⁰,…,p_m⁰=Vx_m⁰) - оптимальная стратегия игрока А, Q⁰=Vy⁰=(q₁⁰=Vy₁⁰,…,q_m⁰=Vy_n⁰) - оптимальная стратегия игрока В. Обратно, если Р⁰=(р₁⁰,…,р_m⁰) и Q⁰=(q₁⁰,…,q_n⁰) - оптимальные стратегии соответственно игроков А и В, а V - цена игры, то x⁰=P⁰=(x₁⁰=p₁⁰/V,…,x_m⁰=p_m⁰/V) - оптимальное решение задачи на min, а y⁰=⁰=(y₁⁰=q₁⁰/V,…,y_m⁰=q_m⁰/V) - оптимальное решение задачи на max.



48. Определение и теорема о симметричной матричной игре

Матричная игра называется симметричной, если её платёжная матрица кососимметрическая, т.е. изначальная платежная матрица А равна своей транспонированной матрице с противоположным знаком А=-А^Т

Теорема.

Для симметричной матричной игры справедливы следующие утверждения.

1. Число m чистых стратегий игрока А совпадает с числом N чистых стратегий игрока В: m=n (по определению)

2. Размерности векторов смешанных стратегий игроков А и В одинаковы.

3. Множество S_A смешанных стратегий игрока А совпадает с множеством S_B смешанных стратегий игрока В: S_A= S_B (т.к. размерности векторов СС обоих игроков одинаковы, а координаты их неотрицательны и в сумме дают 1)

4. Симметричная матричная игра справедлива, т.е. ее цена V=0 (по т. фон Неймана

5. Множество оптимальных стратегий игрока А совпадает с множеством оптимальных стратегий игрока В: (по свойству включения: )

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

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

1. найти при ограничениях x_j ? 0, j=1,2,…,m;

2.

3. найти при ограничениях y_i ? 0, i=1,2,…,n;

4.

эквивалентно решению симметричной матричной игры с матрицей

где - квадратная нулевая матрица порядка m (все элементы - нули); - квадратная нулевая матрица порядка n; - квадратная нулевая матрица 1-го порядка, отождествляемая со своим единственным элементом - нулем;

и - соответственно матрица коэффициентов при неизвестных и вектор-столбец свободных членов системы ограничений в задаче пункта 1; - вектор-строка коэффициентов при неизвестных целевой функции задачи пункта 1; А^Т, В^Т, С^Т - транспонированные матрицы.

Точнее говоря, если является оптимальной стратегией любого игрока в игре с матрицей D и , то - оптимальное решение задачи пункта 1, а - оптимальное решение задачи пункта 2.

50. Игры с природой: сущность, основные понятия, классификация, экономические примеры

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

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

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

Пусть - множество чистых стратегий игрока А, а - множество состояний природы П, которая в любой момент времени может находиться в одном из них. Состояние природы - совокупность {П₁,…,П_n}, формирующаяся либо на основе имеющегося опыта анализа природы, либо в результате предположений и интуиции экспертов.

Выигрыш игрока А при выбранной им стратегии , i=1,2,…,m, и при состоянии , j=1,2,…,n, природы П обозначим , i=1,2,…,m; j=1,2,…,n. Выигрыши могут определяться как значения выигрыш-функции F игрока А:

Из выигрышей игрока А формируется матрица выигрышей (матрица игры, платёжная матрица):



51. Математическая модель игры с природой. Показатель благоприятности состояния природы. Матрица рисков

В игре с природой действуют два игрока:

· Игрок А, действует осознанно и принимает решения

· Природа, не является ни противником, ни союзником игрока A, не действует осознанно, а принимает неопределённым образом то или иное свое состояние, не преследуя конкретной цели и абсолютно безразлично к результату игры.

A/П	П1	П2	П3	….	Пn
A1	a11	a12	a13		a1n
A2	a21	a22	a23		a2n
….
Am	am1	am2	am3		amn

Игрок А имеет m возможных чистых стратегий

Природа - n возможных состояний

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



52. Принятие решений в условиях риска. Критерий Байеса оптимальности чистых стратегиях относительно выигрышей

Пусть известны состояния П₁ … П_n и вероятности q₁ … q_n, с которыми природа П реализует эти состояния. Тогда мы находимся в ситуации принятия решения в условиях риска. Показателем эффективности стратегии Ai по критерию Байеса относительно выигрышей называется среднее значение, или математическое ожидание выигрыша i-й строки с учётом вероятностей всех возможных состояний природы: i=1,…,m

Оптимальной среди чистых стратегий по критерию Байеса относительно выигрышей считается стратегия с максимальным показателем эффективности: т.е. с максимальным средним выигрышем

53. Принятие решений в условиях риска. Критерий Байеса оптимальности чистых стратегиях относительно рисков

Рассмотрим матрицу игры с природой, в которой известны вероятности состояния природы q₁.. q_n. При принятии решения в условиях риска можно пользоваться не только средними выигрышами, но и средними рисками.

Показателем неэффективности стратегии A_i по критерию Байеса относительно рисков называется среднее значение (мат ожидание) рисков i-й строки матрицы, вероятности которых, совпадают с вероятностями природы. Обозначим средний риск при стратегии A_i через , тогда



Тогда оптимальной среди чистых стратегий по критерию Байеса относительно рисков является стратегия A_io, показатель неэффективности которой минимален, т.е. минимален средний риск.

54. Принятие решений в условиях риска. Критерий Лапласа оптимальности смешанных стратегий относительно выигрышей

По - критерию относительно выигрышей:

1. Показателем ( эффективности смешанной стратегии Р=(р₁,…, р_m) назовем среднее арифметическое выигрышей:

(P)= )

2. Ценой () игры в смешанных стратегиях назовем наибольший из показателей эффективности стратегий P?S:

=max{(P):P?S }

3. Оптимальной (во множестве S смешанных стратегий назовем стратегию =(,…,) c наибольшим показателем эффективности:

() = max{:P?S}



Для любой смешанной стратегии Р=(р₁,…, р_m) имеет место равенство:

(P)=

Это неравенство можно представить в матричной форме:

55. Принятие решений в условиях риска. Критерий Лапласа оптимальности смешанных стратегий относительно рисков

По риск-критерию Лапласа (L^r-критерию):

· Показателем неэффективности чистой стратегии А_i называется число

· Ценой игры в чистых стратегиях называется наименьший из показателей неэффективности чистых стратегий:

· Оптимальной во множестве чистых стратегий является стратегия A_k € S^c с наименьшим показателем неэффективности:

Множество (чистых) стратегий, оптимальных во множестве чистых стратегий по риск-критерию Лапласа, обозначим через (S^C)^O(Lr). Критерии Лапласа оптимальности чистых стратегий во множестве чистых стратегий относительно рисков и выигрышей эквивалентны:



56. Принятие решений в условиях неопределенности. Критерий Вальда

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

Оптимальной среди чистых стратегий по критерию Вальда считается та стратегия, при которой минимальный выигрыш является максимальным среди минимальных выигрышей всех чистых стратегий.

для матрицы выигрышей,

для матрицы потерь.

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

57. Принятие решений в условиях неопределенности. Критерий крайнего оптимизма

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

Оптимальной среди чистых стратегий по максимаксному критерию является стратегия А_io с максимальным показателем эффективности:



для матрицы выигрышей,

для матрицы потерь.

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

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

58. Принятие решений в условиях неопределенности. Критерий крайнего пессимизма Сэвиджа

1. Показатель неэффективности:

2. Цена игры:

3. Стратегия Ак - оптимальна, если выполняется:



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

59. Критерий пессимизма-оптимизма Гурвица оптимальности чистых (смешанных) стратегий относительно выигрышей

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

л [0,1]- коэф. Оптимизма

1- л - коэф. Пессимизма

При л? Ѕ A более оптимистичен, чем пессимист.

При л? Ѕ А менее оптимистичен, чем пессимист.

При л= Ѕ А нейтрален

(Hur)^p_i (л)= (1- л)W_i + лM_i, i = 1,2,…,m,

(Hur)^p_i (л) = (M_i -W_i) л + W_i



60. Критерий пессимизма-оптимизма Гурвица оптимальности чистых стратегий относительно рисков

теория антагонистический игра матрица

Критерий пессимизма-оптимизма Гурвща относительно рисков с показателем оптимизма ? [0,1]. Этот критерий занимает промежуточное положение между критерием Сэвиджа крайнего пессимизма и миниминным критерием крайнего оптимизма и является частным случаем обобщенного критерия Гурийца относительно рисков с коэффициентами

Показатель неэффективности стратегии A_i по рассматриваемому критерию определяется формулой

() = R_i(1 - ,0,...,0,) = + =(1-+ , i=1,…,m (1)

1 1

И тогда оптимальной стратегией среди чистых стратегий игрока А по критерию пессимизма-оптимизма Гурвица относительно рисков с показателем оптимизма ? [0,1]. будет стратегия минимальным показателем неэффективности (1):

() = min () = min[(1-+ )].

1 1 1 1

Размещено на Allbest.ru

...