Поиск хорошего равновесия Нэша

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

Ключевая идея заключается в том, что общую стоимость для всех агентов не обязательно использовать как метрику прогресса, по которой ограничивается количество шагов динамики наилучших ответов. Вместо нее подойдет любая величина, которая строго убывает при обновлении пути любым агентом и которая может уменьшаться конечное количество раз.

С учетом этого мы попытаемся сформулировать метрику, обладающую таким свойством. Эта метрика может быть не такой сильной, как общая стоимость с ее интуитивным смыслом, но это нормально — лишь бы она делала то, что нужно.

Для начала более подробно разберемся, почему общая стоимость агентов не подходит. Возьмем простой пример: агент tj в настоящее время совместно использует вместе с x другими агентами путь, состоящий из одного ребра e. (Конечно, в общем случае пути агентов длиннее, но пути из одного ребра упрощают анализ данного примера.)

Допустим, агент tj решает, что для снижения стоимости стоит переключиться на путь, состоящий из одного ребра f, которое в настоящее время не используется ни одним агентом. Чтобы это произошло, должно выполняться условие cf < ce/(x + 1).

Чтобы рассматривать происходящее как метрику прогресса, необходимо заново определить, что же понимать под «прогрессом». В частности, будет полезно иметь метрику, которая могла бы компенсировать дополнительную стоимость cf некоторым выражением того, что общая «потенциальная энергия» системы снизилась на ce/(x + 1).

Это позволило бы нам рассматривать перемещение tj как снижение суммы, так как cf < ce/(x + 1). Для этого можно определить для каждого ребра e «потенциал» с тем свойством, что при уменьшении количества агентов, использующих e, с x + 1 до x, этот потенциал уменьшается на ce/(x + 1). (Соответственно потенциал должен увеличиваться на ту же величину при увеличении количества агентов, использующих e, с x до x + 1).