58

Федеральное агентство по образованию

А.Я. Аснина,

Ю.В. Бондаренко,

И.Н. Щепина

Теория игр: бескоалиционные игры в нормальной форме

Учебное пособие для вузов

Воронеж 2006

Утверждено Учебно-методическим советом факультета Прикладной математики, информатики и механики 8 сентября 2006 г., протокол № 1

Рецензент Красова Н.Е.

Учебное пособие подготовлено на кафедре математических методов исследования операций факультета ПММ Воронежского государственного университета.

Рекомендовано для студентов 4 и 5 курсов факультета ПММ Воронежского государственного университета всех форм обучения.

Для специальности: 010501 (510200) – Прикладная математика и информатика

§ 1. Понятие игры. Классификация игр

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

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

Игры можно классифицировать по следующим признакам:

1. По возможности ведения игроками предварительных переговоров игры делятся на:

1. бескоалиционные игры (игроки действуют самостоятельно, независимо друг от друга, и если какие-то соглашения заключаются, то они не являются обязывающими);

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

2. По свойствам выигрыша различают:

1. антагонистические игры (выигрыш одного игрока равен проигрышу второго);

2. неантагонистические (с ненулевой суммой) игры.

2. По характеру получения информации выделяют:

1. игры в нормальной форме (игроки получают информацию до начала игры);

2. динамические игры (игроки получают информацию в процессе развития игры).

2. По числу стратегий игры делятся на:

1. конечные (множество стратегий каждого из игроков конечно);

2. бесконечные (множество стратегий хотя бы одного из игроков бесконечно).

§ 2. Антагонистические игры в нормальной форме

1. Определение антагонистической игры в нормальной форме. Матричные игры

Рассмотрим игру, в которой принимают участие два игрока ­­– P1 и Р2. Первый игрок выбирать любое действие (стратегию, чистую стратегию) x из множества допустимых стратегий X, а второй игрок соответственно стратегию y из множества Y. Пара (x, y) называется ситуацией (а также в дальнейшем ситуацией в чистых стратегиях).

Для каждого игрока задана функция выигрыша ставящая в соответствие каждой ситуации (x,y) величину выигрыша i-го игрока , полученную в данной ситуации. При этом будем считать, что интересы игроков противоположны, то есть выигрыш первого игрока равен проигрышу второго. Тогда функцию выигрыша первого игрока (проигрыша второго) будем обозначать : .

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

Определение 1. Система , где X, Y – непустые множества стратегий первого и второго игроков соответственно, – функция выигрыша первого игрока (проигрыша второго), называется антагонистической игрой в нормальной форме (игрой с нулевой суммой).

Определение 2. Антагонистическая игра, в которой множества стратегий игроков являются конечными множествами, называется матричной игрой.

Пусть m – количество стратегий игрока 1, тогда . Аналогично, n – число стратегий P2, . В этом случае однозначно определяется заданием матрицы , где – величина выигрыша P1 (проигрыша Р2) при условии, что Р1 выбрал стратегию Р2 стратегию