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

Планирование заданий – это классическая алгоритмическая формулировка задачи: n заданий необходимо распределить между m машинами, учитывая, что задание j требует времени обработки <math>p_{ij}</math> на машине i. В теоретико-игровой формулировке предполагается, что каждая машина i является эгоистичным субъектом, который несет затраты <math>p_{ij}</math> от обработки задания j. Заметим, что платежи в этой формулировке (и в общем случае) могут быть отрицательными, компенсируя такие затраты. Популярной алгоритмической целью является распределение заданий между машинами с целью минимизации «продолжительности работы»: <math>max_i \sum_{j \; is \; assigned \; to \; i} p_{ij}</math> (j назначено i). Это отличается от ориентации на максимизацию благосостояния, которая в данном случае сводится к минимизации <math>\sum_i \sum_{j \; is \; assigned \; to \; i} p_{ij}</math>, что еще раз иллюстрирует проблему различия алгоритмических целей. Таким образом, схема ВКГ здесь не может использоваться, и необходимо разработать новые методы.

Результаты для этой предметной области зависят от конкретных предположений о структуре векторов во время обработки. В случае ''связанных машин'', <math>p_{ij} = p_j / s_i</math> для любого ij, где значения <math>p_j</math> являются общеизвестными, а единственным секретным параметром игрока i является его ''скорость'', <math>s_i</math>.

Более подробно этот результат описан в статье [[Механизм для однопараметрических агентов с одним покупателем]]. Итоговый вывод состоит в том, что, хотя социальная цель отличается от максимизации благосостояния, все же существует правдивый механизм для ее достижения. Достигается нетривиальная гарантия аппроксимации, даже при дополнительном требовании вычислительной эффективности. Однако эта гарантия не соответствует наилучшей гарантии, возможной без требования правдивости, поскольку для этого случая известна схема аппроксимации с полиномиальным временем выполнения (PTAS).

Если число машин фиксировано, в работе [2] приводится такая правдивая схема PTAS.