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

Вектор <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>

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

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