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

Пусть дана ситуация, в которой 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>

Стоимость <math>\lambda^i_p(P) \;</math> пользователя i в P равна <math>\lambda^i_{p_i}(P) \;</math>, т.е. общей задержке вдоль пути.

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

Пусть <math>p_i \;</math> – путь пользователя i, а <math>P^i = (p_1, ..., p_i) \;</math> – профиль чистых стратегий для пользователей 1, ..., i. Тогда наилучшим ответом пользователя i + 1 будет являться путь <math>p_{i + 1} \;</math>, такой, что <math>p_{i + 1} = avg \; min_{p \in P^i} \Bigg\{ \sum_{e \in p} \Big(d_e \Big(l_e \Big( P^i \Big) \Big) \Big) \Bigg\}</math> .

(Допустимый) поток на множестве P путей s — t по графу G задается функцией <math>f: P \to \mathfrak{R}_{ \ge 0} \;</math>, такой, что <math>\sum_{p \in P} f_p = \sum_{i = 1}^n w_i \;</math> .

Игра о загруженности сети одного товара <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math> обладает свойством общего наилучшего ответа, если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно £. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей p' выполняется <math>\sum_{e \in p'} d_e (f_e + w_j) \ge \sum_{e \in p} d_e (f_e + w_j) \; </math>.

Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является [[многослойный граф|многослойным]] в том и только том случае, если все ориентированные пути s—t имеют одну и ту же длину, и каждая вершина графа лежит на некотором ориентированном пути s—t.

Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)

'''Теорема 1. Если граф G является (s—t)-серийно-параллельным, а игра <math>((w_i)_{i \in N}, G, (d_e)_{e \in E} \;</math> обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.'''

'''1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха, даже в случае с 2 идентичными пользователями и идентичными ребрами.'''

'''2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха, даже в случае с 2-слойными серийно-параллельными графами.'''

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