Построение распределенного алгоритмического механизма - Distributed algorithmic mechanism design

Построение распределенного алгоритмического механизма (DAMD) является расширением алгоритмический механизм проектирования.

DAMD отличается от Разработка алгоритмического механизма так как алгоритм вычисляется распределенным образом, а не центральным органом. Это значительно улучшает время вычисления поскольку бремя делят все агенты в пределах сеть.

Одним из основных препятствий в DAMD является обеспечение того, чтобы агенты выявить истинные затраты или предпочтения связанные с данным сценарием. Часто эти агенты предпочел бы солгать, чтобы улучшить свои полезность.DAMD полон новых проблем, поскольку больше нельзя предполагать послушную сетевую и механическую инфраструктуру, в которой рациональные игроки управляют путями сообщений и вычислением механизмов.

Теоретико-игровая модель

Теория игры и распределенных вычислений оба имеют дело с системой со многими агентами, в которой агенты могут преследовать разные цели. Однако у них разные акценты. Например, одна из задач распределенных вычислений - доказать правильность алгоритмов, допускающих одновременное выполнение неисправных агентов и агентов. С другой стороны, в теории игр основное внимание уделяется разработке стратегии, которая приводит нас к равновесию в системе.[1]

равновесие по Нэшу

равновесие по Нэшу - это наиболее часто используемое понятие равновесия в теории игр. Однако равновесие по Нэшу не имеет дело с ошибочным или неожиданным поведением. Протокол, который достигает равновесия по Нэшу, гарантированно работает правильно перед лицом рациональных агентов, и ни один агент не может улучшить свою полезность, отклонившись от протокола.[2]

Предпочтение решения

Нет доверенного центра, как в AMD. Таким образом, механизмы должны реализовываться самими агентами. Предположение о предпочтении решения требует, чтобы каждый агент предпочитал любой результат отсутствию результата: таким образом, у агентов нет стимула не соглашаться по поводу результата или вызывать сбой алгоритма. Другими словами, как Afek et al. сказал: «агенты не могут выиграть, если алгоритм не работает».[3] В результате, хотя у агентов есть предпочтения, у них нет стимула отказывать алгоритму.

Правдивость

Механизм считается правдивым, если агенты ничего не получают, лгая о своих ценностях или ценностях других агентов. Хорошим примером может служить выборы лидера алгоритм, выбирающий вычислительный сервер в сети. Алгоритм определяет, что агенты должны передавать друг другу всю свою вычислительную мощность, после чего самый мощный агент выбирается в качестве лидера для выполнения задачи. В этом алгоритме агенты могут лгать о своей истинной вычислительной мощности, потому что им потенциально грозит опасность выполнения задач с интенсивным использованием ЦП, что снизит их мощность для выполнения локальных задач. Это можно преодолеть с помощью правдивых механизмов, которые без какого-либо априорного знания существующих данных и входных данных каждого агента, заставляют каждого агента правдиво отвечать на запросы.[4]

Хорошо известным правдивым механизмом в теории игр является Викри аукцион.

Классические задачи распределенных вычислений

Выбор лидера (полностью подключенная сеть, синхронный случай)

Выборы лидера является фундаментальной проблемой распределенных вычислений, и существует множество протоколов для решения этой проблемы. Системные агенты считаются рациональными и поэтому предпочитают иметь лидера, а не его отсутствие. У агентов также могут быть разные предпочтения относительно того, кто становится лидером (агент может предпочесть, чтобы он сам стал лидером). Стандартные протоколы могут выбирать лидеров на основе самого низкого или самого высокого идентификатора системных агентов. Однако, поскольку у агентов есть стимул лгать о своих идентификаторах, чтобы улучшить свою полезность, такие протоколы оказываются бесполезными при разработке алгоритмических механизмов.
Протокол для избрания лидера в присутствии рациональных агентов был введен Иттаи и др .:

  • В первом раунде каждый агент i отправляет всем свой идентификатор;
  • В раунде 2 агент i отправляет друг другу агенту j набор полученных им идентификаторов (включая свой собственный). Если наборы, полученные агентом i, не идентичны, или если i не получает идентификатор от какого-либо агента, то i устанавливает свой вывод равным Null, и выбор лидера не выполняется. В противном случае, пусть n будет мощностью набора идентификаторов.
  • Агент i выбирает случайное число Nя в {0, ..., n-1} и отправляет его всем остальным агентам.
  • Затем каждый агент i вычисляет Σя = 1п Nя (mod n), а затем берет агента с N-м наивысшим идентификатором в наборе в качестве лидера. (Если какой-то агент j не отправляет i случайное число, тогда i устанавливает его вывод равным Null.)

Этот протокол правильно выбирает лидера при достижении равновесия и является правдивым, поскольку ни один агент не может получить выгоду, лгая о своем вводе.[5]

Смотрите также

использованная литература

  1. ^ Халперн, Джозеф Ю. (2008). «Информатика и теория игр: краткий обзор». Новый экономический словарь Пэлгрейва.
  2. ^ Мартин, Осборн; Рубинштейн, Ариэль (1994). Курс теории игр. Пресса MIT.
  3. ^ Афек, Иегуда; Гинзберг, Ехонатан; Файбиш, Шир Ландау; Сулами, Моше (2014). «Строительные блоки распределенных вычислений для рациональных агентов». PODC '14 Материалы симпозиума ACM 2014 г. по принципам распределенных вычислений.
  4. ^ Хнейдман, Джеффри; Паркс, Дэвид (2004). «Точность спецификации в сетях с рациональными узлами». двадцать третий ежегодный симпозиум ACM по принципам распределенных вычислений: PODC.
  5. ^ Авраам, Иттай; Долев, Дэнни (2013). «Распределенные протоколы для избрания лидера: теоретико-игровая перспектива». ДИСК: 61–75.

внешние ссылки

  • [1] Дизайн распределенного алгоритмического механизма: последние результаты и будущие направления
  • [2] Разработка распределенных алгоритмических механизмов и сетевая безопасность
  • [3] Распределение услуг в эгоистичных мобильных одноранговых сетях с использованием аукциона Викри