Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 16

x^опт=argmax{minf_x(x_i,y_j)} = x₂                y^опт=argmax{minf_y(x_i,y_j)} = y₁

x_i     y_j                                                    y_j     x_i

2)  оптимальны по Парето только совокупные стратегии {( x₂ ,y₂), (x₃ ,y₁)}: в правом верхнем квадранте от них нет других точек.

Точки с максимальными координатами f_x и f_y всегда оптимальны по Парето.

3)  Нэш. Рассмотрим условные оптимумы:

x^опт(y) = argmax_x f_x(x,y),  y^опт(x) = argmax _y f_y(x,y). Представим эти функции в виде двудольного орграфа. Оптимуму по Нэшу соответствует неориентированное ребро.

Таких может не быть. У нас – это ребра {( x₁ ,y₁), (x₂ ,y₂)} .

Заметим, что оптимумы по Нэшу и по Парето не совпали.

Def: Игра-антагонистическая, если увеличение выигрыша одного из игроков ведет к уменьшению выигрыша другого (интересы противоречивы). Если f_x(x,y)+f_y(x,y)=const, то игра – с постоянной суммой (в т.ч. с нулевой).

Лемма 1: Пусть "x [ f₁(x) £ f₂(x) ],  x₁=arg max f₁, x₂=arg min f₂.

Þ max f₁ (x)= f₁ (x₁)£ f₂ (x₁)£ max f₂ (x),   min f₁ (x)£ f₁ (x₂)£ f₂ (x₂)= min f₂ (x).

Лемма 2: Пусть f₁ (x) + f₂ (x)=0, т.е. f₂ (x) = -f₁ (x) "x.

Þ max f₂ (x)=max {-f₁ (x)}=-min f₁  Þ arg max f₂=arg min f₁.

№13. Матричные игры.

Игра двух лиц с конечными множествами стратегий и нулевой суммой, когда f₁+f₂=0, задается одной матрицей. Пусть Z* - множество всех совокупных стратегий, оптимальных по Нэшу; Z^опт – множество оптимумов по максимину.

1.  Оптимальными по Парето являются все совокупные стратегии.

2.  Z^опт¹Æ, т.е оптимум по максимину существует всегда.

3.  Z*¹Æ Û Z^опт.= Z*, т.е. оптимум по Нэшу может не существовать, но если он существует, то совпадает с оптимумом по максимину.

Лемма 3: Пусть ,         Þ v₁ ≤ v₂  " f.

Доказательство: Имеем  и по лемме 1 Þ

ÞÑ

Числа v₁ и v₂ называются нижним и верхним значениями игры.

Теорема: Утверждения Z*¹Æ, v₁=v₂ и Z* = Z^опт эквивалентны, т.е. матричная игра имеет решение по Нэшу тогда и только тогда, когда v₁=v₂. При этом оптимумы по максимину и по Нэшу совпадают.

Доказательство. 1) Пусть (x*,y*) Î Z*, т.е. Þ т.е. v₂<v₁. Но по лемме 3  v₁<v₂ , Þ v₂ = v₁ и все неравенства суть равенства Þ и , т.е. Z* ÌZ^опт.

2) Пусть v₁=v₂ и ,  . Тогда, т.е.  для всех xиy. Полагая сначала x= x^опт , а потом y=y^опт, получим  ÞZ^оптÌZ*, т.е. любое решение по максимину оптимально по Нэшу Þ Z*¹Æ.Ñ

Оптимум по Нэшу оптимален по всем критериям рационального поведения и называется решением игры в чистых стратегиях. Условием его существования является равенство v₁=v₂=v, а само число v называют значением игры.

Пример1:v₁ = v₂ = v=3. Решение игры - x^опт=x₁,y^опт=y₃. Кстати, цикл  x₂ Þ y₂ Þ x₃ Þ y₁ Þ x₂,  но x₁ Û y₃. p=(0,¹/₂,¹/₂), q=(²/₅,³/₅,0)?

Пример2: x^опт=x₂, y^опт=y₃ , v₁ = -3 ≠ 2= v₂.

Þ решения в чистых стратегиях нет, его нужно искать в смешанных стратегиях.

Доминирование: y₁>y₃ Þ y₁ можно отбросить!!

Игра в смешанных стратегиях.

Пусть {f_ij} - матрица игры размера n´m, т.е. f_ij=f(x_i,y_j) – выигрыш игрока

x, если он играет по стратегии x_i, а его соперник - по стратегии y_j. Смешанными стратегиями игроков назовем векторы p и q, задающие распределение вероятностей на множествах чистых стратегий игроков, т.е. p_i, q_i³0, åp_i=åq_i=1. Разобьем интервал [0,1] на n отрезков с длинами p₁,…,p_n и датчиком равномерного распределения разыграем точку. Попадание в i-ый отрезок ~ выбору стратегии x_i. Þ Стратегия x_i выбирается с вероятностью p_i, а стратегия y_j - с вероятностью q_j. Предположим, что соперники выбирают стратегии независимо друг от друга.