ПРОЕКТИРОВАНИЕ МЕХАНИЗМА

В предыдущем разделе рассматривался вопрос: "Дана некоторая игра; каковой является рациональная стратегия?" В этом разделе приведен ответ на другой вопрос: "Предположим, что агенты являются рациональными; какую игру следует для них спроектировать?" А именно, требуется спроектировать некоторую игру, решения которой, состоящие из действий каждого агента, осуществляющего свою собственную рациональную стратегию, приводят к максимизации некоторой глобальной функции полезности. Эта проблемная область называется проектированием механизма, а иногда обратной теорией игр. Проектирование механизма представляет собой фундамент экономики и политологии. Применительно к коллекциям агентов этот подход обеспечивает возможность использования механизмов теории игр для создания успешно действующих систем из совокупности более ограниченных системных компонентов (даже противоборствующих системных компонентов), во многом аналогично тому, как создаются команды людей, способные достигать целей, далеко превосходящих возможности отдельно взятого человека.
К примерам применения принципов проектирования механизма относится организация аукционов по распродаже дешевых авиабилетов, маршрутизация пакетов TCP между компьютерами, принятие решения о том, как следует распределять выпускников медицинских учебных заведений по лечебным учреждениям, а также определение способа взаимодействия роботизированных игроков-футболистов со своими капитанами команд. Проектирование механизма вышло за рамки академической тематики в конце 1990-х годов, когда несколько государств, столкнувшись с проблемой аукционной распродажи лицензий на вещание в различных частотных диапазонах, потеряли сотни миллионов долларов потенциальных доходов в результате плохого проектирования механизма. Формально механизм состоит, во-первых, из языка для описания (потенциально бесконечного) множества допустимых стратегий, которыми могут руководствоваться агенты, и, во-вторых, из правила определения результата G, которое регламентирует вознаграждения, получаемые агентами при наличии некоторого профиля стратегий, состоящего из допустимых стратегий.
На первый взгляд задача проектирования механизма может показаться тривиальной. Предположим, что глобальная функция полезности [/декомпонуется на любое множество функций полезности отдельных агентов такое, что и = Y,± ui- В таком случае можно утверждать, что если каждый агент максимизирует свою собственную полезность, то нет сомнения в том, что это автоматически приведет к максимизации глобальной полезности. (Например, в лекциях по начальному курсу капитализма утверждается, что если каждый старается стать богаче, то общее благосостояние общества повышается.) К сожалению, такой принцип не оправдывается. Действия каждого агента могут повлиять на благосостояние других агентов так, что глобальная полезность уменьшится. Одним из примеров этого является трагическая деградация общих пастбищ (tragedy of the commons) — ситуация, в которой отдельные фермеры сгоняют все свои стада для того, чтобы они бесплатно паслись на общих сельских пастбищах, в результате чего наступает деградация этих общих пастбищ, что приводит к достижению отрицательной полезности для всех фермеров. Каждый фермер, отдельно взятый, действовал рационально, рассуждая, что он может использовать общие пастбища бесплатно, и хотя интенсивное использование общих пастбищ может привести к их деградации, его отказ выгонять на них свой скот делу не поможет (поскольку другие от этого все равно не откажутся). Аналогичные доводы выдвигаются теми, кто не желает ограничивать выбросы промышленных загрязнений в атмосферу и в океаны.
Стандартный подход при проектировании механизма для решения подобных проблем состоит в том, что с каждого агента должна взиматься плата за использование общих пастбищ. Вообще говоря, следует обеспечить, чтобы все побочные последствия (отрицательные влияния на глобальную полезность, которые не сказываются на результатах, полученных отдельными агентами) были выражены явно. При решении задачи труднее всего правильно определить цены. В пределе этот подход сводится к созданию механизма, который действительно требует от каждого агента, чтобы он максимизировал глобальную полезность. Применительно к отдельному агенту, который не обладает возможностью оценивать текущее состояние мира и не может наблюдать за результатами действий всех других агентов, такая задача становится невероятно трудной. Поэтому проектирование механизма должно сосредоточиваться на поиске таких механизмов, при использовании которых задача принятия решений для отдельных агентов становится несложной.
Вначале рассмотрим аукционы. В своей наиболее общей форме аукцион представляет собой механизм продажи некоторых товаров членам определенного сообщества покупателей. Стратегиями являются стратегии ведения торгов, а результаты определяют, кто получит товары и сколько заплатит. Одним из примеров, в которых аукционы могут войти в состав тематики искусственного интеллекта, является принятие решения совокупностью агентов о том, будут ли они участвовать в совместном плане. Хансбергер и Грош [706] показали, что эта задача может быть эффективно решена с помощью аукциона, в котором агенты распределяют между собой роли в совместном плане.
В данном разделе рассмотрим аукционы, в которых, во-первых, имеется только один вид товара, во-вторых, каждый покупатель руководствуется собственным значением полезности vL по отношению к данному товару, и, в-третьих, эти значения известны только покупателю. Покупатели вносят свои предложения Ьь а товары передаются тому, кто сделал предложение с самой высокой ценой, но механизм определяет, как нужно делать эти предложения и какую цену платит победитель (она не обязательно должна быть равна bi). Наиболее широко известным типом аукциона является английский аукцион, в котором лицо, проводящее аукцион, повышает цену товара, проверяя, остались ли еще заинтересованные покупатели, до тех пор, пока не останется только один потенциальный покупатель. Этот механизм обладает тем свойством, что покупатель, руководствующийся наивысшим значением vi5 получает товары по цене t+d, где t— наивысшая предложенная цена среди цен, предложенных всеми другими игроками, ad— величина, на которую лицо, проводящее аукцион, наращивает цену от одного предложения к другому9. Поэтому английский аукцион обладает тем свойством, что участники аукциона руководствуются простой доминантной стратегией — продолжать выдвигать предложения до тех пор, пока текущая цена остается ниже назначенного лично вами значения. Напомним, что "доминантной" стратегией называется стратегия, позволяющая противодействовать всем другим стратегиям, а это, в свою очередь, имеет тот смысл, что игрок может ею руководствоваться, невзирая на то, что существуют любые другие стратегии. Поэтому игроки не обязаны терять время и энергию, пытаясь предугадать возможные стратегии других игроков. Механизм, в котором игроки имеют доминантную стратегию, позволяющую скрывать свои истинные побуждения, называется механизмом защиты стратегии.
Одним из отрицательных свойств английского аукциона являются большие затраты на связь, поэтому либо следует проводить аукцион в одном помещении, либо предоставить всем участникам аукциона быстродействующие, надежные линии связи. Альтернативным механизмом, для которого требуется гораздо меньший объем связи, является аукцион с запечатанными предложениями. В этом случае каждый участник аукциона подготавливает единственное предложение и сообщает его лицу, проводящему аукцион; после сбора всех предложений побеждает предложение с наибольшей ценой. При использовании этого механизма стратегия, в которой участник аукциона выдвигает в качестве предложения то истинное значение, которым он руководствуется, больше не является доминантной. Если значение полезности для игрока равно vi и он считает, что максимальным из предложений всех других игроков будет 2, то он должен выдвинуть предложение с ценой, меньшей vL и равной Ьт+8. Двумя недостатками аукциона с запечатанными предложениями является то, что игрок с наивысшим значением полезности Vi может не получить товары, а также то, что игроки должны затрачивать свои усилия на прогнозирование стратегий других игроков.
В результате небольшого изменения правил аукционов с запечатанными предложениями был разработан аукцион с запечатанными предложениями на вторую по величине цену, называемый также аукционом Викри10. При проведении таких аукционов победитель платит цену, указанную во втором по величие предложении, а не цену, показанную в своем собственном предложении. Эта простая модификация позволяет полностью устранить необходимость в проведении сложных рассуждений, которые требовались в стандартных аукционах с запечатанными предложениями (т.е. в аукционах с первой по величине ценой), поскольку теперь доминантная стратегия состоит в том, чтобы выдвинуть в качестве предложения цену, соответствующую фактической собственной величине полезности. Чтобы убедиться в этом, достаточно отметить, что каждый игрок может рассматривать данный аукцион как игру с двумя игроками, игнорируя всех игроков, кроме себя и лица, выдвинувшего предложение с наибольшей ценой среди всех других игроков. Значение полезности для игрока i, выраженное в виде цены, указанной в его предложении, bi5 само значение полезности vi9 которым он руководствуется, и наилучшее предложение среди других игроков, и™ связаны между собой таким соотношением:
Чтобы убедиться в том, что выбор значения bi=vL представляет собой доминантную стратегию, отметим, что при положительном значении (Vi-bJ любое предложение, которое побеждает в аукционе, является оптимальным, и, в частности, аукцион можно выиграть, выдвинув предложение vL. С другой стороны, когда значение (vi-bj является отрицательным, оптимальным становится любое предложение, которое проигрывает в этом аукционе, и, в частности, в аукционе проигрывает предложение, в котором применяется значение vi. Поэтому выдвижение предложения на основе значения Vi представляет собой оптимальную стратегию при всех возможных значениях Ьт, и действительно предложение на основе vL — это единственное предложение, которое обладает таким свойством. Благодаря его простоте и минимальным вычислительным требованиям как к тем, кто предоставляет услуги, так и к тем, кто на них претендует, аукцион Викри широко используется при проектировании распределенных систем на основе искусственного интеллекта.
Теперь рассмотрим проблему маршрутизации в Internet. Игроки соответствуют ребрам в графе сетевых соединений. Каждый игрок знает стоимость с± передачи сообщения по его собственному ребру, а стоимость того, что сообщение не будет передано для отправки, равна 0. Задача состоит в том, чтобы найти самый дешевый путь передачи сообщения от отправителя к получателю, где стоимость всего маршрута представляет собой сумму стоимостей отдельных ребер. В главе 4 приведено несколько алгоритмов вычисления кратчайшего пути с учетом стоимости ребер, поэтому остается только предусмотреть, чтобы каждый агент сообщал свою истинную стоимость ci. К сожалению, если будет просто передан запрос каждому агенту, он сообщит стоимости, которые слишком велики, чтобы вынудить нас отправлять свои сообщения по каким-то другим каналам. Поэтому необходимо разработать механизм защиты стратегии. Один из таких механизмов состоит в том, чтобы выплачивать каждому игроку вознаграждение pi5 равное длине кратчайшего пути, который не включает i-e ребро, за вычетом длины кратчайшего пути (вычисленной с помощью алгоритма поиска), где предполагается, что стоимость i-ro ребра равна 0:
Pi = Length (путь, где а = °°) - Length (путь, где а = 0)
Можно показать, что при использовании такого механизма доминантной стратегией для каждого игрока становится выдача правильных сведений о значении и что применение такого подхода приводит к получению самого дешевого пути. Но, несмотря на это желательное свойство, описанный механизм не используется на практике из-за высокой стоимости связи и централизованных вычислений. Проектировщик механизма должен связаться со всеми п игроками, а затем решить задачу оптимизации. Применение такого подхода имело бы смысл, если бы затраты можно было амортизировать по многим сообщениям, но в реальной сети стоимости с± непрерывно колеблются из-за заторов в каналах, а также из-за того, что некоторые компьютеры завершают свою работу аварийно, а другие, наоборот, переходят в оперативный режим. Полностью удовлетворительное решение этой проблемы еще не было предложено.
В этой главе показано, как использовать знания о мире для принятия решений, даже если результаты действий являются неопределенными, а вознаграждения за действия могут оставаться недоступными до тех пор, пока не будет осуществлен целый ряд действий. Основные идеи этой главы кратко изложены ниже.
• Задачи последовательного принятия решений в неопределенных вариантах среды, называемые также марковскими процессами принятия решений (Markov Decision Process — MDP), определяются с помощью моделей перехода, задающих вероятностные результаты действий, и функции вознаграждения, которая показывает, какое вознаграждение соответствует каждому состоянию.
• Полезность последовательности состояний представляет собой сумму всех вознаграждений вдоль этой последовательности, которая, возможно, со временем подвергается обесцениванию. Решением задачи MDP является стратегия, в которой с каждым состоянием, достижимым для агента, связано некоторое решение. Оптимальная стратегия максимизирует полезность встречающейся последовательности состояний при ее осуществлении.
• Полезностью состояния является ожидаемая полезность последовательностей состояний, встречающихся при осуществлении оптимальной стратегии, начиная с этого состояния. Алгоритм итерации по значениям для решения задач MDP действует по принципу итеративного решения уравнений, связывающих полезности каждого состояния с полезностями его соседних состояний.
• В алгоритме итерации по стратегиям чередуются этап вычисления полезностей состояний согласно текущей стратегии и этап усовершенствования текущей стратегии по отношению к текущим полезностям.
• Задачи MDP в частично наблюдаемой среде, или задачи POMDP, являются гораздо более трудными для решения, чем задачи MDP. Они могут быть решены путем преобразования в задачу MDP в непрерывном пространстве доверительных состояний. Оптимальное поведение при решении задач POMDP должно предусматривать сбор информации для уменьшения неопределенности и поэтому принятия лучших решений в будущем.
РЕЗЮМЕ
• Для вариантов среды POMDP может быть создан агент, действующий на основе теории решений. В таком агенте для представления модели перехода и модели наблюдения для обновления его доверительного состояния и проектирования возможных последовательностей действий в прямом направлении используется динамическая сеть принятия решений.
• Теория игр описывает рациональное поведение для агентов в тех ситуациях, в которых одновременно взаимодействуют множество агентов. Решениями для игр являются равновесия Нэша — профили стратегий, в которых ни один из агентов не имеет стимулов, под влиянием которых он мог бы уклониться от определенной для него стратегии.
• Проектирование механизма может использоваться для определения правил, по которым должно быть организовано взаимодействие агентов в целях максимизации некоторой глобальной полезности благодаря функционированию отдельных рациональных агентов. Иногда удается найти механизмы, позволяющие достичь этой цели, не требуя от каждого агента, чтобы он учитывал то, какие варианты выбраны другими агентами.
Мы вернемся к тематике задач MDP и POMDP в главе 21, где описаны методы обучения с подкреплением, позволяющие агенту совершенствовать свое поведение на основании опыта, полученного в последовательных, неопределенных вариантах среды.







Материалы

Яндекс.Метрика