Проектирование распределенных алгоритмических механизмов (DAMD) является расширением проектирования алгоритмических механизмов .
DAMD отличается от конструкции алгоритмического механизма , поскольку алгоритм вычисляется распределенным образом, а не центральным органом. Это значительно сокращает время вычислений , поскольку нагрузка распределяется между всеми агентами в сети .
Одним из основных препятствий в DAMD является обеспечение раскрытия агентами истинных затрат или предпочтений , связанных с данным сценарием. Часто эти агенты предпочитают лгать, чтобы повысить свою полезность . DAMD полон новых проблем, поскольку больше нельзя предполагать послушную сетевую и инфраструктуру механизмов, в которой рациональные игроки контролируют пути сообщений и вычисления механизмов.
Теория игр и распределенные вычисления имеют дело с системой со многими агентами, в которой агенты могут преследовать разные цели. Однако у них разные фокусы. Например, одна из задач распределенных вычислений — доказать правильность алгоритмов, которые допускают неисправные агенты и агенты, выполняющие действия одновременно. С другой стороны, в теории игр основное внимание уделяется разработке стратегии, которая приведет нас к равновесию в системе. [1]
Равновесие Нэша — наиболее часто используемое понятие равновесия в теории игр. Однако равновесие Нэша не касается ошибочного или неожиданного поведения. Протокол, достигающий равновесия Нэша, гарантированно будет корректно выполняться перед лицом рациональных агентов, при этом ни один агент не сможет повысить свою полезность, отклонившись от протокола. [2]
Здесь нет доверенного центра, как в AMD . Таким образом, механизмы должны быть реализованы самими агентами. Предположение о предпочтительности решения требует, чтобы каждый агент предпочитал любой результат отсутствию результата вообще: таким образом, у агентов нет стимула не соглашаться с результатом или вызывать сбой алгоритма. Другими словами, как отмечают Afek et al. сказал: «Агенты не смогут получить выгоду, если алгоритм даст сбой». [3] В результате, хотя у агентов есть предпочтения, у них нет стимула не выполнить алгоритм.
Механизм считается правдивым, если агенты ничего не получают, лгая о своих ценностях или ценностях других агентов. Хорошим примером может служить алгоритм выбора лидера , который выбирает вычислительный сервер в сети. Алгоритм определяет, что агенты должны передать друг другу свою общую вычислительную мощность, после чего самый мощный агент выбирается в качестве лидера для выполнения задачи. В этом алгоритме агенты могут лгать о своей истинной вычислительной мощности, поскольку им потенциально грозит опасность выполнения заданий, требующих интенсивной загрузки ЦП, что снизит их мощность для выполнения локальных заданий. Это можно преодолеть с помощью правдивых механизмов, которые без какого-либо априорного знания существующих данных и входных данных каждого агента заставляют каждого агента правдиво отвечать на запросы. [4]
Хорошо известным правдивым механизмом в теории игр является аукцион Викри .
Выборы лидеров — фундаментальная проблема распределенных вычислений, и существует множество протоколов для решения этой проблемы. Предполагается, что системные агенты рациональны и поэтому предпочитают иметь лидера, чем не иметь его. Агенты также могут иметь разные предпочтения относительно того, кто станет лидером (агент может предпочесть, чтобы лидером стал он сам). Стандартные протоколы могут выбирать лидеров на основе наименьшего или наибольшего идентификатора системных агентов. Однако, поскольку у агентов есть стимул лгать о своем идентификаторе, чтобы повысить свою полезность, такие протоколы становятся бесполезными в условиях разработки алгоритмических механизмов.
Протокол выборов лидера в присутствии рациональных агентов был предложен Иттаи и др.:
Этот протокол правильно выбирает лидера при достижении равновесия и является правдивым, поскольку ни один агент не может получить выгоду, солгав о своих входных данных. [5]