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