Ограничение цены устойчивости

Потенциальная функция также оказывается очень полезной для определения цены стабильности. Дело в том, что хотя и не равна общей стоимости, сформированной всеми агентами, она достаточно близка к ней.

Чтобы убедиться в этом, обозначим C(P1, ..., Pk) полную стоимость для всех агентов при выборе путей P1, …, Pk. Эта величина просто представляет собой сумму ce по всем ребрам, входящим в объединение этих путей, поскольку стоимость каждого такого ребра полностью покрывается агентами, в пути которых оно входит.

Теперь отношение между функцией стоимости 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.