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