- •Лекция №1 Введение в системный анализ
- •Основные понятия теории систем
- •Лекция №2 Модели систем
- •Структурный анализ систем
- •Элементы теории графов
- •Алгебраическое представление графа
- •Лекция №3 Ранжирование элементов систем
- •Лекция №4 Элементы теории сетей
- •Сетевое планирование
- •Лекция №5 Функциональные модели
- •Организации
- •Лекция №6 Тезаурус
- •Управление
- •Программное управление
- •Адаптивное управление
- •Лекция №7 Рефлексивное управление
- •Развитие
- •1. Линейные связи
- •2. Ограничивающие связи
- •3. Запаздывающие связи
- •4. Селектирующие связи
- •Лекция №8 Информационное описание
- •Лекция №9 Исследование операций
- •Элементы теории игр
- •Игры двух лиц с нулевой суммой
- •Лекция №10 Смешанные стратегии
- •Методы определения оптимальных стратегий
- •Итерационный метод решения игр
- •Лекция №11 Игры двух лиц с ненулевой суммой
- •Игры nлиц
- •Игровое моделирование
- •Лекция №12 Теория полезности История вопроса
- •Предпочтение и полезность
- •Лекция №13 Теория ожидаемой полезности
- •Аксиомы для линейной функции полезности
- •Субъективная вероятность
- •Лекция №14 Теория принятия решений
- •Аксиомы теории принятия решений
- •Прогнозирование
- •Лекция №15 Автоматизированные системы управления процессами
- •Лекция №16 Системы искусственного интеллекта
- •Экспертные системы
- •Приложение 1 Элементы булевой алгебры
- •Приложение 2 Общие сведения об операторах
- •Содержание
Игры двух лиц с нулевой суммой
Пусть в игре участвует два игрока AиБ, партия состоит из одного хода игрокаAи ответного хода игрокаБ. Ход игрокаAзаключается в выборе одной изnвозможных стратегий. Ход игрокаБсостоит из выбора одной изmвозможных стратегий. Каждая партия игры состоит в том, что партнеры выбирают по одной своей стратегии, в результате чего определяются платежи игрокам. Пусть игрокAвыбирает стратегию, игрокБ - стратегию. В результате осуществления операции платеж игрокаAигрокуБсоставляет, а платеж игрокаБигрокуA. Такая игра является игрой с нулевой суммой, так как выигрыш игрокаАравен проигрышу игрокаБ.
Игры, для которых сумма платежей одинакова для всех возможных партий, называются играми с нулевой суммой.
Итак, мы рассматриваем конечную игру двух лиц с нулевой суммой. Для нее можно составить матрицу платежей, которая полностью характеризует игру.
Игра, заданная платежной матрицей, называется прямоугольной или матричной игрой, приведенной к нормальной форме.
В каждой партии игрок Aстремится так выбрать свою стратегию, чтобы величина его платежа была минимально возможной. В свою очередь игрокБстремится так выбрать стратегию, чтобы максимизировать выигрыш. Задача состоит в том, чтобы указатьоптимальные стратегиикаждой стороны, т.е. такие стратегии, которые при многократном повторении игры обеспечиваютБмаксимально возможный средний выигрыш, а игрокуА- минимально возможный средний проигрыш.
Решение игровых задач основывается на принципе минимакса. Этот принцип предписывает игрокам выбирать свою стратегию в расчете на наихудший для себя образ действий противника. Суть этого принципа понятна из следующих рассуждений.
Рассмотрим ситуацию с позиции игрока A. На каждую выбранную стратегиюигрокБответит такой стратегией, чтобы максимизировать выигрыш
.
Следовательно, из всех возможных стратегий игроку Аследует выбрать такую, чтобы минимизировать проигрыш. В этом случае
.
Определенная так величина aназываетсяверхней ценой игрыилиминимаксом, а стратегия- минимаксной стратегиейA. Верхняя цена игры - это тот гарантированный уровень, больше которогоAне заплатит при любом поведенииБ, если будет применять свою минимаксную стратегию.
Рассмотрим теперь ситуацию с позиции игрока Б . При каждой стратегиисторонаAприменит такую стратегию, чтобы проиграть как можно меньше :
.
Следовательно, наилучший из наихудших для Бвариантов отвечает такой стратегии, что
.
Величина b, определенная таким образом, называетсянижней ценой игрыили максимином. Нижняя цена игрыb- гарантированный выигрышБпри любом ответеA.
Если
,
то минимаксные стратегии игроков являются оптимальными, т.е. если один из игроков воспользуется минимаксной стратегией, а другой не следует своей минимаксной стратегии, то это может только уменьшить выигрыш (увеличить проигрыш) этого игрока.
В общем случае .
Равновесие пары стратегий определяется для игры двух лиц так же, как и в общем случае игры nлиц. То, что платеж описывается скалярной величиной, а не вектором, упрощает дело.
Ситуация равновесия пары стратегий известна так же, как седловая точка.
Def. Седловой точкойназывается некоторый элементматрицы платежей Rтакой, чтопри любыхi, j.
Таким образом, седловая точка одновременно является наибольшим элементом строки kи наименьшим элементом столбцаl.
Если в некоторой игре существует более одной седловой, то представляет интерес следующая теорема.
Теорема. Пусть и-седловые точки.Тогда итакже являются седловыми точками и, кроме того .
Кратко данную теорему можно выразить так: седловые точки эквивалентны и взаимозаменяемы.
Следует отметить, что сформулированное свойство не распространяется на другие игры, т.е. не выполняется для игр с ненулевой суммой или для игр трех и более лиц.
Теорема.Пусть-седловая точка игры с матрицейR.Тогда.И наоборот,если,то существует седловая точка,причем.
Если , то матричная игра не имеет седловой точки, и минимаксные стратегии не дают решения игры, так как не являются наилучшими ни для одной из сторон. В этом случае говорят, что игра не имеет решения в чистых стратегиях.