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

В эпоху Интернета, когда компьютеры действуют и взаимодействуют от имени эгоистичных субъектов, связь вышеописанной концепции с алгоритмическим дизайном напрашивается сама собой: предположим, что входные данные для алгоритма хранятся у эгоистичных агентов, которые стремятся максимизировать собственную полезность. Как спроектировать алгоритм таким образом, чтобы агенты решили, что сотрудничество будет в их интересах, и в итоге был получен результат (исход), близкий к оптимальному? Этот подход отличается от классических моделей распределенных вычислений, где агенты либо «хорошие» (то есть послушные), либо «плохие» (то есть неисправные или злонамеренные, в зависимости от контекста). Здесь подобное разделение невозможно. Просто предполагается, что все агенты стремятся достичь максимума полезности. Чтобы проиллюстрировать это, приведем

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