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