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

Пусть дана ситуация, в которой n эгоистичных пользователей конкурируют за маршрутизацию своих загрузок в сети. Сеть представляет собой ориентированный s-t-граф с единственной вершиной-источником s и единственной вершиной-приемником t. Пользователи последовательным образом упорядочены. Предполагается, что каждый пользователь делает свой ход после того пользователя, за которым он идет согласно порядку, а желаемый конечный результат представляет собой чистое [[равновесие Нэша]]. Также предполагается, что когда пользователь делает ход (т.е. выбирает путь s-t для маршрутизации своей загрузки), этот ход является наилучшим ответом (т.е. имеет минимальную задержку) с учетом путей и пользователей, в данный момент находящихся в сети. Задача заключается в поиске класса ориентированных графов, для которых существует упорядочение, такое, что соответствующая последовательность наилучших ответов приводит к чистому равновесию Нэша.