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

X₄ < X₁ Þотбросим X₄.

B(q) - верхняя огибающая семейства прямых В_i., q^опт- точка минимума функции B и в ней B₃=B₁

Þ 5q₂+7q₃ = 6q₂+2q₃  или  q₂=5q₃.

Но   q₂+q₃  =1, Þ q₂=⁵/₆ ,  q₃ = ¹/₆.

q^опт =(0, ⁵/₆, ¹/₆),         v = ³²/₆. B₂(q) < v Þp₂=p₄=0 Þ 5p₁+6p₃ = 7p₁+2p₃, Þp^опт=(²/₃, 0, ¹/₃, 0).          Но т.к. A₁(p) = ⁷/₃ < v, то это не решение игры (по ТДН).

Бесконечные антагонистические игры со счетным числом стратегий.

Если игроки имеют не конечное, а счетное число стратегий, то при S |a_ij| < ¥, все теоремы с конечного случая переносятся на счетный.

Иначе возможны следующие «плохие» случаи.

Случай 1: . Члены ряда равномерно ограничены, в чистых стратегиях существуют maxmin и minmax, но .

Перейдем к смешанным стратегиям: , S_n^¥p_k ®0.

монотонно убывает по j и стремится к –1.

Т.о.  не существует, но  .

Аналогично  , ,  монотонно возрастает по i и стремится к +1. Т.о.  не существует, но  ..

Случай 2: . Члены ряда не ограничены, поэтому в чистых стратегиях maxmin и minmax не существуют, как и supinf и infsup. Если p=(½, ¼, 0, ⅛, 0, 0, 0, ¹/₁₆, …), т.е.
p_i = {2^-(k+1)  при i = 2^k  и 0 при i ≠ 2^k}, то  вообще не имеет смысла.

.

№14.Игра на квадрате.

Игра с нулевой суммой, f(x,y)-функция выигрыша первого игрока;  x,yÎ[0,1].

Чтобы существовали u₁ и u₂, достаточно, чтобы были выполннены условия:

1) f- непрерывна;      2) f- строго вогнута? по x, строго выпукла? по y.

Теорема: При выполнении условий 1-2 существует решение в чистых стратегиях.

Доказательство: Определим непрерывные (докажите!) функции .

Пусть x*- неподвижная точка их непрерывной! суперпозиции, т.е. j(y(x*))=x*.

Обозначим y*=y(x*) Þ j(y*)=x*  и  y*- неподвижная точка функции y(j(y)).

Покажем, что  f(x,y*)£f(x*,y*)£f(x*,y):

Þ(x*,y*)- седловая точка (ситуация равновесия), Þ оптимальная стратегия.Ñ

Пример:  f(x,y)= -2x²+y²+3xy-x-2y. Теорема применима. Найдем функции j и y.

Сначала найдем точки абсолютных max и min и проверим условие «Î[0,1]?».

∂f/∂x= -4x+3y-1=0 Þ x_абс = ^3y-1/₄ Î[-¼,+½] при yÎ[0,1].

Аналогично,  ∂f/∂y =  2y+3x-2=0 Þ y_абс = ^2-3x/₂ Î[-½,1]    при xÎ[0,1]     Þ

Предположим, что y* = ψ(x*)=0 Þ х>⅔, но х*= j(y*) = j(0) = 0. Противоречие.  Предположим, что х*= j(y*)=0 Þ y<⅓, но y* = ψ(x*) = ψ(0) = 1. Противоречие.  Þ Нужно брать функции j  и y  не по этим веткам.

Þ х* = j(y*) = (3y*-1)/4при y³ ⅓, но y* = ψ(x*) = (2-3x*)/2; получаем 17x*=4  Þx*=⁴/₁₇y*=1-³/₂* ⁴/₁₇=¹¹/₁₇.   Получили решение игры ( ⁴/₁₇, ¹¹/₁₇).

№15. Позиционные игры.

Def: Под позиционной игрой n лиц понимается:

1)  ориентированное дерево Г с выделенным корнем А (А-начальная позиция, невисячие вершины-промежуточные позиции, а висячие-заключительные);

2)  для висячих вершин заданы n-мерные векторы выигрышей игроков;

3)  задано разбиение невисячих вершин на n+1 подмножество очередности хода S_i, и в каждой вершине vÎS_i ход делает игрок с номером i (0 означает, что ход делается случайно);

4)  для позиций из S₀ заданы распределения вероятностей на исходящих дугах;

5)  задано разбиение S_i (i¹0) на информационные подмножества S_ij (S_i=È S_ij), причем позиции одного информационного подмножества имеют одинаковое количество дочерних позиций;
а материнские позиции находятся в разных информационных подмножествах с дочерними;