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

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

Игра о загруженности сети представляет собой кортеж ((wi )i2N, G, (de )e2E ), где N = f1, ... : : ng – множество пользователей, где пользователь i контролирует wi единиц спроса на трафик. В невзвешенных играх о загруженности wi = 1 для i = 1, ..., : : n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а de – функция задержки, ассоциированная с ребром e 2 E. Предполагается, что de являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются идентичными, если de (x) = x, 8e 2 E. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s _ t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s _ t.

Вектор P = (p1, ..., : : pn), содержащий путь pi модели s _ t для каждого пользователя i, представляет собой профиль чистой стратегии. Пусть le(P) = Pi:e2pi wi обозначает загрузку ребра e в P. Определим стоимость i p(P) для пользователя i, направляющего свой спрос по пути p в профиле P, равной Х'р(Р) =   X  de(le(P))+

Стоимость Яi (P) пользователя i в P равна Aj, ...,  (P), т.е. общая задержка вдоль пути.

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

Наилучший ответ

Пусть pi – путь пользователя i, а Pi = (pi, ..., : : pi) – профиль чистых стратегий для пользователей 1, ..., : : i. Тогда наилучшим ответом пользователя i + 1 будет являться путь pi+1, такой, что pi+1 =

Потоки и общий наилучший ответ

(Допустимый) поток на множестве P путей s — t по графу G задается функцией f: P !< 8t>0, такой, что n p2P

Игра о загруженности сети одного товара ((wi)i2N; G; (de)e2E) обладает свойством общего наилучшего ответа, если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно £. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей p0 выполняется (fe e2p eS.pl

Кроме того, каждый сегмент я пути наилучшего ответа p является наилучшим ответом для маршрутизации спроса любого пользователя между конечными точками n. В данном случае допускается ситуация, когда некоторые пользователи уже внесли свой вклад в изначальный поток f.

Многослойные и серийно-параллельные графы

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

Мультиграф является серийно-параллельным с оконечными точками (s, t), если:

2. он получен из двух серийно-параллельных графов G1, G2 с оконечными точками (s1, t1) и (S2, h) путем соединения их последовательно (in series) или параллельно. При последовательном соединении t1 отождествляется с s2, так что s1 становится источником s, а t2 – приемником t. При параллельном соединении s1 = s2 = s и t1 = t2 = t.

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

1. пользователи идентичны (ifwi = 1 для всех i), а задержки ребер произвольны, но не убывают; либо

2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).

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

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

Примеры подобных игр представлены в [ ].

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