Теория игр

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

Моделями теории игр можно описать экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой. Все такие модели в теории игр принято называть играми.

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

Определения

1. Ситуация наз-ся конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны. 2. Игра - это действительный или формальный конфликт, в котором имеется по крайне мере два участника, каждый из которых стремится к достижению собственных целей.

3. Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются правилами игры. 4. Количественная оценка результатов игры называется платежом. 5. Игра называется парной, если в ней участвуют только два лица.

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

8. Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный средний выигрыш ( минимально возможной средний проигрыш).

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

Пусть 1-й игрок имеет всего m стратегий (i=1,2, …, m), а 2-й – n стратегий (j=1,2,…, n). Тогда игра полностью определяется заданием матрицы, где a ij – выигрыш 1-го игрока при условии, что он выбрал стратегию i (т.е. строку) а 2-й игрок – стратегию j (т.е. столбец). Эти стратегии называют чистыми). Матрица А называется матрицей игры или платежной матрицей.

Схема:

Например, Соответствующие стратегии: i 0 =1(максиминная), j 0 =1;2 (минимаксная).

Теорема. Нижняя цена игры всегда не превосходит верхней цены игры:

Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

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

Пусть – платежная матрица игры. Если она не имеет седловой точки, то единственное решение игры можно найти

1) решив две системы:

2) по формулам: или

Найдем, например, решение игры с платежной матрицей, которая не имеет седловой точки.

1) Составим системы: Решив системы, получим: то есть -решение игры.

2) Найдем решение по формулам:

Сведение матричной игры к двойственной задаче линейного программирования

Пусть матрица игры имеет вид

(1)

Пример. Найти решение игры с матрицей

Решение. Перейдем к положительной матрице, прибавив 3 ко всем элементам матрицы А:

Составим двойственную задачу линейного программирования:

Решим задачу симплексным методом

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 1-я итерация q4q q5q q6q

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 2-я итерация q4q4 02/301/37/310-1/3 q5q5 02/3 0 7/3 4/301-1/3 q1q1 11/3 1 2/3 001/ /3 001/3

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 3-я итерация q4q4 04/70015/71-1/7-2/7 q2q2 12/7 0 14/703/7-1/7 q1q1 11/7 10 2/70-2/73/ /701/72/7

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 4-я итерация q3q3 14/150017/15-1/15-2/15 q2q2 12/ /157/15-1/15 q1q1 11/ /15-4/157/ /152/154/15

Получаем решение двойственной задачи:

Тогда решение игры с матрицей Решение исходной игры: