Теория игр. Основы

несовпадающие цели, значение целевой функции каждой стороны зависит не только

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

действия и т. д.

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

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

если υ > 0 – выигрыш
если υ < 0 – проигрыш
если υ = 0 – ничья

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

выигрышей:
с нулевой суммой и
игры с ненулевой суммой

По виду функций выигрышей:
матричные, биматричные, непрерывные,
выпуклые, сепарабельные, типа дуэлей и др.

По количеству шагов:
одношаговые и многошаговые

действий при каждом личном ходе в зависимости от сложившейся ситуации.

В зависимости от стратегий игры делятся на конечные и бесконечные.
Игра называется конечной, если у каждого игрока имеется в распоряжении только конечное число стратегий (в противном случае игра называется бесконечной).
Процесс игры состоит в выборе каждым игроком одной своей стратегии
В результате каждой партии игры складывается система стратегий s = (s1, s2,…, sn), которая называется ситуацией
Множество всех ситуаций обозначается S = S1, S2, …, Sn и представляет собой декартово произведение множеств, стратегий всех игроков

сумма выигрышей игроков равна нулю (т.е. каждый игрок выигрывает только

за счет других). Самый простой случай – парная игра с нулевой суммой – антагонистическая игра, здесь два игрока четко играют друг против друга.
Число игроков обозначим I, I=(1, 2, …, n).
Бескоалиционной игрой называется система , в которой число игроков I и стратегии игрока Si являются множествами, а платежная функция Hi – функция на множестве S, принимающая вещественные значения
Игра с нулевой суммой:

в ней равно 2, а значения функций выигрышей этих игроков

в каждой ситуации равны по величине и противоположны по знаку

Следовательно, антагонистическая игра также является игрой с нулевой суммой

этом случае имеет следующий вид:

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

строки которой соответствуют стратегиям Ai, а столбцы — стратегиям Bj.
Тогда, в общем виде матричная игра может быть записана следующей платежной матрицей

Верхней чистой ценой игры называется


Игра, для которой

, называется игрой с седловой точкой, где называется ценой игры.
Задача теории игр – поиск оптимальных стратегий (решений).
Решением игры называется пара оптимальных стратегий для игроков А и В, значение цены игры.
Наличие седловой точки означает наличие равновесия в игре.

игры:
Условие существования
седловой точки:

стратегий второго игрока,
– платежная функция или функция выигрыша.
Определение.

Пару называют седловой точкой
функции на , если


или

Графическая интерпретация
седловой точки:

эффективных стратегий
- наилучший гарантированный результат для первого игрока (нижняя цена

игры)

- максиминная стратегия первого игрока, если

- оценка эффективности стратегии y второго игрока, или гарантированный результат

- наилучший гарантированный результат для второго игрока (верхняя цена игры)

- минимаксная стратегия второго игрока, если

на

имела
седловую точку, необходимо и достаточно, чтобы было
выполнено равенство

2) Пусть выполнено равенство (1). Пара тогда и только
тогда является седловой точкой, когда максиминная,
а – минимаксная стратегии первого и второго игроков
соответственно.

Справедливо неравенство:

называют ход, выбранный с вероятностью 1.
Смешанной

стратегией игрока А называется вектор

.

Смешанной стратегией игрока В называется вектор

платежная функция.

чистая стратегия

Пара стратегий называется оптимальной, если

с ненулевой вероятностью.

У каждого из игроков по две стратегии (А1 и А2

у игрока А, В1 и В2 у игрока В). Игра с нулевой суммой.
По оси абсцисс отложим отрезок А1А2, то есть точка А1 изображает стратегию А1 (х=0), А2 – стратегию А2, все промежуточные точки – смешанные стратегии. На оси ординат откладываем выигрыш первого игрока, если второй применил стратегию В1. Аналогично строим второй график, если второй график выбрал стратегию В2.

М1 и М2, соответственно)

В соответствии с принципом минимакса оптимальная стратегия SА* такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум.

при использовании любой смешанной стратегии,
если игрок В выбрал стратегию

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

4/11


a11=4; a12= -1; v=4/11; подставляем в формулу, получаем q1=3/11. Аналогично

q4=8/11.
q2 и q3 = 0, поскольку эти столбцы не соответствуют точке перечения v1=v4