Решение игр в смешанных стратегиях

Математическое моделирование

ЭВМ прочно вошла в нашу жизнь, и практически нет такой области человеческой деятельности, где не применялась бы ЭВМ. ЭВМ сейчас широко используется в процессе создания и исследования новых машин, новых технологических процессов и поиске их оптимальных вариантов; при решении экономических задач, при решении задач планирования и управления производством на различных уровнях. Создание же крупных объектов в ракетотехнике, авиастроении, судостроении, а также проектирование плотин, мостов, и др. вообще невозможно без применения ЭВМ.

Для использования ЭВМ при решении прикладных задач, прежде всего прикладная задача должна быть "переведена" на формальный математический язык, т.е. для реального объекта, процесса или системы должна быть построена его математическая модель.

Слово "Модель" происходит от латинского modus (копия, образ, очертание). Моделирование - это замещение некоторого объекта А другим объектом Б. Замещаемый объект А называется оригиналом или объектом моделирования, а замещающий Б - моделью. Другими словами, модель - это объект-заменитель объекта-оригинала, обеспечивающий изучение некоторых свойств оригинала.

Целью моделирования являются получение, обработка, представление и использование информации об объектах, которые взаимодействуют между собой и внешней средой; а модель здесь выступает как средство познания свойств и закономерности поведения объекта.

Математическое моделирование - это средство изучения реального объекта, процесса или системы путем их замены математической моделью, более удобной для экспериментального исследования с помощью ЭВМ.

Математическое моделирование — процесс построения и изучения математических моделей реальных процессов и явлений. Все естественные и общественные науки, использующие математический аппарат, по сути занимаются математическим моделированием: заменяют реальный объект его моделью и затем изучают последнюю. Как и в случае любого моделирования, математическая модель не описывает полностью изучаемое явление, и вопросы о применимости полученных таким образом результатов являются весьма содержательными. Математическая модель — это упрощенное описание реальности с помощью математических понятий.

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

При математическом моделировании исследование объекта осуществляется посредством модели, сформулированной на языке математики с использованием тех или иных математических методов.

Путь математического моделирования в наше время гораздо более всеобъемлющ, нежели моделирования натурного. Огромный толчок развитию математического моделирования дало появление ЭВМ, хотя сам метод зародился одновременно с математикой тысячи лет назад.

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

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

Все модели можно разделить на два класса:

1. вещественные,
2. идеальные.

В свою очередь вещественные модели можно разделить на:

1. натурные,
2. физические,
3. математические.

Идеальные модели можно разделить на:

1. наглядные,
2. знаковые,
3. математические.

Вещественные натурные модели - это реальные объекты, процессы и системы, над которыми выполняются эксперименты научные, технические и производственные.

Решение игр в смешанных стратегиях

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

	B1	B2
A1	a11	a12
A2	a21	a22

Решение игры и , где , , , . Цена игры равна .
Пример. Игрок А прячет в одной из рук монету. Игрок В пытается угадать руку с монетой. Если В не угадывает, то А получает от В 1 у.е. Если В угадывает руку с монетой и эта рука правая, то он получает от А 1 у.е. Если В находит монету в левой руке, то он получает от А 2 у.е. Определить оптимальные стратегии поведения для каждого игрока и средний выигрыш для А.
Пусть стратегии игроков: А₁ – спрятать в правой; В₁ – искать в правой; А₂ – спрятать в левой; В₂ – искать в левой. Игровая матрица для данной ситуации относительно игрока А имеет вид:

	B1	B2
A1	-1
A2		-2

Тогда вероятности чистых стратегий в смешанной равны:
, , , . Цена игры равна .
Таким образом, игроку А нужно случайно чередовать руки с монетой, но в правой руке прятать в среднем в трех случаях из пяти, а в левой в двух случаях из пяти. В это случае в каждой игре в среднем А получит (-1/5) руб., то есть теряет 20 коп., игра для А не выгодная. Для игрока В выгодно также чередовать руки в которых он ищет монету, но в правой руке искать в 3 случаях из 5, что приведет к среднему выигрышу для него в 20 коп. за игру.
В некоторых случаях удается аналогичным образом решить и игровые ситуации с платежными матрицами, большего размера, упростив их до игры 2х2. При этом используются следующие правила:
1) Если все элементы какой-либо строки платежной матрицы не превышают соответствующих элементов любой другой строки, то строка с меньшими элементами соответствует стратегии, которая для игрока А заведомо не выгодна при любом ответе игрока В. Поэтому из платежной матицы строку с меньшими элементами можно вычеркнуть, тем самым выведя из рассмотрения соответствующую ей стратегию.
2) С другой стороны, для игрока В невыгодна заранее, независимо от ответа А, стратегия, которой соответствует столбец платежной матрицы, у которого все элементы больше или равны соответствующим элементам любого другого столбца. Столбец с большими элементами также можно вывести из рассмотрения, вычеркнув из платежной матрицы.
Пример.
Директор транспортной компании А, оказывающей транспортные услуги по перевозке пассажиров в областном центре, планирует открыть один или несколько маршрутов: А₁, А₂, А₃ и А₄. Для этого было закуплено 100 микроавтобусов. Он может поставить весь транспорт на одном из маршрутов (наиболее выгодном), либо распределить по нескольким маршрутам. Спрос на транспорт, а соответственно и прибыль компании во многом зависит от того, какие маршруты в ближайшее время откроет главный конкурент - компания В. Ее руководство полностью владеет ситуацией и может открыть несколько из пяти маршрутов В₁, В₂, В₃, В₄ и В₅. Оценки прибыли компании А (млн. руб.) при любом ответе В представлена платежной матрицей:

	В1	В2	В3	В4	В5
А1
А2
А3
А4

Находим оптимальное распределение прибыли по маршрутам и ожидаемую прибыль.
Вычеркиваем из таблицы второй столбец, т.к. все его элементы больше или равны элементам третьего. Вычеркиваем четвертую строку, т.к. ее оставшиеся элементы меньше элементов третьей. Элементы первого столбца больше элементов третьего, вычеркиваем первый столбец. Вторую строку вычеркиваем в результате сравнения с первой. Четвертый столбец вычеркиваем после сравнения с третьим. В результате получаем матрицу:

которая эквивалентна матрице:

	B3	B5
A1
A3

Тогда вероятности чистых стратегий компании А в смешанной равны: , . Цена игры равна . Следовательно, 1/6 часть автопарка (17 машин) нужно направить на маршрут А₁, а остальные 5/6 парка (83 машины) на маршрут А₃. Маршруты А₂ и А₄ использовать не рационально. При этом прибыль, не зависимо от ответа компании В будет составлять 34/6 млн. руб.
Рассмотрим случай, когда платежную матрицу нельзя упростить до размера 2х2. Пусть упрощенная платежная матрица имеет вид: . Тогда для нахождения вероятностей и смешанных стратегий и , необходимо решать прямую и двойственную задачи линейного программирования вида:

Из решения задач линейного программирования находятся цена игры и вероятности состояний .
Пример. Построить прямую и двойственную задачи линейного программирования для решения матричной игры, заданной платежной матрицей: .
Прямая и двойственная задачи линейного программирования имеют вид:

Из решения можно найти игры цену игры и вероятности состояний .

Вещественные физические модели - это макеты, муляжи, воспроизводящие физические свойства оригиналов (кинематические, динамические, гидравлические, тепловые, электрические, световые модели).

Вещественные математические - это аналоговые, структурные, геометрические, графические, цифровые и кибернетические модели.

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

Идеальные знаковые модели - это символы, алфавит, языки программирования, упорядоченная запись, топологическая запись, сетевое представление.

Идеальные математические модели - это аналитические, функциональные, имитационные, комбинированные модели.

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

Элементы теории игры

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

Проиллюстрируем это на примере игры . Дадим ей геометрическую интерпретацию — уже пространственную. Три наши стратегии , изобразим тремя точками на плоскости ; первая лежит в начале координат (рис.1). вторая и третья — на осях Ох и Оу на расстояниях 1 от начала.

рис 1.

Через точки проводятся оси I-I, II-II и III-III, перпендикулярные к плоскости . На оси I-I откладываются выигрыши при стратегии на осях II-II и III-III — выигрыши при стратегиях . Каждая стратегия противника изобразится плоскостью, отсекающей на осях I-I, II-II и III-III, отрезки, равные выигрышам

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

рис 2

Для этого семейства также можно построить нижнюю границу выигрыша, как мы это делали в случае, и найти на этой границе точку N с максимальной высотой нал плоскостью . Эта высота и будет ценой игры .

Частоты стратегий в оптимальной стра­тегии будут определяться координатами (x, у) точки N, а именно:

Однако такое геометрическое построение даже для случая нелегко осуществимо и требует большой затраты времени и усилий воображения. В общем же случае игры оно переносится в - мерное пространство и теряет всякую наглядность, хотя употребление геометрической терминологии в ряде случаев может оказаться полезным. При решении игр на практике удобнее пользоваться не геометрическими аналогиями, а расчетными аналитическими методами, тем более, что для решения задачи на вычислительных машинах эти методы единственно пригодны.

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

Здесь мы вкратце остановимся на одном расчетном методе решения игр — на так называемом методе «линейного программирования».

Для этого дадим сначала общую постановку задачи о нахождении решения игры . Пусть дана игра с т стратегиями игрока А и n стра­тегиями игрока В и задана платежная ма­трица

Требуется найти решение игры, т. е. две оптимальные смешанные стратегии игроков А и В

где (некоторые из чисел и могут быть равными нулю).

Наша оптимальная стратегия S*_A должна обеспечивать нам выигрыш, не меньший , при любом поведении про­тивника, и выигрыш, равный , при его оптимальном пове­дении (стратегия S*_B ).Аналогично стратегия S*_B должна обе­спечивать противнику проигрыш, не больший , при любом нашем поведении и равный при нашем оптимальном пове­дении (стратегия S*_A ).

Величина цены игры в данном случае нам неизвестна; будем считать, что она равна некоторому положительному числу. Полагая так, мы не нарушаем общности рассуждений; для того чтобы было > 0, очевидно, достаточно, чтобы все элементы матрицы были неотрицательными. Этого всегда можно добиться, прибавляя к элементам доста­точно большую положительную величину L;при этом цена игры увеличится на L, а решение не изменится.

Пусть мы выбрали свою оптимальную стратегию S*_A . Тогда наш средний выигрыш при стратегии противника будет равен:

Наша оптимальная стратегия S*_A обладает тем свойством, что при любом поведении противника обеспечивает выигрыш не меньший, чем ; следовательно, любое из чисел не может быть меньше . Получаем ряд условий:

(1)

Разделим неравенства (1) на положительную величину и обозначим :

Тогда условие (1) запишется виде

(2)

где — неотрицательные числа. Так как величины удовле­творяют условию

(3)

Мы хотим сделать свой гарантированный выигрыш максимально возможным; очевидно, при этом правая часть равенства (3) принимает минимальное значение.

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

была минимальной.

Обычно при решении задач, связанных с нахождением экстремальных значений (максимумов и минимумов), функцию дифференцируют и приравнивают производные нулю. Но такой прием в данном случае бесполезен, так как функ­ция Ф, которую нужно обратить в минимум, линейна, и ее производные по всем аргументам равны единице, т. е. нигде не обращаются в нуль. Следовательно, максимум функции достигается где-то на границе области изменения аргумен­тов, которая определяется требованием неотрицательности аргументов и условиями (2). Прием нахождения экстре­мальных значений при помощи дифференцирования непри­годен и в тех случаях, когда для решения игры опреде­ляется максимум нижней (или минимум верхней) границы выигрыша, как мы. например, делали при решении игр .Действительно, нижняя граница составлена из участков прямых линий, и максимум достигается не в точке, где производная равна нулю (такой точки вообще нет), а на границе интер­вала или в точке пересечения прямолинейных участков.

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

Задача линейного программирования ставится следующим образом.

Дана система линейных уравнений:

(4)

Требуется найти неотрицательные значения величин удовлетворяющие условиям (4) и вместе с тем обращающие в минимум заданную однородную линейную функцию величин (линейную форму):

Легко убедиться, что поставленная выше задача теории игр является частным случаем задачи линейного программирование при

С первого взгляда может показаться, что условия (2) не эквивалентны условиям (4), так как вместо знаков равенства они содержат знаки неравенства. Однако от знаков неравенства легко избавиться, вводя новые фиктивные неотрицательные переменные и записывая условия (2) в виде:

(5)

Форма Ф , которую нужно обратить в минимум, равна

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