Если имеется несколько конфликтующих сторон (лиц), каждая из которых принимает некоторое решение, определяемое заданным набором правил, и каждому из лиц известно конечное состояние конфликтной ситуации с заранее определенными для каждой из сторон платежами, то говорят, что имеет место игра.
Задача теории игр состоит в выборе такой линии поведения данного игрока, отклонение от которой может лишь уменьшить его выигрыш.
Некоторые определения игры
Количественная оценка результатов игры называется платежом.
Парная игра (два лица) называется игрой с нулевой суммой, если сумма платежей равна нулю, т.е. если проигрыш одного игрока равен выигрышу другого.
Однозначное описание выбора игрока в каждой из возможной ситуаций, при которой он должен сделать личный ход, называется стратегией игрока .
Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный средний выигрыш (или, что - то же самое, минимально возможный средний выигрыш).
Игра, определяемая матрицей А , имеющейm строк иn столбцов, называется конечной парной игрой размерностиm * n ;
где
i
=
- стратегия первого игрока, имеющегоmстратегий;
j
=
- стратегия второго игрока, имеющегоnстратегий;
ij
– выигрыш первого игрока поi
-й
стратегии при использовании вторымj
-й
стратегии (или, что то же самое, проигрыш
второго по своейj
-й
стратегии, при использовании первымi
-й);
А = ij – платежная матрица игры.
1.1 Игра с чистыми стратегиями
Нижняя цена игры (для игрока первого)
= max (min ij ). (1.2)
i j
Верхняя цена игры (для второго игрока):
= min
(max
ij
)
. (1.3)
J i
Если = , игра называется с седловой точкой (1.4), или игра с чистыми стратегиями. При этомV = = называют ценной игры (V - цена игры).
Пример. Дана платежная матрица игры 2 лиц А. Определить оптимальные стратегии для каждого из игроков и цену игры:
(1.4)
max 10 9 12 6
i
min 6
j
- стратегия первого
игрока (строки).
Стратегия второго игрока (столбцы).
- цена игры.
Таким образом, игра имеет седловую точку. Стратегия j = 4 – оптимальная для второго игрока, стратегияi =2 - для первого. Имеем игру с чистыми стратегиями.
1.2 Игры со смешанными стратегиями
Если платежная
матрица не имеет седловой точки, т.е.
,
и ни один из участников игры не может
выбрать один план в качестве своей
оптимальной стратегии, игроки переходят
на «смешанные стратегии». При этом
каждый из игроков использует в процессе
игры несколько раз каждую из своих
стратегий.
Вектор, каждая из компонент которого показывает относительную частоту использования игроком соответствующей чистой стратегии, называется смешанной стратегией данного игрока.
Х = (х 1 …х i …х m ) – смешанная стратегия первого игрока.
У = (у 1 …у j …у n ) – смешанная стратегия второго игрока.
x i , у j – относительные частоты (вероятности) использования игроками своих стратегий.
Условия использования смешанных стратегий
.
(1.5)
Если Х * = (х 1 * ….х i * …х m *) – оптимальная стратегия, выбранная первым игроком;Y * = (у 1 * …у j * …у n *) – оптимальная стратегия, выбранная вторым игроком, то число является ценой игры.
(1.6)
Для того чтобы число V было ценой игры, ах * иу * - оптимальными стратегиями, необходимо и достаточно выполнение неравенств
(1.7)
Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры V вне зависимости от того, с какими частотами будет применять второй игрок стратегии, вошедшие в оптимальную, в том числе и чистые стратегии.
Сведения задач теории игр к задачам линейного программирования.
Пример . Найти решение игры, определяемой платежной матрицейА .
А =
(1.8)
y 1 y 2 y 3
Решение:
Составим двойственную пару задач линейного программирования.
Для первого игрока
(1.9)
у 1 +у 2 +у 3 = 1 (1.10)
Освобождаясь от переменной V (цена игры), разделим левую и правую часть выражений (1.9), (1.10) наV . Приняву j /V за новую переменнуюz i , получим новую систему ограничений (1.11) и целевую функцию (1.12)
(1.11)
.
(1.12)
Аналогично получим модель игры для второго игрока:
(1.13)
х 1 +х 2 +х 3 = 1 . (1.14)
Приведя модель (1.13), (1.14) к форме без переменной V , получим
(1.15)
,
(1.16)
где
.
Если нам необходимо определить стратегию поведения первого игрока, т.е. относительную частоту использования его стратегий (х 1 ….х i …х m ), мы будем использовать модель второго игрока, т.к. эти переменные находятся в его модели выигрыша (1.13), (1.14).
Приведем (1.15), (1.16) к канонической форме
(1.17)
Задача:
Матричная игра задана следующей платежной матрицей:
| Стратегии "B" | ||||||||
| Стратегии "A" | B 1 | B 2 | ||||||
| A 1 | 3 | 5 | ||||||
| A 2 | 6 |
|
||||||
Найти решение матричной игры, а именно:
- найти верхнюю цену игры;
- нижнюю цену игры;
- чистую цену игры;
- указать оптимальные стратегии игроков;
- привести графическое решение (геометрическую интерпретацию), при необходимости.
Шаг:1
Определим нижнюю цену игры - α
Нижняя цена игры α - это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой").Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец (Выделен желтым цветом см. Табл.1).
Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.
Таблица 1
| Стратегии "B" | |||||||||||||||
| Стратегии "A" | B 1 | B 2 | Минимумы строк | ||||||||||||
| A 1 | 3 | 5 | 3 * | ||||||||||||
| A 2 | 6 |
|
|
||||||||||||
В нашем случае нижняя цена игры равна: α = 3 , и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A 1
Шаг:2
Определим верхнюю цену игры - β
Верхняя цена игры β - это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу (Выделена желтым цветом см. Табл.2).
Затем найдем минимальный элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры.
Таблица 2
| Стратегии "B" | ||||||||||||
| Стратегии "A" | B 1 | B 2 | Минимумы строк | |||||||||
| A 1 | 3 | 5 | 3 * | |||||||||
| A 2 | 6 |
| В нашем случае верхняя цена игры равна: β = 5 , и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник (игрок "B") должен придерживаться стратегии B 2 Шаг:3
Смешанная стратегия , это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать
|
|||||||||
где B 1 , B 2 - стратегии игрока "B", а q 1 , q 2 - соответственно вероятности, с которыми эти стратегии применяются, причем q 1 + q 2 = 1.
Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии S A * и S B * соответственно. Пара оптимальных стратегий образует решение игры.
В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Такие стратегии называются активными стратегиями .
Шаг:4
где: p 1 , p 2 - вероятности (частоты) с которыми применяются соответственно стратегии A 1 и A 2
Из теории игр известно, что если игрок "А" использует свою оптимальную стратегию, а игрок "B" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "В" использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок "В" будет пользоваться чистой стратегией B 1 , то средний выигрыш v составит:
k 11 p 1 + k 21 p 2 = v (1)
где: k ij - элементы платежной матрицы.
C другой стороны, если предположить, что игрок "В" будет пользоваться чистой стратегией B 2 , то средний выигрыш составит:
k 12 p 1 + k 22 p 2 = v (2)
Приравняв левые части уравнений (1) и (2) получим:
k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2
А с учетом того, что p 1 + p 2 = 1 имеем:
k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )
Откуда несложно найти оптимальную частоту стратегии A 1 :
| p 1 = |
| (3) |
В данной задаче:
| p 1 = |
| = |
|
Вероятность р 2 найдем вычитанием р 1 из единицы:
| p 2 = 1 - p 1 = | 1 | - |
| = | + | 6 | · |
где: q 1 , q 2 - вероятности (частоты) с которыми применяются соответственно стратегии B 1 и B 2
Из теории игр известно, что если игрок "B" использует свою оптимальную стратегию, а игрок "A" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "А" использует свои активные стратегии. Поэтому если предположить, что игрок "A" будет пользоваться чистой стратегией A 1 , то средний выигрыш v составит:
k 11 q 1 + k 12 q 2 = v (4)
Поскольку цена игры v нам уже известна и учитывая, что q 1 + q 2 = 1 , то оптимальная частота стратегии B 1 может быть найдена как:
| q 1 = |
| (5) |
В данной задаче:
| q 1 = |
| = |
|
Вероятность q 2 найдем вычитанием q 1 из единицы:
| q 2 = 1 - q 1 = | 1 | - |
| = |
|
Ответ:
| Нижняя цена игры: | α = | 3 | |||
| Верхняя цена игры: | β = | 5 | |||
| Цена игры: | v = |
|
| Оптимальная стратегия игрока "А" : |
|
|||||||||||||||
| Оптимальная стратегия игрока "B" : |
|
Геометрическая интерпретация (графическое решение):
Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a 1 и a 2 соответствующие нашим стратегиям A 1 и A 2 . Предположим теперь, что игрок "B" будет пользоваться стратегией B 1 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 3.Отметим соответствующую ему точку на оси a 1 .Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 6. Отметим соответствующую ему точку на оси a 2
(см. Рис. 1). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 3) и (1 , 6), назовем ее линией стратегии B 1 (на Рис.1 показана красным цветом). Абсцисса любой точки на данной прямой равна вероятности p 2 (частоте), с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу k (см. Рис.1).
Рисунок 1.
График зависимости выигрыша k
от частоты р 2
, при использовании противником стратегии B 1
.
Предположим теперь, что игрок "B" будет пользоваться стратегией B 2 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 5.Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 3/2 (см. Рис. 2). Аналогично, если мы будем смешивать в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 5) и (1 , 3/2), назовем ее линией стратегии B 2 . Как и в предыдущем случае, абсцисса любой точки на этой прямой равна вероятности, с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу, но только для стратегии B 2 (см. Рис. 2).
Рисунок 2.
v
и оптимальной частоты р 2
для игрока "А"
.
В реальной игре, когда разумный игрок "В" пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша . Очевидно, что самая высокая точка этой ломанной соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B 1 и B 2 . Обратите внимание, что если выбрать частоту p 2 равной ее абсциссе, то наш выигрыш будет оставаться неизменным и равным v при любой стратегии игрока "B", кроме того он будет максимальным который мы можем себе гарантировать. Частота (вероятность) p 2 , в этом случае, есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p 1 , нашей оптимальной смешанной стратегии, это длина отрезка [p 2 ; 1] на оси абсцисс. (Это потому, что p 1 + p 2 = 1 )
Совершенно аналогично рассуждая, можно найти и частоты оптимальной стратегии для игрока "В", что иллюстрируется на рисунке 3.
Рисунок 3.
Графическое определение цены игры v
и оптимальной частоты q 2
для игрока "В"
.
Только для него следует построить так называемую верхнюю границу проигрыша (красная ломаная линия) и искать на ней самую низкую точку, т.к. для игрока "В" цель, это минимизация проигрыша. Аналогично значение частоты q 1 , это длина отрезка [q 2 ; 1] на оси абсцисс.
Содержание 1 Общие сведения 2 1.1 Игры. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Ходы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Стратегии. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Матричная игра. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Следовая точка. Чистые стратегии 7 2.1 Примеры. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Смешанные стратегии 9 3.1 Игра 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Примеры. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Геометрическая интерпретация. . . . . . . . . . . . . . . . . . . . 12 3.2 Игры 2×n и m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Общие сведения из теории игр 1.1. Игры Теория игр - это математическая теория конфликтных ситуаций, т.е. таких ситуаций, в которых сталкиваются интересы двух или более сторон, преследующих различные цели. Игра - это конфликтная ситуация, регламентированная определенными правилами, в которых должны быть указаны: возможные варианты действий участников количественный результат игры или платеж (выигрыш, проигрыш), к которому при- водит данная совокупность ходов объем информации каждой стороны о поведении другой. Парная игра - игра в которой участвуют только две стороны (два игрока). Парная игра c нулевой суммой - парная игра, в которой сумма платежей равна нулю, т.е. проигрыш одного игрока равен выигрышу второго. В зависимости от отношения каждого из игроков к значению функции выигрыша парные игры подразделяются: Парная игра c нулевой суммой (антагонистическая) - парная игра, в которой сум- ма платежей равна нулю, т.е. проигрыш одного игрока равен выигрышу второго. Неантагонистическая игра - парная игра,в которой игроки преследуют разные, но не прямо противоположные цели. 2 1.2. Ходы Ход - выбор одного из предусмотренных правилами игры действий осуществление этого выбора Ходы бывают двух типов: Личный ход - + сознательный выбор одного из предусмотренных правилами игры действий + осуществление этого выбора Случайный ход - Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного вы- бора. Ниже рассматриваются парные игры с нулевой суммой, содержащие только личные ходы. У каждой стороны отсутствует информация о поведении другой. 3 1.3. Стратегии Стратегия игрока - совокупность правил, определяющих выбор действий при каждом личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры. В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные. Бесконечная игра - игра, в которой хотя бы у одного одного из игроков имеется бесконечное число стратегий. Конечная игра - игра, в которой у каждого игрока имеется только конечное число- стратегий. Число последовательных ходов у любого из игроков определяет под- разделение игр на одноходовые и многоходовые, или позиционные. + В одноходовой игре каждый игрок делает только один выбор из возможных вариантов и после этого устанавливает исход игры. + Многоходовая, или позиционная, игра развивается во времени, представляя собой ряд последовательных этапов, каждый из которых наступает после хода одного из игроков и соответствующего изменения обстановки. В одноходовой игре каждый игрок делает только один выбор из возможных вариантов и после этого устанавливает исход игры. Оптимальная стратегия игрока - стратегия, которая при многократном повторении иг- ры обеспечивает данному игроку максимально возможный средний выигрыш (или, что то же, минимально возможный средний проигрыш). В теории игр все рекомендации вырабатываются исходя из предположения о разумном поведении игроков. Просчеты и ошибки игроков, неизбежные в каждой конфликтной ситуации, а также элементы азарта и риска в теории игр не учитываются. 4 1.4. Матричная игра Матричная игра - одноходовая конечная игра с нулевой суммой.Матричная игра явля- ется теоретико-игровой моделью конфликтной ситуации, в которой противники для до- стижения диаметрально противоположных целей делают по одному выбору (ходу) из ко- нечного числа возможных способов действий.В соответствии с выбранными способами действий (стратегиями) определяется достигаемый результат. Рассмотрим на примере. Пусть имеются два игрока A и B, один из которых может выбрать i-ю стратегию из m своих возможных стратегий A1 , A2 , ...Am , а второй выбирает j-ю стратегию из своих воз- можных стратегий B1 , B2 , ...Bm . В результате первый игрок выигрывает величину aij , а второй проигрывает эту величину. Из чисел aij , составим матрицу a11 a11 · · · a1n a21 a22 · · · a2n A = (aij) = .. .. .. .. . . . . am1 am2 · · · amn Матрица A = (aij), i = 1, m, j = 1, n называется платежной матрицей или матрицей игры m × n. В этой матрице строки всегда для стратегий выигрывающего (максимизирующего) иг- рока A, то есть игрока, который стремится к максимизации своего выигрыша. Столбцы отводятся для стратегий проигрывающего игрока B, то есть игрока, который стремится к минимизации критерия эффективности. Нормализация игры - процесс сведения позиционной игры к матричной игре Игрой в нормальной форме - позиционная игра, сведенная к матрич- ной игре Напомним, что, позиционная многоходовая игра является теоретико- игровой моделью конфликтной ситуации, в которой противники для дости- жения своих целей последовательно делают по одному выбору (ходу) из ко- нечного числа возможных способов действий на каждом этапе развития этой ситуации. Решение игры - нахождение оптимальных стратегий обоих игроков и определение це- ны игры Цена игры - ожидаемый выигрыш (проигрыш) игроков. Решение игры может быть найдено либо в чистых стратегиях - когда игрок должен следовать одной единственной стратегии, либо в смешанных, когда игрок должен c определенными вероятностями применять две чистые стратегии или более. Последние в этом случае называются активными. 5 Смешанная стратегия одного игрока - вектор, каждая из компонент которого показы- вает частоту использования игроком соответствующей чистой стратегии. Максимин или нижняя цена игры - число α = max min aij i j Максиминная стратегия (строка) - стратегия, которую выбрал игрок, чтобы максими- зировать свой минимальный выигрыш. Очевидно, что при выборе наиболее осторожной максиминной стратегии игрок A обеспе- чивает себе (независимо от поведения противника) гарантированный выигрыш не менее α. Максимин или верхняя цена игры - число β = min max aij j i Минимаксная стратегия (столбец) - стратегия, которую выбрал игрок, чтобы миними- зировать свой максимальный проигрыш. Очевидно, что при выборе наиболее осторожной минимаксной стратегии игрок B не дает возможности ни при каких обстоятельствах игроку A выиграть больше, чем β. Нижняя цена игры всегда не превосходит верхней цены игры α = max min aij 6 min max aij = β i j j i Теоремма 1 (основная теорема теории матричных игр). Каждая конечная игра имеет по крайней мере одно решение, возможно, в области смешанных стратегий. 6 2. Игры с седловой точкой. Решение в чистых стратегиях Игра с седловой точкой - игра, для которой α = max min aij = min max aij = β i j j i Для игр с седловой точкой нахождение решения состоит в выборе максиминной и мини- макcной стратегий, которые являются оптимальными., Чистая цена игры - общее значение нижней и верхней цены игры α=β=ν 2.1. Примеры Пример 1 Найти решение в чистых стратегиях игры, заданной матрицей 8 4 7 A= 6 5 9 7 7 8 Решение: определим верхнюю и нижнюю цену игры. Для этого найдем минимальное из чисел aij в i-й строке αi = min aij j и максимальное из чисел aij в j-м столбце βj = max aij i Числа αi (минимумы строк) выпишем рядом с платежной матрицей справа в виде доба- вочного столбца. Числа βi (максимумы столбцов) выпишем под матрицей в виде доба- вочной строки: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Находим максимальное из чисел αi α = max αi = 7 i и минимальное из чисел βj β = min βj = 7 j α = β - игра имеет седловую точку. Оптимальной стратегией для игрока является стра- тегия A3 , а для игрока B - стратегия B2 , чистая цена игры ν = 7 Пример 2 Задана платежная матрица: 2 2 1 1 2 0 1 1 1 1 A= 1 1 1 1 2 1 2 1 1 2 Найти решение игры в чистых стратегиях. Решение: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Игра имеет шесть седловых точек. Оптимальными стратегиями будут: A1 и B3 или B4 A3 и B3 или B4 A4 и B3 или B4 8 3. Решение игры в смешанных стратегиях При α ̸= β. случае, когда при выборе своих стратегий оба игрока не имеют информации о выборе другого, игра имеет решение в смешанных стратегиях. SA = (p1 , p2 , ..., pm) - смешанная стратегия игрока A , в которой стратегии A1 , A2 , ..., Am применяются о вероятностями ∑ m p1 , p2 , ..., pm , pi = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2 , ..., qn) - смешанная стратегия игрока B , в которой стратегии B1 , B2 , ..., Bm применяются о вероятностями ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Если: SA∗ - оптимальная стратегия игрока A , SB∗ - - оптимальная стратегия игрока B , то цена игры - ∑ n ∑ m ν= aij · p∗i · qi∗ j=1 i=1 Следующая теорема дает ответ на вопрос, как найти решение для игр 2 × 2, 2 × n, m × 2 Теоремма 2 (как найти решение для игр 2 × 2, 2 × n, m × 2). Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры ν вне зависимости от того, с какими вероятностями будет применять второй игрок стра- тегии, вошедшие в оптимальную (в том числе и чистые стратегии). 9 3.1. Игра 2 × 2 Рассмотрим игру 2 × 2 о матрицей: () a11 a21 a21 a22 Пусть игра не имеет решения в чистых стратегиях. Найдем оптимальные стратегии SA∗ и SB∗ . Сначала определим стратегию SA∗ = (p∗1 , p∗2). Согласно теореме, если сторона A бу- дет придерживаться стратегии ν, то независимо от образа действий стороны B выигрыш будет оставаться равным цене игры ν. Следовательно, если сторона A придерживается оптимальной стратегии SA∗ = (p∗1 , p∗2), то сторона B может, не меняя выигрыша, приме- нять любую из своих стратегий. Тогда при применении игроком B чистой стратегии B1 или B2 игроке получит средний выигрыш равный цене игры: a11 p∗1 + a21 p∗2 = ν ← при стратегии B1 a12 p∗1 + a22 p∗2 = ν ← при стратегии B2 Принимая во внимание, что p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Цена игры: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Аналогично находится оптимальная стратегия игрока B: SB∗ = (q1∗ , q2∗). Принимая во внимание, что q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Примеры Пример 3 Найти решение игры c матрицей () −1 1 A= 1 −1 10 Решение: игра не имеет седловой точки, так как α= -1, β = 1, α ̸= β. Ищем решение в смешанных стратегиях. По формулам для p∗ и q ∗ получаем p∗1 = p∗2 = 0.5 и q1∗ = q2∗ = 0.5, ν = 0 Таким образом, SA∗ = (0.5, 0.5) SB∗ = (0.5, 0.5) Пример 4 Найти решение игры c матрицей () 2 5 A= 6 4 Решение: игра не имеет седловой точки, так как α= 4, β = 5, α ̸= β. Ищем решение в смешанных стратегиях. По формулам для p∗ и q ∗ получаем p∗1 = 0.4, p∗2 = 0.6 и q1∗ = 0.2 q2∗ = 0.8, ν = 4.4 Таким образом, SA∗ = (0.4, 0.6) SB∗ = (0.2, 0.8) 11 3.1.2. Геометрическая интерпретация Игре 2 × 2 можно дать простую геометрическую интерпретацию. Возьмем единичный участок оси абсцисс, каждой точке которого поставим в соответствие некоторую сме- шанную стратегию S = (p1 , p2) = (p1 , 1 − p1) причем вероятность p1 стратегии A1 будет равна расстоянию от точки SA до правого конца участка, а вероятность p2 , стратегии A2 - расстоянию до левого конца. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ В частности, левый конец участка (точка с абсциссой = 0) отвечает стратегии A1 , правый конец участка (x = 1) - стратегии A2 На концах участка восстанавливаются два перпендикуляра к оси абсцисс: ось I − I - откладывается выигрыш при стратегии A1 ось II − II - откладывается выигрыш при стратегии A2 Пусть игрок B применяет стратегию B1 ; она дает на осях I − I и II − II соответственно точки с ординатами a11 и a21 . Проводим через эти точки прямую B1 − B1′ . При любой смешанной стратегии SA = (p1 , p2) выигрыш игрока определяется точкой N на прямой B1 −B1′ , соответствующей точке SA на оси абсцисс, делящей отрезок в отношении p2: p1 . Очевидно, точно таким же способом может быть построена и прямая B2 − B2′ , определя- ющая выигрыш при стратегии B2 . 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Необходимо найти оптимальную стратегию SA∗ , т.е. такую, при которой минимальный выигрыш игрока A (при наихудшем для него поведении игрока B) обращался бы в мак- симум. Для этого строиться нижняя граница выигрыша игрока A при стратегиях B1 , B2 , т.е. ломаная B1 N B2′ ;. На этой границе будет лежать минимальный выигрыш игрока A при любой его смешанной стратегии, точка N , в которой этот выигрыш достигает максимума и определяет решение и цену игры. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ордината точки N есть не что иное, как цена игры ν, ее абсцисса равна ∗2 , а расстояние до правого конца отрезка равно ∗1 , т.е. расстояние от точки SA∗ до концов отрезка равны вероятностям ∗2 и ∗1 стратегий A2 и A1 оптимальной смешанной стратегии игрока A. в данном случае решение игры определялось точкой пересечения стратегий B1 и B2 . Ниже показан случай, когда оптимальной стратегией игрока является чистая стратегия A2 . Здесь стратегия A2 (при любой стратегии противника) выгоднее стратегии A1 , 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .I . .x . 2∗ P . A∗ S = A2 . 2∗ P . A∗ S = A2 Правее показан случай, когда заведомо невыгодная стратегия имеется у игрока B. Гео- метрическая интерпретация дает возможность наглядно изобразить также нижнюю цену игры α и верхнюю β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P На том же графике можно дать и геометрическую интерпретацию оптимальных страте- гий игрока B . Нетрудно убедиться, что доля q1∗ стратегии B1 оптимальной смешанной стратегии SB∗ = (q1∗ , q2∗) равна отношению длины, отрезка KB2 к сумме длин отрезков KB1 и KB2 на оси I − I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 или LB2′ q1∗ = LB2′ + LB1′ Оптимальную стратегию SB∗ = (q1∗ , q2∗) можно найти и другим способом, если поменять местами игроков B и B, а вместо максимума нижней границы выигрыша рассмотреть минимум верхней границы. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Игры 2 × n и m × 2 Решение игр 2 × n и m × 2 основывается на следующей теореме. Теоремма 3. У любой конечной игры m × n существует решение, в котором число ак- тивных стратегий каждой стороны не превосходит наименьшего из чис->ел m и n. Согласно этой теореме у игры 2 × n всегда имеется решение, в котором каждый игрок имеет не более двух активных стратегий. Стоит только найти эти стратегии, и игра 2 × n превращается в игру 2 × 2, которая решается элементарно. Нахождение активных стра- тегий может выполняться графическим способом: 1) строится графическая интерпретация; 2) определяется нижняя граница выигрыша; 3) выделяются на нижней границе выигрыша две стратегии второго игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной ординатой (ес- ли в ней пересекаются более двух прямых, берется любая пара) - эти стратегий представляют собой активные стратегии игрока B. Таким образом, игра 2 × n сведена к игре 2 × 2. Также может быть решена игра m × 2, с той разницей, что строится не нижняя, а верхняя граница выигрыша и на ней ищется не максимум, а минимум. Пример 5 Найти решение игры () 7 9 8 A= 10 6 9 Решение: используя геометрический метод, выделяем активные стратегии. Прямые B1 − B1′ , B2 − B2′ и B3 − B3′ соответствуют стратегиям B1 , B2 , B3 . Ломаная B1 N B2 - нижняя граница выигрыша игрока. Игра имеет решение S∗A = (23 , 31); S∗B = (0.5; 0.5; 0); v = 8. 16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .x . 2∗ P . A∗ S . 1∗ P 17 Предметный указатель игра, 2 ход, 3 2 × 2, 10 личный, 3 2 × 2, 9 случайный, 3 геометрия, 12 чистая цена игры, 7 примеры, 10 2 × n, 9, 16 m × 2, 9, 16 бесконечная, 4 в нормальной форме, 5 конечная, 4 многоходовая, 4 одноходовая, 4 матричная, 5 парная, 2 c нулевой суммой, 2 антагонистическая, 2 неантагонистическая, 2 решение, 5 в смешанных стратегиях, 5, 9 в чистых стратегиях, 5 с седловой точкой, 7 цена, 5 верхняя, 6 нижняя, 6 чистая, 7 максимин, 6 матрица игры, 5 платежная, 5 минимакс, 6 нормализация игры, 5 стратегия, 4 максиминная, 6 минимаксная, 6 оптимальная, 4 смешанная, 5 теория игр, 2 18
Из популярного американского блога Cracked.
Теория игр занимается тем, что изучает способы сделать лучший ход и в результате получить как можно больший кусок выигрышного пирога, оттяпав часть его у других игроков. Она учит подвергать анализу множество факторов и делать логически взвешенные выводы. Я считаю, её нужно изучать после цифр и до алфавита. Просто потому что слишком многие люди принимают важные решения, основываясь на интуиции, тайных пророчествах, расположении звёзд и других подобных. Я тщательно изучил теорию игр, и теперь хочу рассказать вам о её основах. Возможно, это добавит здравого смысла в вашу жизнь.
1. Дилемма заключенного
Берто и Роберт были арестованы за ограбление банка, не сумев правильно использовать для побега угнанный автомобиль. Полиция не может доказать, что именно они ограбили банк, но поймала их с поличным в украденном автомобиле. Их развели по разным комнатам и каждому предложили сделку: сдать сообщника и отправить его за решетку на 10 лет, а самому выйти на свободу. Но если они оба сдадут друг друга, то каждый получит по 7 лет. Если же никто ничего не скажет, то оба сядут на 2 года только за угон автомобиля.
Получается, что, если Берто молчит, но Роберт сдает его, Берто садится в тюрьму на 10 лет, а Роберт выходит на свободу.
Каждый заключенный - игрок, и выгода каждого может быть представлена в виде «формулы» (что получат они оба, что получит другой). Например, если я ударю тебя, моя выигрышная схема будет выглядеть так (я получаю грубую победу, ты страдаешь от сильной боли). Поскольку у каждого заключенного есть два варианта, мы можем представить результаты в таблице.
Практическое применение: Выявление социопатов
Здесь мы видим основное применение теории игр: выявление социопатов, думающих лишь о себе. Настоящая теория игр - это мощный аналитический инструмент, а дилетантство часто служит красным флагом, с головой выдающим человека, лишенного понятия чести. Люди, делающие расчеты интуитивно, считают, что лучше поступить некрасиво, потому что это приведет к более короткому тюремному сроку независимо от того, как поступит другой игрок. Технически это правильно, но только если вы недальновидный человек, ставящий цифры выше человеческих жизней. Именно поэтому теория игра так популярна в сфере финансов.
Настоящая проблема дилеммы заключенного в том, что она игнорирует данные. Например, в ней не рассматривается возможность вашей встречи с друзьями, родственниками, или даже кредиторами человека, которого вы посадили в тюрьму на 10 лет.
Хуже всего то, что все участники дилеммы заключенного действуют так, как будто никогда не слышали ней.
А лучший ход - хранить молчание, и через два года вместе с хорошим другом пользоваться общими деньгами.
2. Доминирующая стратегия
Это ситуация, при которой ваши действия дают наибольший выигрыш, независимо от действий оппонента. Что бы ни происходило - вы всё сделали правильно. Вот почему многие люди при «дилемме заключенного» считают: предательство приводит к «наилучшему» результату независимо от того, что делает другой человек, а игнорирование действительности, свойственное этому методу, заставляет всё выглядеть супер-просто.
Большинство игр, в которые мы играем, не имеет строго доминирующих стратегий, потому что иначе они были бы просто ужасны. Представьте, что вы всегда делали бы одно и то же. В игре «камень-ножницы-бумага» нет никакой доминирующей стратегии. Но если бы вы играли с человеком, у которого на руках надеты прихватки, и он мог показать только камень или бумагу, у вас была бы доминирующая стратегия: бумага. Ваша бумага обернет его камень или приведет к ничьей, и вы не сможете проиграть, потому что соперник не может показать ножницы. Теперь, когда у вас есть доминирующая стратегия, нужно быть дураком, чтобы попробовать что-нибудь другое.
3. Битва полов
Игры интереснее, когда у них нет строго доминирующей стратегии. Например, битва полов. Анджали и Борислав идут на свидание, но не могут выбрать между балетом и боксом. Анджали любит бокс, потому что ей нравится, когда льется кровь на радость орущей толпе зрителей, считающих себя цивилизованными только потому, что они заплатили за чьи-то разбитые головы.
Борислав хочет смотреть балет, потому что он понимает, что балерины проходят через огромное количество травм и сложнейших тренировок, зная, что одна травма может положить конец всему. Артисты балета - величайшие спортсмены на Земле. Балерина может ударить вас ногой в голову, но никогда этого не сделает, потому что ее нога стоит гораздо дороже вашего лица.
Каждый из них хочет пойти на своё любимое мероприятие, но они не хотят наслаждаться им в одиночестве, таким образом, получаем схему их выигрыша: наибольшее значение - делать то, что им нравится, наименьшее значение - просто быть с другим человеком, и ноль - быть в одиночестве.
Некоторые люди предлагают упрямо балансировать на грани войны: если вы, несмотря ни на что, делаете то, что хотите, другой человек должен подстроиться под ваш выбор или потерять все. Как я уже говорил, упрощённая теория игр отлично выявляет глупцов.
Практическое применение: Избегайте острых углов
Конечно, и у этой стратегии есть свои значительные недостатки. Прежде всего, если вы относитесь к вашим свиданиям как к «битве полов», она не сработает. Расстаньтесь, чтобы каждый из вас мог найти человека, который ему понравится. А вторая проблема заключается в том, что в этой ситуации участники настолько не уверены в себе, что не могут этого сделать.
По-настоящему выигрышная стратегия для каждого - делать то, что они хотят, а после, или на следующий день, когда они будут свободны, пойти вместе в кафе. Или же чередовать бокс и балет, пока в мире развлечений не произойдет революция и не будет изобретен боксерский балет.
4. Равновесие Нэша
Равновесие Нэша - это набор ходов, где никто не хочет сделать что-то по-другому после свершившегося факта. И если мы сможем заставить это работать, теория игр заменит всю философскую, религиозную, и финансовую систему на планете, потому что «желание не прогореть» стало для человечества более мощной движущей силой, чем огонь.
Давайте быстро поделим 100$. Вы и я решаем, сколько из сотни мы требуем и одновременно озвучиваем суммы. Если наша общая сумма меньше ста, каждый получает то, что хотел. Если общее количество больше ста, тот, кто попросил наименьшее количество, получает желаемую сумму, а более жадный человек получает то, что осталось. Если мы просим одинаковую сумму, каждый получает 50 $. Сколько вы попросите? Как вы разделите деньги? Существует единственный выигрышный ход.
Требование 51 $ даст вам максимальную сумму независимо от того, что выберет ваш противник. Если он попросит больше, вы получите 51 $. Если он попросит 50 $ или 51 $, вы получите 50 $. И если он попросит меньше 50 $, вы получите 51 $. В любом случае нет никакого другого варианта, который принесет вам больше денег, чем этот. Равновесие Нэша - ситуация, в которой мы оба выбираем 51 $.
Практическое применение: сначала думайте
В этом вся суть теории игр. Не обязательно выиграть и тем более навредить другим игрокам, но обязательно сделать лучший для себя ход, независимо от того, что подготовят для вас окружающие. И даже лучше, если этот ход будет выгоден и для других игроков. Это своего рода математика, которая могла бы изменить общество.
Интересный вариант этой идеи - распитие спиртного, которое можно назвать Равновесием Нэша с временной зависимостью. Когда вы достаточно много пьете, то не заботитесь о поступках других людей независимо от того, что они делают, но на следующий день вы очень жалеете, что не поступили иначе.
5. Игра в орлянку
В орлянке участвуют Игрок 1 и Игрок 2. Каждый игрок одновременно выбирает орла или решку. Если они угадывают, Игрок 1 получает пенс Игрока 2. Если же нет - Игрок 2 получает монету Игрока 1.
Выигрышная матрица проста…
…оптимальная стратегия: играйте полностью наугад. Это сложнее, чем вы думаете, потому что выбор должен быть абсолютно случайным. Если у вас есть предпочтения орла или решки, противник может использовать его, чтобы забрать ваши деньги.
Конечно, настоящая проблема здесь заключается в том, что было бы намного лучше, если бы они просто бросали один пенс друг в друга. В результате их прибыль была бы такой же, а полученная травма могла бы помочь этим несчастным людям почувствовать что-то, кроме ужасной скуки. Ведь это худшая игра из существующих когда-либо. И это идеальная модель для серии пенальти.
Практическое применение: Пенальти
В футболе, хоккее и многих других играх, дополнительное время - это серия пенальти. И они были бы интереснее, если бы строились на том, сколько раз игроки в полной форме смогут сделать «колесо», потому что это, по крайней мере, было бы показателем их физических способностей и на это было бы забавно посмотреть. Вратари не могут чётко определить движение мяча или шайбы в самом начале их движения, потому что, к огромному сожалению, в наших спортивных состязаниях роботы все еще не участвуют. Вратарь должен выбрать левое или правое направление и надеяться, что его выбор совпадет с выбором противника, бьющего по воротам. В этом есть что-то общее с игрой в монетку.
Однако обратите внимание, что это не идеальный пример сходства с игрой в орла и решку, потому что даже при правильном выборе направления вратарь может не поймать мяч, а нападающий может не попасть по воротам.
Итак, каково же наше заключение согласно теории игр? Игры с мячом должны заканчиваться способом «мультимяча», где каждую минуту игрокам один на один выводится дополнительный мяч/шайба, до получения одной из сторон определенного результата, который был показателем настоящего мастерства игроков, а не эффектным случайным совпадением.
В конце концов, теория игр должна использоваться для того, чтобы сделать игру умнее. А значит лучше.
Теория игр как раздел исследования операций – это теория математических моделей принятия оптимальных решений в условиях неопределенности или конфликта нескольких сторон, имеющих различные интересы. Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных решений системы научных и хозяйственных экспериментов, организацией статистического контроля, хозяйственных взаимоотношений между предприятиями промышленности и других отраслей. Формализуя конфликтные ситуации математически, их можно представить как игру двух, трех и т.д. игроков, каждый из которых преследует цель максимизации своей выгоды, своего выигрыша за счет другого.Раздел "Теория игр" представлен тремя онлайн-калькуляторами :
- Оптимальные стратегии игроков . В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры
. Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
- Минимакс . Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
- Симплекс-метод . Используется для решения игры в смешанных стратегиях методами линейного программирования.
- Графический метод . Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
- Итерационный метод Брауна-Робинсона . Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы. Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
Во всех методах применяется проверка на доминирующие строки и столбцы. - Биматричная игра . Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.
- Игры с природой . Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда , Сэвиджа , Гурвица .
Для критерия Байеса необходимо также будет ввести вероятности наступления событий. Если они не заданы, оставьте значения по умолчанию (будут равнозначные события).
Для критерия Гурвица укажите уровень оптимизма λ . Если в условиях данный параметр не задан можно использовать значения 0, 0.5 и 1 .
Во многих задачах требуется находить решение средствами ЭВМ. Одним из инструментов служат вышеприведенные сервисы и функции
