Связь с локальным поиском

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

Равновесия Нэша являются естественными аналогиями локальных минимумов в этом процессе: это решения, для которых невозможны улучшающие перемещения. «Локальная» природа поиска также очевидна, поскольку агенты обновляют свои решения только тогда, когда это приводит к немедленному улучшению.

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

Другими словами, сама функция стоимости предоставляла метрику прогресса, необходимую для обоснования завершения.

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

Если оба агента начинают со среднего пути, то у t1 будет стимул для перехода на внешний путь; его стоимость уменьшается с 3,5 до 3, но в процессе стоимость t2 увеличивается с 3,5 до 6. (Когда это произойдет, t2 также переместится на внешний путь, и это решение — при котором оба узла используются внешними путями — является уникальным равновесием Нэша.)