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

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

1. Основы теории матричных игр

Теория игр впервые была систематически изложена Дж. фон Нейманом и О. Моргенштерном в 1994 г., хотя отдельные исследования в этой области публиковались ещё в 1920 годах. Дж. фон Нейман и О. Моргенштерн написали книгу, которая содержала в основном экономические примеры, т.к. описать конфликт легче в числовой форме. После второй мировой войны всерьез теорией игр заинтересовались военные, т.к. увидели в ней аппарат для исследования стратегических решений. Затем внимание снова переключилось на экономические проблемы. Сейчас ведется большая работа, направленная на расширение сферы применения теории игр.

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

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

Различают три вида причин неопределенности результата игры:

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

2. Влияние различных факторов (чаще встречается в азартных играх, такой как рулетка). Здесь исход игры зависит от случайных причин.

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

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

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

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

Каждая модель социально-экономического явления должна отражать черты конфликта, т. е. описывать:

1. Множество заинтересованных сторон (в теории матричных игр их называют игроками, т. е. сторонами, участвующими в конфликте. Так же их называют субъектами, сторонами, участниками).

2. Возможные действия каждой из сторон, именуемые стратегиями или ходами. («Ход» — выбор одного из предложенных правилами игры действий; «стратегия» — план, по которому игрок совершает выбор в любой ситуации и т. д.).

3. Интересы сторон, представленные функциями выигрыша (платежа) для каждого из игроков («выигрыш» — исход конфликта).

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

1.1 Классификация игр

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

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

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

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

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

Наиболее часто приводимым примером игр с ненулевой суммой является игра «Дилемма заключенного». Суть игры состоит в том, что два преступника ожидают приговора суда за содеянное. Адвокат конфиденциально предлагает каждому из преступников облегчить его участь, если он сознается и даст показания против сообщника, которому грозит угодить в тюрьму за совершенное преступление на 10 лет. Если никто не сознается, то обоим угрожает заключение на определенный срок (например, 1 год) по обвинению в незначительном преступлении. Если сознаются оба преступника, то, с учетом чистосердечного признания, им обоим грозит попасть в тюрьму на 5 лет. Каждый заключенный имеет на выбор 2 стратегии: не сознаться или сознаться, выдав при этом сообщника.

· 1 игрок — сознаться или не сознаться;

· 2 игрок — сознаться или не сознаться.

В итоге можно получить следующую матрицу «выигрышей» для обоих игроков:

(5,5) (0,10)

(10,0) (1,1)

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

В игре могут участвовать как два игрока (её называют парной), так и множество. Но наибольшее практическое значение имеют парные игры, в которых участников обозначают за A и B. Простейшим видом стратегической игры — игра двух лиц с нулевой суммой (т.е. сумма выигрышей сторон равна нулю).

Игра состоит из двух ходов: игрок A выбирает одну из своих возможных стратегий A_i (i = 1, 2, …, m), а игрок B выбирает стратегию B_j(j = 1, 2., n), причем каждый участник делает выбор в полной ситуации незнании выбора другого игрока. В результате выигрыши ц₁ (A_i, B_j) и ц₂ (A_i, B_j) каждого из игроков удовлетворяют соотношению

— ц₁ (A_i, B_j)+ ц₂ (A_i, B_j)=0

Если ц₁ (A_i, B_j)= ц (A_i, B_j), то ц₂ (A_i, B_j)= - ц (A_i, B_j)

Цель игрока, А — максимизировать функцию ц (A_i, B_j), а игрока В-минимизировать эту же функцию. Каждый из игроков может выбирать одну из переменных, от которых зависит значение функции. Если игрок, А выбирает некоторую из стратегий A_i, то это может влиять на значение функции ц (A_i, B_j). Влияние A_i на величину значения ц (A_i, B_j) является неопределенным, а определенность имеет место только после выбора, например, игроком B переменной B_j (при этом B_j определяется другим игроком). Пусть ц (A_i, B_j)=a_ij, тогда составим матрицу:

А=

Строки матрицы соответствуют стратегиям A_i, столбцы — стратегиям B_j. Матрица, А называется матрицей игры, а элемент a_ij матрицы — выигрыш игрока А, если он выбрал стратегию A_i, а игрок B выбрал стратегию B_j.

Пусть игрок, А выбрал некоторую стратегию A_i, тогда в худшем случае он получит выигрыш, равный min a_ij. Поэтому предвидя такую возможность, игрок, А должен выбрать ту стратегию, которая позволит максимизировать его минимальный выигрыш б: б =max min a_ij. Величина б — гарантированный выигрыш игрока, А — называется нижней ценой игры, а стратегия A_i0, обеспечивающая получение б — максиминной.

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии B_j его B_j проигрышнее превысит максимального из значений элементов j-го столбца матрицы, т. е. меньше или равен max a_ij. Рассматривая множество max a_ij для различных значений j, игрок В выбирает такое значение j, при котором его максимальный проигрыш в минимизируется: в = min max a_ij. Величина в называется верхней ценой игры, а соответствующая выигрышу в стратегия B_j — минимаксной.

Фактический выигрыш игрока, А при разумных действиях обоих участников ограничен нижней и верхней ценой игры. Если эти выражения будут равны, т. е. max min a_ij = min max a_ij = v, то выигрыш игрока, А — вполне определенное число, значит игра называется вполне определенной, а выигрыш — значением игры и равен элементу матрицы a_i0j0.

Вполне определенные игры называют играми с седловой точкой. Элемент a_i0j0 в матрице такой игры является одновременно минимальным в строке i₀, максимальным в столбце j₀ и называется седловой точкой.

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

Точка называется седловой из-за формы графика функции выигрыша в точке a_i0j0, которая напоминает седло, убывая при изменении одной из переменных и возрастая при изменении другой переменной.

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

Задача: определить верхнюю и нижнюю цены для игр, заданных платежными матрицами, А и В:

A=

B=

Решение: минимальное значение a_ij в строках матрицы, А равны соответственно 2,3,1. Максимальное значение из них равно 3. Следовательно, б₁ — нижняя цена игры, которой соответствует матрица A, равна 3.

б₁ =min {2; 3; 4}=3

Для определения в₁ (верхней цены игры) найдем максимальные значения элементов в столбцах матрицы. По столбцам имеем: 4, 5, 6, 5. Следовательно, в₁ =4.

в₁=max {4; 5; 6; 5}=4

Для матрицы B составляем аналогично б₂ и в₂:

б₂= max {5; 4; 4} и в₂=min {0; 0; - 1; 3}

Таким образом, б₂ = в₂=v — цена игры. Решение данной игры состоит в выборе игроком, А стратегии A₂, при этом выигрыш составит не меньше 4, а для игрока B стратегия B₂, позволяющая ограничить проигрыш числом 3.

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

1.2 Смешанные стратегии в матричных играх

Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследованием игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью.

Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2., m, то его смешанная стратегия x — это набор чисел x = (x1., xm) удовлетворяющих соотношениям:

xi >= 0 (i = 1, m), = 1

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y — это набор чисел y = (y1,…, yn):

yj >= 0, (j = 1, n), = 1

Чистая стратегия есть частный случай смешанной стратегии. Если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

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

б = min max Е (А, х, y)

Аналогичной должна быть ситуация и для игрока 2, т. е. нижняя цена игры должна быть:

б = max min Е (А, х, y)

Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы х_о, у_о соответственно, которые удовлетворяют равенству:

Е (А, х, y) max min = Е (А, х, y) = Е (А, х_о, у_о)

Величина Е (А, х_о, у_о) называется ценой игры и обозначается через v.

Имеется и другое определение оптимальных смешанных стратегий: х_о, у_о называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е (А, х, у_о)<= Е (А, х_о, у_о)<= Е (А, х_о, у) Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

1.3 Свойства решений матричных игр

Обозначим через G (Х, Y, А) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х є Х, игрок 2 — y є V, после чего игрок 1 получает выигрыш, А = А (х, y) за счёт игрока 2.

Стратегия х1 игрока 1 доминирует (строго доминирует) над стратегией х2, если, А (х¹, y)>= А (х², y) (А (х¹, y) > А (х², y)), y є V

Стратегия y1 игрока 2 доминирует (строго доминирует) над стратегией y2, если, А (х, y¹)<= А (х, y²) (А (х, y¹) < А (х, y²)), х є Х При этом стратегии х2 и y2 называются доминируемыми (строго доминируемыми).

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

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

Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Игра G' = (Х', Y', А') называется подыгрой игры G (Х, Y, А), если Х’c Х, V’c V, а матрица А' является подматрицей матрицы А. Матрица А' при этом строится следующим образом. В матрице, А остаются строки и столбцы, соответствующие стратегиям Х' и V', а остальные «вычеркиваются». Всё то что «останется» после этого в матрице, А и будет матрицей А'.

Свойство 3. Пусть G = (Х, Y, А) — конечная антагонистическая игра, G' = (Х х', Y, А) — подыгра игры G, а х' - чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией, спектр которой не содержит х'. Тогда всякое решение (х_о, y_о, v) игры G' является решением игры G.

Свойство 4. Пусть G = (Х, Y, А) — конечная антагонистическая игра, G' = (Х, Y y', А) — подыгра игры G, а y' - чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией, спектр которой не содержит y'. Тогда всякое решение игры G' является решением G.

Свойство 5. Если для чистой стратегии х' игрока 1 выполнены условия свойства 3, а для чистой стратегии y' игрока 2 выполнены условия свойства 4, то всякое решение игры G' = (Х х', Y y', А) является решением игры G = (Х, Y, А).

Свойство 6. Тройка (х_о, y_о, v) является решением игры G = (Х, Y, А) тогда и только тогда, когда (х_о, y_о, кv +а) является решением игры G (Х, Y, кА+а), где, а — любое вещественное число, к > 0.

Свойство 7. Для того, чтобы х_о =(x⁰_1,…, x⁰_i,…, x⁰_m) была оптимальной смешанной стратегией матричной игры с матрицей, А и ценой игры v, необходимо и достаточно выполнение следующих неравенств Аналогично для игрока 2: чтобы y_о = (y⁰₁,…, y⁰_j,…, y⁰_n.,) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

Из последнего свойства: чтобы установить, является ли предполагаемые (х, y) и v решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями получим решение матричной игры.

матричный игра стратегия неравенство Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например, для матрицы 33 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства min a_ij= min max a_ij.

Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 — чистую максиминную, а игрок 2 — чистую минимаксную). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные.

Основные этапы нахождения решения игры 2Чn или mЧ2:

1. Строят прямые, соответствующие стратегиям первого (второго) игрока.

2. Определяют нижнюю (верхнюю) границу выигрыша.

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

4. Определяют цену игры и оптимальные стратегии.

Пример 1. Рассмотрим игру, заданную платёжной матрицей.

Таким образом, ординаты точек, принадлежащих ломанной В1 M N В'3 определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно, этой точке соответствует оптимальная стратегия Х* = (x, 1-x), а её ордината равна цене игры v. Координаты точки N находим как точку пересечения прямых В2 B'2 и В3 B'3.

2. Графический способ решения игры

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

.

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

Решение:

.

Найдём нижнюю и верхнюю цены игры:

.

Так как (68), то матричная не имеет седловой точки или решения в чистых стратегиях. Цена игры при этом. Решение данной игры надо искать в смешанных стратегиях.

Применим графический способ.

Пусть вероятности использования чистых игроком А: и. А вероятности использования чистых стратегий игроком В: .

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

Построим эти прямые в системе координат wOp.

Получили нижнюю огибающую решения — ломанную АМВ. Точка М является точкой максимума — она является точкой пересечения прямых и. Найдём её координаты:

Таким образом, оптимальная стратегия игрока А:

Цена игры

v=

Определим смешанные стратегии для игрока В. Для этого составим следующую систему:

Таким образом, оптимальная стратегия для игрока В:

Ответ: цена игры v=6,5.

Заключение

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

Для грамотного решения задач с конфликтными ситуациями необходимы научно обоснованные методы. Такие методы разработаны математической теорией конфликтных ситуаций, которая носит название теория игр.

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

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

1. Акулич И. Л. Математическое программирование в примерах и задачах/ И. Л. Акулич.-М.: Высшая школа, 1986.-с. 319.

2. Афанасьев М. Ю., Суворов Б. П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие/ М. Ю. Афанасьев, Б. П. Суворов — М.: ИНФРА-М. 2003.-с. 448.

3. Вилкас Э. И. Оптимальность в играх и решениях. М.: «Наука», 1986

4. Замков О. О. Математические методы в экономике/ О. О Замков, А. В Толстопятенко, Ю. Н. Черемных.-М.: Изд-во «Дело и Сервис», 2004.-с. 368.

5. Красс М. С. Математические методы и модели для экономистов/ М. С. Красс, Б. П. Чупрынов. — СПб.: Питер, 2006.-с. 466.

6. Кузнецов А. В. Высшая математика: математическое программирование/ А. В. Кузнецов, В. А. Сакович, Н. И. Холод. — Минск, 2001.-с. 447.

7. Конюхова П. В. Математические методы исследования операций в экономике/ П. В. Конюхова. — СПб: Питер, 2000.

8. Кремер Н. Ш. Исследование операций в экономике/ Н. Ш. Кремер, Б. А. Путко, И. М. Тришин, М. Н. Фридман. — Москва. 2003.-с. 407.

9. Петросян Л. А. Теория игр/ Л. А. Петросян, Н. А. Зенкевич, Е. А. Семина. — М.: Книжный дом «Университет». 1998. с. 304.