диплом крнфликты. Ю. В. Литвинов Моделирование конфликтов в двухсторонней теории игр Учебное пособие
 Скачать 0.67 Mb.
|
|
максимизации точка превращается в расширяющуюся окружность, которая, при появлении ограничений, упирается в эллипс. Поэтому задача вписывания окружности в эллипс является задачей максимума с ограничениями в виде равенства. 13 Аналогично, если нет ограничений, то максимум J(x)=∞, линия постоянного уровня представляет окружность бесконечного радиуса. При минимизации окружность сужается, пока не сожмет эллипс. Поэтому задача описывания окружности вокруг эллипса будет задачей минимизации целевой функции с ограничениями в виде равенства. Значение λ в данном случае можно было и не находить. Однако в других задачах без определения вектора λ не найти вектор х. Поясним назначение вектора λ с помощью рис. Рисунок Точка экстремума в задаче нелинейного программирования На рис показано решение экстремальной задачи. Линия G(x)=0 задает ограничения, J(x)=Const - линия постоянного уровня целевой функции. Вектор- градиент показывает величину и направление возрастания целевой функции в точке касания. По определению он перпендикулярен касательной к целевой функции. Величина возрастания определяет степень кривизны целевой функции. Аналогично производная также определяет степень кривизны и направление возрастания ограничений в транспонированном направлении. В соответствии с первым уравнением Лагранжа должно выполняться условие Ò ) ( ) ( dx x dG dx x dJ , те. векторы производных должны лежать на одном направлении и быть одинаковыми по длине. Они лежат на одном направлении, поскольку перпендикулярны одной и той касательной. Длина же каждого из векторов зависит от степени кривизны его кривой. Поскольку кривизна ограничений и целевой функции в точке касания в общем случае может быть разной, то множитель λ выравнивает эту длину, чтобы строго выполнялось равенство 14 Ò ) ( ) ( dx x dG dx x dJ Если задать уравнение ограничений в виде линейной функции a x 1 + b x 2 = 0, а целевую функцию оставить прежней, то задача экстремума геометрически представляет собой задачу касания (рис) и является задачей максимума с ограничением в виде равенства. Рис. Ограничение в виде линейной функции Решается задача аналогично. Вектор х определяет координаты точки касания. 2. Введение в матричную теорию игр двух лиц Основоположником математической теории игр является американский математик Дж. Фон Нейман [3]. Теория игр используется для моделирования конфликтных ситуаций, когда сталкиваются противоположные интересы нескольких или двух лиц. В экономике теория игр описывает явление конкуренции. В задачах технического творчества с помощью теории игр можно моделировать процесс конфликта между альтернативными свойствами технического противоречия. Рассмотрим, как наиболее простую, игру двух сторон или лиц игроков Аи В. Игра задается правилами, в которых определяются поведение игроков или ходы, а также расплата каждой из сторон за их ходы. В дискретных играх, когда число возможных ходов образует счетное множество, игра обычно задается матрицей игры. В матрице игры записываются выигрыши или проигрыши игроков при определенных ходах. Матрица игры приведена в таблице 1. В таблице 1 обозначения A1, A2 ... An являются возможными ходами игрока A, и B1, B2 ... Bm – возможные ходы игрока B. 15 Таблица 1. Платежная матрица игры B1 B2 … Bm A1 a 1,1 a 1,2 … a 1,m A2 a 2,1 a 2,2 … a 2,m … … … … … An a n,1 a n,2 … На пересечении строки столбцов (j=1,...m) находятся элементы a i,j , которые означают расплату заходи ответный ход Bj. 2.1. Игра с нулевой суммой. Минимаксная стратегия В играх с нулевой суммой выигрыш игрока А равен проигрышу игрока В. Примем следующее условие если a i,j > 0, то это выигрыш игрока Аи проигрыш игрока В, если a i,j < 0, то это проигрыш игрока Аи выигрыш игрока В. В качестве примера рассмотрим следующую игру с нулевой суммой. Пусть игрок А имеет 3 возможных хода А – игрок А ходит красной картой втемную (рубашкой карты вверх, А - игрок А ходит черной картой втемную, А – игрок А ходит зеленой картой втемную. Игрок В имеет два возможных хода В- игрок Входит красной картой, В - игрок Входит черной картой. После каждой игры, а в математической теории игра одна игра включает ход игрока Аи ответный ход игрока В, наступает следующая расплата если при открытии обе карты оказались одного цвета, то А выигрывает 5 рублей, долларов или каких-то 5 единиц чего-то, а игрок В проигрывает эти 5; если карты оказались красной и черной, то А проигрывает 5, а В выигрывает 5; если карты оказались зеленой и красной, то А выигрывает 4, а В проигрывает 4; если карты оказались зеленой и черной, то А проигрывает 4, а В выигрывает 4. Платеж задается матрицей в таблице 2. Таблица 2. Платежная матрица игры B1 B2 A1 5 -5 A2 -5 5 A3 4 -4 Матрица игры позволяет найти нижнюю Wa и верхнюю Wb цены игры. Зададим новую игру матрицей в таблице 3. 16 Таблица 3. Платежная матрица игры B1 B2 B3 min по строке A1 2 -3 4 -3 A2 -3 4 -5 -5 A3 4 -5 6 -5 max по столбцу Wa=-3 max по столбцу 4 4 6 min по строке Wb=4 Как может рассуждать игрок А, разглядывая эту матрицу Если я буду играть А, то могу выиграть 2 или 4, а проиграть -3; если буду играть А, то могу выиграть 4, а проиграть -3 или -5; приходе А могу выиграть 4 или 6, а проиграть -5». Если игрок А очень осторожен, то он всегда будет ходить Атак как в этом случае больше -3 он не проиграет никогда, как бы не отвечал игрок В. Следовательно, величина, равная Wa=-3, есть гарантированный результат игры для игрока А. Этот гарантированный результат игрока А называется нижней ценой игры и определяется по формуле ij j i a a min Рассмотрим ситуацию для игрока В. Если В будет отвечать В, то проиграет 2 или 4, а выиграет – 3; если будет отвечать В, то проиграет 4, а выиграет –3 или –5; если ответит В, то выиграет – 5 , а проиграет 4 или 6. Следовательно, для игрока В гарантированный проигрыш равен 4. Гарантированный результат для игрока В называется верхней ценой игры и определяется по формуле ij i j a b max Нахождение Wa и Wb показано в таблице 3, в последней строке и последнем столбце. Для определения Wa сначала по строке А находится минимальный элемент (на пересечении Аи В, затем также по строке А находится минимальный элемент (на пересечении Аи В, потом минимальный элемент по строке А (Аи В. Затем из этих трех элементов выбирается максимальный элемент. Аналогично находится и Wb, только сначала находится максимум по столбцам, а затем из этих максимальных элементов находится минимальный. Иногда матрица игры содержит только положительные элементы a i,j >0. Это получается тогда, когда один игрок (А) всегда сильнее, чем другой игрок 17 В. Для игрока В смысл игры заключается в том, чтобы проиграть как можно меньше, а не играть игрок Вне может, поскольку между ними игроком А есть конфликт. Игрок В вынужден принимать те или иные решения, те. ходить в ответ на действия (ходы) игрока А. Даже если матрица игры имеет отрицательные элементы, то она легко приводится к эквивалентной матрице только с положительными элементами. Для этого ко всем элементам матрицы добавляется одно и тоже положительное число, по крайней мере, большее или равное максимальному модулю отрицательных чисел. Например, если ко всем элементам матрицы в таблице 3 добавить число 5 или больше, то получим матрицу с положительными элементами. Добавим, например, 10. Тогда получим следующую матрицу игры Таблица 4. Платежная матрица игры B1 B2 B3 A1 12 7 14 A2 7 14 5 A3 14 5 16 С такой матрицей игрок А будет все время выигрывать. Чтобы расплата была эквивалентна матрице игры в таблице 3, перед началом каждой игры (хода) игрок А должен заплатить игроку В добавленное число, те. 10. Когда верхняя и нижняя цены игры одинаковы, тов игре существует седловая точка (Табл. 5). Таблица 5. Платежная матрица игры B1 B2 min по строке A1 3 2 2 A2 4 1 1 max по столбцу Wa=2 max по столбцу 4 2 min по строке Wb=2 18 Седловая точка получается приходе А1В2. Наличие в игре седловой точки является самой выгодной ситуацией для осторожных игроков. Правило выбора ходов, при котором каждой из играющих сторон гарантируется определенный результат, называется минимаксной или максиминной стратегией (название происходит от вида формул, по которым определяются цены игры. Для матрицы игры в таблице 5 Wa=2 означает, что игрок А, придерживаясь минимаксной стратегии, выиграет не менее 2, как бы не играл игрок В. Для игрока В Wb=2 означает, что игрок В проиграет не более 2, если будет придерживаться минимаксной стратегии, как бы не играл игрок А. Рассмотрим еще пример игры (табл. 6): Таблица 6. Платѐжная матрица игры B1 B2 min по строке A1 2 3 2 A2 4 1 1 max по столбцу Wa=2 max по столбцу 4 3 min по строке Wb=3 В этой игре нет седловой точки, так Wa = 2, а Wb = 3. Нетрудно убедиться, что минимаксной стратегией для игрока А будет все время ход А, а для игрока Вход В. Это гарантирует игроку А выигрыш не менее 2, а игроку В – проигрыш не более 3. Простейшая картинка (рис) поясняет эту ситуацию, на которой изображены линии верхней и нижней цен игры и промежуток между ними, который называется ядром игры. Рисунок 2.1. Ядро игры Как видно, ядро непустое оно равно 1. В игре же с седловой точкой ядро пустое, поскольку верхняя и нижняя цены игры совпадают. Игроку Вне понизить верхнюю цену (чтобы уменьшить гарантированный проигрыша игроку Ане повысить нижнюю цену (чтобы поднять гарантированный 19 выигрыш. В седловой точке игроки максимально сближаются по своим интересам, можно сказать, попадают в точку равновесия. Если ядро непустое, то между положениями игроков есть некоторое пространство, которое представляет интерес как для одного, таки другого игрока, чтобы его использовать с целью улучшения своего результата. Рассмотрим ситуацию нескольких, подряд идущих игр, те. как бы одну многоходовую игру. Например, игрок В видит, что А все время ходит Аи может подумать Зачем мне все время отвечать В и проигрывать 3? Лучше я отвечу ходом В и проиграю всего 2». И игрок В начинает рисковать, уходя от минимаксной стратегии. Ситуация становится менее выгодной для игрока А он стал выигрывать меньше – вместо 3 всего 2. Хотя это и гарантированный выигрыш, нона каждой игре терять 1 – может не понравиться игроку А. Тогда игрок А тоже начинает рисковать, уходя от минимаксной стратегии, и на ходы В будет отвечать А, выигрывая при этом 4. Стратегия В1А2 становится очень невыгодной для игрока Вон все время проигрывает 4. Естественно, он возвращается снова к своей минимаксной стратегии, начиная на ход А отвечать В. При этом игрок В проигрывает всего лишь 1. Складывается ситуация, самая невыгодная для игрока А – он не получает даже гарантированного выигрыша. Он тоже возвращается к своей минимаксной стратегии А. Игра, в смысле стратегии, снова начинается с исходного положения и т.д. С геометрической точки зрения уход от осторожной к рисковой стратегии для каждого игрока как рази означает «вгрызание» в ядро игры со своей границы. Интересы игроков противоположны, один стремится как можно больше выиграть, а другой – как можно меньше проиграть, но объективно они могут покусать ядро игры каждый со своей стороны, чтобы поднять нижнюю цену игры Wa (выигрыш не менее для игрока Аи опустить верхнюю цену игры Wb (проигрыш не более для игрока В. Конечно, каждый старается откусить от ядра больше, чем противник. Но как этого добиться, зависит от степени информированности игроков о поведении друг друга. И тот и другой игрок желают знать, когда, после какой очередной игры противник меняет стратегию, те. узнать серию постоянно повторяющихся и чередующихся ходов противника. С другой стороны, каждый из них заинтересован сохранять свою стратегию в секрете от противника. Такая ситуация самая интересная в теории игр. Возникает вопрос нет ли в этой ситуации многоходовой игры какой-либо седловой точки внутри ядра Нельзя ли прийти к какому-нибудь равновесию при отсутствии информации о возможной стратегии противника и получить гарантированный результат Положительный ответ на эти вопросы дают так называемые смешанные стратегии и основной результат теории игр. 20 2.2. Смешанные стратегии В смешанных стратегиях предполагается, что ходы могут выбираться двояким образом. Это - личные ходы игроков, когда они сами выбирают тот или иной хода также ходы, которые выбираются случайным образом. Если все ходы каждого из противников выбираются случайным образом, получается смешанная стратегия, наиболее засекреченная для противника. В матрице игры после каждого хода проставляется его вероятность p i – вероятность хода Ai и q j – вероятность хода Bj. Матрица игры со случайными ходами используется также для описания игры с природой. Матрица игры для смешанной стратегии имеет следующий вид (Табл. 7): Природа свои действия, ходы выбирает случайным образом, причем одни ходы могут благоприятствовать нашим действиям, а другие ходы могут вредить. Таблица 7. Платѐжная матрица игры B1 B2 … Bm q 1 q 2 … q m A1 p 1 a 1,1 a 1,2 … a 1,m A2 p 2 a 2,1 a 2,2 … a 2,m … … … … … … An p n a n,1 a n,2 … Для вероятностей ходов каждого из игроков должно выполняться правило нормировки 1 , 1 Для нашего примера с матрицей игры из таблицы 6 в случае использования смешанных стратегий необходимо ввести вероятности ходов А1,А2 и В1,В2. Возникает вопрос как назначать вероятности ходов Ответ на этот вопрос может дать основной результат теории игр. Получаем матрицу игры в таблице 8: Таблица 8. Платежная матрица игры B1 B2 min по строке q 1 q 2 A1 p 1 2 3 2 A2 p 2 4 1 1 max по столбцу 4 3 min по строке Wb=3 max по столбцу 21 Основной результат теории игр. Если игрок А использует оптимальную смешанную стратегию, то его ожидаемый выигрыш остается постоянными равным ν, независимо оттого, какую стратегию использует игрок В. Аналогично, если игрок В использует оптимальную смешанную стратегию, то его ожидаемый проигрыш остается постоянными равным ν, независимо оттого, какую стратегию использует игрок А. Примечание оба игрока должны использовать только активную стратегию, те. вероятности каждого из возможных ходов не должны быть нулевыми. Этот результат был получен фон Нейманом [3] и здесь приводится без доказательства. Оптимальная смешанная стратегия определяется в результате решения задачи максимина или минимакса на протяжении уже многих игр (ходов. Величина ν называется эффективностью игры и равна n i m j j i j i i j n i m j j i j i j i q p a q p a ν 1 1 , 1 1 , max min min Таким образом, эффективность игры можно найти по этим формулам, если известны вероятности ходов. Однако, чаще всего, решается другая задача найти вероятности ходов p i и q j , которые дают экстремальную эффективность игры ν при ограничениях 0 , 0 , 1 , 1 Такая задача относится к задачам на нахождение условного экстремума функции многих переменных, тек задачам программирования. За много игр ходов) величина ν будет определять гарантированный выигрыш игрока Аи гарантированный проигрыш игрока В, причем по сравнению с чисто минимаксными стратегиями ν ≥ Wa, ν ≤ Wb. Игрок А может выиграть больше, чем Wa, а игрок В – проиграть меньше, чем Wb. Собственно, это и есть основной результат теории игр. Как и любая задача линейного или нелинейного программирования, задача нахождения вероятностей, экстремизирующих ν, может иметь решения, а может и не иметь. Ответ на этот вопрос дает теорема Куна-Такера [4,5] для решения экстремальных задач с ограничениями в виде равенств и неравенств. В частном случае, когда игра имеет всего два возможных хода у каждого из игроков, задача экстремизации решается просто – она сводится к решению системы линейных уравнений в виде равенств. Рассмотрим снова пример игры с матрицей из таблицы 8. Обе системы имеют потри уравнения и потри неизвестных две вероятности и эффективность ν . Для этого случая вероятности ходов находятся из решения системы уравнений 22 p 1 a 11 + p 2 a 21 =ν p 1 a 12 + p 2 a 22 =ν p 1 + p 2 =1 q 1 a 11 + q 2 a 12 = ν q 1 a 21 + q 2 a 22 = ν q 1 + q 2 = 1 Решая отдельно для p и q эти системы, получаем решение p 1 = 0,75, p 2 = 0,25, ν =2,5 q 1 = 0,5, q 2 = 0,5, ν =2,5 Следовательно, игрок А должен ходить ходом Ас вероятностью 0.75, а ходом Ас вероятностью 0.25. Игрок В должен ходить ходами В и В равновероятно, по 0.5. Практически реализовать такую игру игроком А можно с помощью урны с 4 шарами одинаковой формы тремя белыми и одним черным. При вытаскивании белого шара игрок А делает ход А, а при вытаскивании черного шара – ход А. После каждого хода шар должен возвращаться в урну. Для игрока В реализовать его случайные ходы можно при помощи подбрасывания монеты. Обратим внимание, что для этого примера нижняя цена игры (см. рис) поднялась на 0.5, а верхняя цена игры опустилась на 0.5. Нижняя и верхняя цены за множество ходов становятся равными, непустое ядро размером 1 стягивается в седловую точку, игроки Аи В в среднем разгрызают ядро поровну. Для случая матрицы игры размером больше х для нахождения неизвестных вероятностей решается задача линейного программирования. Задача ставится следующим образом. Задана матрица игры М a i,j ] . Необходимо найти 1) вектор p мерностью n x 1 вероятностей ходов А, который максимизирует эффективность игры ν при ограничениях 0 , 1 , 1 1 1 где - n p p p p 2 1 T , а единичная матрица-строка [1 1 …1] имеет размер х n. 2) вектор q мерностью m x 1 вероятностей ходов Bj, который минимизирует эффективность игры ν при ограничениях , 23 0 , 1 , 1 1 1 где - m q q q q 2 1 , а единичная матрица-строка [1 1 …1] имеет размер х m. Рассмотрим пример. Задана матрица игры М, необходимо найти вероятности ходов игроков Аи В, обеспечивающих оптимальную смешанную стратегию. 2 3 2 1 2 4 4 1 2 3 2 3 M Найдем вероятности ходов для игрока А. Записываем произведение 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 T 2 3 2 ; 2 4 ; 4 2 ; 3 2 3 2 3 2 1 2 4 4 1 2 3 2 3 p p p p p p p p p p p p p p p M Каждый элемент матрицы-строки в правой части равенств должен быть больше или равен ν: 3p 1 +2p 2 +3p 3 ≥ν 2p 1 +p 2 +4p 3 ≥ν 4p 1 +2p 2 +p 3 ≥ν 2p 1 +3p 2 +2p 3 ≥ν Целевой функцией, которую надо максимизировать, является также ν. Величина ν находится в правой части неравенств, поэтому для получения целевой функции одно из неравенств приводим к эквивалентному равенству при помощи новой фиктивной переменной p 4 ≥ 0. Возьмем, например, первое неравенство и из его левой части вычтем p 4 . Получаем равенство, определяющее целевую функцию, 3p 1 +2p 2 +3p 3 - p 4 = ν . Остальные неравенства совместно с уравнением нормировки вероятностей образуют ограничения задачи линейного программирования, причем в их правую часть подставляется найденное значение ν. , 24 Задача линейного программирования решается с помощью стандартной программы максимизации и минимизации функций среды Mathcad. Программа может быть написана в разных вариантах, в том числе, с использованием индексированных переменных. Впервой строке задаются произвольно начальные значения вероятностей 0 ≤ p i <1. Во второй строке определяется зависимость целевой функции от ее аргументов. Собственно программа максимизации начинается словом «Given», после которого размещаются в произвольном порядке все уравнения ограничений в виде равенства и неравенств. Вектор p содержит ответ задачи линейного программирования p1 = p2 = p3 = p4 =1/3 (Mathcad дает ответ в виде десятичной дроби с ограничением числа знаков в дробной части числа. Подстановка полученных значений pi=1/3 в функцию ν дает ее значение в экстремальной точке ν = 2.3333=7/3. Текст программы без индексированных переменных приведен на рис. 2.2. Рисунок 2.2. Программа максимизации для игрока А Обратим внимание, что нижняя цена игры при минимаксной стратегии равна Wa=2, оптимальная смешанная стратегия повышает нижнюю цену игры для игрока А на 1/3. Аналогично находим вероятности ходов для игрока В 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 2 4 3 3 2 2 2 4 2 3 2 3 2 1 2 4 4 1 2 3 2 3 q q q q q q q q q q q q q q q q q M 3q 1 +2q 2 +4q 3 +2q 4 ≤ ν 25 2q 1 +q 2 +2q 3 +3q 4 ≤ ν 3q 1 +4q 2 +q 3 +2q 4 ≤ ν Для нахождения ν клевой части первого неравенства добавляем фиктивную вероятность q 5 ≥ 0: 3q 1 +2q 2 +4q 3 +2q 4 + q 5 = ν Ответом являются вероятности q1=0, q2=0.25, q3=0.16667=1/6, q4=0.58333=7/12, q5=0. Минимальное значение υ=2.3333=7/3. Обратим внимание, что верхняя цена этой игры при минимаксной стратегии Wb=3. Таким образом, верхняя цена игры при оптимальной смешанной стратегии для игрока В понижается на 2/3. Ядро стягивается в седловую точку. Игрок В разгрызает 2/3 ядра, а игрок А – всего 1/3. Кроме того, вероятность q1 хода В для игрока В равна 0, поэтому этот ход должен быть исключен из возможных ходов игрока В. Программа в среде Mathcad имеет вид (рис Рисунок 2.3. Программа минимизации для игрока В Окончательно матрица игры для смешанной оптимальной стратегии приобретает вид, представленный в (табл. 9). Таблица 9. Платежная матрица игры |