Правдивое планирование работы - Truthful job scheduling

Правдивое планирование работы это конструкция механизма вариант планирование работы цеха проблема от исследование операций.

У нас есть проект, состоящий из нескольких «заданий» (задач). Есть несколько рабочих. Каждый работник может выполнять любую работу, но для каждого рабочего требуется разное количество времени для выполнения каждой работы. Наша цель - распределить рабочие места между рабочими так, чтобы общая готовность проекта сведено к минимуму. В стандартной задаче планирования работы цеха время всех рабочих известно, поэтому у нас есть стандартная задача оптимизации. Напротив, в задаче точного расписания работы время рабочих неизвестно. Мы спрашиваем каждого рабочего, сколько времени ему нужно на выполнение каждой работы, но рабочие могут нам солгать. Следовательно, мы должны стимулировать рабочих сообщать нам свое истинное время, заплатив им определенную сумму денег. Задача состоит в том, чтобы разработать механизм оплаты, который совместимость со стимулом.

Проблема точного планирования заданий была представлена ​​Нисаном и Роненом в их статье 1999 г. алгоритмический механизм проектирования.^[1]

Определения

Есть ${\displaystyle n}$ рабочие места и ${\displaystyle m}$ рабочих ("m" означает "машина", поскольку проблема возникает из-за планирования рабочие места к компьютерам). Рабочий ${\displaystyle i}$ может делать работу ${\displaystyle j}$ во время ${\displaystyle T_{i,j}}$. Если рабочий ${\displaystyle i}$ назначается набор работ ${\displaystyle J_{i}}$, то он может выполнить их вовремя:

${\displaystyle T_{i}(J_{i})=\sum _{j\in J_{i}}t_{i,j}}$

Учитывая распределение ${\displaystyle J_{1},\dots ,J_{m}}$ рабочих мест для рабочих, готовность проекта это:

${\displaystyle MakeSpan(J_{1},\dots ,J_{n})=\max _{i}{T_{i}(J_{i})}}$

An оптимальное распределение - это распределение рабочих мест между рабочими с минимальным сроком изготовления. Минимальный срок изготовления обозначается ${\displaystyle MinMakeSpan}$.

А механизм - функция, которая принимает на вход матрицу ${\displaystyle T}$ (время, необходимое каждому рабочему для выполнения каждой работы) и возвращается как результат:

• Распределение рабочих мест среди рабочих, ${\displaystyle J_{1},\dots ,J_{n}}$;
• Плата каждому работнику, ${\displaystyle p_{1},\dots ,p_{n}}$.

Полезность рабочего ${\displaystyle i}$, при таком механизме:

${\displaystyle u_{i}=p_{i}-T_{i}(J_{i})}$

То есть агент получает оплату, но теряет время, которое он тратит на выполнение задач. Обратите внимание, что оплата и время измеряются в одних и тех же единицах (например, мы можем предположить, что платежи производятся в долларах и что каждая единица времени обходится работнику в один доллар).

Механизм называется правдивый (или же совместимость со стимулом ), если каждый рабочий может получить максимальную полезность, сообщая свой истинный вектор времени (т. е. ни у одного рабочего нет стимула лгать о своих временах).

В коэффициент приближения механизма - наибольшее соотношение между ${\displaystyle Makespan}$ и ${\displaystyle MinMakespan}$ (чем меньше, тем лучше; коэффициент приближения 1 означает, что механизм является оптимальным).

Исследование правдивого планирования заданий направлено на поиск верхней (положительной) и нижней (отрицательной) границ коэффициентов аппроксимации истинных механизмов.

Положительная граница - m - механизм VCG

Первое решение, которое приходит на ум, это Механизм VCG, который является универсальным правдивым механизмом. Для минимизации суммы затрат можно использовать механизм VCG. Здесь мы можем использовать VCG, чтобы найти распределение, которое минимизирует «общий итог», определяемый как:

${\displaystyle MakeTotal(J_{1},\dots ,J_{n})=\sum _{i}{T_{i}(J_{i})}}$

Здесь минимизировать сумму можно, просто назначив каждое задание работнику, которому требуется наименьшее время для выполнения этой работы. Чтобы механизм оставался правдивым, каждому работнику, который соглашается на работу, платят второе по времени время за эту работу (как в Викри аукцион ).

Пусть OPT будет выделением, которое минимизирует время изготовления. Потом:

${\displaystyle MakeSpan[VCG]\leq MakeTotal[VCG]\leq MakeTotal[OPT]\leq m\cdot MakeSpan[OPT]}$

(где последнее неравенство следует из принцип голубятни ). Следовательно, коэффициент аппроксимации решения ВКГ не более ${\displaystyle m}$ - количество рабочих.

Следующий пример показывает, что коэффициент аппроксимации решения VCG действительно может быть точно ${\displaystyle m}$. Предположим, есть ${\displaystyle n=m}$ рабочие места и расписание рабочих следующие:

• Рабочий 1 может выполнить любую работу за время 1.
• Другие работники могут выполнять любую работу вовремя ${\displaystyle 1+\epsilon }$, куда ${\displaystyle \epsilon >0}$ - малая константа.

Затем механизм VCG распределяет все задачи работнику 1. И «итоговая сумма», и время изготовления равны ${\displaystyle n=m}$. Но, когда каждая работа поручается другому работнику, время изготовления ${\displaystyle 1+\epsilon }$.

Фактор приближения ${\displaystyle m}$ не очень хорошо, и многие исследователи пытались улучшить его в последующие годы.

С другой стороны, есть некоторые результаты о невозможности, которые доказывают, что фактор аппроксимации не может быть слишком малым.

Отрицательная граница - 2

Фактор приближения каждого правдивого детерминированный Механизм не менее 2.^[1]:177–

Доказательство типично для нижних оценок конструкции механизмов. Проверяем конкретные сценарии (в нашем случае конкретные тайминги воркеров). По правде говоря, когда одинокий рабочий изменяет свое заявление, он не должен извлекать из этого выгоду. Это вызывает некоторые ограничения на выделение памяти, возвращаемое механизмом в различных сценариях.

В следующем эскизе доказательства для простоты мы предполагаем, что есть 2 рабочих и что количество работ четное, ${\displaystyle n=2k}$. Мы рассматриваем следующие сценарии:

1. Время обоих рабочих для всех заданий равно 1. Поскольку механизм детерминирован, он должен возвращать уникальное распределение. ${\displaystyle J_{1},J_{2}}$. Предположим, без ограничения общности, что ${\displaystyle |J_{1}|\leq |J_{2}|}$ (Работнику 1 назначается не больше рабочих мест, чем работнику 2).
2. Время рабочего 1 до рабочих мест в ${\displaystyle J_{1}}$ находятся ${\displaystyle \epsilon }$ (очень маленькая положительная константа); время рабочего 1 до рабочих мест в ${\displaystyle J_{2}}$ находятся ${\displaystyle 1+\epsilon }$; а тайминги рабочего 2 для всех заданий по-прежнему равны 1. Рабочий 1 знает, что, если он лжет и говорит, что его тайминги для всех заданий равны 1, (детерминированный) механизм распределит ему задания в ${\displaystyle J_{1}}$ и его стоимость будет очень близка к нулю. Чтобы оставаться правдивым, механизм должен делать то же самое здесь, чтобы рабочий 1 не выиграл от лжи. Однако время изготовления можно уменьшить вдвое, разделив рабочие места на ${\displaystyle J_{2}}$ поровну между агентами.

Следовательно, коэффициент приближения механизма должен быть не менее 2.

Рекомендации

1. Нисан, Ноам; Ронен, Амир (2001). «Дизайн алгоритмических механизмов». Игры и экономическое поведение. 35 (1–2): 166–196. Дои:10.1006 / игра.1999.0790.