Антагонистические игры

Введение Модели и моделирование очень важны в современном мире. Они позволяют человеку легко и безопасно события и явления, анализировать их и интерпретировать результаты. Совершенствование современных компьютеров позволило существенно расширить область применения моделей и моделирования. Они используются практически везде.
Будем считать, что модель- это объект, который заменяет оригинал в целях анализа и изучения, сохраняя его существенные характеристики. Под моделированием обычно понимают два различных процесса: создание модели и работа с уже созданной моделью, ее исследование в целях получения требуемых результатов и выводов. Можно моделировать иным образом, заменяя оригинал не материальным предметом, а абстрактным, например, схемой, графиком, формулой или набором правил, которым подчиняется данный оригинал. Математическая модель – это приближенное описание какого-либо класса явлений, выраженное с помощью математической символики.
Принятие решений при совместных действиях Рассмотрим ситуации в которых важную роль играют совместные действия участников. Если принятие решения зависит от нескольких участников, то, как правило, неизбежен конфликт, так как крайне редко все участвующие имеют одинаковые цели и интересы. В этом случае конфликт понимается как ситуация, которую формируют различные участники, имеющие не совпадающие цели (не обязательно противоположные). Один из способов изучения и анализа таких ситуаций - моделирование в терминах теории игр. Теоретическая возможность применять игровые модели имеется для любой ситуации с несколькими участниками, например, для любого микро-, макроэкономического или социального явления. Фактическая возможность такого применения зависит не только от адекватности модели реальной ситуации и возможности аналитического или численного решения, но и от формулировки принципа оптимальности. Единого принципа оптимальности нет, и причина этого скорее в противоречивости содержания конфликта, чем в недостатках математического аппарата. Например, понятие оптимального решения должно учитывать справедливость результата для всех участников (каждый участник должен считать принятое решение справедливым для себя и, желательно, для остальных), что можно понимать по-разному. Разумеется, на практике применяются некоторые принципы оптимальности. Например, для принятия решения участниками используется голосование (“за” должен быть некоторый процент участников, например, половина плюс один или две трети); диктатура (одним участником (диктатором) принимается решение, остальные к нему присоединяются, точнее - остальные подчиняются); консенсус (для всех участников достигается полное единодушие мнений); анархия (каждый поступает как считает нужным) и т. д. Для реализации этих принципов не обязательны предварительные консультации и соглашения между участниками. Предполагается, что каждый участник имеет своё мнение о том, как ему действовать. К сожалению, при таких условиях невозможно принятие обоснованного коллективного решения. Строгая формулировка последнего утверждения составляет теорему Эрроу: Пусть на множестве возможных решений введено отношение предпочтения. Оно обозначается x>y : решение х лучше у для некоторого участника. Если правило принятия решения участниками удовлетворяет условиям 1) транзитивности, т. е. если решение х лучше у, а у лучше z, то решение х лучше z: если x>y ,y>z , то x>z; 2) полноты, т. е. из любых двух решений можно выбрать лучшее; 3) единогласия, т. е. если для всех участников решение х лучше у, то коллективное решение х также лучше у. 4) независимости, т. е. при сравнении решений х и у другие решения не рассматриваются. Тогда это правило принятия решения - диктатура, т. е. присоединение участников к решению одного, независимо от их личных предпочтений. Однако после консультаций некоторые участники могут изменить своё решение, они могут договориться о сотрудничестве (создать коалицию), пойти на уступки или потребовать плату за изменение решения. Тогда может быть осуществимо демократическое коллективное принятие решения.
Антагонистические игры Рассмотрим простейшую модель антагонистической игры. В ней участвуют два игрока, у каждого имеется конечное число стратегий, а их интересы противоположны — выигрыш одного равен проигрышу другого. В этом случае для элементов платёжной матрицы выполнено условие aij + bij = 0 (1) так как выигрыш 1-го игрока равен проигрышу 2-го при избрании ими любых стратегий. Следовательно, в платёжной матрице такой игры в каждой паре числа равны по модулю и противоположны по знаку. Для упрощения записи в платёжной матрице такой игры каждый элемент — одно число aij. Это — выигрыш 1-го игрока. bij = - aij - соответствующий проигрыш 2-го. Эта же модель включает в себя игры с постоянной суммой, в них для элементов платёжной матрицы выполнено условие aij + bij = const Рассмотрим простейшие примеры ситуаций, которые можно рассматривать как модели антагонистических игр. Пусть два предприятия, ограниченные одним рынком сбы­та, выпускают продукцию одинакового назначения, но разного типа. Будем считать, что 1-е предприятие выпускает продукцию А1, а2 а3 и A4, а 2-е предприятие — В1, В2 и B3. Себестоимость и продажная цена любого типа продукции одинаковы. Имеется прогноз рынка сбыта: гарантирован, сбыт всего 1000 единиц продукции и просчитан прогнозируемый сбыт каждого вида продукции (табл. 1). Таблица 1

2-е предприятие выпускает продукцию
В1

В2

В3

1-е пред­приятие выпускает продукцию
А1
(500, 500)
(400, 600)
(500, 500)
А2

(100,900)
(600, 400)
(650, 350)
А3
(900, 100)
(700, 300)
(800, 200)
А4
(400, 600)
(200, 800)
(300,700) Данные таблицы интерпретируются следующим образом: если 1-е предприятие выпускает продукцию А1, а 2-е предпри­ятие — продукцию В2, то сбыт составляет 500 единиц продукции А1 и 500 единиц продукции В1, если 1-е предприятие выпускает продукцию А2, а 2-е предприятие — продукцию В1, то сбыт со­ставляет 100 единиц продукции А2 и 900 единиц продукции В1. Пусть доход от продажи единицы продукции равен одной де­нежной единице, а мощности каждого из предприятий достаточ­ны, чтобы полностью обеспечить рынок.
Поскольку суммарный сбыт предприятий в каждом случае полностью обеспечивает рынок (сумма чисел в каждой ячейке таблице равна 1000), то интересы предприятий противоположны, и данную ситуацию можно смоделировать в виде антагонистической игры. Первое предприятие является игроком 1, и у него есть четыре стратегии: выпускать продукцию А1, а2 а3 и A4. Его противник (2-е предприятие) имеет три стратегии: выпускать продукцию В1, В2 и B3. Каждое из предприятий намерено выбрать стратегию, гарантирующую максимальную прибыль при любых действиях противника.
В таблице 1 представлена платёжная матрица этой игры. На пересечении i-й строки и J-го столбца матрицы находится число aij — выигрыш 1-го игрока, если он выпускает продукцию Ai, а его противник — Bi. Выигрыш 2-го игрока при этом равен 1000 — aij (таким образом, это — антагонистическая игра с постоянной суммой): Рассмотрим другую ситуацию. Пусть некоторый банк может принять участие в кредитовании трёх проектов. Возврат кредита и получение дохода зависят от общей финансовой ситуации, которая сложится в будущем году. Существующие прогнозы будущей финансовой ситуации противо­речивы. Специалисты банка составили классификацию возможных финансовых ситуаций и сделали прогноз эффективности кредитования (табл. 2). Так, если сложится исключительно благоприятная финансовая ситуация, то кредитование 1-го проекта обещает прибыль 720 денежных единиц, 2-го – 660, а 3-го – 440. Таблица 2 Финансовая ситуация
Доход от проекта
1
2
3 Исключительно благоприятная
720
660
440 Благоприятная
600
550
320 Нейтральная
200
680
430 Неблагоприятная
180
340
330 Исключительно неблагоприятная
0
100
50 Банк хочет спланировать кредиты, чтобы гарантировать наибольший доход даже при наиболее неблагоприятной финан­совой ситуации. Данную ситуацию можно смоделировать в виде антагонистической игры. Банк является игроком 1, он имеет три стратегии: кредитовать проект 1, 2 или 3. Его противник — при­рода (общая финансовая ситуация) является игроком 2. Будем считать, что у игрока 2 имеется пять стратегий: исключительно благоприятная общая финансовая ситуация, благоприятная, нейтральная, неблагоприятная и исключительно неблагоприят­ная. Поскольку банк хочет получить максимальный доход при самой неблагоприятной ситуации, то предполагаем, что природа «хочет» навредить банку как можно сильнее. Если ситуация бу­дет лучше, то доход банка увеличится. В табл. 2 представлена платёжная матрица этой игры: Рассмотрим платёжную матрицу произвольной антагони­стической игры. Основное предположение при ана­лизе антагонистических игр: каждый игрок действует наилуч­шим для себя образом, т. е. пытается получить максимально возможный выигрыш при любых стратегиях противника, считая, что противник также действует наилучшим для себя образом. Следовательно, игрок 1 считает, что при выборе им любой стра­тегии (любой строки платёжной матрицы), противник выберет столбец, дающий ему максимальный выигрыш, т. е. минималь­ный для игрока 1. Тогда оптимальная стратегия игрока 1 - вы­брать самый большой из минимальных выигрышей, т. е. выбрать v = max min aij (2) i j Эта стратегия гарантирует наибольший выигрыш незави­симо от стратегии противника. Такая стратегия называется максиминной стратегией (стратегия максимизации минимального выигрыша), а v — максимином. Аналогично, если игрок 2 выбирает j-ю стратегию, то в худшем случае он проигрывает max aij i поэтому его гарантированный проигрыш: v*= min max aij j i (3) Такая стратегия называется минимаксной стратегией (стратегия минимизации максимального проигрыша), а v- минимаксом. Например, в игре, моделирующей конкуренцию предпри­ятий, игрок 1 считает, что независимо от его стратегии выбора продукции для производства (т. е. независимо от выбора им строки платёжной матрицы), игрок 2 выберет стратегию (столбец платёжной матрицы), максимизирующую его выигрыш, т.е. минимизирующую выигрыш игрока 1. Если игрок 1 будет произво­дить продукцию А1 (выберет 1-ю строку платёжной матрицы), то игрок 2 может производить продукцию В2 (выбрать 2-й столбец), тогда выигрыш игрока 1 равен 400, а выигрыш игрока 2 — 600. Если игрок 1 будет производить продукцию А2 (выберет 2-ю строку), то игрок 2 может производить продукцию В1 (выбрать 1-й столбец). Тогда выигрыш игрока 1 будет 100, а игрока 2 - 900. Поэтому игроку 1 нужно найти минимальный выигрыш в каждой строке платёжной матрицы и рассматривать только его. Этот выигрыш ему гарантирован. Рассмотрим платёжную матрицу этой игры:
400 100 700 200 900 700 800 Справа в столбец выписаны минимальные элементы каждой строки. Оптимальная стратегия игрока 1- выбрать строку с самым большим минимальным элементом, это гарантируем ему наибольший выигрыш, независимо от стратегии игрока 2. Максимальный среди минимальных элементов строк выигрыш 700 (он заключён в квадрат). Следовательно, при выпуске любой продукции 2-м предприятием, доход 1-го предприятия не будет меньше 700 денежных единиц, если он будет выпускать продукцию А3. Таким образом, для игрока 1 максиминной является 3-я стратегия, она оптимальна. Максимин равен:
v = max min aij = 700 i j Игрок 2 также рассматривает наихудшие варианты и стремится обеспечить себе максимальный выигрыш (минимально выигрыш своему противнику). Если игрок 2 выберет 1-й столбец, то игрок 1 может выбрать 3-ю строку и обеспечить себе выигрыш 900. Выигрыш игрока 2 при этом – 100. Если игрок 2 в, берет 3-й столбец, то игрок 1 может выбрать 3-ю строку и обеспечить себе выигрыш 800, а выигрыш игрока 2 при этом – 200. Следовательно, игрок 2 может рассматривать только максимальные элементы каждого столбца. Они выписаны под матрицей. Выбрав среди них наименьший (700), игрок 2 имеет гарантированный проигрыш не больше 700, т.е. выигрыш не меньше 300 (1000 - 700 = 300) при любых деиствиях игрока 1. Таким образом, для игрока 2 минимаксной является 2-я стратегия, она оптимальна, а минимакс:
v* = min max aij = 700 j i Рассуждая аналогично, найдём максимин и минимакс в игре, моделирующей кредитование проектов банком. Платёжная матрица этой игры: 0 100 320 720 600 680 340 450 максимин и минимакс (курсив): v = max min aij = 320 i j v* = min max aij = 340 j i Максиминная стратегия игрока 1- выбрать 3-ю строку платёжной матрицы (кредитовать проект 3). Она ему гаранти­рует, что какая бы не сложилась финансовая ситуация, он получит выигрыш не меньше 320. Для природы минимаксной является 4-я стратегия. Если цель природы - гарантированно максимально уменьшить выиг­рыш игрока 1, то ей следует создать неблагоприятную финансо­вую ситуацию. Если игрок 1 следует максиминной стратегии, то его выиг­рыш v в игре будет не меньше максимина v , а если игрок 2 вы­бирает минимаксную стратегию, то его проигрыш (-v) будет не больше минимакса v*, т.е. v = max min aij ≤ v ≤ v* = min max aij i j j i В антагонистической игре всегда v ≤ v*. Если выполнено строгое равенство v = v*, то стратегии игроков являются совместимыми, а платёжная матрица имеет седловую точку: v = v­ = v*­ = max min aij = min max aij i j j i являющуюся одновременно минимаксом и максимином. Так, в игре моделирующей конкуренцию между двумя предприятиями, максимин и минимакс совпадают: v­ = max min aij = min max aij=v* =700 i j j i платёжная матрица имеет седловую точку а32, стратегии игроков совместимы. Игрок 1 выбирает 3-ю стратегию, игрок 2 - 2-ю, каждый получает свой гарантированный выигрыш (700 и 300). Седловая точка соответствует равновесию в игре. При этом, если один из игроков выбирает стратегию, соответствую­щую положению равновесия, то другому также выгоднее всего избрать стратегию, отвечающую седловой точке. Тогда каждый игрок получает свой гарантированный платёж (выигрыш или проигрыш). Выбор другой стратегии может уменьшить гаранти­рованную прибыль или увеличить возможные потери. Например, если игрок 2 в модели конкуренции предприятий выберет 3-ю стратегию, то он может получить выигрыш 500 (если игрок 1 выберет 1-ю стратегию), а может - только 200 (если иг­рок 1 изберёт свою оптимальную 3-ю стратегию). Игра двух игроков с нулевой суммой, имеющая седловую точку, называется вполне определённой. Игры, в которых выпол­няется строгое равенство v­ = max min aij i j j i называются не полностью определёнными играми. Игра, моделирующая кредитование проектов, является не полностью определённой, так как в ней выполнено строгое неравенство: v­ = max min aij =320 i j j i Если в игре не существует положения равновесия, т. е. v­ = max min aij i j j i то максиминная и минимаксная стратегии не являются оптимальными. Игрокам может быть невыгодно следовать им, так как возможен больший выигрыш или меньший проигрыш. Действительно, пусть в игре кредитования проектов игрок 1 выбирает свою 3-ю максиминную стратегию (при которой его выигрыш равен 320) и ожидает, что при этом игрок 2 выберет 2-ю стратегию (поскольку максимин а32 = 320), а игрок 2 выберет свою 4-ю минимаксную стратегию и ожидает, что игрок 1 выберет 2-ю стратегию и получит выигрыш 340 (так как минимакс а24 = 340). Тогда игрок 1 получает выигрыш 330 (поскольку а34 = 330), не предполагавшийся ни одним из игроков. Фактически для не вполне определённых игр происходит распределение разницы v­ - v* = min max aij - max min aij j i i j между игроками. Если игра не вполне определённая, то минимаксная и максминная стратегии не являются оптимальными для игроков. Игроки могут получить больший выигрыш, избирая другие стратегии, но при условии, что противнику не известен их выбор. В ситуации равновесия игроки знают оптимальные стратегии друг друга и знают, что будут им следовать. В не вполне определенной игре игроки должны позаботиться о скрытности своей стратегии. Наибольшую секретность выбора стратегии обеспечивает случайность: противник не может знать выбор игрока, так как этот выбор не известен самому игроку до реализации случайного механизма. Рассматривавшиеся выше стратегии называются чистыми. В случае не вполне определённой игры игрокам разумно действовать случайно, при этом противнику не известен способ выбора стратегии. Для описания случайного выбора стратегии вводится понятие смешанной стратегии. Смешанная стратегия - это набор чистых стратегий, выбранных случайно с некоторыми вероятностями. Рассмотрим платёжную матрицу антагонистической игры Строки платёжной матрицы являются чистыми стратегиями игрока 1, а столбцы платёжной матрицы являются чистыми стратегиями игрока 2. Пусть ξi- вероятность выбора i-й чистой стратегии игроком 1 при использовании им смешанной стратегии ξ, а ηj - вероятность выбора j-й чистой стратегии игроком 2 при использовании им смешанной стратегии η. Тогда смешанная стратегия ξ игрока 1 запишется в виде вектора вероятностей ξ = (ξ1, ξ2, … ξм), , ξi ≥ 0, i =1, …, m. Например, в игре, моделирующей кредитование проектов вектор ξ (0; 0,2; 0,8) описывает смешанную стратегию, при которой игрок 1 выбирает строку 2 платёжной матрицы с вероятностью 0,2 и строку 3 — с вероятностью 0,8 (т.е. 1-ю чистую стратегию не выбирает никогда, 2-ю чистую стратегию использует каждый пятый раз, а 3-ю — каждые четыре раза из пяти). Аналогично, смешанная стратегия η игрока 2 описывается вектором вероятностей η = (η 1, η 2, … η м), , η j ≥ 0, j=1, …, n. Чистые стратегии являются частным случаем смешанны они описываются единичными векторами вероятностей ξi = 1, ξj = 0, i ≠ j, i = 1, …, m.
Например, вектор ξ = (0, …, 1, …, 0) Описывает i-ю чистую стратегию игрока 1, поскольку с вероятностью единица будет выбрана i-я стратегия. Таким образом, вешанные стратегии расширяют понятие чистой стратегии. Игра, в которой помимо чистых рассматриваются, и смешанные стратегии, называется смешанным расширением исходной игры.
Основной в теории игр двух игроков является следующая теорема о минимаксе: Любая антагонистическая матричная игра имеет поло­жение равновесия, если допускается использование смешанных стратегий. В смешанном расширении исходной игры ожидаемый выигрыш игрока 1 определяется как математическое ожидание, при условии, что он применяет смешанную стратегию ξ, а игрок 2 пользует свою стратегию j: ξ 1a1j + ξ2a2j + … + ξmamj = , j = 1, …, n. Как и в случае использования только чистых стратегий, игрок 1 стремится получить максимальный из гарантированных возможных выигрышей и выбирает стратегию ξ так, чтобы иметь максимальный из минимальных значений ожидаемых выигрышей: max min ξ j (4) Игрок 2 стремится достигнуть минимального из максимальных значений ожидаемых проигрышей, поэтому выбирает стратегию η так: min max η i (5) Теорема о минимаксе гарантирует существование положения равновесия, то есть оптимальных стратегий ξ* = (ξ*1, ξ*2, …, ξ*m) и η* = (η1*, η1*, …, η1*). Тогда для любых стратегий ξ и η выполнены условия: ξi ηj*aij и Обозначим (6) Следовательно, существует хотя бы одна пар смешанных стратегий ξ* и η*, при которых возникает ситуация равновесия с седловой точкой v – максимальным ожидаемым выигрышем игрока 1 и минимальным ожидаемым выигрышем игрока 2. Явный поиск оптимальных стратегий с помощью формул (4) и (5) сложен. Ниже будут рассмотрены приемлемые на практике методы поиска оптимальных стратегий и положения равновесия. Таким образом, вполне определенная игра имеет положение равновесия, если игроки используют только чистые стратегии. Решение может быть не единственным. Не полностью определенная игра имеет положение равновесия, но при этом хотя бы один игрок использует смешанную стратегию. Если один игрок использует свою оптимально смешанную стратегию, то другому также выгодно придерживаться своей оптимально смешанной стратегии. Так, ранее рассмотренная игра, моделирующая конкуренцию предприятий, является вполне определенной. Положению равновесия соответствует 3-я чистая стратегия игрока 1 и 2-я стратегия игрока 2. А игра, моделирующая кредитование проекта, не является вполне определенной, положения равновесия в чистых стратегиях в ней нет, оптимальные смешанные стратегии игроков будут найдены ниже. Чем больше размер платежной матрицы игры, тем сложнее анализ. Однако в некоторых случаях можно исключить некоторые стратегии игроков, поскольку игроки их иногда не используют. Действительно если результат стратегии ξ’’ игрока 1 хуже результата стратегии ξ’ при любых действиях игрока 2, то при анализе игры стратегию ξ’’ можно игнорировать. Стратегия ξ’ игрока 1 доминирует его стратегию ξ’’, если для всех чистых стратегий j=1, …, n игрока 2 выполняются неравенства Стратегия ξ’ называется доминирующей, а стратегия ξ’’ доминируемой. Аналогично стратегия η’ игрока 2 доминирует его стратегию η’’, если для всех чистых стратегий i=1,…, m игрока 1 выполнено Считая векторы ξ и η единичными, получаем формулировку определения доминирования для чистых стратегий. Стратегия i' игрока 1 доминирует его стратегию i" (строка платёжной матрицы i' доминирует строку i"), если для всех j=1 ,…,n. Аналогично, стратегия j' игрока 2 доминирует его стратегию j" (столбец платёжной матрицы j' доминирует столбец j") если для всех i = 1, ., m. Доминирующая стратегия не хуже, а может быть и лучше доминируемой, поэтому игроку не следует использовать доминируемую стратегию. Существуют оптимальные стратегии, при которых вероятность использования доминируемых строк и столбцов равна нулю, поэтому эти строки и столбцы в платёжной матрице можно исключить. Таким образом, пусть v - седловая точка некоторой игры с платёжной матрицей А­m*n. Пусть стратегия i игрока 1 доминируема в этой игре (т.е. доминируема i-я строка матрицы А). Пусть - матрица, полученная из матрицы А вычёркиванием i-и строки. Тогда в игре седловая точка . Любая оптимальная стратегия игрока 2 в игре с матрицей является оптимальной в игре с матрицей А. Если - оптимальная стратегия игрока 1 в игре с матрицей , то стратегия ξ = (ξ1, ξ2, …, ξm) = является оптимальной в игре с матрицей А. Аналогично для игрока 2. Используя эти утверждения, можно понижать размерность платежной матрицы, а затем применять теорему о минимаксе. Например, в игре, моделирующей конкуренцию предприятий, 1-я строка доминирует 4-ю, т.е. игрок 1 не будет использовать свою 4-ю чистую стратегию, поэтому её можно не рассматривать. Упрощённая платёжная матрица игры:
В игре, моделирующей кредитование проектов, 2-й столбец доминирует 1-й, а 4-й доминирует 3-й, т. е. игрок 2 не будет ис­кать свои 1-ю и 3-ю чистые стратегии, поэтому их можно сматривать. Упрощённая платёжная матрица игры:
Для полного анализа игры достаточно рассмотреть эти матрицы. Другой способ упрощения платёжной матрицы — преобразование её элементов. Пусть каждый элемент платёжной матрицы изменяется по правилу (k ≠ 0). Тогда оптимальные стратегии игр с платёжными матрицами и сопадают, а седловая точка игры равна . Выполнив преобразование, можно упростить платежиvi матрицу и последующий анализ. Кроме того, из этого свойства следует, что можно изменять масштаб элементов матрицы, то есть менять единицы, в которых задаётся выигрыш. Упрощение платёжной матрицы важно, если анализ игры выполняется вручную или графическим методом. Если же для нахождения оптимальных стратегий используются численные методы, например итерационные, то усилия и время, затрачиваемые на поиск доминируемых стратегий и подходящего преобразования элементов платёжной матрицы, могут оказаться потраченными зря, поскольку численный анализ исходной и упрощенной матриц выполняется по одному и тому же алгоритму, а разница во времени вычислений несущественна для человека, однако существуют платёжные матрицы, численный анализ которых до упрощения сложен. Один из способов нахождения оптимальной стратегии игроков — сведение матричной игры к задаче линейного программирования. Игрок 1 рассматривает минимальные ожидаемые выигрыши, при этом он ищет свою оптимальную стратегию ξ и седловую точку (число v), такие что аналогично игрок 2 минимизирует платежи, то есть ищет вектор η=(η1,η2,…,ηn) и седловую точку v, такие что выполнялись те же неравенства. Будем считать, что выполнены преобразования, в результате которых получена платёжная матрица А, все элементы которой положительны. Тогда можно считать число v также поло­чным: v>0. Разделим соотношения (7) на v и определим: Задача игрока 1 — максимизировать выигрыш, т.е. максимизировать v. Поскольку (9) то v максимально, когда минимальна. Аналогично, задача игрока 2- минимизировать v, а так как (10) то v минимальна, когда максимальна. Тогда анализ платёжной матрицы с точки зрения игрока 1 эквивалентен задаче линейного программирования: найти минимум целевой функции. f = x1+x2+…+xm при условиях (11) Задачу игрока 2 также можно сформулировать как задачу линейного программирования, двойственную к задаче (11): найти максимум целевой функции g = y1+y2+…+yn при условиях (12) Задачи линейного программирования (11) и (12) можно решить, например, симплекс-методом. Пусть у* = (у*1, у*2, ., у*n)- решение задачи линейного программирования (12), х* = (х*1, х*2, ., х*­m) — теневые цены (решение двойственной задачи). Тогда значение седловой точки v определяется из условий (9), (10): (13) а оптимальные стратегии игроков получаются из решения з| чи линейного программирования нормированием: ξ*i=v x*i ,i=1,…,m, η*j=v y*j ji=1,…,n. (14) Пусть антагонистическая игра задана платёжной матрицей . Словесно-формульное описание алгоритма анализа платёжной матрицы антагонистической игры сведением к задаче линейного программирования: 1* начало процесса. 2* ввод платёжной матрицы игры А. 3* Формулировка задачи линейного программирования (12): найти максимум функции при условиях Ay ≤ 1, y≥ 0. 4* Решение задачи линейного программирования (12). Результат у* = (у*1, у*2, ., у*n)- оптимальный вектор, х* = (х*1, х*2, ., х*­m) теневые цены. 5* Определение положения равновесия: ; оптимальной стратегии игрока 1: оптимальной стратегии игрока 2:. 6* Вывод результата 7* Конец процесса Другой способ нахождения оптимальных стратегий игроков и седловой точки игры — решать матричную игру с помощью итерационных методов. Рассмотрим простейший итерационный метод нахождения оптимальных стратегий в матричных играх - метод Брауна-Робинсона. Идея метода состоит в следующем: имитируется многократное повторение игры и набирается статистика, показывающая какие стратегии максимизируют выигрыш, и таким образом определяется оптимальная стратегия. Для анализа антагонистической игры с матрицей строится итерационный процесс, каждый шаг которого - розыгрыш игры. В первой игре у игроков ещё нет никакой информации, поэтому они выбирают свои стратегии произвольно. Положим для определённости, что в первой игре оба игрока всегда выбирают свои 1-е чистые стратегии: k =1 ; ξ1 = (1,0,…,0); η1=(1,0,…,0). Верхний индекс обозначает номер игры k. Предположим, состоялось k игр, в них игрок 1 использовал свою i-ю стратегию ξki раз, а игрок 2 использовал свою j-ю стратегию ηkj раз. Определим максимальный ожидаемый выигрыш игрока 1 и минимальный ожидаемый проигрыш игрока 2 с учётом результатов состоявшихся игр: (15) В (k + 1)-й игре игрок 1 должен использовать свою стратегию ik+1 , доставляющую максимальный ожидаемый выигрыш vmaxk, а игрок 2 – стратегию jk+1, обеспечивающую минимальный ожидаемый проигрыш vmink. Тогда векторы, координаты которых равны частотам, с которыми чистые стратегии обеспечивали максимальный выигрыш игроку 1 и минимальный проигрыш игроку 2
(16) являются k-м приближением к оптимальным стратегиям игроков. При этом является приближением к положению равновесия (седловой точке), так как седловая точка находится между vmaxk и vmink. Точность этого приближения можно оценить соотношением
Итерационный процесс сходится, т. е. после достаточного числа итераций можно получить решение с заданной точностью. Но у данного метода довольно малая скорость сходимости, т. е. для получения приемлемого решения необходимо выполнить большое число итераций.
Задачи Принятие решений при совместных действиях. 1. задача Магазин может завести в различных пропорциях товары типа (А, Б, В). Их реализация, а следовательно и прибыль (Сij) завися от вида товара и состояния спроса. Предполагая, что последний может характеризоваться тремя состояниями (1 2 3) и учитывая, что спрос зависит от моды и прогнозировать его невозможно, определить оптимальные пропорции в закупке товаров из условия гарантированной прибыли при следующих вариантах матриц. 1 2 вариант 1 При сведении этой задачи к задаче линейного программирования получаем результат Седловая точка: 6,6 Оптимальная стратегия первого игрока: x1 = 0,1 x2 = 0,1 x3 = 0,8 Оптимальная стратегия второго игрока: y1 = 0,2 y2 = 0,6 y3 = 0,1 Это означает, оптимальные пропорции выпуска товаров являются: 10% доля товара А, 10% доля товара Б, 80% доля товара В. При этом соотношении магазин получит доход не менее 6,6. вариант 2 Седловая точка: 13,8 Оптимальная стратегия первого игрока: x1 = 0 x2 = 0,8 x3 = 0,2 Оптимальная стратегия второго игрока: y1 = 0,1 y2 = 0,9 y3 = 0 При данных матрицы 2 разумнее всего 80% продавать товара Б и 20% товара В, при этом товар А вообще не реализуется. Магазин получит доход не менее 13,8 Задача 2 Магазин может завести в различных пропорциях товары типа (А, Б, В). Их реализация, а следовательно и прибыль (Сij) завися от вида товара и состояния спроса. Предполагая, что последний может характеризоваться тремя состояниями (1 2 3) и учитывая, что спрос зависит от моды и прогнозировать его невозможно, определить оптимальные пропорции в закупке товаров из условия гарантированной прибыли при следующей матрице. Точность: 0,5 Седловая точка: 14,8 Оптимальная стратегия первого игрока: x1 = 0,3 x2 = 0 x3 = 0,7 Оптимальная стратегия второго игрока: y1 = 0,1 y2 = 0 y3 = 0,9 Методом Брауна-Робинсона установлено, что наилучший вариант реализации продукции для магазина 30% товара А, 70% товара В. При этом гарантирован доход 14,8. Задача 3 Является ли игра с платежной матрицей
(60, 20)
(10, 50)
(20, 80)
(40, 70)
(40, 20)
(50, 30)
(80, 50)
(30, 60)
(90, 70) Антагонистической? Существуют ли в ней 1. ситуация равновесия в чистых стратегиях? 2. Вполне смешанная ситуация? 3. Ситуация оптимальная по Парето? Чтобы назвать эту игру антагонистической нужно, чтобы выполнялось условие: aij + bij = 0 или aij + bij = const , в данном случае игра не является антагонистической. 1. В игре не существует ситуация равновесия в чистых стратегиях. 2. В игре не существует вполне смешанной ситуации. 3. Расчет игровых ситуаций оптимальных по Паретто Платежная матрица игрока 1 60 10 20 40 40 50 80 30 90 Платежная матрица игрока 2 20 50 80 70 20 30 50 60 70 Множество ситуаций, оптимальных по Парето, содержит 2 элемента: (1, 3) (3, 3)