Теория игр

1. ТЕОРИЯ ИГР

Санкт-Петербургский колледж информационных технологий
ТЕОРИЯ ИГР
Учебное пособие по дисциплине
«Математическое моделирование»
Преподаватель Алексеева Н.Н.

2. ТЕОРИЯ ИГР

метод моделирования, используемый для
оценки воздействия решения на конкурентов
(теория принятия решений в условиях
неопределенности)

3. Основные понятия

Конфликт - столкновение интересов.
Разрешение конфликта - согласование интересов между участниками.
Игра в теории игр – математическая модель конфликтной ситуации.
Компоненты игры:
1. Игрок – это сторона, отстаивающая единые интересы. Игроком может
быть не только физическое лицо, но и предприятие, фирма, корпорация.
Иногда в качестве игрока принимается природа (некая среда, формирующая
обстоятельства).
2. Стратегия игрока - выбираемые игроком действия (правило выбора
некоторого действия на основе известной ему информации о данной
ситуации).
3. Выигрыши игроков в соответствующих ситуациях - степень
осуществления целей каждого игрока в ситуации, которая складывается в
результате выбора игроками своих стратегий.

4. Классификация игр

По выигрышу
По характеру
получения
информации
По
количеству
стратегий
• Антагонистические игры – игры с нестрогим соперничеством,
в которых возможен обоюдный интерес;
• Игры с нулевой суммой - игры со строгим соперничеством, в
которых игроки имеют противоположные интересы;
• Игры в нормальной форме – игроки получают всю
информацию до игры;
• Динамические игры – информация поступает во
время игры;
• Конечные игры
• Бесконечные игры
• Имитирующие игры

5. Основная задача теории игр

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

6. Матричная игра с нулевой суммой

Матричной игрой называется игра, осуществляемая по
следующим правилам:
1. В игре участвуют два игрока;
2. Каждый из игроков обладает конечным набором стратегий;
3. Игра заключается в том, что каждый из игроков, не имея
информации о действиях противника, делает один ход (выбирает
одну из своих стратегий). Результатом выбора игроками стратегий
является выигрыш и проигрыш в игре.
4. И выигрыш, и проигрыш выражаются числами.
Матричная игра называется игрой с нулевой суммой, если в
этой игре выигрыш одного игрока равняется проигрышу другого
игрока.

7. Платежная матрица игры

8.

Таким образом, если игрок A будет придерживаться максиминной
стратегии, то ему гарантирован выигрыш, не меньший, чем α , при
любом поведении игрока В.
Проанализируем теперь платежную матрицу с точки зрения игрока
B, заинтересованного в том, чтобы игрок A выиграл, как можно
меньше.
Если игрок B выберет стратегию Bj , то все возможные выигрыши
игрока A будут элементами j - го столбца платежной матрицы С. В
наихудшем для игрока B случае, когда игрок A применяет
стратегию, соответствующую максимальному элементу этого
столбца, выигрыш игрока B будет равен числу max(i) Cij.
Следовательно, игроку B нужно выбрать такую стратегию, для
которой число max(i) Cij минимально.
Число β =min(i) max(j) C ij называется верхней ценой игры, а
стратегия игрока B, соответствующая наименьшему из чисел
max(i) Cij , называется минимаксной.

9.

Таким образом, если игрок A будет придерживаться максиминной
стратегии, то ему гарантирован выигрыш, не меньший, чем α , при
любом поведении игрока В.
Проанализируем теперь платежную матрицу с точки зрения игрока
B, заинтересованного в том, чтобы игрок A выиграл, как можно
меньше.
Если игрок B выберет стратегию Bj , то все возможные выигрыши
игрока A будут элементами j - го столбца платежной матрицы С. В
наихудшем для игрока B случае, когда игрок A применяет
стратегию, соответствующую максимальному элементу этого
столбца, выигрыш игрока B будет равен числу max(i) Cij.
Следовательно, игроку B нужно выбрать такую стратегию, для
которой число max(i) Cij минимально.
Число β =min(i) max(j) C ij называется верхней ценой игры, а
стратегия игрока B, соответствующая наименьшему из чисел
max(i) Cij , называется минимаксной.

10.

Таким образом, если игрок B применяет минимаксную стратегию,
то игрок A не может выиграть больше, чем b .
Принцип осторожности, заставляющий игроков придерживаться
максиминной и минимаксной стратегий соответственно, называют
«Принципом минимакса», а минимаксную стратегию и
максиминную стратегию называют общим термином
«Минимаксные стратегии».

11. Пример

12. Игры с седловой точкой

Игра называется игрой с седловой точкой, если ее
нижняя и верхняя цены совпадают, то есть выполняется равенство
α =max min Сij = min max Сij = β
Для игры с седловой точкой общее значение нижней и
верхней цены игры
V = α = β называется ценой игры.

13. Игры с седловой точкой

Игра называется игрой с седловой точкой, если ее
нижняя и верхняя цены совпадают, то есть выполняется
равенство
α =max min Сij = min max Сij = β
Для игры с седловой точкой общее значение нижней и
верхней цены игры
V = α = β называется ценой игры.
Замечание 1. В Примере нижняя и верхняя цены игры совпадают
и равны 3, т.е. рассмотренная игра является игрой с седловой
точкой.
Замечание 2. Максиминной стратегией является стратегия
A 2 , минимаксной стратегией является стратегия B3.

14. Седловая точка

Рассмотрим теперь для игры с седловой точкой такой элемент
платежной матрицы Сi j , который соответствует минимаксным
стратегиям Ai и Bj . Этот элемент является одновременно
минимальным в своей строке и максимальным в своем столбце, и
выполняются неравенства
α =max Сij = min Сij= β
Следовательно, выполняется равенство Сi j =V .
Элемент платежной матрицы Сi j называется седловой точкой.
Замечание 3. В примере седловой точкой является элемент С23
платежной матрицы. Этот элемент равен 3 и, конечно же,
совпадает с ценой игры.

15. Игры без седловой точкой

Найти нижнюю и верхнюю цены игры
с платежной матрицей:
Найдем нижнюю и верхнюю
цену игры:
Нижняя цена игры α = max{-1, 2, -2,1}= 2 .
Верхняя цена игры β = min{5, 4, 5}= 4.

16. Игры без седловой точкой

Замечание 1. В примере2 нижняя цена игры отличается
от верхней цены игры, следовательно, игра является
игрой без седловой точки.
Максиминной стратегией является стратегия A2 .
Минимаксной стратегией является стратегия B2 .
Для любой игры без седловой точки выполнено
неравенство α < β .