2.Теоретические основы матричных игр

2.1 Структура матричных игр и принципы оптимальности

Определение 2.1. Антагонистические игры, в которых каждый игрок имеет конечное число стратегий, называют матричными играми [3].

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

Определение 2.2. Игры, в которых имеется только два участника (игрок I и игрок II) с диаметрально противоположными интересами называют антагонистическими играми или играми с нулевой суммой.

Формально противоположность интересов игроков выражается в том, что при переходе от некоторой ситуации s к ситуации sⁱ игрок I приобретает (теряет) ровно столько, сколько теряет (соответственно, приобретает) игрок II [6]:

Н₁(s)- Н₁(sⁱ)= Н₂(sⁱ)- Н₂(s)

Иначе это можно выразить как постоянство суммы выигрышей игроков во всех ситуациях:

Н₁(s)+ Н₁(s)= Н₁(sⁱ)+ Н₁(sⁱ)

Определение 2.3. Тройка

Г = < X, Y, H > (2.1)

(где X и Y — множества, Н — функция от двух переменных х X и у Y) называется антагонистической игрой. Если множества X и Y конечны, то тройка (1.1) называ­ется конечной антагонистической игрой. Множества X , Y называются множествами стратегий. Элементы х X на­зываются стратегиями (точнее чистыми стратегиями) иг­рока I, элементы у Y — (чистыми) стратегиями игро­ка II, функция Н — функцией выигрыша игрока I или просто функцией выигрыша, а пара (х, у) — ситуацией в чистых стратегиях[1].

Необходимо ещё раз отметить, что для игр с нулевой суммой достаточно только задать значение функции выигрыша игрока 1.

Итак, будем считать, что оба игрока в антагонистической игре (2.1) имеют конечное число стратегий каждый. Тогда значение функции выигрыша удобно расположить в виде следующей таблицы:

Таблица 1

	y1	y2	…	yn
x1	Н(х1, у1)	Н(х1, у1)	…	Н(х1, у1)
x2	Н(х1, у1)	Н(х1, у1)	…	Н(х1, у1)
…	…	…	…	…
xm	Н(х1, у1)	Н(х1, у1)	…	Н(х1, у1)

Поскольку число возможных действий каждого из иг­роков конечно, а названия стратегий для нас несущест­венны, можно полагать х = {1,2, . . ., т} и у = {1, 2, ...,п} (здесь т и п соответственно число чистых стратегий игроков I и II). Тогда значения функции Н естественно представить в виде матрицы.

Каждая ситуация в такой игре будет обозначаться парой чисел i,j , где i может принимать значения 1,2,…m, а j – значения 1,2,…n. Нашу таблицу теперь можно переписать в виде:

где h_ij- значение функции выигрыша в ситуации ij.

Таблицы подобного вида в математике называются матрицами. Горизонтальные ряды матрицы называются её строками, а вертикальные – столбцами. Числа, стоящие в клетках таблицы являются значениями выигрыша для игрока I.

Иногда для того, чтобы подчеркнуть, что в нашей игре игрок I имеет m стратегий, и игрок II – n стратегий, её называют матричной mхn игрой.

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

Игрок II столько же проигрывает, сколько выигрывает игрок I. Поэтому ве­личину Н(х, у) также называют проигрышем игрока II.

Такимобразом, всякую конечную антагонистическую игру можно задать вещественной матрицей, которая на­зывается матрицей выигрышей. В этой терминологии ко­нечная антагонистическая игра называется матричной. Вы­бор игроком I стратегии i означает выбор строки i, а вы­бор игроком II стратегии j—выбор столбца j. Выигрыш игрока I будет при этом равен элементу матрицы Н, стоящему на пересечении i-й строки и j-го столбца.

Если игрок I выбирает стратегию х⁰X, то игрок II может выбрать такую стратегию у Y, при которой выигрыш игрока I будет равен наименьшему из выигрышей H ( х⁰, у),т. е. min H (х⁰, у).

уY

Поэтому игрок I будет склонен выбрать свою стратегию х⁰ так, чтобы этот минимальный выигрыш был наиболь­шим, т. е. равным

H ( х⁰, у),т. е. min H (х⁰, у),

уY

minH(х⁰,у)=maxminН(х,у)=v(Г) (2.2)

уY хX уY

Величину v (Г) будем называть нижним значением игры Г = (X, Y, H). Соответствующую этому значению стратегию игрока I называют его максиминной чистой стратегией. Применяя эту стратегию, игрок I при любом поведении игрока II обеспечивает себе выигрыш, не меньший чем v (Г).

Это можно записать в виде неравен­ства

H(x°,y)≥ v(T) у Y. (2.3)

Аналогично стратегия у°, определяемая из равенства

max H(х, у°) = min max H(x_, у) = (Г), (2.4)

уY уY хX

называется минимаксной чистой стратегией игрока II. Применяя ее, игрок II при любых действиях игрока I проигры­вает ему не больше (Г), что соответствует неравенству

H(х, у °) ≤ (Г) x X (2.5)

Величину (Г) будем называть верхним значением игры Г = (X, Y, H).

Полагая в (2.3) у = у°, а в (2.5) x=x°, мы получим

v(Г)≤H(x°,y°)≤(Г) (2.6)

Придерживаясь стратегии x°, игрок I поступает очень осторожно: он желает получить величину v(Г) независимо от действий игрока II. Принцип, которому он следует, называется принципом максимина, потому что гаранти­рованный выигрыш игрока I как раз равен величине

max min Н (x,y).

хX уY

Игрок I этот выигрыш может всегда себе обеспечить, а большей суммы ему не позволит выиграть противник.

Если игрок II придерживается стратегии y°, то он тоже следует этому принципу. А выигрыш игрока II ра­вен — H(x,y), (то есть проитвоположен выигрышу игрока I )

max min. (—H(x,y)) = — min max H(x,y) (2.7)

хX уY уY хX

Таким образом, его проигрыш не больше (Г) при любых действиях игрока I.

Принцип максимина был впервые явно сформулиро­ван Дж. фон Нейманом [1] в 1928 г.

Этот принцип име­ет важное значение и широко используется в теории игр. В частности, теория антагонистических игр изучает по­ведение игроков, придерживающихся именно этого прин­ципа.