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

Теорема 7 [26]. Существует ожидаемо правдивый рандомизированный многотоварный комбинаторный аукцион с полиномиальным временем выполнения для B > 1 экземпляров каждого товара, позволяющий получить O(m1 /(B+1))-аппроксимацию оптимального общественного благосостояния.

Таким образом, за счет введения случайности разрыв со стандартным вычислительным статусом полностью закрывается. Определение «ожидаемой правдивости» является естественным расширением понятия правдивости на рандомизированную среду: ожидаемая полезность игрока максимизируется, если он правдив.

Однако это понятие строго слабее детерминистского, поскольку оно неявно подразумевает, что игроков волнует только ожидание их полезности (а не, например, дисперсия). В экономической литературе это называется предположением о «нейтральном отношении к риску». Промежуточным понятием для рандомизированных механизмов является понятие «универсальной правдивости»: механизм правдив при любом фиксированном результате броска монеты. Здесь нейтральное отношение к риску уже не требуется. В [15] приводится универсально правдивый комбинаторный аукцион для В = 1, который дает O(pm)-аппроксимацию.  

Универсально правдивые механизмы все-таки слабее детерминированных правдивых механизмов по двум причинам: (1) Неясно, как именно следует организовать правильное и точное распределение вероятностей с помощью детерминированного компьютера. Ситуация здесь отличается от ситуации в «обычных» алгоритмических условиях, где можно использовать различные методы дерандомизации, поскольку они в общем случае не несут в себе свойства правдивости. (2) Даже если естественный источник случайности существует, нельзя улучшить качество фактического результата, повторив вычисления несколько раз (используя закон больших чисел). Подобное повторение разрушит правдивость. Таким образом, именно потому, что теоретико-игровые вопросы рассматриваются параллельно с вычислительными, важность детерминизма возрастает.

Открытый вопрос № 3: каков наилучший возможный коэффициент аппроксимации, который детерминированные и правдивые комбинаторные аукционы могут получить за полиномиальное время?