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

Перейти к навигации Перейти к поиску
Строка 59: Строка 59:
'''Предметная область 1: планирование заданий'''
'''Предметная область 1: планирование заданий'''


Планирование заданий – это классическая алгоритмическая формулировка задачи: n заданий необходимо распределить между m машинами, при том что задание j требует времени обработки pij на машине i. В теоретико-игровой формулировке предполагается, что каждая машина i является эгоистичным субъектом, который несет затраты pij от обработки задания j. Заметим, что платежи в этой формулировке (и в общем случае) могут быть отрицательными, компенсируя такие затраты. Популярной алгоритмической целью является распределение заданий между машинами с целью минимизации «продолжительности работы»: maxi Pj назначается i pij. Это отличается от ориентации на максимизацию благосостояния, которая в данном случае сводится к минимизации Pi Pj назначается pij, что еще раз иллюстрирует проблему различия алгоритмических целей. Таким образом, схема VCG не может использоваться, необходимо разработать новые методы.
Планирование заданий – это классическая алгоритмическая формулировка задачи: 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>, что еще раз иллюстрирует проблему различия алгоритмических целей. Таким образом, схема ВКГ здесь не может использоваться, и необходимо разработать новые методы.




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


Теорема 2 [3, 22]. Для планирования заданий на связанных машинах существуют правдивый механизм с экспоненциальным временем выполнения, позволяющий получить оптимальную продолжительность работы, и правдивый механизм с полиномиальным временем выполнения, позволяющий получить аппроксимацию оптимальной продолжительности работы с коэффициентом аппроксимации 3.


'''Теорема 2 [3, 22]. Для планирования заданий на связанных машинах существуют правдивый механизм с экспоненциальным временем выполнения, позволяющий получить оптимальную продолжительность работы, и правдивый механизм с полиномиальным временем выполнения, позволяющий получить аппроксимацию оптимальной продолжительности работы с коэффициентом аппроксимации 3.'''


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


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


Открытый вопрос № 1: существует ли правдивая схема PTAS для минимизации продолжительности работы на связанных машинах?
Если число машин фиксировано, в работе [ ] приводится такая правдивая схема PTAS.


'''Открытый вопрос № 1''': существует ли правдивая схема PTAS для минимизации продолжительности работы на связанных машинах?


Вышеприведенная картина полностью меняется при переходе к более общему случаю несвязанных машин, где элементы pij могут быть произвольными:


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


Теорема 3 [13, 30]. Ни один правдивый механизм планирования для несвязанных машин не может аппроксимировать оптимальную продолжительность работы с коэффициентом лучше 1 + p2 (для детерминированных механизмов) и 2 - 1/m (для рандомизированных механизмов).
 
Вышеприведенная картина полностью меняется при переходе к более общему случаю ''несвязанных машин'', где элементы <math>p_{ij}</math> могут быть произвольными:
 
 
'''Теорема 3 [13, 30]. Ни один правдивый механизм планирования для несвязанных машин не может аппроксимировать оптимальную продолжительность работы с коэффициентом лучше <math>1 + \sqrt{2}</math> (для детерминированных механизмов) и <math>2 - 1/m</math> (для рандомизированных механизмов).'''




Строка 84: Строка 86:




Открытый вопрос № 2: какова наилучшая возможная аппроксимация для правдивой минимизации продолжительности работы на несвязанных машинах?
'''Открытый вопрос № 2''': какова наилучшая возможная аппроксимация для правдивой минимизации продолжительности работы на несвязанных машинах?




Строка 199: Строка 201:


В этом построении элегантно используются принципы теории обучения. Аукционы с объявленной ценой для этого случая также возможны; в этом случае аддитивные потери возрастают до O(hloglogh). В [ ] рассматриваются полностью правдивые онлайн-аукционы для максимизации дохода, но авторам удается получить только очень высокие (хотя и фиксированные) коэффициенты конкурентоспособности. Построение полностью правдивых онлайн-аукционов с близким к оптимальному доходом остается открытым вопросом. Еще один интересный открытый вопрос связан с многомерными оценками. Работа [24] остается единственным источником для игроков, которым может требоваться несколько товаров. Однако их конкурентные гарантии довольно высоки, и достижение лучших приближенных гарантий (особенно в отношении дохода) является сложной задачей.
В этом построении элегантно используются принципы теории обучения. Аукционы с объявленной ценой для этого случая также возможны; в этом случае аддитивные потери возрастают до O(hloglogh). В [ ] рассматриваются полностью правдивые онлайн-аукционы для максимизации дохода, но авторам удается получить только очень высокие (хотя и фиксированные) коэффициенты конкурентоспособности. Построение полностью правдивых онлайн-аукционов с близким к оптимальному доходом остается открытым вопросом. Еще один интересный открытый вопрос связан с многомерными оценками. Работа [24] остается единственным источником для игроков, которым может требоваться несколько товаров. Однако их конкурентные гарантии довольно высоки, и достижение лучших приближенных гарантий (особенно в отношении дохода) является сложной задачей.


== Вопросы повышенной сложности ==
== Вопросы повышенной сложности ==
Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритмический_дизайн_механизмов