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

[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B7%D0%B0%D0%B9%D0%BD_%D0%BC%D0%B5%D1%85%D0%B0%D0%BD%D0%B8%D0%B7%D0%BC%D0%BE%D0%B2 Дизайн механизмов] представляет собой раздел экономики и теории игр, изучающий построение социальных механизмов в присутствии эгоистичных агентов. Природа агентов определяет основной контраст между специалистом по социальному планированию, который стремится достичь социально желательного результата, и агентами, которые заботятся только о своей личной выгоде. Основной вопрос заключается в том, как стимулировать агентов к сотрудничеству, чтобы достичь социально желательных результатов.

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