Алгоритмы наилучших ответов для эгоистичной маршрутизации: различия между версиями

Пусть дана ситуация, в которой n эгоистичных пользователей конкурируют за маршрутизацию своих загрузок в сети. Сеть представляет собой ориентированный s-t-граф с единственной вершиной-источником s и единственной вершиной-приемником t. Пользователи последовательным образом упорядочены. Предполагается, что каждый пользователь делает свой ход после того пользователя, за которым он идет согласно порядку, а желаемый конечный результат представляет собой чистое [[равновесие Нэша]]. Также предполагается, что когда пользователь делает ход (т.е. выбирает путь s-t для маршрутизации своей загрузки), этот ход является наилучшим ответом (т.е. имеет минимальную задержку) с учетом путей и пользователей, в данный момент находящихся в сети. Задача заключается в поиске класса ориентированных графов, для которых существует упорядочение, такое, что соответствующая последовательность наилучших ответов приводит к чистому равновесию Нэша.

''Игра о загруженности сети'' представляет собой кортеж <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math>, где N = {1, ..., n} – множество пользователей, где пользователь <math>i \;</math> контролирует <math>w_i \;</math> единиц спроса на трафик. В ''невзвешенных'' играх о загруженности <math>w_i = 1 \;</math> для i = 1, ..., n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а <math>d_e \;</math> – функция задержки, ассоциированная с ребром <math>e \in E \;</math>. Предполагается, что <math>d_e \;</math> являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются ''идентичными'', если <math>d_e (x) = x \; \forall e \in E</math>. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s-t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s-t.

Вектор <math>P = (p_1, ..., p_n \;</math>), содержащий путь <math>p_i \;</math> модели s-t для каждого пользователя i, представляет собой ''профиль чистой стратегии''. Пусть <math>l_e(P) = \sum_{i: e \in p_i} w_i \;</math> обозначает загрузку ребра e в P. Определим ''стоимость'' <math>\lambda^i_p(P) \;</math> для пользователя i, направляющего свой спрос по пути p в профиле P, равной <math>\lambda^i_p(P) = \sum_{e \in p \cap p_i} d_e (l_e(P)) + \sum_{e \in p \smallsetminus p_i} d_e (l_e(P)) + w_i \;</math>

Профиль чистой стратегии P представляет собой чистое равновесие Нэша в том и только том случае, если ни один из пользователей не может уменьшить свою задержку за счет ''одностороннего отклонения'', то есть выбора другого пути s-t для своей загрузки, в то время как все остальные пользователи не меняют путей.

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