Ограничение цены устойчивости
Потенциальная функция также оказывается очень полезной для определения цены стабильности. Дело в том, что хотя и не равна общей стоимости, сформированной всеми агентами, она достаточно близка к ней.
Теперь отношение между функцией стоимости C и потенциальной функцией может быть выражено следующим образом:
(12.16) Для любого множества путей P1,…,Pk выполняется
C(P1, …, Pk) ≤ (P1, …, Pk) ≤ H(k) · C(P1, …, Pk).
Доказательство. Вспомните, что ранее количество путей, содержащих ребро e, обозначалось xe. Для сравнения C с мы также определяем E+ как множество всех ребер, принадлежащих минимум одному из путей P1, …, Pk. Тогда по определению C имеем C(P1, …, Pk).
Обратите внимание на простой факт: xe ≤ k для всех e. Теперь мы просто записываем C(P1, …, Pk) = = (P1, …, Pk) и (P1, …, Pk) = = H(k) · C(P1, …, Pk).
Это позволяет определить границу для цены устойчивости:
(12.17) В каждом экземпляре существует решение с равновесием Нэша, для которого общая стоимость всех агентов превышает стоимость социального оптимума не более чем на множитель H(k).
Доказательство. Для получения желаемого равновесия Нэша мы начнем с социального оптимума, состоящего из путей P* , …, P*, и выполним динамику наилучших ответов. Согласно (12.15), это должно привести к завершению в равновесии Нэша P1, …, Pk.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу