Навигатор ОлимпиадКалькулятор ОлимпиадОлимпиадный ТаймлайнНовости Олимпиад
В блогn2tutor
Теория ИгрДизайн механизмов

Аукцион Викри: Как победить страх переплаты

10 мин чтения Н. Саперов

Представьте, что вы хотите купить уникальную картину на аукционе. Вы готовы отдать за нее 1000$, но боитесь, что конкуренты предложат лишь 100$. Зачем вам переплачивать 900$? В теории игр есть гениальный механизм, который заставляет всех участников называть свою истинную ценность без страха переплаты. Добро пожаловать в мир Аукциона второй цены.

Проблема стандартного аукциона

В классическом закрытом аукционе первой цены (First-price sealed-bid auction) участники подают заявки в конвертах. Побеждает тот, кто предложил больше всех, и он платит именно ту сумму, которую назвал.

Угроза (Shading): Если ваша истинная ценность картины v = 1000, вы никогда не напишете в конверте 1000$. Если вы выиграете со ставкой 1000$, ваша полезность будет равна нулю (1000 - 1000 = 0). Вы всегда будете занижать свою ставку (shade your bid), пытаясь угадать ставки конкурентов, чтобы получить положительный выигрыш.

Это приводит к сложнейшим стратегическим вычислениям и неэффективности: картина может достаться не тому, кто ценит её больше всего, а тому, кто лучше угадал чужие ставки.

Гениальность Уильяма Викри

В 1961 году экономист Уильям Викри (получивший позже Нобелевскую премию) предложил элегантное решение: Аукцион второй цены (Vickrey auction).

Правила Аукциона Викри

  • Все участники тайно подают свои ставки.
  • Побеждает тот, кто предложил максимальную сумму.
  • НО платит он цену, предложенную вторым по величине участником.

Доказательство доминирующей стратегии

Самое красивое в этом аукционе то, что правдивая ставка является слабо доминирующей стратегией (weakly dominant strategy). Вам выгодно назвать свою истинную ценность (b = v), независимо от того, что делают другие игроки! Это излюбленная тема для задач на олимпиадах.

Математическая логика:

Пусть v — ваша истинная ценность, b — ваша ставка, а M — максимальная ставка среди всех остальных участников.

  • Сценарий 1: Вы занижаете ставку (b < v). Если M < b, вы выигрываете и платите M. Ваш выигрыш v - M. Если бы вы поставили честно (v), вы бы тоже выиграли и заплатили M. Ничего не изменилось. НО, если b < M < v, вы проигрываете аукцион (выигрыш 0). А если бы поставили честно, вы бы выиграли и получили положительный выигрыш (v - M > 0). Занижение ставки может только навредить.
  • Сценарий 2: Вы завышаете ставку (b > v). Если M > b, вы проигрываете. Если M < v, вы выигрываете и платите M (результат такой же, как при честной ставке). НО, если v < M < b, вы выигрываете аукцион, но платите M, что больше вашей ценности v. Вы получаете убыток (v - M < 0). Завышение ставки ведет к риску убытков.

Вывод: Ставить b = v (честную ценность) всегда лучше или так же хорошо, как любую другую ставку.

Применение в реальном мире

Аукцион Викри — это не просто абстрактная математика. Ранние системы продажи рекламы в поисковиках (Google AdWords, Яндекс.Директ) базировались именно на принципах аукциона второй цены (позже эволюционировав в обобщенные аукционы VCG). Это позволяло системам работать эффективно, не заставляя рекламодателей постоянно подстраивать ставки в попытках обмануть конкурентов.

Разбираем теорию игр на практике

Задачи на аукционы и дизайн механизмов регулярно встречаются на финалах ВсОШ. Хотите научиться строго доказывать доминирующие стратегии?

Записаться на курс