Антагонистические игры

Основы теории

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

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

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

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

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

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

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

где X и Y — множества; Н — функция от двух переменных х X и у Y; называется антагонистической игрой.

Если множества X и Y конечны, то тройка (2.1) называ­ется конечной антагонистической игрой. Множества X, Y называются множествами стратегий.

Элементы х X на­зываются стратегиями (точнее чистыми стратегиями) иг­рока I.

Элементы у Y на­зываются (чистыми) стратегиями игро­ка II.

Функция Н на­зывается функцией выигрыша игрока I,или просто функцией выигрыша.

Пара (х, у)на­зывается ситуацией в чистых стратегиях [1].

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

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

Таблица 2.1

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

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

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

Для того чтобы подчеркнуть, что в нашей игре игрок 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;

min H(х⁰, у)=max minН(х, у)=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.

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

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