Проектирование распределенного алгоритмического механизма
Проектирование распределенных алгоритмических механизмов (DAMD) является расширением проектирования алгоритмических механизмов .
DAMD отличается от конструкции алгоритмического механизма , поскольку алгоритм вычисляется распределенным образом, а не центральным органом. Это значительно сокращает время вычислений , поскольку нагрузка распределяется между всеми агентами в сети .
Одним из основных препятствий в DAMD является обеспечение раскрытия агентами истинных затрат или предпочтений, связанных с данным сценарием. Часто эти агенты предпочитают лгать, чтобы повысить свою полезность .DAMD полон новых проблем, поскольку больше нельзя предполагать послушную сетевую и инфраструктуру механизмов, в которой рациональные игроки контролируют пути сообщений и вычисления механизмов.
игровая Теоретико - модель
Теория игр и распределенные вычисления имеют дело с системой со многими агентами, в которой агенты могут преследовать разные цели. Однако у них разные фокусы. Например, одна из задач распределенных вычислений — доказать правильность алгоритмов, допускающих неисправные агенты и агенты, выполняющие действия одновременно. С другой стороны, в теории игр основное внимание уделяется разработке стратегии, которая приведет нас к равновесию в системе. [1]
Равновесие Нэша [ править ]
Равновесие Нэша — наиболее часто используемое понятие равновесия в теории игр. Однако равновесие Нэша не касается ошибочного или неожиданного поведения. Протокол, достигающий равновесия Нэша, гарантированно будет корректно выполняться перед лицом рациональных агентов, при этом ни один агент не сможет повысить свою полезность, отклонившись от протокола. [2]
Предпочтение решения [ править ]
Здесь нет доверенного центра, как в AMD . Таким образом, механизмы должны быть реализованы самими агентами. Предположение о предпочтительности решения требует, чтобы каждый агент предпочитал любой результат отсутствию результата вообще: таким образом, у агентов нет стимула не соглашаться с результатом или вызывать сбой алгоритма. Другими словами, как отмечают Afek et al. сказал: «Агенты не смогут получить выгоду, если алгоритм даст сбой». [3] В результате, хотя у агентов есть предпочтения, у них нет стимула не выполнить алгоритм.
Правдивость [ править ]
Механизм считается правдивым, если агенты ничего не получают, лгая о их ценности или ценности других агентов.Хорошим примером может служить алгоритм выбора лидера , который выбирает вычислительный сервер в сети. Алгоритм определяет, что агенты должны передать друг другу свою общую вычислительную мощность, после чего самый мощный агент выбирается в качестве лидера для выполнения задачи. В этом алгоритме агенты могут лгать о своей истинной вычислительной мощности, поскольку им потенциально грозит опасность выполнения заданий с интенсивным использованием ЦП, что снизит их мощность для выполнения локальных заданий. Это можно преодолеть с помощью правдивых механизмов, которые без какого-либо априорного знания существующих данных и входных данных каждого агента заставляют каждого агента правдиво отвечать на запросы. [4]
Хорошо известным правдивым механизмом в теории игр является аукцион Викри .
вычислений Классические распределенных задачи
лидера (полностью связанная сеть, синхронный случай ) Выборы
Выборы лидеров — фундаментальная проблема распределенных вычислений, и существует множество протоколов для решения этой проблемы. Предполагается, что системные агенты рациональны и поэтому предпочитают иметь лидера, чем не иметь его. Агенты также могут иметь разные предпочтения относительно того, кто станет лидером (агент может предпочесть, чтобы лидером стал он сам). Стандартные протоколы могут выбирать лидеров на основе наименьшего или наибольшего идентификатора системных агентов. Однако, поскольку у агентов есть стимул лгать о своем идентификаторе, чтобы повысить свою полезность, такие протоколы становятся бесполезными в условиях разработки алгоритмических механизмов.
Протокол выборов лидера в присутствии рациональных агентов был предложен Иттаем и др.:
- В первом раунде каждый агент i отправляет всем свой идентификатор;
- На втором этапе агент i отправляет друг другу агенту j набор полученных им идентификаторов (включая свои собственные). Если наборы, полученные агентом i, не все идентичны или если я не получил идентификатор от какого-либо агента, то я устанавливаю его вывод в значение Null, и выбор лидера завершается неудачно. В противном случае пусть n будет мощностью набора идентификаторов.
- Агент i выбирает случайное число N i из {0,..., n−1} и отправляет его всем остальным агентам.
- Затем каждый агент i вычисляет Σ н
i=1 N i (mod n), а затем выбирает агента с N-м наибольшим идентификатором в наборе в качестве лидера. (Если какой-то агент j не отправляет случайное число, то я устанавливает его вывод равным нулю.)
Этот протокол правильно выбирает лидера при достижении равновесия и является правдивым, поскольку ни один агент не может получить выгоду, солгав о своих входных данных. [5]
См. также [ править ]
- Алгоритмическое проектирование механизмов
- Конструкция механизма
- Теория игр
- Распределенные вычисления
Ссылки [ править ]
- ^ Халперн, Джозеф Ю. (2008). «Информатика и теория игр: краткий обзор» . Новый экономический словарь Пэлгрейва . дои : 10.1057/978-1-349-95121-5_2133-1 .
- ^ Мартин, Осборн; Рубинштейн, Ариэль (1994). Курс теории игр . Пресс-центр МТИ.
- ^ Афек, Иегуда ; Гинзберг, Ионатан; Фейбиш, Шир Ландау; Сулами, Моше (2014). «Строительные блоки распределенных вычислений для рациональных агентов». Материалы симпозиума ACM 2014 года по принципам распределенных вычислений . стр. 406–415. дои : 10.1145/2611462.2611481 . ISBN 9781450329446 . S2CID 2048291 .
- ^ Шнейдман, Джеффри; Паркс, Дэвид (2004). «Достоверность спецификации в сетях с рациональными узлами» . Материалы двадцать третьего ежегодного симпозиума ACM по принципам распределенных вычислений . п. 88. дои : 10.1145/1011767.1011781 . ISBN 1581138024 . S2CID 5518144 .
- ^ Авраам, Иттай; Долев, Дэнни (2013). «Распределенные протоколы для выборов лидера: теоретико-игровая перспектива». ДИСК : 61–75.