4430
правок
Алгоритмический дизайн механизмов: различия между версиями
Материал из WEGA
Алгоритмический дизайн механизмов (посмотреть исходный код)
Версия от 21:52, 9 июля 2023
, 9 июля 2023→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Правдивость является достаточно сильным понятием: игроку не требуется знать ничего о других игроках, даже то, что они рациональны | Правдивость является достаточно сильным понятием: игроку не требуется знать ничего о других игроках, даже то, что они рациональны; он все равно сможет определить наилучшую для себя стратегию. Весьма примечательно, что существует механизм поддержки правдивости, даже на текущем уровне абстракции. Этот механизм подходит для всех предметных областей, где социальной целью является максимизация «общественного благосостояния»: | ||
| Строка 39: | Строка 39: | ||
'''Теорема 1 (Викри-Кларка-Гровса, ВКГ). Зафиксируем любое множество альтернатив A и любую область V и предположим, что <math>f: V \to A</math> максимизирует общественное благосостояние. Тогда существуют цены p, такие, что механизм (f, p) является правдивым.''' | '''Теорема 1 (Викри-Кларка-Гровса, ВКГ). Зафиксируем любое множество альтернатив A и любую область V и предположим, что функция <math>f: V \to A</math> максимизирует общественное благосостояние. Тогда существуют цены p, такие, что механизм (f, p) является правдивым.''' | ||
Этот подход дает «бесплатное» решение задачи поиска кратчайшего пути и многих других алгоритмических проблем. Большим преимуществом схемы ВКГ является ее универсальность: она подходит для ''любых'' предметных областей. Недостатком, однако, является то, что метод специализирован под максимизацию общественного благосостояния. Это обстоятельство оказывается ограничивающим, особенно в алгоритмических и вычислительных задачах, по нескольким причинам: | Этот подход дает «бесплатное» решение задачи поиска кратчайшего пути и многих других алгоритмических проблем. Большим преимуществом схемы ВКГ является ее универсальность: она подходит для ''любых'' предметных областей. Недостатком, однако, является то, что метод специализирован под максимизацию общественного благосостояния. Это обстоятельство оказывается ограничивающим, особенно в алгоритмических и вычислительных задачах, по нескольким причинам: | ||
(1) Различные алгоритмические цели: в литературе по алгоритмам рассматривается множество целей, включая немало таких, которые не могут быть | (1) Различные алгоритмические цели: в литературе по алгоритмам рассматривается множество целей, включая немало таких, которые не могут быть сведены к максимизации благосостояния. В этих случаях подход ВКГ нам не поможет. | ||
(2) Вычислительная сложность: даже если целью является максимизация благосостояния, во многих случаях достижение точного оптимума является вычислительно трудной задачей. Вычислительные науки обычно преодолевают | (2) Вычислительная сложность: даже если целью является максимизация благосостояния, во многих случаях достижение точного оптимума является вычислительно трудной задачей. Вычислительные науки обычно преодолевают эту трудность с помощью алгоритмов аппроксимации, но ВКГ не будет работать с таким алгоритмом – достижение точного оптимума является необходимым требованием этого механизма. | ||
(3) Различные алгоритмические модели: распространенные модели вычислительных наук изменяют «базовую установку», что приводит к неожиданным трудностям при попытке использовать подход | (3) Различные алгоритмические модели: распространенные модели вычислительных наук изменяют «базовую установку», что приводит к неожиданным трудностям при попытке использовать подход ВКГ (например, онлайн-модель, где входные данные раскрываются со временем; это распространено в вычислительных науках, но изменяет неявную установку, лежащую в основе механизма ВКГ). Это актуально даже в том случае, если целью остается максимизация благосостояния. | ||
