Цена анархии в задаче максимизации минимальной задержки машин в системе обслуживания

Автор(ы): Чиркова Ю. В.

Название статьи: Цена анархии в задаче максимизации минимальной задержки машин в системе обслуживания

Выпуск: 62

Рубрика: Системный анализ

Год: 2016

Библиография: Чиркова Ю. В. Цена анархии в задаче максимизации минимальной задержки машин в системе обслуживания / Управление большими системами. Выпуск 62. М.: ИПУ РАН, 2016. С.30-59.

Дата опубликования: 31.07.2016

Ключевые слова: система обслуживания, максимизация минимальной задержки, равновесие по Нэшу, цена анархии

Аннотация: Исследуется игра максимизации минимальной задержки системы обслуживания. Игроки распределяют свои задачи различного объема между машинами, различающимися скоростями обслуживания. Каждый игрок стремится минимизировать время обслуживания своей задачи на выбранной им машине. Выигрышем системы является минимальная среди всех машин задержка. Оптимальным для системы распределением задач по машинам является такое, где максимизируется наименьшая среди всех машин задержка. Для общего случая N машин найдена нижняя граница цены анархии и для случая трех машин найдено ее точное значение. Для двух машин доказано, что при добавлении в систему новой третьей машины цена анархии не изменяется либо растет. Также предложен алгоритм вычисления точного значения цены анархии на примере системы трех машин.

Author(s): Chirkova J.

Article title: Price of anarchy for maximizing the minimum machine load

Issue: 62

Year: 2016

Keywords: Nash equilibrium, cover, maximizing the minimum load, price of anarchy, selfish load balancing

Abstract: The maximizing the minimum machine delay game with uniformly related machines is considered. Players choose machines with different speeds to run their jobs trying to minimize job’s delay, i.e. chosen machine’s completion time. The social payoff is the minimal delay over all machines. For the general case of N machines we find the lower bound for Price of Anarchy (PoA), and for the case of 3 machines we find its exact value. We prove that the PoA either remains the same or increases when an additional third machine is included into the system with two machines. Also we propose a method of computation the PoA value and illustrate it for 3 machines.

в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 3951; загрузок: 1758, за месяц: 23.

Назад