Матричные игры.

По виду функций выигрышей игры делятся на: матричные, бимат-ричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др.

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

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

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

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

Матричные игры — это игры, где два игрока играют в игру с нулевой суммой, имея конечное число «чистых» стратегий: (1,…, m) и (1,…, n) и ∀ (ij) задан платеж aij второго игрока первому. Матрица (aij) задает выигрыш первого игрока и проигрыш второго, aij ≷ 0! (Матрица — математический объект, записываемый в виде прямоугольной таблицы или поля, которая представляет собой совокупность строк и столбцов, на пересечении которых находятся её элементы).

Обычно выделяют 2 наиболее важных типа матричных игр:

·         «Игры с природой», в которых только один участник стремится максимизировать свою прибыль, которая зависит от того, какой будет погода, или каким будет состояние рынка. Если единственный участник принял решение оптимально спланировать свою хозяйственную деятельность при самых неблагоприятных погодных или рыночных условиях, то он может считать природу или рынок активным враждебным субъектом.

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

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

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

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

Методы решения матричных игр

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

• Решение матричной игры сведением к задаче линейного программирования: В этом случае вся игра задана платежной матрицей. Оптимальные смешанные стратегии игроков А и В могут быть найдены в результате решения пары двойственных задач линейного программирование.
• Решение матричной игры графическим методом: при поиске оптимальных стратегий в матричных играх целесообразно использовать графический метод решения задач линейного программирования и свойства оптимальных планов пары двойственных задач: если в оптимальном плане задачи переменная положительна, то соответствующее ограничение двойственной задачи обращается в равенство; если оптимальным планом задачи ограничение обращается в строгое неравенство, то в оптимальном плане двойственной задачи соответствующая переменная равна нулю.
• Решение игр с природой по различным критериям: поскольку игры с природой являются частным видом парных матричных игр, то вся теория стратегических игр переносится и на игры с природой. Однако игры с природой обладают и некоторыми особенностями. Например, при упрощении платежной матрицы отбрасывать те или иные состояния природы нельзя, так как она может реализовать любое состояние. И ещё одна важная особенность: в играх с природой смешанные стратегии имеют ограниченное значение. Смешанные стратегии приобретают смысл только при многократном повторении игры. [3]

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

Описание алгоритма:

1. На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
2. Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
3. Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
4. Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Пример

В матричной игре её правила определяет платёжная матрица.

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока - n чистых стратегий. Поскольку рассматривается игра, естественно, что в этой игре есть выигрыши и есть проигрыши.

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

Составим платёжную матрицу:

.

Если первый игрок выбирает i-ю чистую стратегию, а второй игрок - j-ю чистую стратегию, то выигрыш первого игрока составит aij единиц, а проигрыш второго игрока - также aij единиц.

Так как aij + (- aij) = 0, то описанная игра является матричной игрой с нулевой суммой.

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

.

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