Лекция: Марковская модель согласования решений
При создании математических моделей согласования решений должны фигурировать следующие компоненты
— конечное множество решений (альтернатив) Ki, стратегий, где i ϵ S – номер состояния системы:
— матрици переходов П[s], соответствующие тому или иному принятию к- решению
— матрицы доходов (расходов) R[s], также отражающее эффективность данного решения
Формально, управляемой цепью Маркова (УЦМ) называется случайный процесс, обладающий марковским свойством и включающий в качестве элементов математической модели конструкцию (кортеж) < Ki, П[s], R[s] >. Решение, принимаемое в каждый конкретный момент (шаг процесса) назовем частным управлением.
Таким образом, процесс функционирования системы описываемой УЦМ, выглядит следующим образом:
-если система находится в состоянии i ϵ S и принимается решение k ϵКiто она получает доход ri;
-состояние системы в последующий момент времени (шаг) определяется вероятностью Pij, то есть вероятность того, что система из состояния I € S перейдет в состояние j ϵS, если выбрано решение Ki.
Очевидно, общий доход за n -шагов является случайной величиной, зависящей от начального состояния системы и качества принимаемых в в течение хода процесса принятиярешений, причем это качество оценивается величиной среднего суммарного дохода (при конечном времени) или среднего дохода за единицу времени (при бесконечном времени). В этих двух случаях для нахождения оптимальных решений обычно сводится в первом случае к решению задач динамического стохастического программирования — рекуррентный алгоритм нахождения оптимального решения, а во втором к решению задач линейного программирования — итерационный алгоритм.
33. Согласование групповых решений: Принцип Курно, Парето, Эджворта
Принцип Курно(принцип индивидуальной рациональности)
Если все участники решения являются независимыми друг от друга и имеют различные предпочтения, то никому из участников решения не выгодно менять предлагаемый вариант решения, если для каждого из них не существует лучшего варианта. Реализация принципа индивидуальной рациональности зависит от тех предпочтёний, которые имеет каждый участник решения. Принцип действует только тогда, когда индивидуальные предпочтения для вариантов решения таковы, что каждому участнику в итоге они не принесут большого ущерба или выгоды.
Принцип Парето.
Если все участники группового решения имеют общие и согласованные цели, то все они являются сильно зависимыми друг от друга, представляют одну коалицию, и их предпочтения могут быть таковы, чтобы принять один вариант из множества так называемых недоминированных вариантов решения. Это означает, что всем участникам коалиции невыгодны остальные варианты, которые называют доминированными вариантами решения. Решения, соответствующие этому принципу, называются решениями по принципу Парето. Рассмотрим сначала понятие доминирования. Допустим, есть два варианта решения и каждый из них описывается своими значениями, число которых равно к: B1= (x11, x12, ..., x1х), B2 = (x21, x22,...,x2х).
Вариант В1 будем называть вариантом, доминирующим над вариантом В2, если все значения его характеристик не хуже значений характеристик варианта В2 и значение хотя бы одной характеристики лучше. Каждый из доминирующих вариантов доминирует над областью, ограниченную значениями своих характеристик, в которую может попасть несколько вариантов. Если имеем исходное множество вариантов, число которых более двух, то среди этих вариантов можно выделить то множество, которое называется множеством недоминируемых вариантов,или множествомПарето.
Варианты множества Парето обладают двумя важными свойствами:
1) варианты множества Парето доминируют над всеми остальными вариантами исходного множества;
2) варианты внутри множества Парето находятся в противоречивых отношениях и среди них нет доминирующих вариантов.
Принцип Эджворта (Принцип коалиций).
Если число участников решения в каждой коалиции больше одного, то их предпочтения могут быть таковы, что каждой из коалиций невыгодно менять свое решение, когда у них нет лучшего решения. Этот принцип называется принципом Эджворта. По количеству коалиций этот принцип занимает промежуточное место между принципом Курно — индивидуальной рациональности и принципом Парето — сильной заинтересованности одной коалиции в выборе доминирующих вариантов решения.
34. Теория игр: платежная матрица, чистые и смешанные стратегии, решение игры.
Тео́рия игр –это математическаятеория конфликтных ситуаций, т.е. таких ситуаций, в которых сталкиваются интересы двух или более сторон, преследующих различные цели.
Играпредставляет собой математическую модель реальной конфликтной ситуации. От реальной конфликтной ситуации она отличается тем, что ведется по определенным правилам, в которых должны быть указаны:
— порядок чередования действий (ходов) участников;
— правила выполнения каждого хода;
— количественный результат игры (выигрыш, проигрыш), к которому приводит данная совокупность ходов.
Игра, в которой участвуют два игрока Аи В,называется парной,если игроков больше двух, то это игра – множественная. Игра, в которой выигрыш одного из игроков равен проигрышу другого, называется игрой с нулевой суммой (антагонистической игрой).
Стратегией игроканазывается совокупность правил, определяющих выбор варианта действий при каждом личном ходе игрока в зависимости от ситуации, сложившейся в процессе игры.
Стратегия выбираемая игроком сознательно исходя из анализа сложившейся обстановки называется личной (или чистой).
Стратегия игрока называется оптимальной, еслиона обеспечивает данному игроку (обычно игроку А) при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш независимо от поведения противника (могут быть использованы и другие показатели оптимальности).
Оптимальные стратегии характеризуются устойчивостью, то есть ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии.
Партия игры– это однократная возможная реализация правил игры (стратегий) игроками.
Матричной игрой называется парная игра, осуществляемая по следующим
правилам:
1. В игре участвуют два игрока — Аи В;
2. Каждый из игроков обладает конечным набором стратегий (для игрока А — это стратегии А1, А2, …… Аm, а для игрока В — это стратегии В1, В2,…….Вn);
3. Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
4. И выигрыш, и проигрыш выражаются числами аij, которые являютсяэлементами, так называемой платежной матрицы. В частности, выигрыш для игрока А при выборе стратегии Аi, и игроком В – стратегии Вj равен аij, а для игрока В –он равен вij =-аij, то есть является проигрышем.
Платежная матрица (или матрица игры) –является одним из способов задания матричной игры, который называется нормальным. Второй способ задания игры – позиционный способ связан развернутой формой задания игры и сводится к построению графа последовательных шагов игры (дереву игры).
Если условие вij =-аijне выполняется, то есть каждый из игроков имеет свою платежную матрице, тогдаэтапарная игра является игрой с ненулевой суммой и называется биматричной игрой.
Решить матричную (антагонистическую) игру– значит найти для игроков А и В их оптимальные стратегии.
Решение игры связано с матрицей (аij)и следующими понятиями:
Нижняя цена игры α=maxmin аij (сначала находится минимум в каждой строке, а
I j
потом из полученных минимумов находится максимум). Это гарантированный выигрыш игрока Апри любой стратегии игрока В.
Верхняя цена игры β=minmax аij(сначала находится максимум в каждом столбце,
J i
а потом из полученных максимумов находится минимум). Это гарантированный проигрыш игрока Впри любой стратегии игрока А.
Очевидно α<= β.В случае α=βговорят о цене игры ν=α=β.Соответствующие цене игры стратегии являются оптимальными, а сама игра есть игра с седловой точкой.
В случае, когда α<β седловой точки не существует.В этом случаерешение игры ищестся в смешанных стратегиях. Доказано (Дж. Фон Нейман), что конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно в смешанных стратегиях.
Смешанная стратегия состоит в том, что при повторении игры происходит случайный выбор стратегии из множества смешиваемых стратегий и для каждой смешиваемой стратегии указывается вероятность (частота) ее выбора. В таком случае для каждого игрока указывается вектор частот, с которым следует применить ту или иную стратегию.
Для игрока А это Р=(р1,….рm), а для игрока В – это Q=(q1,…….,qn), при этом
Σ pi=1 и Σ qj=1,средний выигрыш игрока А равен НА(Р,Q)=Σ Σ аij pi qj
Если вероятность применения стратегии отлична от нуля, то такая стратегия называется активной.
Оптимальными смешанными стратегиями Р0и Q0 называются стратегии, если выполняется неравенство:
НА(Р,Q0)=< НА(Р0,Q0)=< НА(Р0,Q)
В этом случае НА(Р0,Q0)называется ценой игрыи обозначаетсяα=<ν=< β
Первое из неравенств означает, что отклонение игрока Аот своей оптимальной смешанной стратегии при условии, что игрок В придерживается своей оптимальной смешанной стратеги, приводит к уменьшению среднего выигрыша игрока А.Второе из неравенств по смыслу аналогично первому с той лишь разницей что касается игрока В.
Решение всякой парной конечной игры с нулевой суммой может быть получено методами линейного программирования.
Сведение матричной игры к задаче линейного программирования
Из свойств оптимальных смешанных стратегий игроков вытекает, что при любой стратегии игрока Вдля игрока Аимеет место неравенство:
Σ аij pi>= νi
Обозначая далее
xi= pi/ ν
исходное неравенство можно переписать следующим образом
Σ аij хi>=1и Σ хi>=1/ν
ii
Поскольку игрок А стремиться максимально увеличить свой гарантированный выигрыш, то задача отыскания решения матричной игры сводится к следующей задаче линейного программирования:
Σ хi → min
i
Σ аij хi>=1
i
Рассуждая аналогичным образом со стороны игрока В –он стремиться сделать свой гарантированный проигрыш минимальным. И вводя обозначения:
yi= qi/ ν
и учитывая, что Σ аij yi<=1получаем двойственную по отношению к
i
рассмотренной следующую задачу линейного программирования:
Σ yi→ max, Σ аij yi<=1