4501
правка
Алгоритмический дизайн механизмов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 14:04, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 46: | Строка 46: | ||
(1) Различные алгоритмические цели: в литературе по алгоритмам рассматривается множество целей, включая немало таких, которые не могут быть сведены к максимизации благосостояния. В этих случаях подход ВКГ нам не поможет. | (1) Различные алгоритмические цели: в литературе по алгоритмам рассматривается множество целей, включая немало таких, которые не могут быть сведены к максимизации благосостояния. В этих случаях подход ВКГ нам не поможет. | ||
(2) Вычислительная сложность: даже если целью является максимизация благосостояния, во многих случаях достижение точного оптимума является вычислительно трудной задачей. Вычислительные науки обычно преодолевают эту трудность с помощью алгоритмов | (2) Вычислительная сложность: даже если целью является максимизация благосостояния, во многих случаях достижение точного оптимума является вычислительно трудной задачей. Вычислительные науки обычно преодолевают эту трудность с помощью аппроксимационных алгоритмов, но ВКГ не будет работать с таким алгоритмом – достижение точного оптимума является необходимым требованием этого механизма. | ||
(3) Различные алгоритмические модели: распространенные модели вычислительных наук изменяют «базовую установку», что приводит к неожиданным трудностям при попытке использовать подход ВКГ (например, онлайн-модель, где входные данные раскрываются со временем; такая ситуация распространена в вычислительных науках, но изменяет неявный базис механизма ВКГ). Это актуально даже в том случае, если целью остается максимизация благосостояния. | (3) Различные алгоритмические модели: распространенные модели вычислительных наук изменяют «базовую установку», что приводит к неожиданным трудностям при попытке использовать подход ВКГ (например, онлайн-модель, где входные данные раскрываются со временем; такая ситуация распространена в вычислительных науках, но изменяет неявный базис механизма ВКГ). Это актуально даже в том случае, если целью остается максимизация благосостояния. | ||
| Строка 68: | Строка 68: | ||
Более подробно этот результат описан в статье [[Механизм для однопараметрических агентов с одним покупателем]]. Итоговый вывод состоит в том, что, хотя социальная цель отличается от максимизации благосостояния, все же существует правдивый механизм для ее достижения. Нетривиальная гарантия аппроксимации достигается даже при дополнительном требовании вычислительной эффективности. Однако эта гарантия не соответствует наилучшей гарантии, возможной без требования правдивости, поскольку для этого случая известна схема | Более подробно этот результат описан в статье [[Механизм для однопараметрических агентов с одним покупателем]]. Итоговый вывод состоит в том, что, хотя социальная цель отличается от максимизации благосостояния, все же существует правдивый механизм для ее достижения. Нетривиальная гарантия аппроксимации достигается даже при дополнительном требовании вычислительной эффективности. Однако эта гарантия не соответствует наилучшей гарантии, возможной без требования правдивости, поскольку для этого случая известна аппроксимационная схема с полиномиальным временем выполнения (PTAS). | ||