Математическая теория игр

Одним из общепринятых коллективных принципов оптимальности является ситуация равновесия.

Ситуация и⁰ называется ситуацией равновесия, если выполнены следующие условия для любого i (1.8)

 

.    (1.8)

 

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

Основные  недостатки ситуации равновесия:

1. Ситуация равновесия не всегда существует.
2. В случае неединственности ситуации равновесия нет разумного основания выбора одной из них.
3. Могут существовать неравновесные ситуации, в которых выигрыши всех игроков превышают их выигрыши в ситуации равновесия.

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

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

Выбор оптимальной по Парето точки относится к коллективным принципам принятия рациональных решений.

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

1.3 Решение матричной игры

 

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

Пусть первый игрок выберет j-ю стратегию, тогда в худшем для него случае он получит выигрыш величиной (1.9)

 

      (1.9)

где m - количество строк в матрице игры, т.е. количество чистых стратегий второго игрока.

 

 Пусть второй игрок выберет такую строку, т.е. i-ю стратегию ( n-количество столбцов в матрице игры), при которой этот минимум максимальный.

Число называется нижней ценой игры или максимином, а, соответствующая ему стратегия (строка) - максиминной.

Аналогично, второй игрок, также исходя из наихудшего исхода, выберет i-ю стратегию, тогда в худшем для него случае он потеряет величину (1.10)

 

.      (1.10)

 

Тогда он должен выбрать такой столбец, т.е. j-ю стратегию, при которой этот максимум минимальный.

Число называется верхней ценой игры или минимаксом, а, соответствующая ему стратегия игрока (столбец) - минимаксной.

Если для некоторой игры верхняя и нижняя цены равны, т.е. выполняется равенство (1.11)

 

    (1.11)

где а_i*_j* - соответствующий элемент матрицы игры, для этого элемента выполняется неравенство:

 

Сравнивая его с  видим, что оказывается ситуация является равновесной, т.е. оптимальной. Величина является ценой игры.

Игра, для которой  называется игрой с седловой точкой.

Решение матричной игры в смешанных стратегиях.

Игра, заданная некоторой  матрицей, может не иметь седловой точки.

Теорема. Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях. При этом если А - платежная матрица, - оптимальная смешанная стратегия первого игрока, a - второго, то число является ценой игры.

Нахождение такого решения  сводится к решению задачи линейного  программирования, точнее говоря к  решению пары взаимосопряженных задач. Рассмотрим, что это за задачи.

Итак, пусть А - платежная матрица игры размерности (1.12)

 

.     (1.12)

 

Так как в смешанных стратегиях всегда существует оптимальная стратегия первого игрока и цена игры, то для нее должно выполняться неравенство (1.13)

 

.     (1.13)

 

Это означает, что при любой чистой стратегии второго игрока (т.е. любого столбца матрицы А) его проигрыш будет не меньше цены игры (т.е. максимина). Пусть . Введем обозначение тогда условие можно переписать в виде (1.14)

 

.       (1.14)

 

Разделив  обе части неравенства  на v, получаем (1.15)

 

.     (1.15)

 

Поскольку целью первого игрока является максимизация величины v, т.е. минимизация величины 1/v, то нахождение его оптимальной смешанной стратегии сводится к решению следующей задачи линейного программирования при ограничениях (1.16)

 

     (1.16)

 

Найдя решение y* этой задачи легко переходим к U* по формулам (1.17)

 

.    (1.17)

 

Рассуждая совершенно аналогично получим, что задача нахождения оптимальной смешанной стратегии второго игрока сводится к нахождению вектора являющегося решением следующей задачи линейного программирования при ограничениях (1.18)

 

     (1.18)

 

Найдя решение x* этой задачи, легко переходим к z* по формулам (1.19)

.    (1.19)

1.4 Виды теории игр

 

Игра с природой. Кроме антогонистических рассматривают так называемые неантогонистические игры. В этом случае предполагают, что действия противника не носят характер строгого противостояния. Его интересы могут быть разными и в общем случае не совпадающими с нашими, однако они не являются «злонамеренно» направленными против нас. Рассмотрим простейший пример такой ситуации.

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

Будем для определенности считать, что известна смешанная  стратегия  , постоянно применяемая вторым игроком. Причем она совершенно не обязательно является оптимальной для него. В этих условиях возникает вопрос, как первому игроку построить стратегию U* максимизирующую его ожидаемый выигрыш. Ответ на этот вопрос даётся просто. А именно оптимальной будет та чистая стратегия, для номера i* которой достигается максимум (1.20)

 

.     (1.20)

 

Кооперативная теория. Другим классом неантогонистических игр являются кооперативные игры.

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

Быть может, самым простым  будет при этом выделение некоторого множества игроков называемого коалицией (бескоалиционность рассматриваемых игр в том и состоит, что никакие коалиции первоначально в правилах игры не предусмотрены), и рассмотрение антагонистической игры Г(К) коалиции К как единого игрока против ее «окружения» I/К в целом. При этом комбинации стратегий игроков из К (и из I\К) составляют стратегии К (соответственно стратегии I/К), а сумма выигрышей игроков из К - выигрыш коалиции К. Значение v(K) этой игры естественно понимать как силу коалиции К в общей игре Г.

Соответствие  для каждой коалиции в условиях бескоалиционной игры Г называется ее характеристической функцией и обозначается через v_r.

Характеристическая функция v_r дает представление о возможностях коалиций и отдельных игроков в условиях игры Г даже без указания множества стратегий и функций выигрыша в ней. Изучение характеристических функций игр и составляет содержание кооперативной теории игр.

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

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

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

 

2 МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ИГР

2.1 Экономическая задача, сводящаяся к решению математической теории игр

 

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

Задача 1. Руководитель цеха рассматривает три возможных решения относительно существующего фрезерного станка.

1. Модифицировать имеющийся станок, установив на нем автоматическую подачу (АП).

2. Купить новый станок с программным управлением (ПУ).

3. Заменить станок обрабатывающим центром (ОЦ).

Три альтернативы оцениваются  на основе двух критериев: денежный и функциональный. Следующая таблица содержит необходимые данные.

 

Таблица 2.1 –Исходные  данные

Критерий	АП	ПУ	ОЦ
Денежный
Начальная стоимость (долл.)	12000	25000	120000
Стоимость обслуживания (долл.)	2000	4000	15000
Стоимость обучения персонала (долл.)	3000	8000	20000
Функциональный
Производительность (изделия/день)	8	14	40
Время наладки (минуты)	30	20	3
Металлические отходы (фунты в день)	440	165	44

 

Руководитель считает, что денежный критерий в полтора  раза важнее функционального. Кроме того, производительность в два раза важнее времени наладки и в три раза важнее, чем количество получаемых металлических отходов. Показатель, связанный со временем наладки, считается в четыре раза важнее показателя, связанного с количеством металлических отходов. Что же касается денежного критерия, то руководитель считает, что стоимость обслуживания и стоимость обучения персонала одинаково важны, а начальная стоимость в два раза важнее каждого из этих двух показателей.

Проанализируйте описанную ситуацию и дайте соответствующие рекомендации.

Задача 2. Компания использует каталог товаров для продажи, включающий более 200 тыс. наименований, хранящихся на многих региональных складах. В прошлом компания считала важным иметь точный перечень запасов на каждом складе. Поэтому каждый год проводился переучет – интенсивная и неприятная работа, которая неохотно выполнялась всеми складами. Компания для проверки качества складских операций в регионе сопровождала каждый переучет ревизией, которая охватывала около 100 наименований на каждом складе. Результаты проверки обнаружили, что в среднем лишь 64 % наименований на каждом складе соответствовали действительной инвентарной описи, что является неприемлемым. Дабы исправить ситуацию, компания распорядилась чаще проводить переучет дорогих и быстро реализуемых товаров. Системному аналитику была поставлена задача разработать процедуры для реализации этих планов.

Вместо того чтобы  напрямую заняться выполнением задания  компании, системный аналитик решил  установить причину возникшей проблемы. Он перешел в своем исследовании от формулировки «Как мы можем увеличить частоту переучетов?» к «Как можно повысить точность переучетов?». Изучение проблемы под таким углом зрения свелось к следующему анализу. Предполагая, что доля точно сосчитанных наименований на складе равна р, аналитик затем предположил следующее. Есть основания считать, что существует 95 % -ная вероятность того, что если изделие было правильно учтено в первый раз, то будет правильно переучтено и при последующем переучете. Для части 1-р товаров, которая не была точно учтена в первом раунде проверки, доля правильного учета во втором раунде равна 80 %. Используя эту информацию, аналитик с помощью дерева решений построил график безубыточности, который сравнил точность учета в первом и втором раундах проверки. Конечный результат сводился к тому, что склады, на которых уровень точности выше порога безубыточности, не требовали переучета. Удивительным результатом предложенного решения было рьяное усердие со стороны каждого склада сделать правильный учет за первый раз, что привело к повышению точности учета на всех складах.