Алгоритмы наилучших ответов для эгоистичной маршрутизации: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) (→Модель) |
Irina (обсуждение | вклад) (→Модель) |
||
| Строка 28: | Строка 28: | ||
Игра о загруженности сети одного товара <math>((w_i)_{i \in N}, G, (d_e)_{e \in E}) \;</math> обладает свойством общего наилучшего ответа, если для каждого изначального потока f (не обязательно допустимого) все пользователи имеют один и тот же набор наилучших ответов относительно £. Иначе говоря, если путь p является наилучшим ответом относительно f для некоторого пользователя, то для всех пользователей j и всех путей | Игра о загруженности сети одного товара <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>. | ||
Кроме того, каждый сегмент | Кроме того, каждый сегмент <math>\pi \;</math> пути наилучшего ответа p является наилучшим ответом для маршрутизации спроса любого пользователя между конечными точками <math>\pi \;</math>. В данном случае допускается ситуация, когда некоторые пользователи уже внесли свой вклад в изначальный поток f. | ||
Многослойные и серийно-параллельные графы | '''Многослойные и серийно-параллельные графы''' | ||
Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является многослойным в том и только том случае, если все ориентированные пути | Ориентированный (мульти)граф G(V, E) с выделенным источником s и приемником t является [[многослойный граф|многослойным]] в том и только том случае, если все ориентированные пути s—t имеют одну и ту же длину, и каждая вершина графа лежит на некотором ориентированном пути s—t. | ||
Мультиграф является серийно-параллельным с оконечными точками (s, t), если: | Мультиграф является [[серийно-параллельный граф|серийно-параллельным]] с ''оконечными точками'' (s, t), если: | ||
1. он представляет собой единственное ребро (s, t) либо | 1. он представляет собой единственное ребро (s, t) либо | ||