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

(Допустимый) поток на множестве P путей s — t по графу G задается функцией <math>f: P \to \mathfrak{R}_{ \ge 0} \;</math>, такой, что <math>\sum_{p \in P} f_p = \sum_{i = 1}^n w_i \;</math> .

Игра о загруженности сети одного товара <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>.