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

Вектор <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 \backslash p_i} d_e (l(e(P)) + w_i \;</math>

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

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

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