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

Теория игр «наоборот»

Традиционная теория игр задает правила игры и пытается предсказать, как поведут себя рациональные игроки. Мы ищем равновесие Нэша в уже существующих условиях.

Но в 1960-х годах выдающийся экономист Леонид Гурвич (Leonid Hurwicz) задал обратный вопрос: что если мы знаем желаемый результат (например, эффективное распределение ресурсов), но не знаем истинных предпочтений людей? Можем ли мы спроектировать такие правила игры (механизм), при которых эгоистичные агенты сами придут к нашему желаемому результату?

Так родилась теория Дизайна механизмов (Mechanism Design) — инженерный подход к экономике, за который в 2007 году Гурвич, Маскин и Майерсон получили Нобелевскую премию.

Проблема асимметрии информации

Главный враг любого планировщика — скрытая информация. Люди знают свою истинную готовность платить (свою ценность $v_i$ ), но не хотят её раскрывать, если могут на этом заработать. Механизм должен быть Incentive Compatible (совместимым со стимулами).

Задача: 4 мальчика и один велосипед

Давайте рассмотрим интуитивный пример. У нас есть 4 мальчика и один коллекционный велосипед. Мы хотим отдать велосипед тому, кто ценит его больше всех. У каждого мальчика есть своя истинная, скрытая в голове ценность этого велосипеда (в рублях):

Мальчик А: истинная ценность $v_A = 100$
Мальчик Б: истинная ценность $v_B = 80$
Мальчик В: истинная ценность $v_C = 50$
Мальчик Г: истинная ценность $v_D = 20$

Если мы просто спросим их: «Кто хочет велосипед сильнее всего?», — каждый крикнет «Я! Моя ценность миллион!». Это классический провал механизма прямого опроса: говорить правду невыгодно.

Решение: Аукцион Викри (Второй цены)

Чтобы извлечь из них правду, мы спроектируем специальный механизм — закрытый аукцион второй цены (Vickrey Auction).

Правила игры: Каждый мальчик тайно пишет свою ставку $b_i$ на бумажке. Тот, кто напишет самую высокую сумму — забирает велосипед. Но! Заплатить он должен не свою ставку, а сумму, которую написал второй по величине участник.

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

Математика этого механизма элегантна. Полезность участника $i$ равна $U_i = v_i - p$ (где $p$ — цена второго места), если он выигрывает, и $U_i = 0$ , если проигрывает.

Рассмотрим Мальчика А ( $v_A = 100$ ). Почему ему невыгодно лгать?

Что если он занизит ставку (напишет $b_A = 70$ )?
Если высшая ставка оппонентов равна 80 (Мальчик Б), то написав 70, Мальчик А проиграет. Его выигрыш 0. Но если бы он честно написал 100, он бы выиграл велосипед, заплатил бы 80 и получил бы полезность $100 - 80 = +20$ . Занижать невыгодно — упускаешь победу.
Что если он завысит ставку (напишет $b_A = 150$ )?
Если оппоненты ставят меньше 100, он и так выигрывает, говоря правду. Но представьте, что кто-то из оппонентов поставит 120. Если Мальчик А завышает ставку до 150, он выигрывает аукцион. Но теперь он обязан заплатить вторую цену — 120! Его полезность: $100 - 120 = -20$ . Он ушел в минус. Завышать невыгодно — риск купить слишком дорого.

b_i^* = v_i

Следовательно, стратегия честности ( $b_i = v_i$ ) является слабо доминантной для каждого игрока.

Интерактив: Аукцион Викри (Вторая цена)

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

Ваша истинная ценность: 100₽

Ваша заявка (ставка на аукционе): 100₽

Оптимальная стратегия (Говорить правду)Вы выиграли! Ваша полезность: 100 (ценность) - 85 (цена) = +15. Это максимально возможный выигрыш.

Распределение заявок

Победитель платит85₽

Ваша чистая выгода+15

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

Дизайн механизмов — это не просто абстрактная математика. Именно эти алгоритмы сегодня работают «под капотом» крупнейших мировых рынков:

Аукционы Google AdWords: когда рекламодатели борются за клики, Google использует обобщенный аукцион второй цены (GSP-аукцион), чтобы заставить компании раскрыть истинную ценность клиента.
Распределение радиочастот: государства продают 5G частоты телекомам с помощью сложных аукционов (FCC auctions), спроектированных Полом Милгромом (Нобелевская премия 2020), чтобы максимизировать эффективность использования спектра.
Алгоритм Гейла-Шепли: механизм мэтчинга, который помогает распределять студентов по университетам и врачей по больницам без использования денег, но так, что никому не выгодно обманывать систему.

🧠 Олимпиадная задача: Механизм Кларка-Гровса (VCG)

Город решает, строить ли новый парк стоимостью $C = 100$ . В городе 3 жителя. Истинные полезности от парка для них равны: $v_1 = 60$ , $v_2 = 50$ , $v_3 = 10$ . Суммарная полезность $\sum v_i = 120 > 100$ , значит, парк строить эффективно.

Однако жители скрывают свои ценности, опасаясь налогов. Мэр решает использовать механизм VCG (Викри-Кларка-Гровса). Каждый житель сообщает свою ценность $b_i$ . Парк строится, если $\sum b_i \ge 100$ .

Если парк строится, каждый платит налог Кларка: налог жителя $i$ равен ущербу, который его присутствие наносит остальным. Формула налога: $T_i = C - \sum_{j \neq i} b_j$ (если эта разница положительна, иначе 0).

Задание: Рассчитайте налоги Кларка для каждого из трех жителей при условии, что они говорят правду. Покажите, покрывают ли собранные налоги стоимость парка.

Математический разбор:

Проверим сумму заявок (при условии честности): $60 + 50 + 10 = 120 \ge 100$ . Парк строится.

Рассчитаем налог для Жителя 1: $T_1 = 100 - (b_2 + b_3) = 100 - (50 + 10) = 40$ .

Рассчитаем налог для Жителя 2: $T_2 = 100 - (b_1 + b_3) = 100 - (60 + 10) = 30$ .

Рассчитаем налог для Жителя 3: $T_3 = 100 - (b_1 + b_2) = 100 - (60 + 50) = 100 - 110 = -10$ . Так как налог не может быть отрицательным (государство не субсидирует в базовой модели VCG), $T_3 = 0$ .

Итого сборы: $T_1 + T_2 + T_3 = 40 + 30 + 0 = 70$ .

Вывод для олимпиады: Суммарные налоги (70) не покрывают стоимость парка (100). Это фундаментальная проблема механизма VCG: он гарантирует честность (Incentive Compatibility) и эффективность (выбор лучшего проекта), но не гарантирует сбалансированность бюджета (Budget Balance). Государству придется доплачивать 30 из внешних источников.