Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 232
Текст из файла (страница 232)
Основное различие между ними состоит в том, что вместо простого определения максимума или минимума дочерних значений алгоритм должен найти решение игры в терминах смешанных стратегий на каждом уровне, при условии, что для дочерних узлов найдены решения и имеются точно определенные значения, с которыми можно дальше работать. Повторяющиеся игры в частично наблюдаемых вариантах среды называются играми с Ж частичной информацией. К примерам таких игр относятся карточные игры наподобие покера и бриджа, в которых каждый игрок видит только некоторое подмножество карт, а также более серьезные "игры", такие как моделирование атомной войны, когда ни одна из сторон не знает местонахождение всех пусковых установок противника. Решения игр с частичной информацией можно найти, рассматривая дерево доверительных состояний, как и в случае задач РОМ РР (см, раздел 17.4).
Одно важное различие между ними состоит в том, что собственное доверительное состояние является наблюдаемым, а доверительное состояние противника — нет. Для таких игр практически применимые алгоритмы были разработаны только недавно. Например, найдено решение для некоторой упрощенной версии покера и доказано, что вариант, в котором игроки блефуют, действительно является рациональным, по крайней мере в составе тщательно сбалансированной смешанной стратегии. В результате этих исследований было сделано одно важное открытие, которое заключается в том, что смешанные стратегии полезны не только для того, чтобы сделать действия игрока непредсказуемыми, но и для минимизации объема информации, которую противник может извлечь из наблюдений за действиями этого игрока. Интересно отметить, что разработчики программ для игры в бридж хорошо понимают важность сбора и сокрытия информации, но ни один из них не предложил использовать рандомизированные стратегии.
851 Глава 17. Принятие сложных решений До сих пор обнаруживались определенные барьеры, которые препятствовали широкому использованию теории игр в проектах агентов. Во-первых, следует отметить, что при поиске решения на основе равновесия Нэша игрок предполагает, что его противник со всей определенностью будет вести игру на основе равновесной стратегии. Это означает, что игрок не способен учесть какие-либо убеждения, которые у него могут быть в отношении того, как скорее всего будут действовать другие игроки, и поэтому не сможет воспользоваться своими важными преимуществами, защищаясь от угроз, которые так никогда и не материализуются.
Эта проблема частично решается благодаря использованию понятия св. равновесия Байеса — Нэша, т.е. равновесия применительно к распределению априорных вероятностей игрока по отношению к стратегиям других игроков; иными словами, равновесие Байеса — Нэша выражает уверенность игрока в том, какие вероятные стратегии будут применять лругие игроки. Во-вторых, в настоящее время отсутствует удобный способ совместного применения стратегий управления, основанных на теории игры н модели РОМОР. Из-за наличия этих н других проблем теория игр в основном использовалась для анализа вариантов среды, находящихся в равновесном состоянии, а не для управления агентами, действующими в некоторой среде. Но ниже будет показано, что теория игр может помочь и при проектировании вариантов среды.
17.7. ПРОЕКТИРОВАНИЕ МЕХАНИЗМА В предыдугцем разделе рассматривался вопрос: "Дана некоторая игра; каковой является рациональная стратегия?" В этом разделе приведен ответ на другой вопрос: "Предположим, что агенты являются рациональными; какую игру следует для них спроектировать?" А именно, требуется спроектировать некоторую игру, решения которой, состоящие из действий каждого агента, осуществляющего свою собственную рациональную стратегию, приводят к максимизации некоторой глобальной функции полезности.
Эта проблемная область называется 'св проектированием механизма, а иногда обратной теорией игр. Проектирование механизма представляет собой фундамент экономики и политологии. Применительно к коллекциям агентов этот подход обеспечивает возможность использования механизмов теории нгр для создания успешно действующих систем из совокупности более ограниченных системных компонентов (даже противоборствующих системных компонентов), во многом аналогично тому, как создаются команды людей, способные достигать целей, далеко превосходящих возможности отдельно взятого человека.
К примерам применения принципов проектирования механизма относится организация аукционов по распродаже дешевых авиабилетов, маршрутизация пакетов ТСР между компьютерами, принятие решения о том, как следует распределять выпускников медицинских учебных заведений по лечебным учреждениям, а также определение способа взаимодействия роботизированных игроков-футболистов со своими капитанами команд. Проектирование механизма вышло за рамки академической тематики в конце 1990-х годов, когда несколько государств, столкнувшись с проблемой аукционной распродажи лицензий на вещание в различных частотных диапазонах, потеряли сотни миллионов долларов потенциальных доходов в результате плохого проектирования механизма. Формально 'оь механизм состоит, во-первых, из языка для описания (потенциально бесконечного) множества допустимых стратегий, которыми могут ру- 852 Часть Ч.
Неопределенные знания и рассуждения в условиях неопределенности ководствоваться агенты, и, во-вторых, из правила определения результата О, которое регламентирует вознаграждения, получаемые агентами при наличии некоторого профиля стратегий, состояшего из допустимых стратегий. На первый взгляд задача проектирования механизма может показаться тривиальной. Предположим, что глобальная функция полезности ггдекомпонуется на любое множество функций полезности отдельных агентов ггг, такое, что гг = ',Г гг,. В таком случае можно утверждать, что если каждый агент максимизирует свою собственную полезность, то нет сомнения в том, что это автоматически приведет к максимизации глобальной полезности.
(Например, в лекциях по начальному курсу капитализма утверждается, что если каждый старается стать богаче, то общее благосостояние общества повышается.) К сожалению, такой принцип не оправдывается. Действия каждого агента могут повлиять на благосостояние других агентов так, что глобальная полезность уменыпится.
Одним из примеров этого является з трагическая деградация общих пастбищ (ггаяег)у о( г)те согпгпопз) — ситуация, в которой отдельные фермеры сгоняют все свои стада для того, чтобы они бесплатно паслись на общих сельских пастбищах, в результате чего наступает деградация этих общих пастбиш, что приводит к достижению отрицательной полезности для всех фермеров. Каждый фермер, отдельно взятый, действовал рационально, рассуждая, что он может использовать общие пастбища бесплатно, и хотя интенсивное использование обших пастбищ может привести к их деградации, его отказ выгонять на них свой скот делу не поможет (поскольку другие от этого все равно не откажутся).
Аналогичные доводы выдвигаются теми, кто не желает ограничивать выбросы промышленных загрязнений в атмосферу и в океаны. Стандартный подход при проектировании механизма для решения подобных проблем состоит в том, что с каждого агента должна взиматься плата за использование обших пастбищ. Вообще говоря, следует обеспечить, чтобы все ~ побочные последствия (отрицательные влияния на глобальную полезность, которые не сказываются на результатах, полученных отдельными агентами) были выражены явно.
При решении задачи труднее всего правильно определить цены. В пределе этот подход сводится к созданию механизма, который действительно требует от каждого агента, чтобы он максимизировал глобальную полезность. Применительно к отдельному агенту, который не обладает возможностью оценивать текущее состояние мира и не может наблюдать за результатами действий всех других агентов, такая задача становится невероятно трудной. Поэтому проектирование механизма должно сосредоточиваться на поиске таких механизмов, при использовании которых задача принятия решений для отдельных агентов становится несложной.
Вначале рассмотрим аукционы. В своей наиболее обшей форме аукцион представляет собой механизм продажи некоторых товаров членам определенного сообшества покупателей. Стратегиями являются стратегии ведения торгов, а результаты определяют, кто получит товары и сколько заплатит. Одним из примеров, в которых аукционы могут войти в состав тематики искусственного интеллекта, является приятие решения совокупностью агентов о том, будут ли они участвовать в совместном плане. Хансбергер и Грош ~706) показали, что эта задача может быть эффективно решена с помошью аукциона, в котором агенты распределяют между собой роли в совместном плане. 853 Глава 17.
Принятие сложных решений В данном разделе рассмотрим аукционы, в которых, во-первых, имеется только один вид товара, во-вторых, каждый покупатель руководствуется собственным значением полезности ь; по отношению к данному товару, и, в-третьих, эти значения известны только покупателю. Покупатели вносят свои предложения Ь„а товары передаются тому, кто сделал предложение с самой высокой ценой, но механизм определяет, как нужно делать эти предложения и какую цену платит победитель (она не обязательно должна быть равна Ь,). Наиболее широко известным типом аукциона является Ъ. английский аукцион, в котором лицо, проводящее аукцион, повышает цену товара, проверяя, остались ли еше заинтересованные покупатели, до тех пор, пока не останется только один потенциальный покупатель.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
