Теория игр. Игровые модели

Игровые модели теории игр

Теория игр

• Теория игр представляет собой математическую теорию конфликтных ситуаций.
• Ее цель – выработка рекомендаций по разумному поведению участников конфликта
• Впервые описана в 1944 – в монографии фон Неймана и Моргеншерна

• Игра – это ситуация, в которой эффективность решений одного игрока зависит от действий другого игрока.
• Игра развивается по определенным правилам, которые определяют последовательность ходов игроков.
• Конец игры наступает в том случае, когда все возможные ходы игроками сделаны.

• Игра характеризуется:

• Множество заинтересованных сторон – лиц, участников, игроков
• Множеством возможных действий (ходов) для каждого игрока – стратегий
• Интересами игроков, задаваемых с помощью функции выигрыша – функции платежа.

Игры можно классифицировать

• Игры парные (2 игрока) и множественные .
• По количеству возможных стратегий:

• конечные (конечное у каждого игрока)
• бесконечные (хотя бы у одного игрока бесконечное число стратегий)

• По свойствам функции платежа:

• антагонистическая (с нулевой суммой) – выигрыш одного = проигрышу другого,
• игра с постоянной разностью (участники выигрывают и проигрывают одновременно, следовательно выгодно действовать сообща).

• По наличию предварительной договоренности о совместных действиях : кооперативные (есть договоренность) и некооперативные (договоренности нет).

ОПРЕДЕЛЕНИЯ

• Стратегия – совокупность правил, определяющих выбор варианта действия игроком в зависимости от ситуации в игре.
• Целью является отыскание оптимальной стратегии для каждого игрока.
• Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный выигрыш или минимально возможный проигрыш независимо от поведения противника.
• Выбор одной из возможных стратегий и ее реализация называется ходом .
• Ход – может быть личным (выбор стратегии сознателен) и случайным .

Игру можно описать разными способами

• Позиционный – задается в виде дерева шагов.
• Нормальный – задаются допустимые стратегии для каждого игрока и функция выигрыша, которая определяет выигрыш или проигрыш для каждой стратегии. Чаще всего задается в виде платежной матрицы

Конечная парная антагонистическая игра

• Два игрока (I и II) обладают конечным набором стратегий:
• I стратегии А 1 …..A m
• II стратегии B 1 ….B n
• Эта игра размерностью n ×m .

• Предположим, что на некотором ходе игрок I выбрал стратегию A i , а игрок II отвечает стратегией B j
• Тогда W 1 (A i , B j ) – выигрыш , который получит игрок I при этой паре стратегий.
• W 2 (A i , B j ) – выигрыш , который получит игрок II при этой паре стратегий
• Так как игра антагонистическая, то
• W 1 (A i , B j ) + W 2 (A i , B j ) =0
• Или W 1 (A i , B j ) =- W 2 (A i , B j ) = W (A i , B j )

• Обозначим W (A i , B j )=a ij тогда получим платежную матрицу

Каждый положительный элемент это выигрыш I игрока, каждый отрицательный – проигрыш II

Пример

• Играют 2 игрока, каждый называет цифру 1, 2, или 3. Если разница между цифрами игроков положительная, то это выигрыш I игрока, если отрицательная – II игрока, если =0, то ничья.
• I A 1 =1 A 2 =2 A 3 =3
• II B 1 =1 B 2 =2 B 3 =3

• Запишем платежную матрицу.

• Следует найти оптимальную стратегию для I и II игроков.
• Используем основной принцип ТИ:
• Какую бы стратегию не выбрал I игрок, II игрок всегда ответит на нее такой стратегией, при которой выигрыш I будет минимальным и следовательно у II минимальный проигрыш.

• Для поиска лучшей стратегии I игрока найдем минимальный элемент в каждой строке платежной матрицы α i =min a ij
• Среди α i найдем максимальный α=maxα i

α=max (min a ij ) - нижняя цена игры или гарантированный выигрыш I (максимин)

• Стратегия I игрока, при которой достигается α называется максиминой или перестраховочной.
• При этой стратегии I игроку гарантирован выигрыш не менее α .

• Наилучшая стратегия для II игрока.
• Находим максимальный элемент в каждом столбце матрицы β j =max a ij
• Среди β j найдем минимальный β=min β j

β = min (max a ij ) верхняя граница или минимакс.

• Стратегия II игрока, при которой достигается это значение называется минимаксной или перестраховочной для II.
• Если II придерживается своей минимаксной стратегии, то он получает выигрыш не больший, чем β

• В ТИ доказано, что α≤β
• Существуют игры, в которых α=β=γ - чистая цена игры , это игры с седловой точкой.
• Пара оптимальных стратегий (A * I , B * j ) для I и II игроков , при которых достигается чистая цена игры называется седловой точкой платежной матрицы.
• Если игра содержит седловую точку, то говорят, что решение находится в чистых стратегиях.

Пример

α=0

β=0

γ=0

Игра содержит седловую точку (A 3 , B 3 )

• Оптимальные чистые стратегии обладают свойством равновесия : игроки всегда придерживаются своих оптимальных стратегий, так как это выгодно.
• I игрок не может увеличить выигрыш больше чем γ, а II игрок не может уменьшить проигрыш и сделать больше γ

• Если седловой точки в платежной матрице нет, то решение игры ищем в смешанных стратегиях.
• Смешанная стратегия – сложная стратегия, в которой чистые стратегии игроков применяются с некоторыми частотами (вероятностями)

• I игрок . р 1 - вероятность применения стратегии А 1 ,… р i - вероятность применения стратегии А i … р m вероятность применения стратегии А m p i ≥0, i=1…m, ∑ p i =1.
• Чистая стратегия А i называется активной , если вероятность ее использования отлична от нуля p i ≠0 .

• II игрок . q 1 - вероятность применения стратегии B 1 ,… q j - вероятность применения стратегии B j … q n вероятность применения стратегии B n q j ≥0, j=1…n, ∑ q j =1.
• Чистая стратегия B j называется активной , если вероятность ее использования отлична от нуля q j ≠0 .

• Любая антагонистическая парная конечная игра имеет по крайней мере одно решение, возможное в смешанных стратегиях .
• Следовательно игра имеет цену γ , α≤ γ ≤ β
• Игрок I стремится добиться выигрыша = γ , а игрок II стремится минимизировать проигрыш до γ.
• Смешанные стратегии также обладают свойством равновесия , обоим игрокам выгодно их применять.