Игра с седловой точкой

Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число  =  =  называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.

Пример. Пусть игра задана следующей платежной матрицей:

	В1	В2	В3	В4	i
- лучшая стратегия для игрока А – (А3) А1	9	3	8	2	2
А2	4	2	7	3	2
А3	6	4	7	8	4
А4	5	3	4	7	3
 j	9	4	8	8
цена игры  =  =  = 4
min max - лучшая стратегия для игрока В – (В2)

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

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

Рассмотрим платежную матрицу (1). Пусть игрок А использует чистые стратегии А₁, А₂, … А_i,…А_m с вероятностями p₁, p₂, … p_i,…p_m, причем =1, а игрок В использует свои чистые стратегии В₁, В₂, … В_j,…B_n с вероятностями q₁, q₂, … q_j,… q_n, причем = 1.

Тогда набор S_A = (p₁, p₂, … p_i,…p_m) называется смешанной стратегией игрока А, а набор S_B = (q₁, q₂, … q_j,… q_n) - смешанной стратегией игрока В.

Поскольку игроки выбирают свои стратегии случайным образом, то вероятность выбрать комбинацию А_iВ_j по теории вероятности равна (P_i  q_j). При использовании смешанных стратегий игра становится случайной, тогда говорят о среднем значении выигрыша, который определяется платежной функцией

f(S_A, S_B) = . (40)

Смешанные стратегии = ( , ,… … ) и = ( , ,… … ) называются оптимальными, т.е. дающими каждой стороне максимальный возможный для нее средний выигрыш (для А) или минимальный средний проигрыш (для В), если они образуют седловую точку для платежной функции (2), т.е. если выполняется следующее условие:

f(S_A, )  f( , )  f( , S_B).

Величина  = f( , S_B) называется ценой игры.

Теорема 2. В смешанных стратегиях любая матричная игра имеет седловую точку, или каждая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.