Алгоритмический дизайн механизмов: различия между версиями

Основной вопрос стимулирования также вполне понятен: механизм ВКГ обеспечивает правдивость. Поскольку ВКГ необходим точный оптимум, вычисление которого является NP-полной задачей, эти два соображения конфликтуют друг с другом при попытке использовать классические техники. Разработка алгоритмических механизмов направлена на разработку новых техник, позволяющих объединить эти два желаемых аспекта.

Первый положительный результат для этой интеграционной задачи был получен в работе [29] для особого случая «целеустремленных» участников торгов: каждый участник торгов, i, заинтересован в приобретении конкретного пакета <math>S_i</math> за стоимость <math>v_i</math> (любой пакет, содержащий <math>S_i</math>, стоит <math>v_i</math>, а другие пакеты имеют нулевую стоимость). И <math>v_i</math>, и <math>S_i</math> являются частными для игрока i.