Концепция решений ; чистые и смешанные стратегии равновесия Нэша ; оптимальность по Парето ; кооперация против некооперации ; антагонистический и другие. - презентация

1 Концепция решений ; чистые и смешанные стратегии равновесия Нэша ; оптимальность по Парето ; кооперация противне кооперации ; антагонистический и другие виды взаимодействия ; как происходит кооперация дилемма заключенного и эксперименты Аксельрода.

2 МАС – это система, образованная несколькими взаимодействующими интеллектуальными агентами. Взаимодействие агентов – первое, что выступает перед нами, когда мы говорим о создании мультиагентной системы ( МАС ).

3 Постановка задачи состоит из следующего : В игре участвуют агенты. У игры есть различные исходы. У каждого агента есть некий набор действий, которые он может предпринимать. Введём тип агента θ i Θ для i- го агента. У игры есть набор исходов, и для каждого агента каждый исход означает какую - то прибыль. Так появляется функция полезности (utility function) u i (ω, θ i ) для типа θ i и исхода ω. Агент i предпочитает исход ω 1 исходу ω 2, если u i ( ω 1, θ i ) > u i ( ω 2, θ i ).

4 Стратегия агента – это план, который полностью описывает его поведение во всех возможных состояниях окружающего мира. Через Σ i будем обозначать множество стратегий агента i, через s i ( θ i ) Σ i - его стратегию. Стратегии бывают чистые (pure) и смешанные (mixed). Чистые стратегии жёстко задают поведение в каждом состоянии окружающего мира, смешанные задают распределения вероятностей на множестве возможных действий агента. Понятно, что функцию полезности можно с конкретных исходов продолжить на стратегии. Если N агентов имеют фиксированные стратегии (s 1, …, s N ) то функция полезности u i (s 1, …, s N, θ i ) будет просто равна функции полезности на исходе ω, который однозначно задаётся этими стратегиями.

5 Каждый агент пытается максимизировать свою собственную прибыль. Он решает задачу оптимизации, добиваясь оптимальной стратегии. В результате система оказывается в каком - либо состоянии. Будем рассматривать возможные определения равновесного состояния системы, к которому она может прийти после решения каждым агентом своей локальной задачи. Обозначения : s = (s 1, …, s N ) – профиль всех стратегий участников ( агентов ). s -i = (s 1, …, s i-1, s i+1, …, s N ) - стратегии всех агентов, кроме i- го. Введём также аналогичные обозначения θ и θ -i для типов агентов.

6 Ключевое понятие всей теории игр – равновесие Нэша (Nash equilibrium) Определение : То есть, профиль стратегий s находится в равновесии Нэша, если каждый агент при данных стратегиях других агентов выбирает для себя оптимальную стратегию. При этом : агенту невыгодно отклоняться от избранной стратегии, но ему это делать невыгодно только в конкретном профиле.

7 Равновесие Нэша - тип решений игры двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив свою стратегию, когда другие участники стратегий не меняют. Такая совокупность стратегий, выбранных участниками, и их выигрыши называются равновесием Нэша. Бывают игры с несколькими равновесиями Нэша. Бывают игры, где нет равновесий Нэша для чистых стратегий. Но равновесие Нэша всегда есть в смешанных стратегиях.

8 Определение : Бывают игры, где нет равновесий Нэша для чистых стратегий. Но оно всегда ( в конечном случае ) есть в смешанных стратегиях. Пример : где будет равновесие для игры камень - ножницы - бумага? Камень НожницыБумага Камень 01 Ножницы 01 Бумага 10

9 Предположим, что второй игрок выбирает камень, ножницы или бумагу с вероятностью 1/3, а первый выбирает их с вероятностью p, q и 1-p-q. Тогда первый игрок выигрывает, проигрывает или делает ничью с вероятностью 1/3 (p + q + 1-p-q) = 1/3. То есть если противник выбирает стратегию равновероятно, для игрока все стратегии эквиваленты. Поскольку игра симметрична, то получается, что профиль смешанных стратегий [(1/3,1/3,1/3), (1/3,1/3,1/3)] находится в равновесии.

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

11 Мы хотим построить механизм, при котором то или иное равновесное состояние системы будет оптимальным относительно той или иной цели. Для этого нужно определить, какая же у нас цель. Функция социального выбора : Функция социального выбора – это то, чего нам бы хотелось получить от механизма, который мы разрабатываем. Но при этом каждый из агентов будет максимизировать собственную прибыль. Это надо примирить.

12 Определим, что же такое механизм :

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

14 Попробуем реализовать тривиальный механизм, который могу бы реализовывать всевозможные функции социального выбора. Просто спросим у каждого агента, какой у него тип ( ответы на этот вопрос будут всевозможными стратегиями агентов ), а потом в качестве функции исходов возьмём функцию социального выбора :. Казалось бы, всё работает … Но ведь агенты не обязаны говорить нам правду ! Агенты будут максимизировать свой доход, сообщая тот тип, который выгоднее. Нам нужно построить механизм таким образом, чтобы решение этой задачи для агентов сошлось с желаемым. В данном случае нам нужно было бы реализовать правдивый механизм, при котором агентам выгодно было бы говорить правду и сообщать свои настоящие типы.

15 Есть ряд свойств функций социального выбора, которые могут помочь при дизайне механизмов, а также гарантировать много полезных свойств механизмов, их реализующих. Сейчас мы их рассмотрим. Кроме этого, введём ограничения ( естественные ) на агентов. Определение : Оптимальность по Парето означает, что если кому - то стало лучше, чем в предлагаемом функцией f варианте, то кому - то другому обязательно стало хуже. То есть нельзя монотонно улучшить дела сразу всех агентов.

16 Равновесие по Парето это ситуация равновесия, при которой улучшение положения одного агента невозможно без ухудшения состояния другого. Принцип Парето применяется для сильно централизованных систем, подсистемы которых имеют широкие возможности обмена информацией о принимаемых решениях, а равновесие по Нэшу характеризует децентрализованные системы. Эти типы оптимальности имеют разные идейные основания : основой оптимальности по Нэшу является устойчивость МАС, обусловленная интересами и возможностями отдельных агентов, тогда как принцип оптимальности по Парето опирается на идею полезности, выгоды для МАС в целом, понимаемой как выгода сразу для всех ее агентов. Методы теории полезности и теории игр, в частности, известные модели и условия оптимальности, выраженные в виде принципов равновесия, являются классическими методами исследования кооперации и переговорных процессов.

17 Теперь можно ввести вполне естественное определение оптимального механизма :

18 Понятие кооперации агентов играет центральную роль в МАС.. Кооперация между агентами означает их коллективную работу в интересах получения совместных результатов. По сути, это основная форма социального поведения и организации взаимодействия между агентами, характеризуемая объединением их усилий для достижения совместной цели при одновременном разделении между ними функций и обязанностей. Формирование совместной цели возможно в двух различных случаях : цели отдельных агентов близки или практически совпадают, цель, сформированная одним агентом, полностью принимается другими агентами. В общем случае понятие кооперации можно определить формулой : кооперация = сотрудничество + координация действий + разрешение конфликтов.

19 Главные преимущества от кооперации агентов таковы : 1. Возможность совместного решения задачи, которую нельзя решить в одиночку. 2. Повышение эффективности и производительности каждого агента. 3. Увеличение качества общего решения за счет роста числа и более детальной проработки частных решений, обмена информацией между агентами. 4. Увеличение вероятности того, что решение будет найдено, благодаря объединению различных точек зрения, и пр. Основными критериями кооперации могут служить : время коллективного решения задачи ( насколько оно меньше по сравнению со временем индивидуального решения ); эффективность распределения задач между агентами ; успешность объединения различных точек зрения.

20 Более подробно об уровне кооперации агентов в МАС можно судить на основе следующих показателей : 1. степень распределения обязанностей, ответственности и ресурсов ( в том числе, знаний ); 2. уровень координации действий, включая согласование направления действий агентов в пространстве и во времени ; 3. степень запараллеливания ( совмещения ) задач, решаемых различными агентами ; 4. неизбыточность действий, довольно малое число дублирующих, повторяющих друг друга действий ; 5. избегание ( или малая длительность ) конфликтов ; 6. живучесть, понимаемая как способность МАС пережить отказ или потерю агента.

21 Три типичных способа централизованного распределения задач между агентами и согласования их действий : 1. Командное управление или система господин - раб (master-slave), когда агент - менеджер самостоятельно распределяет все задачи между заранее определенными агентами - исполнителями и контролирует их выполнение ; 2. Распределение по принципу торгов ( или объявление конкурса ), когда агент - менеджер распространяет объявление об общем задании, а потенциальные агенты - исполнители предлагают свои услуги, т. е. исполнители заранее не определены, а отбираются в результате конкурса ; однако и распределение отдельных задач, и контроль остаются прерогативой менеджера ; 3. Распределение путем соревнования, когда агенты - исполнители дают свои предложения уже на уровне отдельных задач, т. е. происходит подбор исполнителя под конкретную задачу, а роль менеджера сводится к контролю и координации их действий.

22 Дилемма заключенного (prisoners dilemma) – классический пример из теории игр : Двоим заключенным предлагают признаться в преступлении и заложить своего сообщника ; Реальных доказательств у обвинения нет, поэтому, если оба промолчат, то оба отсидят по полгода за другие грешки ; Если оба признаются, обоим за примерное поведение дадут по два года ; А если один признается, а другой нет, то признавшегося за сотрудничество отпустят, а упорствующему впаяют по полной, лет десять ; Держать связь заключенные не могут. Что делать каждому из них ?

23 Получается такая матрица возможных стратегий : Вне зависимости от выбора первого заключённого, второму всё равно выгоднее признаться ! Получается, что для каждого из них сознаться – доминантная стратегия, и в результате они будут сидеть по 2 года, а не по 0.5. * В дилемме заключённого только профиль стратегий ( Сознаться, Сознаться ) находится в равновесии Нэша : преступнику всегда выгоднее сознаться, чем промолчать. Промолчать Сознаться Промолчать (0.5, 0.5)(10,0) Сознаться (0,10)(2,2)

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

25 В книге « Эволюция кооперации » (1984) Роберт Аксельрод исследовал расширение сценария дилеммы заключённого ( ДЗ ), которое он назвал повторяющаяся дилемма заключённого ( ПДЗ ). В ней участники делают выбор снова раз за разом и помнят предыдущие результаты. « Жадные » стратегии давали плохие результаты в долгосрочном периоде, тогда как более « альтруистические » стратегии работали лучше, с точки зрения собственного интереса. Лучшей детерминистской стратегией оказалась « Око за око » (Tit for Tat), которую разработал и выставил на чемпионат Анатолий Рапопорт. Она была простейшей из всех участвовавших программ, состояла всего из 4 строк кода на языке Бейсик. Стратегия проста : сотрудничать на первой итерации игры, после этого игрок делает то же самое, что делал оппонент на предыдущем шаге. Чуть лучше работает стратегия « Око за око с прощением ». Когда оппонент предаёт, на следующем шаге игрок иногда, вне зависимости от предыдущего шага, сотрудничает с небольшой вероятностью (1-5 %). Это позволяет случайным образом выйти из цикла взаимного предательства. Она лучше всего работает, когда в игру вводится недопонимание когда решение одного игрока сообщается другому с ошибкой.

26 Анализируя стратегии, набравшие лучшие результаты, Аксельрод назвал несколько условий, необходимых, чтобы стратегия получила высокий результат : Добрая. Важнейшее условие стратегия должна быть « доброй », то есть не предавать, пока этого не сделает оппонент. Почти все стратегии - лидеры были добрыми. Поэтому чисто эгоистичная стратегия по чисто эгоистическим причинам не будет первой « бить » соперника. Мстительная. Успешная стратегия не должна быть слепым оптимистом. Она должна всегда мстить. Пример прощающей стратегии всегда сотрудничать. Это очень плохой выбор, поскольку « подлые » стратегии воспользуются этим. Прощающая. Другое важное качество успешных стратегий уметь прощать. Отомстив, они должны вернуться к сотрудничеству, если оппонент не продолжает предавать. Это предотвращает бесконечное мщение друг другу и максимизирует выигрыш. Независтливая. Последнее качество не быть завистливым, то есть не пытаться набрать больше очков, чем оппонент. Таким образом, Аксельрод пришёл к утопично звучащему выводу : эгоистичные индивиды во имя их же эгоистического блага будут стремиться быть добрыми, прощающими и не завистливыми.