Дизайн механизмов и теория аукционов: алгоритмы VCG и максимизация общественного блага

Центральной проблемой дизайна механизмов является выявление истинных предпочтений (Truthful Revelation). Участники рынка имеют скрытую информацию (например, истинную ценность лицензии на 5G-частоту). Если регулятор просто спросит их, сколько они готовы заплатить, компании соврут, занизив оценку, чтобы купить актив дешевле. Механизм называется совместимым по стимулам (Incentive Compatible), если для абсолютно каждого участника математически наиболее выгодной стратегией является раскрытие своей настоящей, честной оценки, независимо от того, как именно ведут себя конкуренты. Это позволяет алгоритмам оптимизации получать достоверные входные данные для вычисления идеального распределения ресурсов.

Простейшим и самым известным совместимым по стимулам механизмом является закрытый аукцион второй цены (Аукцион Викри). В отличие от классического английского аукциона, здесь участники подают заявки в запечатанных конвертах. Победителем объявляется тот, кто предложил самую высокую цену, но платит он не свою ставку, а ставку участника, занявшего второе место. Математическое доказательство Викри гениально: если вы попытаетесь занизить свою ставку, вы рискуете проиграть аукцион, не изменив цену, которую заплатили бы в случае выигрыша. Если вы попытаетесь завысить ставку, вы рискуете купить товар по цене, превышающей вашу истинную оценку. Таким образом, единственная оптимальная (доминирующая) стратегия — написать в конверте ровно ту сумму, в которую вы оцениваете лот.

Для сложных систем, где распределяется не один товар, а комбинации множества разнородных ресурсов (комбинаторные аукционы), аппарат Викри был обобщен до алгоритма Викри-Кларка-Гровса (VCG-механизм). Цель алгоритма VCG — максимизировать социальное благосостояние (суммарную ценность ресурсов для всех победителей). Алгоритм собирает заявки от всех участников и решает гигантскую задачу целочисленного линейного программирования для поиска оптимального распределения благ. Самое сложное — это расчет справедливых платежей. По правилам VCG каждый участник платит налог, в точности равный экстерналии (ущербу), которую его присутствие на аукционе нанесло всем остальным участникам рынка.

Аналитически этот налог вычисляется путем двукратного решения задачи оптимизации. Сначала алгоритм считает максимальное социальное благосостояние всей системы без участия данного игрока. Затем вычисляет социальное благосостояние остальных игроков при условии, что этот участник присутствует и забирает свои лоты. Разница между этими двумя значениями и является налогом VCG. Этот математический механизм гарантирует, что участникам абсолютно всегда выгодно говорить правду. Однако VCG имеет вычислительные проблемы: он требует многократного решения NP-трудных задач комбинаторной оптимизации, что вынуждает исследователей операций создавать приближенные, но быстродействующие эвристические механизмы для работы бирж контекстной рекламы в миллисекундных таймфреймах.