<<
>>

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

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

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

С другой стороны, в динамике наилучших ответов каждый агент имеет соб- ственную целевую функцию, которую он пытается минимизировать, поэтому не так очевидно, какой общий «прогресс» происходит, например, при обновлении агентом t. своего пути из 5. Конечно, для t. прогресс существует, поскольку его стоимость пути снижается, но снижение может быть скомпенсировано еще боль- шим возрастанием стоимости у другого агента. Для примера рассмотрим сеть на рис. 12.9. Если оба агента начинают со среднего пути, то у t1 будет стимул для перехода на внешний путь; его стоимость уменьшается с 3,5 до 3, но в процессе стоимость t2 увеличивается с 3,5 до 6. (Когда это произойдет, t2 также переместится

на внешний путь, и это решение — при котором оба узла используются внешними путями — является уникальным равновесием Нэша.)

Рис.

12.9. Сеть, в которой уникальное равновесие Нэша отличается от социального оптимума

Впрочем, в некоторых ситуациях эффекты возрастания стоимости динамики наилучших ответов могут быть намного худшими. Взгляните на рис. 12.10: име- ются k агентов, каждый из которых имеет возможность выбрать общий внешний путь со стоимостью 1 + ε (для некоторого малого числа ε > 0) или собственный альтернативный путь. Альтернативный путь для 1. имеет стоимость 1/j. Теперь предположим, что мы начинаем с решения, в котором все агенты совместно ис- пользуют внешний путь. Каждый агент платит (1 + ε)/k, и это решение минимизи- рует общую стоимость по всем агентам. Но с применением динамики наилучших ответов, начиная с этого решения, события начинают стремительно развиваться. Сначала tk переключается на свой альтернативный путь, так как 1/k < (1+ε)/k. В результате теперь внешний путь используется только к - 1 агентами, поэтому tk - 1 переходит на альтернативный путь, так как 1/(k - 1) < (1 + ε)/(k - 1). После этого переходит tk - 2, потом tk - 3, и т. д., пока все k агентов не будут использовать альтернативные пути прямо из 5. Здесь изменения временно прекращаются из-за следующего факта.

(12.13) Решение на рис. 12.10, в котором каждый агент использует свой прямой путь от s, является равновесием Нэша; более того, в данном экземпляре оно явля- ется уникальным равновесием Нэша.

Доказательство. Чтобы убедиться в том, что данное решение является равно- весием Нэша, достаточно проверить, что ни у одного агента нет причин для пере- хода с его текущего пути. Но это очевидно, поскольку все агенты платят не более 1, а единственный другой вариант — (в настоящее время свободный) внешний путь — имеет стоимость 1 + ε.

А теперь предположим, что существует другое равновесие Нэша.

Чтобы оно отличалось от рассматриваемого решения, в нем должен быть задействован по крайней мере один из агентов, использующих внешний путь. Пусть iА , tА , ..., f, — агенты, использующие внешний путь, где jl l, и у агента f, есть возмож- ность заплатить только 1 /jl< 1/C за счет использования альтернативного пути прямо из 5. Следовательно, у tj есть стимул для отклонения от текущего решения, а значит, решение не может быть равновесием Нэша. ■

Рисунок 12.8, b уже показал, что может существовать равновесие Нэша с общей стоимостью гораздо худшей, чем у социального оптимума, но примеры на рис. 12.9 и 12.10 наглядно раскрывают еще более важный момент: общая стоимость для всех агентов даже в самом выгодном решении с равновесием Нэша может быть хуже общей стоимости в социальном оптимуме. Насколько хуже? Общая стоимость со- циального оптимума в этом примере равна 1 + ε, тогда как стоимость уникального

равновесия Нэша составляет 1+ — + —

2 3 к

чалось в главе 11, где мы определили его как гармоническое число H(k) и показали, что его асимптотическое значение равно H(k) = θ(⅛ k).

Эти примеры поясняют, что социальный оптимум не следует рассматривать как аналогию глобального минимума в традиционной процедуре локального поиска. При стандартном локальном поиске глобальный минимум всегда является устой- чивым решением, так как никакие улучшения невозможны. Однако социальный оптимум может быть неустойчивым решением, так как для этого достаточно, чтобы всего один агент был заинтересован в отклонении.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Связь с локальным поиском:

  1. Поиск смысла жизни – это поиск бессмертия!
  2. МОЗГ ГОЛОВНОЙ: ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ
  3. ЛОКАЛЬНЫЙ
  4. ПСИХОФИЗИОЛОГИЯ ПОРАЖЕНИЙ ЛОКАЛЬНЫХ МОЗГА ГОЛОВНОГО
  5. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  6. 4.3. Акти договірного та локального характеру у сфері трудового права
  7. Аспекты, исходящие от планет разной локальной детер- минации
  8. СВЯЗЬ ВРЕМЕННАЯ
  9. 3.6.1. Обратная связь
  10. Обратная связь
  11. 4. Причинная связь
  12. СВЯЗЬ ОБРАТНАЯ
  13. 4.10. ОТРИЦАТЕЛЬНАЯ ОБРАТНАЯ СВЯЗЬ
  14. Обратная связь телевидения
  15. СВЯЗЬ
  16. Связь с любовью
  17. СВЯЗЬ С ПОДСОЗНАНИЕМ