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

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

Игра о загруженности сети представляет собой кортеж ((wi )i2N, G, (de )e2E ), где N = f1, ... : : ng – множество пользователей, где пользователь i контролирует wi единиц спроса на трафик. В невзвешенных играх о загруженности wi = 1 для i = 1, ..., : : n. G(V, E) – ориентированный граф, представляющий сеть коммуникаций, а de – функция задержки, ассоциированная с ребром e 2 E. Предполагается, что de являются неотрицательными и неубывающими функциями от загрузок ребра. Ребра называются идентичными, если de (x) = x, 8e 2 E. Далее модель ограничивается играми о загруженности сети одного товара, в которых G имеет единственный источник s и приемник t, а множество пользовательских стратегий представляет собой множество путей s _ t, обозначаемое как P. Без потери общности можно предположить, что граф G является связным и что каждая вершина G лежит на ориентированном пути s _ t.