теория игр, распределенные вычисления, обмен секретами

[ded_maxim]

Позавчера к нам приезжал с докладом Джозеф Халперн. Доклад был на тему распределенных аварийно-устойчивых алгоритмов для обмена секретами. Это очень интересно -- объединяя теорию игр с теорией распределенных вычислений, мы можем моделировать ситуации, в которых большинство агентов рационально и стремится максимизировать полезность, но некоторое число агентов "иррационально" (например, их функции полезности неизвестны, или у них сбоят компьютеры etc.). Теория игр прекрасно моделирует стратегические ситуации, но игнорирует аварийно-устойчивость, теория распределенных вычислений прекрасно моделирует аварийно-устойчивые системы, но игнорирует стратегические соображения. Синтез этих двух подходов был бы крайне плодотворен не только в криптографическом контексте, но и в контексте искусственного интеллекта, а также в экономике (позволяя в какой-то степени учитывать несравнимость субъективных предпочтений).

Comments

[ex-ex-annut.livejournal.com]

теория игр активно еще применяют в распределенных вычислениях в некоторых направлениях p2p где она позволяет формализовать проблемы оптимального data placement (где есть несколько опт функций)

[ded-maxim.livejournal.com]

Ага, спасибо. Но в данном случае меня заинтересовал тот факт, что модель Халперна и коллег учитывает не только рационально мотивированные попытки "обмануть" алгоритм, но и сбои в результате нестандартного поведения агентов. Т.е. мы имеем дело не с простым применением теории игр к распр. выч., но с нетривиальным их синтезом.

[ex-ex-annut.livejournal.com]

Очень интересно
А что за игры..это как-то близко к Request-Answer Games разработанных Видгерсоном, Карпом, и Бородиным для анализа онлайновых алгоритмов -- они очень удобны для анализа различных adversary моделей в пейджинговых или распределение нагрузки задачах. Наверное, сбои можно представить как рандомизированного "врага".

[ded-maxim.livejournal.com]

Насколько я понял из доклада (а статьи на сайтах авторов нет, но она, по словам Халперна, принята на PODC 2006), у каждого агента есть функция полезности и две цели: (1) узнать секрет (значение некоторой функции) и (2) постараться сделать так, чтобы секрет стал известен как можно меньшему числу других агентов. Затем ищется равновесие по Нэшу. Используя multiparty computation (результаты Вигдерсона и др.) и рандомизованную симуляцию доверенного арбитра, доказывается существование равновесных стратегий при определенных ограничениях на количество потенциальных обманщиков и потенциальных "странных" (иррациональных) агентов.

[ex-ex-riser.livejournal.com]

напомнает МОЗГ.

[ded-maxim.livejournal.com]

Что такое МОЗГ?

[ex-ex-annut.livejournal.com]

??