4446
правок
Алгоритмы наилучших ответов для эгоистичной маршрутизации: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы наилучших ответов для эгоистичной маршрутизации (посмотреть исходный код)
Версия от 19:24, 30 ноября 2016
, 30 ноября 2016→Основные результаты
Irina (обсуждение | вклад) (→Модель) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR) | Жадный алгоритм с наилучшим ответом Greedy Best Response (GBR) | ||
Алгоритм GBR рассматривает пользователей поочередно ''в порядке невозрастания веса'' (т. е. <math>w_1 \ge w_2 \ge ... \ge w_n) \;</math>. Каждый пользователь вырабатывает стратегию наилучшего для себя ответа на основе множества (уже реализованных в сети) наилучших ответов предыдущих пользователей. Пользователь не может менять свою стратегию в будущем. Алгоритм GBR ''достигает успеха'', если итоговый профиль P представляет собой чистое равновесие Нэша. | |||
'''Характеризация''' | |||
В работе [3] показано: | |||
'''Теорема 1. Если граф G является (s—t)-серийно-параллельным, а игра <math>((w_i)_{i \in N}, G, (d_e)_{e \in E} \;</math> обладает свойством общего наилучшего ответа, то алгоритм GBR достигает успеха.''' | |||
'''Теорема 2. Взвешенная игра о загруженности сети одного товара в многослойной сети с идентичными ребрами обладает свойством общего наилучшего ответа для любого множества пользовательских весов.''' | |||
'''Теорема 3. Для любой игры о загруженности сети одного товара в серийно-параллельных сетях алгоритм GBR достигает успеха, если:''' | |||
'''1. пользователи идентичны (если <math>w_i = 1 \;</math> для всех i), а задержки ребер произвольны, но не убывают; либо''' | |||
'''2. граф является многослойным, а его ребра идентичны (для произвольных пользовательских весов).''' | |||
'''Теорема 4. Если сеть состоит из пакетов параллельных связей, соединенных последовательно, то чистое равновесие Нэша можно получить, применив алгоритм GBR к каждому пакету.''' | |||
'''Теорема 5.''' | |||
'''1. Если сеть не является серийно-параллельной, то существуют игры, на которых GBR не достигает успеха, даже в случае с 2 идентичными пользователями и идентичными ребрами.''' | |||
Примеры подобных игр представлены в [ ]. | '''2. Если сеть не обладает свойством наилучшего ответа (и не состоит из пакетов параллельных связей, соединенных последовательно), то существуют игры, на которых GBR не достигает успеха, даже в случае с 2-слойными серийно-параллельными графами.''' | ||
Примеры подобных игр представлены в [3]. | |||
== Применение == | == Применение == | ||