Два основных вопроса
Динамика наилучших ответов может проявлять разнообразные варианты поведения, и мы уже видели несколько примеров, демонстрирующих разные аспекты. Будет полезно сделать шаг назад, оценить наш текущий уровень понимания и задать некоторые основные вопросы. Мы объединим их в две группы.
- Существование равновесия Нэша. На данный момент мы еще не располагаем доказательствами того, что решение с равновесием Нэша хотя бы существует в каждом экземпляре задачи многоадресной передачи. Самый естественный кандидат на метрику прогресса — общая стоимость всех агентов — не обязательно убывает при обновлении одним агентом его пути.
С учетом этого обстоятельства даже неясно, как обосновать, что динамика наилучших ответов должна завершиться. Почему не может возникнуть цикл, при котором агент t1 улучшает свое решение за счет t2, а затем t2 улучшает свое решение за счет t1, и т. д. до бесконечности?
- Цена устойчивости. До настоящего момента равновесие Нэша рассматривалось в основном в роли «наблюдателей»: фактически мы «выпускаем» агентов на граф в произвольной начальной точке и смотрим, что они сделают.
Но если рассматривать происходящее с точки зрения разработчиков протокола, пытаясь определить процедуру построения агентами путей из s, можно пойти по следующему пути: для заданного множества агентов, находящихся в узлах t1, t2, …, tk, можно предложить множество путей (по одному для каждого агента), обладающее двумя свойствами:
- Множество путей образует решение с равновесием Нэша;
- С учетом (i) общая стоимость для всех агентов настолько мала, насколько это возможно.
Конечно, в идеале нам хотелось бы добиться наименьшей общей стоимости, как при социальном оптимуме. Но если предложить социальный оптимум, который не является равновесием Нэша, он не будет устойчивым: агенты начнут отклоняться и строить новые пути. Таким образом, свойства (i) и (ii) совместно представляют попытку нашего протокола найти оптимум с учетом устойчивости и отыскать лучшее решение, от которого ни один агент не захочет отойти.
По этой причине для заданного экземпляра задачи определяется цена устойчивости как отношение стоимости лучшего решения с равновесием Нэша к стоимости социального оптимума. Эта характеристика отражает рост стоимости, обусловленный требованием о том, что наше решение должно быть устойчивым в контексте личного интереса каждого агента.
Эту пару вопросов можно задать практически для любой задачи, в которой агенты с собственными интересами генерируют коллективное решение. Мы сейчас ответим на оба вопроса для задачи маршрутизации при многоадресной передаче.
Мы покажем, что для любого экземпляра динамика наилучших ответов, начинающаяся с социального оптимума, приводит к равновесию Нэша, стоимость которого увеличивается не более чем с коэффициентом H(k) = Θ(log k).
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу