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

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

Как выбрать путь и платежи, предполагая, что каждое ребро будет действовать так, чтобы максимизировать свою полезность? Один из вариантов заключается в том, чтобы полностью игнорировать стратегический аспект, попросить ребра просто сообщить их веса и вычислить кратчайший путь. Однако в этом случае ребро не хочет быть выбранным и поэтому предпочтет сообщить очень большой вес (намного больше своего истинного веса), чтобы уменьшить шансы оказаться выбранным. Другим вариантом является выплата каждому выбранному ребру заявленного им веса или заявленного веса с небольшим фиксированным «бонусом». Однако в этом случае все ребра будут сообщать меньшие веса, поскольку быть выбранным будет означать положительное приобретение.

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