Равновесное распределение потоков по путям
Обозначим
множество пар
источник-сток
,
– поток по пути
;
– множество путей, отвечающих
корреспонденции
,
– множество всех путей;
– поток на ребре
(здесь и далее
,
),
где
;
– затраты на ребре
(
);
– затраты на пути
;
– множество допустимых распределений
потоков по путям, где
–
корреспонденция, отвечающая паре
.
Определение
1. Распределение
потоков по путям
называется равновесием (Нэша–Вардропа)
в популяционной игре
,
если из
(
)
следует
.
Или, что то же самое:
для
любых
выполняется
Теорема
1 (см. [2,
8–11]).
Популяционная
игра
является потенциальной. Равновесие
в этой игре всегда существует, и находится
из решения задачи выпуклой оптимизации
,
(1)
где
Мы
оставляем в стороне вопрос единственности
равновесия (детали см., например, в [2,
10]).
Отметим лишь, что при естественных
условиях равновесное распределение
потоков по ребрам
единственно. В частности, для этого
достаточно, чтобы
для всех
.
Если дополнительно
однозначно разрешимо относительно
(в реальных транспортных сетях часто
случается, что число допустимых для
перевозки путей меньше числа ребер, это
как раз и приводит к однозначной
разрешимости), то отсюда будет следовать,
что равновесное распределение потоков
по путям
единственно.
Удобно
считать [1, 2], что возрастающие функции
затрат
зависят от параметра
,
причем
В таком пределе задачу выпуклой оптимизации можно переписать как задачу ЛП [13]:
.
Такого типа транспортные задачи достаточно хорошо изучены [14, 15].
Для
дальнейшего будет важно переписать
задачу
через двойственную [2]:
,
(2)
где
– сопряженная функция к
,
– длина кратчайшего пути из
в
(
)
на графе, взвешенном согласно вектору
,
–сильно выпуклая функция по первому
аргументу. При этом
где
– равновесное распределение потоков,
рассчитывающееся по формуле (1), а
–
решение задачи (2), при естественных
условиях единственное [2]. Описанный
предельный переход позволяет переходить
к задачам, в которых вместо функции
затрат на ребрах
заданны
ограничения на пропускные способности
и затраты
на прохождения ребер, когда на ребрах
нет “пробок” (
)
[2, 13].
Основным
для дальнейшего выводом из этого всего
является способ (основанный на применении
теоремы Демьянова–Данскина [16, 17], как
правило, в градиентном варианте в виду
единственности
)
потенциального описания набора
:
(3)
В
[2,
10,
11]
приведены эволюционные динамики,
приводящие к описанным здесь равновесиям.
Отметим, однако, что если рассматривать
Logit
динамику [2,
11]
(ограниченно рациональных агентов с
параметром
[18]),
то задачу (1) необходимо будет переписать
в виде (говорят, что вместо равновесия
Нэша–Вардропа ищется стохастическое
равновесие [2, 19]):
.
(4)
Это замечание понадобится нам в дальнейшем.
В
заключение этого раздела отметим, что
теорема 1 может быть распространена и
на случай, когда затраты на ребрах
удовлетворяют условию потенциальности
(частный случай – это когда
)
[11]:
.
Тогда
Такого рода обобщение нужно, например, когда пропускные способности узлов зависят от потоков, пересекающих узлы. В случае транспортных потоков такими узлами являются, в частности, перекрестки. Тогда, путем раздутия исходного графа, мы с одной стороны “развязываем узел”, сводя затраты прохождения узла по разным путям к затратам прохождения фиктивных (введенных нами) ребер, а с другой стороны приобретаем более общую зависимость .