Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 233
Текст из файла (страница 233)
Этот механизм обладает тем свойством, что покупатель, руководствуюшийся наивысшим значением ыг, получает товары по цене Ь +с1, где .܄— наивысшая предложенная цена среди цен, предложенных всеми другими игроками, а гз — величина, на которую лицо, проводяшее аукцион, наращивает цену от одного предложения к другому'. Поэтому английский аукцион обладает тем свойством, что участники аукциона руководствуются простой доминантной стратегией — продолжать выдвигать предложения до тех пор, пока текушая цена остается ниже назначенного лично вами значения.
Напомним, что "доминантной" стратегией называется стратегия, позволяюшая противодействовать всем другим стратегиям, а это, в свою очередь, имеет тот смысл, что игрок может ею руководствоваться, невзирая на то, что существуют любые другие стратегии. Поэтому игроки не обязаны терять время и энергию, пытаясь предугадать возможные стратегии других игроков.
Механизм, в котором игроки имеют доминантную стратегию, позволяющую скрывать свои истинные побуждения, называется механизмом Ъ. защиты стратегии. Одним из отрицательных свойств английского аукциона являются большие затраты на связь, поэтому либо следует проводить аукцион в одном помешении, либо предоставить всем участникам аукциона быстродействующие, надежные линии связи. Альтернативным механизмом, для которого требуется гораздо меньший объем связи, является Ьь аукцион с запечатанными предложениями.
В этом случае каждый участник аукциона подготавливает единственное предложение и сообшает его лицу, проводяшему аукцион; после сбора всех предложений побеждает предложение с наибольшей ценой. При использовании этого механизма стратегия, в которой участник аукциона выдвигает в качестве предложения то истинное значение, которым он руководствуется, больше не является доминантной.
Если значение полезности для игрока равно т;. и он считает, что максимальным из предложений всех других игроков будет.Ь, то он должен выдвинуть предложение с ценой, меньшей гг, и равной Ь +е. Двумя недостатками аукциона с запечатанными предложениями является то, что игрок с наивысшим значением полезности ггг может не получить товары, а также то, что игроки должны затрачивать свои усилия на прогнозирование стратегий других игроков. В результате небольшого изменения правил аукционов с запечатанными предложениями был разработан Ъ.
аукцион с запечатанными предложениями иа вторую по Э Фактически шансы на то, что игрок с наибольшим значением ч, не сможет получить товары, невелики; это произойдет, только если сь<ч.<Ь,,+с1. Вероятность такого события может стать сколь угодно малой благодаря уменьшению прирашения <З. 854 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности величине цену, называемый также еа аукционом Викри". При проведении таких аукционов победитель платит цену, указанную во втором по величие предложении, а не цену, показанную в своем собственном предложении.
Эта простая модификация позволяет полностью устранить необходимость в проведении сложных рассуждений, которые требовались в стандартных аукционах с запечатанными предложениями (т.е. в аукционах с первой по величине ценой), поскольку теперь доминантная стратегия состоит в том, чтобы выдвинуть в качестве предложения цену, соответствующую фактической собственной величине полезности. Чтобы убедиться в этом, достаточно отметить, что каждый игрок может рассматривать данный аукцион как игру с двумя игроками, игнорируя всех игроков, кроме себя и лица, выдвинувшего предложение с наибольшей ценой среди всех других игроков.
Значение полезности для игрока з, выраженное в виде цены, указанной в его предложении, Ь;, само значение полезности у„, которым он руководствуется, и наилучшее предложение среди других игроков, Ь, связаны между собой таким соотношением: (ю — Ь ) если Ь, > Ь , (Ьз, Ьа) — 0 в противном случае Чтобы убедиться в том, что выбор значения Ь,= у, представляет собой доминантную стратегию, отметим, что при положительном значении ( у,-Ь„) любое предложение, которое побеждает в аукционе, является оптимальным, и, в частности, аукцион можно выиграть, выдвинув предложение уз. С другой стороны, когда значение (уь-Ь ] является отрицательным, оптимальным становится любое предложение, которое проигрывает в этом аукционе, и, в частности, в аукционе проигрывает предложение, в котором применяется значение уь Поэтому выдвижение предложения на основе значения уг представляет собой оптимальную стратегию при всех возможных значениях .Ь, и действительно предложение на основе у, — это единственное предложение, которое обладает таким свойством.
Благодаря его простоте и минимальным вычислительным требованиям как к тем, кто предоставляет услуги, так и к тем, кто на них претендует, аукцион Викри широко используется при проектировании распределенных систем на основе искусственного интеллекта.
Теперь рассмотрим проблему маршрутизации в )шегпе(. Игроки соответствуют ребрам в графе сетевых соединений. Каждый игрок знает стоимость с, передачи сообщения по его собственному ребру, а стоимость того, что сообщение не будет передано для отправки, равна О. Задача состоит в том, чтобы найти самый дешевый путь передачи сообщения от отправителя к получателю, где стоимость всего маршрута представляет собой сумму стоимостей отдельных ребер. В главе 4 приведено несколько алгоритмов вычисления кратчайшего пути с учетом стоимости ребер, поэтому остается только предусмотреть, чтобы квкдый агент сообщал свою истинную стоимость са.
К сожалению, если будет просто передан запрос каждому агенту, он сообщит стоимости, которые слишком велики, чтобы вынудить нас отправлять свои сообщения по каким-то другим каналам. Поэтому необходимо разработать механизм зашиты стратегии. Один из таких механизмов состоит в том, чтобы выплачивать каждому игроку вознаграждение р„равное длине кратчайшего пути, который 'а Названный в честь Уильяма Викри (1914-1996), лауреата Нобелевской премии по экономике за 199б гол.
855 Глава 17. Принятие сложных решений не включает 1-е ребро, за вычетом длины кратчайшего пути (вычисленной с помо- щью алгоритма поиска), где предполагается, что стоимость 1-го ребра равна Рл р, = ьепдеп1путь, гле а, = ) — Ьепдеп(путь, гле гл = О) Можно показать, что при использовании такого механизма доминантной стратегией для каждого игрока становится выдача правильных сведений о значении с, и что применение такого подхода приводит к получению самого дешевого пути.
Но, несмотря на это желательное свойство, описанный механизм не используется на практике из-за высокой стоимости связи и централизованных вычислений. Проектировщик механизма должен связаться со всеми и игроками, а затем решить задачу оптимизации. Применение такого подхода имело бы смысл, если бы затраты можно было амортизировать по многим сообщениям, но в реальной сети стоимости с, непрерывно колеблются из-за заторов в каналах, а также из-за того, что некоторые компьютеры завершают свою работу аварийно, а другие, наоборот, переходят в оперативный режим. Полностью удовлетворительное решение этой проблемы еше не было предложено.
17.8. РЕЗЮМЕ В этой главе показано, как использовать знания о мире для принятия решений, даже если результаты действий являются неопределенными, а вознаграждения за действия могут оставаться недоступными до тех пор, пока не будет осуществлен целый ряд действий. Основные идеи этой главы кратко изложены ниже.
° Задачи последовательного принятия решений в неопределенных вариантах среды, называемые также марковскими процессами принятия решений (Маг)гот Оесвйоп Ргосезз — МОР), определяются с помощью моделей перехода, задающих вероятностные результаты действий, и функции вознаграждения, которая показывает, какое вознаграждение соответствует каждому состоянию. ° Полезность последовательности состояний представляет собой сумму всех вознаграждений вдоль этой последовательности, которая, возможно, со временем подвергается обесцениванию. Решением задачи МОР является стратегия, в которой с каждым состоянием, достижимым для агента, связано некоторое решение. Оптимальная стратегия максимизирует полезность встречающейся последовательности состояний при ее осуществлении.
° Полезностью состояния является ожидаемая полезность последовательностей состояний, встречающихся при осуществлении оптимальной стратегии, начиная с этого состояния. Алгоритм итерации по значениям для решения задач МОР действует по принципу итеративного решения уравнений, связывающих полезности каждого состояния с полезностями его соседних состояний. ° В алгоритме итерации по стратегиям чередуются этап вычисления полезностей состояний согласно текущей стратегии и этап усовершенствования текущей стратегии по отношению к текущим полезностям. ° Задачи МОР в частично наблюдаемой среде, или задачи РОМРР, являются гораздо более трудными для решения, чем задачи МОР.
Они могут быть ре- 856 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности шены путем преобразования в задачу М[3Р в непрерывном пространстве доверительных состояний. Оптимальное поведение при решении задач РОМОР должно предусматривать сбор информации для уменьшения неопределенности и поэтому принятия лучших решений в будущем. ° Для вариантов среды РОМРР может быть создан агент, действующий на основе теории решений.
В таком агенте для представления модели перехода и модели наблюдения для обновления его доверительного состояния и проектирования возможных последовательностей действий в прямом направлении используется динамическая сеть принятия решений. ° Теория игр описывает рациональное поведение для агентов в тех ситуациях, в которых одновременно взаимодействуют множество агентов.
Решениями для игр являются равновесия Нэша — профили стратегий, в которых ни один из агентов не имеет стимулов, под влиянием которых он мог бы уклониться от определенной для него стратегии. ° Проектирование механизма может использоваться для определения правил, по которым должно быть организовано взаимодействие агентов в целях максимизации некоторой глобальной полезности благодаря функционированию отдельных рациональных агентов.
Иногда удается найти механизмы, позволяюшие достичь этой цели, не требуя от каждого агента, чтобы он учитывал то, какие варианты выбраны другими агентами. Мы вернемся к тематике задач МОР и РОМРР в главе 21, где описаны методы обучения с подкреплением, позволяюгцие агенту совершенствовать свое поведение на основании опыта, полученного в последовательных, неопределенных вариантах среды. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Основателем современного подхода к анализу задач последовательного принятия решений был Ричард Ьеллман [97], который в целом предложил использовать подход на основе динамического программирования и в частности алгоритм итерации по значениям.
В тезисах докторской диссертации Рона Говарда [691] введено понятие итерации по стратегиям и изложена идея среднего вознаграждения, предназначенная для применения при решении задач с бесконечным горизонтом. Несколько дополиительных результатов было предложено в [96).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
