Теория игр занимается изучением т.н. конфликтных ситуаций, где сталкиваются интересы индивидов, партий, государств и т. п.
Как утверждал Г.Лейбниц, "...и игры заслуживают изучения; и если какой-нибудь проницательный математик посвятит себя их изучению, то получит много важных результатов, ибо нигде человек не показывает столько изобретательности, как в игре ".
Нет математической теории, которая могла бы дать алгоритм любой реальной игры, но существуют ситуации, подобные игровым и допускающие математический анализ.
Остановимся на классификации игр.
Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называется антагонистической.
В игре могут участвовать два или более игроков. Случай игры с одним участником (пасьянс, управление физическим объектом и т.д.) в сущности является игрой двух лиц, где вторым участником выступает природа (судьба, рок, провидение).
Игроки могут в игре выступать каждый за себя или объединяться в группы. В последнем случае игра называется коалиционной.
Игры, в которых игроки осведомлены о состоянии своем и партнеров, а также о прошлом поведении участников игры, относятся к категории игр с полной информацией (типичные примеры - шахматы, "крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против "природы").
Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой.
Система правил, однозначно определяющая выбор хода игрока в зави-симости от сложившейся ситуации, называется стратегией.
Каждая фиксированная стратегия игрока, где любой ситуации сопоставлен конкретный выбор, называется чистой. В реальности чаще используются т.н. смешанные стратегии, где чистые стратегии смешиваются с некоторыми частотами.
Простейшими являются игры 2 лиц с нулевой суммой.
Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2-свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричной и матрица R = [ Rij / i=1..m, j=1..n ] называется матрицей выигрышей (платежной матрицей).
При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой.
Проведем рассуждения за игрока 1. Если Я воспользуюсь i-м выбором, мой противник для минимизации моего выигрыша сделает тот из своих выборов, который даст min Rij. Соответственно, Я должен использовать тот выбор, который гарантирует мне выигрыш, не меньший
Противник, рассуждая аналогично, приходит к выводу о гарантированном проигрыше, не превышающем
Если в матрице выигрышей существует элемент Rkl = V1 = V2, то говорят о наличии оптимальной политики "в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловой точкой.
Если в матрице выигрышей существует элемент Rkl = V1 = V2, то говорят о наличии оптимальной политики "в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловой точкой.
Статистические решения. Основные понятия
Теория статистических решений может быть истолкована как теория поиска оптимального недетерминированного поведения в условиях неопределенности. Современная концепция статистического решения выдвинута А.Вальдом и считает поведение оптимальным, если оно минимизирует риск в последовательных экспериментах, т.е. математическое ожидание убытков статистического эксперимента. В такой постановке любая задача статистических решений может рассматриваться как игра двух лиц, в которой одним из игроков является "природа".
Выбор наилучших решений в условиях неполной информации является одним из основных занятий людей.
Собираясь в туристический поход, мы укладываем вещи в рюкзак с учетом неизвестной погоды и преследуем цель получить максимум удовольствий, не превращаясь в рекордсмена по переноске тяжестей.
Проектируя гидротехнические сооружения, мы стремимся сделать их надежными, несмотря на непредсказуемые землетрясения, паводки и т.п.
Создавая систему профилактических и аварийных ремонтов, мы преследуем какую-то цель, не зная в точности времени возникновения аварий.
Если процесс определяется повторяющимися ситуациями, то его усредненные характеристики испытывают тенденцию к стабилизации и появляется возможность либо замены случайного процесса детерминированным, либо использования каких-то методов исследования стационарных случайных процессов (в частности, методов теории массового обслуживани я).
Однако большинство процессов характеризуется "дурной неопределенностью" и невозможно найти законы распределения и другие вероятностные характеристики. В таких ситуациях приходится прибегнуть к экспертным оценкам.
Возникает и проблема выбора критерия оптимальности, поскольку решение, оптимальное для каких-то условий, бывает неприемлемым в других и приходится искать некоторый компромисс.
Пусть задан некоторый вектор S = (S1,S2,..,Sn), описывающий n состояний внешней среды, и вектор X = (X1,X2,..,Xm), описывающий m допустимых решений. Требуется найти вектор X* =(0,0,..,0, Xi,0,..,0), который обеспечивает оптимум некоторой функции полезности W(X,S) по некоторому критерию K.
Информация oб указанной функции представляют матрицей размерности m x n c элементами Wij = F(Xi, Sj), где F - решающее правило.