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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Ключевые слова и синонимы = Атомарные эгоистичные потоки == Постановка задачи == Пусть …»)
 
 
(не показано 16 промежуточных версий 1 участника)
Строка 1: Строка 1:
== Ключевые слова и синонимы  =
== Ключевые слова и синонимы  ==
Атомарные эгоистичные потоки
Атомарные эгоистичные потоки


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




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




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




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




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


Пусть pi – путь пользователя i, а Pi = (pi, ..., : : pi) – профиль чистых стратегий для пользователей 1, ..., : : i. Тогда наилучшим ответом пользователя i + 1 будет являться путь pi+1, такой, что pi+1 =
Пусть <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) + w_{i+1} \Big) \Big) \Bigg\}</math> .




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


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




Игра о загруженности сети одного товара ((wi)i2N; G; (de)e2E) обладает свойством общего наилучшего ответа, если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно £. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей p0 выполняется (fe e2p eS.pl
Игра о загруженности сети одного товара <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math> обладает свойством ''общего наилучшего ответа'', если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно 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>.




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




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


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


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


1. он представляет собой единственное ребро (s, t) либо
1. он представляет собой единственное ребро (s, t) либо


2. он получен из двух серийно-параллельных графов G1, G2 с оконечными точками (s1, t1) и (S2, h) путем соединения их последовательно (in series) или параллельно. При последовательном соединении t1 отождествляется с s2, так что s1 становится источником s, а t2 – приемником t. При параллельном соединении s1 = s2 = s и t1 = t2 = t.
2. он получен из двух серийно-параллельных графов <math>G_1, G_2 \;</math> с оконечными точками <math>(s_1, t_1) \;</math> и <math>(s_2, t_2) \;</math> путем соединения их ''последовательно'' (in series) или ''параллельно''. При последовательном соединении <math>t_1 \;</math> отождествляется с <math>s_2 \;</math>, так что <math>s_1 \;</math> становится источником (s), а <math>t_2 \;</math> – приемником (t). При параллельном соединении <math>s_1 = s_2 = s \;</math> и <math>t_1 = t_2 = t \;</math>.


==Основные результаты ==
==Основные результаты ==


Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)
'''Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR)'''
Алгоритм GBR рассматривает пользователей поочередно в порядке невозрастания веса (т.е. w1 > w 2 > ... > wn). Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR достигает успеха, если итоговый профиль P представляет собой чистое равновесие Нэша.


Алгоритм GBR рассматривает пользователей поочередно ''в порядке невозрастания веса'' (т. е. <math>w_1 \ge w_2 \ge ... \ge w_n) \;</math>. Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR ''достигает успеха'', если итоговый профиль P представляет собой чистое равновесие Нэша.


Характеризация


В работе [ ] показано:
'''Характеризация'''


В работе [3] показано:


Теорема 1. Если граф G является (s — t)-серийно-параллельным, а игра ((WI)I2N; G; (de)e2E) обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.


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


Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.


'''Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.'''


Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:


1. пользователи идентичны (ifwi = 1 для всех i), а задержки ребер произвольны, но не убывают; либо
'''Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:'''


2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).
'''1. пользователи идентичны (если <math>w_i = 1 \;</math> для всех i), а задержки ребер произвольны, но не убывают; либо'''


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


Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.


'''Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.'''


Теорема 5.


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


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


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


== Применение ==
== Применение ==
Строка 83: Строка 84:




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


== Открытые вопросы ==
== Открытые вопросы ==
Строка 101: Строка 102:


5. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommun. Syst. 17(4), 385-409 (2001)
5. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommun. Syst. 17(4), 385-409 (2001)
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 10:59, 7 декабря 2024

Ключевые слова и синонимы

Атомарные эгоистичные потоки

Постановка задачи

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

Модель

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


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


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


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

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


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

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


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


Кроме того, каждый сегмент [math]\displaystyle{ \pi \; }[/math] пути наилучшего ответа p является наилучшим ответом для маршрутизации спроса любого пользователя между конечными точками [math]\displaystyle{ \pi \; }[/math]. В данном случае допускается ситуация, когда некоторые пользователи уже внесли свой вклад в изначальный поток f.


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

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

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

1. он представляет собой единственное ребро (s, t) либо

2. он получен из двух серийно-параллельных графов [math]\displaystyle{ G_1, G_2 \; }[/math] с оконечными точками [math]\displaystyle{ (s_1, t_1) \; }[/math] и [math]\displaystyle{ (s_2, t_2) \; }[/math] путем соединения их последовательно (in series) или параллельно. При последовательном соединении [math]\displaystyle{ t_1 \; }[/math] отождествляется с [math]\displaystyle{ s_2 \; }[/math], так что [math]\displaystyle{ s_1 \; }[/math] становится источником (s), а [math]\displaystyle{ t_2 \; }[/math] – приемником (t). При параллельном соединении [math]\displaystyle{ s_1 = s_2 = s \; }[/math] и [math]\displaystyle{ t_1 = t_2 = t \; }[/math].

Основные результаты

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

Алгоритм GBR рассматривает пользователей поочередно в порядке невозрастания веса (т. е. [math]\displaystyle{ w_1 \ge w_2 \ge ... \ge w_n) \; }[/math]. Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR достигает успеха, если итоговый профиль P представляет собой чистое равновесие Нэша.


Характеризация

В работе [3] показано:


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


Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.


Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:

1. пользователи идентичны (если [math]\displaystyle{ w_i = 1 \; }[/math] для всех i), а задержки ребер произвольны, но не убывают; либо

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


Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.


Теорема 5.

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

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

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

Применение

Алгоритм GBR имеет естественное распределенное приложение на основе алгоритма выбора лидера. Каждый игрок в нем представлен процессом. Предполагается, что все процессы знают сеть и функции задержки ребер. Также предполагается наличие подсистемы передачи сообщений и базового механизма синхронизации (например, в виде логических временных меток), что обеспечивает возможность выполнения распределенного протокола в виде логических этапов.


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

Открытые вопросы

Что представляет собой класс сетей, в которых (идентичные) пользователи могут получить чистое распределение Нэша за счет k-кратного повторения последовательности наилучших ответов? Что происходит со взвешенными пользователями? В целом, как топология сети влияет на последовательности наилучших ответов? Эти открытые вопросы служат предметом текущих исследований.

См. также

Литература

1. Awerbuch, B., Azar, Y., Epstein, A.: The price of Routing Unsplittable Flows. In: Proc. ACM Symposium on Theory of Computing (STOC) 2005, pp. 57-66. ACM, New York (2005)

2. Duffin, R.J.: Topology of Series-Parallel Networks. J. Math. Anal. Appl. 10, 303-318 (1965)

3. Fotakis, D., Kontogiannis, S., Spirakis, P.: Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost. In: Proc. of the 3rd Workshop of Approximate and On-line Algorithms (WAOA 2005). Lecture Notes in Computer Science (LNCS), vol. 3879, pp. 161-175. Springer, Berlin Heidelberg (2006)

4. Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish Unsplittable Flows. J.Theor. Comput. Sci. 348,226-239 (2005)

5. Libman, L., Orda, A.: Atomic Resource Sharing in Noncooperative Networks. Telecommun. Syst. 17(4), 385-409 (2001)