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

Пусть имеется взвешенный граф. Цель заключается в том, чтобы найти кратчайший путь (с учетом весов ребер) между заданными исходной и целевой вершинами. Каждое ребро контролируется эгоистичным субъектом, а вес ребра, <math>w_e</math>, представляет собой частную информацию данного ребра. Если ребро выбрано алгоритмом для включения в кратчайший путь, оно понесет затраты, равные его весу со знаком минус (затраты на коммуникацию). Платежи ребрам разрешены, и общая полезность ребра, входящего в кратчайший путь и получающего платеж <math>p_e</math>, предполагается равной <math>u_e = p_e - w_e</math>. Обратите внимание, что ''кратчайший путь находится с учетом истинных весов агентов, хотя разработчику они не известны''.

Хотя этот пример написан на алгоритмическом языке, на самом деле это задача о дизайне механизмов, а решение, ставшее классическим, было предложено в 70-х годах прошлого века. Далее изложение будет организовано следующим образом: вначале дается абстрактная формулировка для таких задач, описывается классическое решение из области экономики, обсуждаются его преимущества и недостатки для алгоритмических целей. Затем в следующем разделе описываются новые результаты, которые дает алгоритмический дизайн механизмов.

''Функция социального выбора'' <math>f: V \to A</math> назначает социально желательную альтернативу любому заданному профилю стоимостей игроков. Это служит параллелью понятию алгоритма. ''Механизм'' представляет собой кортеж <math>M = (f, p_1, ..., p_n)</math> где f – функция социального выбора, а <math>p_i: V \to \mathfrak{R}</math> (для i = 1, ..., n) - цена, взимаемая с игрока i. Интерпретация заключается в том, что специалист по социальному планированию просит игроков раскрыть свои истинные оценки, выбирает альтернативу в соответствии с функцией f, как если бы игроки действительно действовали правдиво, и, кроме того, вознаграждает и наказывает игроков ценами. Эти цены должны порождать «правдивость» в следующем сильном смысле: независимо от того, что заявляют другие игроки, в интересах игрока i всегда раскрыть свою истинную оценку, поскольку это максимизирует его полезность. Формально это можно изложить следующим образом: