- •Оглавление
- •3.1. Основы теории 42
- •5.1. Основы теории 69
- •6.1. Основы теории 94
- •Введение
- •1. Предмет, задачи теории игр. Классификации игр
- •1.1. Предмет, задачи теории игр
- •1.2. Классификации игр
- •1.3. Постановка задачи
- •2. Антагонистические игры
- •2.1. Основы теории
- •2.2. Антагонистическая игра с полной информацией
- •2.3. Антагонистическая игра без информации. Смешанные стратегии
- •3. Многошаговые игры
- •3.1. Основы теории
- •3.2. Многошаговые (позиционные) игры с полной информацией
- •3.3 Игра с выжиданием
- •4. Неантагонистические (биматричные) игры
- •4.1. Бескоалиционная игра в нормальной форме
- •4.2. Биматричные игры. Основы теории
- •4.3. Решение биматричной игры
- •5. Кооперативные игры
- •5.1. Основы теории
- •5.2. Арбитражные схемы
- •5.3. Классические кооперативные игры
- •5.4 Кооперативные игры с бесконечным числом игроков
- •5.5 Игра с тремя игроками. Справедливые дележи
- •5.6. Игра с тремя игроками. Устойчивость
- •6. Бескоалиционные игры
- •6.1. Основы теории
- •6.2. Задача, касающаяся рекламы
- •6.3. Диадические игры. Пример: экологический конфликт
- •6.4. Пример. Справедливое распределение штрафа
- •Заключение
- •Библиографический список
- •Теория игр Реализация игрового подхода в управлении фирмой
- •195251, Санкт-Петербург, Политехническая ул., 29
2. Антагонистические игры
2.1. Основы теории
Определение 2.1. Игры, в которых имеется только два участника (игрок I и игрок II) с диаметрально противоположными интересами называют антагонистическими играми или играми с нулевой суммой.
Формально противоположность интересов игроков выражается в том, что при переходе от некоторой ситуации s к ситуации si игрок I приобретает (теряет) ровно столько, сколько теряет (соответственно, приобретает) игрок II:
Н1(s)- Н1(si)= Н2(si)- Н2(s).
Иначе это можно выразить как постоянство суммы выигрышей игроков во всех ситуациях:
Н1(s)+ Н1(s)= Н1(si)+ Н1(si).
Определение 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
|
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. Таблицу теперь можно переписать в виде:
где hij- значение функции выигрыша в ситуации ij.
Для того чтобы подчеркнуть, что в нашей игре игрок I имеет m стратегий и игрок II – n стратегий, ее называют матричной mхn игрой.
Процесс разыгрывания конечной антагонистической игры состоит в том, что игроки I и II независимо друг от друга выбирают соответственно некоторые чистые стратегии х и у, в результате чего складывается ситуация (х, у). После этого игрок I получает выигрыш.
Игрок II проигрывает столько, сколько выигрывает игрок I, поэтому величину Н(х, у) также называют проигрышем игрока II.
Такимобразом, всякую конечную антагонистическую игру можно задать, используя вещественную матрицу, которая называется матрицей выигрышей. В этой терминологии конечная антагонистическая игра называется матричной. Выбор игроком I стратегии i означает выбор строки i, а выбор игроком II стратегии j—выбор столбца j. Выигрыш игрока I будет при этом равен элементу матрицы Н, стоящему на пересечении i-й строки и j-го столбца.
Если игрок I выбирает стратегию х0X, то игрок II может выбрать такую стратегию уY, при которой выигрыш игрока I будет равен наименьшему из выигрышей H ( х0, у),т. е. min H (х0, у).
уY.
В этой связи игрок I будет склонен выбрать свою стратегию х0 так, чтобы минимальный выигрыш был наибольшим, т. е. равным
H ( х0, у), т. е. min H (х0, у),
уY;
min H(х0, у)=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].