3 1. Парная конечная игра. Платежная матрица. Максиминная и минимаксная стратегии.

Игра называется парной, если в ней участвуют два игрока. Игра называется конечной, если у каждого игрока имеется конечное число стратегий. любая конечная игра двух лиц с нулевой суммой имеет по крайней мере одно решение — пару оптимальных стратегий, в общем случае смешанных {S*A, S*B), и соответствующую цену.

Пусть у игрока А имеется m стратегий, у В – n стратегий

A(A1…Am) B(B1…Bm). Каждый шаг игроков имеет стоимость aij – выигрыш А= проигрыш В

В B1 B2…. Bn

A

A1 a11 a12…. a1n

A2 a21 a22…..a2n

…

Am am1 am2 …amn

Полученная матрица A называется платежной матрицей (Матрицей игры)

С тратегия называется оптимальной, если для каждого игрока выполняется либо условие выгодности (1), либо усл-е справедливости(2): H(xi)≤H(x*), *-opt, i=1,n i€I (1);

H(x*,y)≤H(x*,y*)≤H(x;y*) (2).

Стратегия игроков в условиях равновесия наз-ся чистой стратегией. Нахождение решения в чистых стратегиях осущ-ся с помощью максиминной и минимаксной стратегий.

В B1 B2…. Bn β – верхняя цена игры, минимакс. α – нижняя ЦИ, максими

A если α=β=υ – цена игры. Сама игра наз-ся игрой с седлов.

A1 a11 a12…. a1n α1 точкой, разрешима в чистых стратегиях.

A2 a21 a22…..a2n α2

… ………………………

Am am1 am2 …amn αm α=max αi=maxi min_j aij

β1 β2 βn β=minjβj=minj maxi aij

32. Цена игры. Устойчивость решений. Седловые точки.

Нижней ценой игры V_* называется величина, являющаяся максиминным значением платёжной матрицы:

V_* = max min a_ij

_{i j}

Верхней ценой игры V^* называется величина, являющаяся минимаксным значением платёжной матрицы:

V^* = min max a_ij

_{j i}

В силу того, что игра антагонистическая, всегда V_* ≤ V^*. Если V_* = V^* = V, то просто говорят о цене игры, такая игра называется вполне определённой, игрой с седловой точкой, поскольку значение элемента платёжной матрицы, равное V = V_* = V^* является минимальным в своей строке и максимальным в своём столбце. Соответствующие этой цене игры стратегии называются оптимальными, поскольку второй игрок не может понизить нижнюю цену игры, а первый игрок не может повысить верхнюю цены игры.

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

X(x1…xn), xi – частота использов. S (x1…xn) pi - вероятность

(p1…pn)

Σpi=1 – полная группа, описание всех возможных исходов.

V = V_* = V^* седловая точка существует, это есть элемент платежной матрицы, которому соотв-ет единственная опт-стратегия 2х игроков . Если V = V_* = V^* и сущ-ет несколько элементов Пл матрицы,  сущ-ет неск. опт-решений,кот-м будет соотв-ть несколько пар стратегий (конечная антагонистическая игра может иметь множество оптимальных решений (множество пар оптимальных стратегий). V_* < V^* – выполняется соотношение строгого неравенства, следовательно, седловая точка в игре отсутствует, ситуации равновесия не существует.

33. Методы решения матричных игр. Графическое представление игры для п=2.

1. Если α=β=υ мы говорим об игре с седловой точкой, разрешимой в чистых стратегиях

# α=β=a11= υ, (A1,B1), A(1,0,0) B(1,0,0)

2. Решение игры в смешанных стратегиях. Пусть дана матрица А. Говорят, что строка I доминирует строку k, если aij≥akj. Причем сущ-т хотя бы одно значение jo, такое что aijo>akjo. Столбец j доминирует l-столбец, если aij≤ail. при этом сущ-т io такое что aioj<aiol. Теорема: пусть А - матричная игра , и пусть строки i1,i2…ik доминируются. Тогда 1й игрок имеет такую опт-стратегию, в кот xi1=xi2=…=xik=φ. При этом любая опт-стратегия для игры, кот получается после удаления строк, явл-ся опт-ной и для исх-й игры (справедливо и для столбцов). Дале полученная игра сводится к системе.

1доминирование

♦ строится графическое изображение игры; i-строкам соотв x, j-столбцам – y, составляется vi – по столбцам/строкам методом скалярного умножения

♦ выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры γ;

♦ определяется пара стратегий, пересекающихся в точке оптимума M. Эти стратегии являются активными стратегиями игрока B. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них;

♦ решается полученная игра 2x2: нахождение векторов x и y, выписывается ответ.

Решение игры mx2 осуществляется аналогично. Вместо пункта 2 применяется;

♦ выделяется верхняя граница выигрыша, и на ней находится точ