Теория игр для математического решения задач

max a

i

т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю чистую стратегию, затем игрок 2 отыскивает свою j=j стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

min max a=a= (2)

j i

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

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

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

Пример 3: Провести SP-разбиение матрицы игры (Н)

Решение: вычисляем верхнюю и нижнюю цену игры

Исходная игра имеет SP (x1,y1) в чистых стратегиях. Существование SP в чистых стратегиях матричной игры с полной информацией позволяет провести SP-разбиение (Н) исходной игры:

Формирование SP- разбиения матричной игры с SP по существу и является рациональным представлением исходной матрицы (Н) игры. Значит, понятие рациональности представления матрицы игры преследует цель сформулировать методы рационального преобразования платёжной матрицы с целью вычисления цены игры v или упрощения построения подыгры-решения.

Далее рассмотрим такое понятие, как решение, при помощи фиктивногоразыгрывания. Есть 2 игрока, которые без теории игр, хотят сделать игру несколько раз, причём каждый из них склонен к статистике и оценивает стратегию своего противника. При каждом разыгрывании противоборствующие стороны стремятся максимизировать свой ожидаемый выигрыш против наблюдаемого вероятностного распределения противника: если игрок 2 использует j-ю стратегию раз, то игрок 1 выберет i-ю стратегию, чтобы максимизировать . Аналогично, если игрок 1 использует i-ю стратегию раз, то игрок 2 выберет j-ю стратегию, чтобы минимизировать . Условно эмпирические распределения сходятся к оптимальным стратегиям. Точнее, пусть - число использований первым игроком i-ой стратегии в течение первых N розыгрышей. Пусть , то тогда является смешанной стратегией. Здесь справедливо утверждение о том, что предел любой сходящейся подпоследовательности является оптимальной стратегией, т.е. если и полученные стратегии игроков 1 и 2, то выполняется равенство . Такой метод полезен в случае игры с большим числом стратегий.

Опишем некоторые свойства решений матричных игр. Пусть G(X,Y,A) - игра двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию , а игрок 2 - , после чего игрок 1 получает выигрыш A=A(x,y) за счёт игрока 2.

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

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

Свойство 3: Если - конечная антагонистическая игра, а , подыгра игры G причём - чистая стратегия игрока 1 в игре G, доминируемая над некоторой стратегией , спектр которой не содержит . Тогда всякое решение игры является решением игры G.

Свойство 4: Тройка является решением игры <=>, когда является решением игры , где а - любое вещественное число, к>0

Глава 2. Игры с нулевой суммой в чистых стратегиях

2.1 Вычисление оптимальных стратегий на примере решения задач

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

Теорема: пусть А - матричная игра и строки данной матрицы являются доминирующими. Тогда игрок 1 имеет такую оптимальную стратегию х, что; кроме того, любая оптимальная стратегия для игры, получающаяся в результате удаления доминирующих строк, будет также оптимальной для первоначальной игры.

Пример 1. Игра доминирования

Рассмотрим игру с матрицей . Здесь второй столбец доминирует 4 и игрок 2 соответственно не будет использовать 4 стратегию. Поэтому можно рассмотреть матрицу следующего вида . В этой матрице третья строка доминирует первую. При удалении получается матрица . А в этой матрице третий столбец доминируется вторым. Следовательно, исходная матрица сводится к следующей матрице .

Пример 2. Игра на уклонение.

Предполагается, что игроки выбирают целые числа i и j между 1 и n, а игрок 1 выигрывает величину , т.е. расстояние между i и j. Пусть первый игрок придерживается стратегии , тогда для всех (( - значение игры).

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

Ситуация называется ситуацией равновесия в чистых стратегиях, если для любых выполнено двойное неравенство (*). Если каждый из игроков стремится достичь ситуации равновесия, то принцип, которому они следуют, называют принципом равновесия. Для игры, заданной матрицей равенство (т.е. верхнее значение игры равно нижнему значению) записывается в виде , а неравенство (*) - в виде , где чистые максиминная и минимаксная стратегии соответственно игроков I и I I.

Пример 3. Игра «Дуэль».

Два дуэлянта (игроки А и В) начинают сходиться в момент времени t=0. Встреча произойдёт в момент времени t=1. У каждого есть возможность выстрелить в любой момент времени. Если одному из них удастся выстрелить раньше соперника, то он становится победителем. Если же оба выстрелят одновременно, то дуэль закончится вничью. Если игрок А произведёт выстрел в момент времени x () то его выстрел будет успешным с вероятностью р(x). Подобным образом будет вероятным выстрел игрока В в момент времени y () c вероятностью q(y). При условии игрок А выиграет с вероятностью р(x), а проиграет с вероятностью (1- р(x)) q(y). Тем самым его средний выигрыш при будет равен . С другой стороны, если x> y, то его средний выигрыш будет равен . При x= y средний выигрыш

2.2 Примеры матричных игр в чистой и смешанной стратегиях Уменьшение порядка платёжной матрицы

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

Например, в матрице

Платёжная матрица с доминируемыми и дублирующими стратегиями. Стратегия A1 является доминируемой по отношению к стратегии A2, стратегия B6 является доминируемой по отношению к стратегиям B3, B4 и B5, а стратегия B5 является дублирующей по отношению к стратегии B4. Данные стратегии не будут выбраны игроками, так как являются заведомо проигрышными и удаление этих стратегий из платёжной матрицы не повлияет на определение нижней и верхней цены игры, описанной данной матрицей.

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

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

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

Задача

Два предприятия производят продукцию и поставляют её на рынок региона. Они являются единственными поставщиками продукции в регион, поэтому полностью определяют рынок данной продукции в регионе.

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

Затраты на единицу продукции, произведенной на предприятиях региона (д.е.).

В результате маркетингового исследования рынка продукции региона была определена функция спроса на продукцию:

Y = 6 - 0.5X,

где Y - количество продукции, которое приобретёт население региона (тыс. ед.), а X - средняя цена продукции предприятий, д.е.

Данные о спросе на продукцию в зависимости от цен реализации приведены в таблице.

Спрос на продукцию в регионе, тыс. ед.

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

Доля продукции предприятия 1, приобретаемой населением в зависимости от соотношения цен на продукцию

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

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

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

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

3. Сколько продукции будет реализовано в ситуации равновесия? Какое предприятие окажется в выигрышном положении?

Решение задачи

1. Определим экономический смысл коэффициентов выигрышей в платёжной матрице задачи. Каждое предприятие стремится к максимизации прибыли от производства продукции. Но кроме того, в данном случае предприятия ведут борьбу за рынок продукции в регионе. При этом выигрыш одного предприятия означает проигрыш другого. Такая задача может быть сведена к матричной игре с нулевой суммой. При этом коэффициентами выигрышей будут значения разницы прибыли предприятия 1 и предприятия 2 от производства продукции. В случае, если эта разница положительна, выигрывает предприятие 1, а в случае, если она отрицательна - предприятие2.

2. Рассчитаем коэффициенты выигрышей платёжной матрицы. Для этого необходимо определить значения прибыли предприятия 1 и предприятия 2 от производства продукции. Прибыль предприятия в данной задаче зависит:

- от цены и себестоимости продукции;

- от количества продукции, приобретаемой населением региона;

- от доли продукции, приобретённой населением у предприятия.

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

D = p(SR1-SC1) - (1-p) (SR2-SC2) (1),

где D - значение разницы прибыли от производства продукции предприятия 1 и предприятия 2;

p - доля продукции предприятия 1, приобретаемой населением региона;

S - количество продукции, приобретаемой населением региона;

R1 и R2 - цены реализации единицы продукции предприятиями 1 и 2;

C1 и C2 - полная себестоимость единицы продукции, произведённой на предприятиях 1 и 2.

Вычислим один из коэффициентов платёжной матрицы.

Пусть, например, предприятие 1 принимает решение о производстве продукции в соответствии с технологией III, а предприятие 2 - в соответствии с технологией II. Тогда цена реализации единицы. продукции для предприятия 1 составит 2 д.е. при себестоимости единицы. продукции 1,5 д.е. Для предприятия 2 цена реализации единицы. продукции составит 6 д.е. при себестоимости 4 д.е. (табл. 1.1).

Количество продукции, которое население региона приобретёт при средней цене 4 д.е., равно 4 тыс. ед. (таблица 1.2). Доля продукции, которую население приобретёт у предприятия 1, составит 0,85, а у предприятия 2 - 0,15 (табл. 1.3). Вычислим коэффициент платёжной матрицы a32 по формуле (1): a32 = 0,85(42-41,5) - 0,15(46-44) = 0,5 тыс. ед. где i=3 - номер технологии первого предприятия, а j=2 - номер технологии второго предприятия.

Аналогично вычислим все коэффициенты платёжной матрицы. В платёжной матрице стратегии A1 - A3 - представляют собой решения о технологиях производства продукции предприятием 1, стратегии B1 - B3 - решения о технологиях производства продукции предприятием 2, коэффициенты выигрышей - разницу прибыли предприятия 1 и предприятия 2. Платёжная матрица в игре «Борьба двух предприятий за рынок продукции региона».

В данной матрице нет ни доминируемых, ни дублирующих стратегий. Это значит, что для обоих предприятий нет заведомо невыгодных технологий производства продукции. Определим минимальные элементы строк матрицы. Для предприятия 1 каждый из этих элементов имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Минимальные элементы матрицы по строкам имеют значения: 0,17, -1,5, 0,4.

Определим максимальные элементы столбцов матрицы. Для предприятия 2 каждый из этих элементов также имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Максимальные элементы матрицы по столбцам имеют значения: 3, 0,62, 0,4.

Нижняя цена игры в матрице равна 0,4. Верхняя цена игры также равна 0,4. Таким образом, нижняя и верхняя цена игры в матрице совпадают. Это значит, что имеется технология производства продукции, которая является оптимальной для обоих предприятий в условиях данной задачи. Эта технология III, которая соответствует стратегиям A3 предприятия 1 и B3 предприятия 2. Стратегии A3 и B3 - чистые оптимальные стратегии в данной задаче.

Значение разницы прибыли предприятия 1 и предприятия 2 при выборе чистой оптимальной стратегии положительно. Это означает, что предприятие 1 выиграет в данной игре. Выигрыш предприятия 1 составит 0,4 тыс. д.е. При этом на рынке будет реализовано 5 тыс. ед. продукции (реализация равна спросу на продукцию, таблица 1.2).. Оба предприятия установят цену за единицу продукции в 2 д.е. При этом для первого предприятия полная себестоимость единицы продукции составит 1,5 д.е., а для второго - 1 д.е (таблица 1.1). Предприятие 1 окажется в выигрыше лишь за счёт высокой доли продукции, которую приобретёт у него население.

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