Теория игр

Теория игр изучает и рассматривает методы определения оптимального поведения при управлении системами, в которых характерно наличие конфликтной ситуации (столкновение интересов). Участники конфликтов вынуждены действовать в условиях риска и неопределенности

Модель конфликтной ситуации - игра Описывает: а) множество заинтересованных сторон, которые называются игроками; б) возможные действия каждой из сторон, именуемые стратегиями или ходами; в) интересы сторон, представленные функциями выигрыша (платежа) для каждого из игроков.

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

Классификация игр Бескоалиционными называются игры, в которых игроки не имеют права вступать в соглашения. В коалиционной игре игроки могут вступать в соглашения и образовывать коалиции. В кооперативной игре игроки могут принимать соглашения о своих стратегиях (возможность предварительных переговоров) до начала игры. В некооперативной игре игроки не могут координировать свои стратегии, принимают решения независимо друг от друга.

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

Термины и понятия Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Личный ход – это сознательный выбор игроком одного из возможных действий. Случайный ход – это случайно выбранное действие. Стратегией игрока называется совокупность правил, определяющих выбор действия при каждом ходе в зависимости от сложившейся ситуации.

Решение игры Чтобы решить игру, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, то есть один из игроков получает максимальный выигрыш, когда второй придерживается своей стратегии. Второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны удовлетворять условию устойчивости, то есть любому из игроков должно быть невыгодно отказываться от своей стратегии.

Пример Игра в «орлянку». Если оба выбирают одинаковые стратегии (оба говорят орел), то 1-й выигрывает 1 рубль (а второй проигрывает); если выбирают разные, то 2-й выигрывает. Матрица выигрыша первого игрока (Н 1 ) Матрица выигрыша второго игрока (Н 2 ) ОрелРешка Орел Решка ОрелРешка Орел Решка

Пример Игра в «орлянку». Если оба выбирают одинаковые стратегии (оба говорят орел), то 1-й выигрывает 1 рубль (а второй проигрывает); если выбирают разные, то 2-й выигрывает. Матрица выигрыша первого игрока (Н 1 ) Матрица выигрыша второго игрока (Н 2 ) ОрелРешка Орел1–1 Решка–11 ОрелРешка Орел–11 Решка1–1

Важно помнить Матрица, элементами которой являются выигрыши, соответствующие стратегиям игроков, называется платежной матрицей или матрицей игры. Нижняя цена игры (α) (максиминный выигрыш – максимин) – это гарантированный выигрыш первого игрока при любой стратегии второго игрока Стратегия, соответствующая максимину называется максиминной. Верхняя цена игры (β) (минимаксный выигрыш – минимакс) – это гарантированный проигрыш второго игрока. Стратегия, соответствующая минимаксу, называется минимаксной. Если верхняя и нижняя цены игры совпадают α=β=, то эта цена называется чистой ценой игры или ценой игры. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями или решением игры.

Пример B1B1 B2B2 B3B3 α A1A1 A2A2 A3A3 β Платежная матрица игры

Пример B1B1 B2B2 B3B3 α A1A1 0,50,60,80,5 A2A2 0,90,70,80,7 A3A3 0,6 β0,90,70,80,7 Платежная матрица игры – цена игры. Седловая точка (А 2, В 2 ).

Смешанная стратегия Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Смешанной стратегией называется применение чистых стратегий с разными вероятностями. Сумма вероятностей равна 1. Цена игры будет удовлетворять неравенству: Каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Геометрическая интерпретация игры 22 Пусть имеется два игрока А и В. У каждого из игроков по две стратегии (А 1 и А 2 у игрока А, В 1 и В 2 у игрока В). Игра с нулевой суммой.

Решение игры графическим способом Отрезок В 1 N – минимальный выигрыш игрока А при использовании любой смешанной стратегии, если игрок В выбрал стратегию В 1. Отрезок В 2 N – выигрыш игрока А, если игрок В выбрал стратегию В 2. Оптимальную стратегию определяет точка N, то есть минимальный выигрыш достигает максимума.

Пример Решить графически игру, заданную платежной матрицей: Р= Определим верхнюю и нижнюю цены игры:. Седловая точка отсутствует, будем искать решение в смешанных стратегиях.

Приведение матричной игры к задаче линейного программирования Платежная матрица игры В1В1 В2В2 В3В3 В4В4 α А1А А2А А3А β

Приведение матричной игры к задаче линейного программирования Платежная матрица игры В1В1 В2В2 В3В3 В4В4 α А1А А2А А3А β

Приведение матричной игры к задаче линейного программирования Поскольку, следовательно седловая точка отсутствует, решение будем искать в смешанных стратегиях. Чтобы привести игру к задаче линейного программирования, обозначим: Поскольку, следовательно седловая точка отсутствует, решение будем искать в смешанных стратегиях. Чтобы привести игру к задаче линейного программирования, обозначим:.

Приведение матричной игры к задаче линейного программирования Для первого игрока Для второго игрока Поскольку, следовательно седловая точка отсутствует, решение будем искать в смешанных стратегиях. Чтобы привести игру к задаче линейного программирования, обозначим:. (так как.

Алгоритм Исключить из платежной матрицы заведомо невыгодные стратегии. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m×n рекомендуется симплексный метод, для игр размера 2×2, 2×n, n×2 возможно геометрическое решение.

СПАСИБО ЗА ВНИМАНИЕ! к.т.н., доц. Калашникова Т.В.