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

Date: 2006-05-03 05:29 pm (UTC)
From: [identity profile] ex-ex-annut.livejournal.com
теория игр активно еще применяют в распределенных вычислениях в некоторых направлениях p2p где она позволяет формализовать проблемы оптимального data placement (где есть несколько опт функций)

Date: 2006-05-03 05:34 pm (UTC)
From: [identity profile] ded-maxim.livejournal.com
Ага, спасибо. Но в данном случае меня заинтересовал тот факт, что модель Халперна и коллег учитывает не только рационально мотивированные попытки "обмануть" алгоритм, но и сбои в результате нестандартного поведения агентов. Т.е. мы имеем дело не с простым применением теории игр к распр. выч., но с нетривиальным их синтезом.

Date: 2006-05-03 05:54 pm (UTC)
From: [identity profile] ex-ex-annut.livejournal.com
Очень интересно
А что за игры..это как-то близко к Request-Answer Games разработанных Видгерсоном, Карпом, и Бородиным для анализа онлайновых алгоритмов -- они очень удобны для анализа различных adversary моделей в пейджинговых или распределение нагрузки задачах. Наверное, сбои можно представить как рандомизированного "врага".

Date: 2006-05-03 07:23 pm (UTC)
From: [identity profile] ded-maxim.livejournal.com
Насколько я понял из доклада (а статьи на сайтах авторов нет, но она, по словам Халперна, принята на PODC 2006), у каждого агента есть функция полезности и две цели: (1) узнать секрет (значение некоторой функции) и (2) постараться сделать так, чтобы секрет стал известен как можно меньшему числу других агентов. Затем ищется равновесие по Нэшу. Используя multiparty computation (результаты Вигдерсона и др.) и рандомизованную симуляцию доверенного арбитра, доказывается существование равновесных стратегий при определенных ограничениях на количество потенциальных обманщиков и потенциальных "странных" (иррациональных) агентов.

Date: 2006-05-03 07:18 pm (UTC)
From: [identity profile] ex-ex-riser.livejournal.com
напомнает МОЗГ.

Date: 2006-05-03 07:24 pm (UTC)
From: [identity profile] ded-maxim.livejournal.com
Что такое МОЗГ?

Date: 2006-05-10 04:32 pm (UTC)

Profile

ded_maxim: (Default)
ded_maxim

December 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
2425 2627282930
31      

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 27th, 2025 11:13 pm
Powered by Dreamwidth Studios