WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 | 2 || 4 | 5 |   ...   | 8 |

Метод расширения стратегий. В исходной игре все агенты выбирают свои стратегии одновременно и независимо, не обмениваясь информацией с другими игроками (возможность и целесообразность обмена информацией – информационные расширения игр – в играх с запрещенными ситуациями описаны в [12]). Можно рассмотреть игру, в которой каждый из игроков делает предположения о выборе других игроков или реакции других игроков на выбор им той или иной стратегии. В подобных играх используют концепцию П-решения (см. также Байесовское равновесие, равновесие Штакельберга и др. [16, 37, 50]), которая включает в себя максиминные равновесия, равновесия Нэша и ряд других как частные случаи.

Существует несколько частных случаев, в которых учет глобальных ограничений производится «автоматически». Если у каждого из игроков имеется доминантная стратегия (или в игре существует единственное равновесие Нэша), и игра характеризуется полной информированностью, то каждый из игроков может вычислить доминантные стратегии всех остальных игроков (соответственно – точку Нэша). Если при этом вектор доминантных стратегий (или точка Нэша) удовлетворяют глобальным ограничениям, то проблем их учета не возникает.

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

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

Метод согласования. Основная идея метода согласования заключается в следующем (см. также двухшаговый метод решения вероятностных и др. задач стимулирования и метод согласованного планирования [29, 32, 33]). На первом шаге решения задачи управления (стимулирования) центр для каждого вектора действий, принадлежащего множеству A’ (без учета глобальных ограничений) ищет допустимое управление, при котором данный вектор действий принадлежит множеству решений игры агентов. Результатом первого шага, например, в задаче стимулирования, является множество AM действий агентов, реализуемых при данных ограничениях M на систему стимулирования, AM A’. Затем на втором шаге центр ищет множество A* действий агентов, которые, вопервых, реализуемы, во-вторых, удовлетворяют заданным глобальным ограничениям B, и на которых достигается максимум его целевой функции – см. предыдущий раздел. То есть, на втором шаге центр решает следующую задачу:

(1) A* = Arg max (y).

y AM B Максимальная эффективность управления при этом равна (y*), где y* – произвольный элемент множества A*.

Метод изменения порядка функционирования. Обычно предполагается, что при известной стратегии центра агенты выбирают свои действия одновременно и независимо. Если центр (как метаигрок) может изменить порядок функционирования, то есть последовательность получения информации и выбора стратегий агентами, то, варьируя последовательность выбора стратегий агентами, можно существенно упростить задачу учета глобальных ограничений. Если существует нумерация агентов, такая что допустимые множества имеют вид: Ai = Ai(y1, y2, …, yi-1), то каждый агент должен при выборе своей стратегии учитывать ограничения, наложенные совместно глобальным ограничением и уже выбранными стратегиями агентов с меньшими номерами.

Например, допустимой с рассматриваемой точки зрения является последовательность функционирования ОС, имеющая вид сетевого графика (без контуров). Частным случаем является последовательный выбор стратегий агентами – так называемые производственные цепочки [34].

Еще раз подчеркнем, что возможность использования метода изменения порядка функционирования должна быть предусмотрена «правилами игры», то есть, учтена в модели ОС. Кроме того, следует иметь в виду, что множество равновесий в новой «иерархической» игре может отличаться то множества равновесий в исходной игре [30, 35].

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

Взаимозависимость и взаимосвязь агентов. В [34] ОС с зависимыми агентами были названы системы, в которых либо существуют глобальные ограничения на множество возможных действий, либо/и целевая функция каждого агента зависит не только от его собственных действий, но и от действий других агентов. Для того чтобы различать эти два случая, мы будем придерживаться следующей терминологии: если агенты производят свой выбор независимо (отсутствуют глобальные ограничения на вектор действий агентов), и целевая функция каждого агента зависит только от его собственной стратегии, и отсутствуют общие ограничения на управляющие переменные (допустимые функции стимулирования и т.д.), то такую ОС будем называть ОС с независимыми и несвязанными агентами1. Если добавляются общие ограничения на управления, то такие ОС будем называть ОС со слабо связанными агентами (агенты оказываются связаны косвенно – через ограничения на стратегии центра) [29, 33, 34]. Если добавляется зависимость целевой функции агентов от обстановки игры, то такую ОС будем называть ОС с сильно связанными (но независимыми!) агентами. Если добавляются только общие ограничения на множество стратегий агентов системы, то такую ОС будем называть ОС с зависимыми агентами (см. таблицу 1 ниже).

В [32, 34] исследовались задачи стимулирования в ОС с сильно связанными и независимыми агентами. В рамках гипотезы независимого поведения оптимальным оказывалось использование центром принципа декомпозиции игры агентов. Этот принцип заключается в следующем. Центр обещает каждому агенту: «я компенсирую твои затраты (подставив в них сложившуюся ситуацию игры) только в том случае, если твое действие совпадет с планом, во всех остальных случаях твое вознаграждение будет равным нулю». Использование такого управления реализует вектор планов как равновесие в доминантных стратегиях игры аген Таким образом, «независимость» агентов отражает свойства множеств их допустимых стратегий, а «связанность» – зависимость целевой функции агента от действий других агентов или наличие общих ограничений на управление.

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

Метод штрафов в задачах стимулирования в многоэлементных ОС имеет следующий вид. В общем случае считаем, что затраты агентов несепарабельны и приравниваем их минус бесконечности при недопустимых (с точки зрения глобальных ограничений) действиях агентов, после чего применяем технику анализа, описанную в [34] для ОС с независимыми агентами.

Метод согласования может использоваться в приведенном выше виде без каких-либо изменений. Напомним, что при решении задач стимулирования в многоэлементных ОС реализуемый оптимальной квазикомпенсаторной системой стимулирования вектор действий агентов входит в эту систему стимулирования как параметр [34]. Поэтому, в более общем случае, охватывающем и метод штрафов, и метод согласования, можно считать, что на агентов (или центр, что то же самое в силу оптимальности компенсаторных систем стимулирования) наложены штрафы следующего вида:

~ ( y), yA'B i ~ (y) = ( y) – некоторые неотрицательные i 0, yA'B, где i функции, i N. Тогда, если AM – множество реализуемых действий, определяемых без учета глобальных ограничений на действия агентов, то целевая функция центра в задаче стимулирования (с учетом глобальных ограничений) имеет вид:

n (2) (y) = H(y) – {c ( y) + ( y)}.

i i i=Задача планирования запишется в виде:

n (3) x* = arg max [H(y) – {c ( y) + ( y)}], i i xAM i =а максимальная эффективность1 стимулирования (эффективность оптимальной системы стимулирования) равна K* = (x*).

Мы не будем останавливаться подробно на таких простых утверждениях, следующих из анализа выражений (1)-(3), как то, что с расширением множеств AM (то есть с ростом возможностей центра по управлению) и B (ослаблением внешних – глобальных – ограничений) эффективность стимулирования не уменьшается и т.д.

В таблице 1 представлены возможные комбинации глобальных ограничений («+» – наличие глобальных ограничений, «-» – отсутствие глобальных ограничений) на множества допустимых стратегий агентов, их целевые функции и управления.

Таблица Классификация взаимосвязанности и взаимозависимости агентов Множества Управления Целевые допустимых (допустимые функции Тип ОС стратегий стратегии агентов агентов центра) ОС с независимыми и --несвязанными агентами 1.

ОС с зависимыми и +-несвязанными агентами 2.

ОС с зависимыми и ++- сильно связанными 3.

агентами ОС с зависимыми и слабо +-+ связанными агентами 4.

ОС с независимыми и -+- сильно связанными 5.

агентами ОС с независимыми и слабо связанными агента--+ 6.

ми ОС с независимыми и сильно связанными -++ 7.

агентами ОС с зависимыми и сильно связанными +++ 8.

агентами Рассмотрим, следуя [34], кратко все восемь случаев (см. таблицу 1) и покажем для них, что при решении задач стимулирования в многоэлементных ОС с зависимыми агентами учет глобальных ограничений на множества допустимых действий агентов возможно осуществлять, применяя как метод штрафов, так и метод согласования, причем их использование не изменяет результатов [32, 34] анализа систем с независимыми агентами.

Качественное обоснование справедливости последнего утверждения таково – взаимосвязь агентов (в смысле целевых функций) учитывается при решении задач стимулирования, а, используя выражения (2) и (3), удается декомпозировать и учесть «независимо» факторы, связанные с ограничениями на множества допустимых стратегий агентов и центра. Другими словами, в общем случае алгоритм действий при учете глобальных ограничений таков: для любой задачи стимулирования на втором этапе решения (этапе поиска оптимального для центра реализуемого действия) максимизация целевой функции центра ведется не по всему множеству A’ допустимых действий агентов, а по множеству: A’ B AM.

При этом «автоматически» обеспечивается учет глобальных ограничений как на действия агентов, так и на стимулирование.

Случай 1. ОС с независимыми и несвязанными агентами. Очевидно, что многоэлементная ОС с независимыми и несвязанными агентами может быть представлена в виде набора невзаимодействующих одноэлементных ОС (ни согласование с глобальными ограничениями, ни штрафы в данном случае не требуются). На втором этапе решения задачи стимулирования максимизация целевой функции центра ведется по множествам Ai, i N, независимо.

Случай 2. ОС с зависимыми и несвязанными агентами. Отметим, что в работе [12] при описании игр с запрещенными ситуациями взаимозависимость агентов отражалась следующим образом: целевая функция i-го агента определялась как wi( y), yBi fi(y) =, где Bi A’, i N.

-, yBi Если i N Bi = B, то имеет место случай одинаковых ограничений. В дальнейшем мы по умолчанию ограничимся случаем одинаковых ограничений, в котором центр имеет возможность использовать индивидуальное стимулирование для каждого агента, рассматривая в качестве реализуемых только вектора действий, принадлежащие множеству допустимых с точки зрения глобальных ограничений (метод согласования), то есть на втором этапе решения задачи стимулирования максимизация целевой функции центра ведется по множеству A’ B.

Случай 3. ОС с зависимыми и сильно связанными агентами (глобальные ограничения на управление отсутствуют). На втором этапе решения задачи стимулирования максимизация целевой функции центра также ведется по множеству A’ B.

Случай 4. ОС с зависимыми и слабо связанными агентами (глобальные ограничения на управление присутствуют). На втором этапе решения задачи стимулирования максимизация целевой функции центра ведется по множеству A’ B AM.

Случай 5. ОС с независимыми и сильно связанными агентами (глобальные ограничения на управление отсутствуют). На втором этапе решения задачи стимулирования максимизация целевой функции центра ведется по множеству A’.

Случай 6. ОС с независимыми и слабо связанными агентами (глобальные ограничения на управление присутствуют). На втором этапе решения задачи стимулирования максимизация целевой функции центра ведется по множеству A’ AM. Как отмечалось выше, задача управления ОС с независимыми и слабо связанными агентами может быть сведена к параметрической задаче управления набором одноэлементных ОС и задаче выбора оптимального значения параметра.

Случай 7. ОС с независимыми и сильно связанными агентами (глобальные ограничения на управление присутствуют). На втором этапе решения задачи стимулирования максимизация целевой функции центра также ведется по множеству A’ AM.

Случай 8. ОС с зависимыми и сильно связанными агентами (глобальные ограничения на управление присутствуют). На втором этапе решения задачи стимулирования максимизация целевой функции центра ведется по множеству A’ AM B.

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

Исследуем задачу управления ОС, в которой центр, помимо выбора системы стимулирования, имеет возможность влиять и на множества допустимых действий агентов (задачи управления ОС с переменными множествами допустимых действий рассматривались как в теории активных систем [8], так и в теории иерархических игр [12], причем, в основном, для динамических моделей – см. обзор в [31]).

Рассмотрим, следуя [34], многоэлементную ОС, в которой центр имеет возможность выбирать, помимо функций стимулирования, управляющие параметры ui Ui, i N, определяющие множества допустимых действий агентов, то есть Ai = Ai(ui). Тогда вектор действий агентов y принадлежит допустимому множеству n n A(u) = Ai(ui ), u = (u1, u2, …, un) U’ =.

U i i =1 i =Предположим, что y A’ u U’: y A(u). Содержательно данное предположение означает, что множество допустимых управлений центра достаточно «велико» для того, чтобы сделать допустимым любой вектор действий агентов.

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

n (4) (y,, u) = H(y) – ( y) – (u).

i i =Действия y*, выбираемые агентами, являются равновесием Нэша при данных управлениях, то есть n y* EN(, u) = {y Ai(ui ) | i N, zi Ai(ui) i= (y) – ci(y) (y-i, zi) – ci(y-i, zi)}.

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

(5) max,u) (y,, u) maxU.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 8 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.