Разработка распределенного алгоритмического механизма
-
Основы проектирования распределенных алгоритмических механизмов (DAMD)
- DAMD отличается от разработки алгоритмических механизмов тем, что алгоритм вычисляется распределенным образом.
- Это сокращает время вычислений, распределяя нагрузку между агентами в сети.
-
Проблемы и задачи DAMD
- Обеспечение того, чтобы агенты раскрывали истинные затраты или предпочтения.
- Агенты могут лгать для повышения своей полезности.
- DAMD требует новых подходов к сетевой инфраструктуре и механизмам, где рациональные игроки управляют коммуникациями и вычислениями.
-
Теоретико-игровая модель
- Теория игр и распределенные вычисления рассматривают системы с множеством агентов, преследующих разные цели.
- Равновесие Нэша является ключевым понятием в теории игр, но не связано с ошибками или неожиданным поведением.
-
Предпочтение решения и правдивость
- В DAMD нет надежного центра, поэтому механизмы должны быть реализованы агентами.
- Предпочтение решения требует, чтобы каждый агент предпочитал любой результат отсутствию результата.
- Механизм считается правдивым, если агенты не выигрывают от лжи о его ценности.
-
Классические задачи распределенных вычислений
- Проблема выборов лидера является фундаментальной в распределенных вычислениях.
- Существуют протоколы для выбора лидера, но они становятся неэффективными из-за стремления агентов лгать.
- Иттаи и соавторы предложили протокол выборов лидера, который является правдивым и правильно выбирает лидера при равновесии.