Совершенная Имплементация Механизмов с Медиатором в Нормальной Форме Измалков Лепински Микали Cанкт-Петербург Декабрь 2009

Мотивация Во многих взаимодействиях присутствует медиатор: –Аукционер (продавец) –Принципал (менеджер, директор) –Правительство Теоретические решения с медиаторами: –Принцип Откровенности (The Revelation Principle) –Оптимальные аукционы/ контракты/ налоги /торговля –Теория Имплементации Пробел между теорией и реальностью (практикой): –медиаторам нужно доверять; на практике тяжело найти; –реалистичные механизмы требуются –меньше доверия === меньше сохранности частной информации Мы: Пробела нет (!) любой частный медиатор имплементируем.

Mediation The activity of mediation appeared in very ancient times. Historians presume early cases in Phoenician commerce (but suppose its use in Babylon, too). The practice developed in Ancient Greece (the non-marital mediator as a proxenetas), then in Roman civilization, Roman law (from Justinian's Digest of CE) recognized mediation. The Romans called mediators by a variety of names, including internuncius, medium, intercessor, philantropus, interpolator, conciliator, interlocutor, interpres, and finally mediator. The Middle Ages regarded mediation differently, sometimes forbidding the practice or restricting its use to centralized authorities. Some cultures regarded the mediator as a sacred figure, worthy of particular respect; and the role partly overlapped with that of traditional wise men or tribal chief. Confidentiality lies at the heart of mediation. The mediator must inform the parties that communications between them during the intake discussions and the mediation process are to be private and confidential. It is imperative for parties to trust the process. Very few mediations will ever succeed unless the parties can communicate fully and openly without fear of compromising their case before the courts. source: mediation Wikipedia (17pages)

Пример: Принцип Откровенности Можно ли достичь желаемого результата? если ДА, то можно в прямой игре с медиатором Слабый ответ: –множественность равновесий (*теория имплементации) –требуется знающий и доверяемый центр –для естественных центров: аукционист/ принципал/ монополист/ правительство возникают проблемы коммитмента и защиты/ сохранности информации (privacy) –динамические проблемы и Информированного Принципала проблемы Непрямые игры тяжело искать, и они часто сложны (напр. механизмы Дасгупты и Маскина). В лучшем случае только примерная цель может быть достигнута? А в худшем?

Закрытый Аукцион 2й цены В идеале: Игроки делают ставки. Максимальная ставка выигрывает, платит 2й по величине бид. –Эффективен в доминантных стратегиях: оптимально называть настоящую предельную ценность; макс. ценность выигрывает. –3 игрока: ставки: 1000, 4000, 5000 итог: 3й побеждает, цена 4000 НО! Как этот результат получается из ставок на практике? Публичная: аукционист публично открывает конверты, все видят кто выиграл и по какой цене. Имплементации: Частная: аукционист собирает ставки в конвертах; Секретно открывает конверты; секретно вычисляет результат; аннонсирует его.

Конфиденциальность и Доверие Конфиденциальность: люди (могут) беспокоится о том, что их сообщения/типы станут известны. Доверие: медиатору должны доверять в том, что он действует как предполагается; доверяемых медиаторов нужно поискать обычно: доверие предполагается, конфиденциальность игнорируется Публичная Имплементация: Не требуется доверие, Нет конфиденциальности Частная Имплементация: Полная конфиденциальность, Полное доверие Эффективность идеального механизма утеряна!?

Механизмы в Нормальной Форме (с медиатором) Mеханизм: ( N, M, g, Y ) –Nигроки –M действия (сообщения); M i для игрока i –Y результаты –g результирующая функция g : M 1 ×... × M n Y Айкцион 2й цены: сообщения -- биды; макс. бид побеждает, платит 2й по величине бид

Механизмы в Нормальной Форме (с медиатором) Игра = Механизм + Контекст Контекст: N, Y, T, p, {u i } –T пространство типов; T i для игрока i –pверы –u i предпочтения IPV контекст: t i = V i ~ F i [0,B] незав. от t -i Взаимозависимые V : V i = V i ( t 1, …, t n )

Mедиаторы 1.Получают сообщения 2.Вычисляют результат 3.Объявляют результат Ex 0 : дизайнер механизмов, аукционист (продавец), принципал, бюрократ, … Все это не происходит само по себе, Кто-то должен это делать !!! Mедиаторы/ Mеханизмы должны быть имплементированы

К теории конкретной имплементации Цель: имплементация идеального механизма (доверяемый частный медитор) конкретным механизмом. Основные требования: –Отсутствие доверия: публичная медиация === только публичные действия –Полная Конфиденциальность: такая же информация как и в изначальной игре –Одинаковые решения у получающихся игр - Явные и простые физические предположения: что игроки/ медиатор могут делать - Операционная эффективность: легко найти и просто играть Публичный медиатор: Нет личной информации; нет выбора !

Неподходящая имплементация Аукцион 2й цены, 2 игрока, 20-битные биды. См. Также Krishna (07) и Ben-Porath (98) 1.Приготовление таблицы конвертов: –для каждой пары (b 1i,b 2k ) создание конверта, содержащего y = g (b 1i,b 2k ). 2.Игроки: –игрок i секретно переставляет строки –игрок k секретно переставляет столбцы 3.Открывание конверта в правом-верхнем углу. Проблемы: размер игры; неявные действия/ дополнительные угрозы конфиденциальности.

Стратегическая Эквивалентность Что хотим? –Сохранить ВСЕ изначальные равновесия –НЕ создать новых –Для ВСЕХ концепсий равновесий –Для ВСЕХ контекстов Мы требуем результат-сохраняющий изоморфизм нормальных форм изначального и имплементирующего механизмов (*)

… … … … trust … Стратегическая Эквивалентность

… … … … trust Информационная Эквивалентность m1m1 m2m2 m4m4 m3m3 Y EI: EP: …

Действия: 3 Физические предположения / публичные действия конверты супер-конверты перемешивающая урна

Основной Результат Для любого конечного механизма с медиатором мы конструируем эквивалентный механизм без медиатора (Ballot-Box mechanism with public mediator)

Основной Результат 2 ОР1 достигается универсально и вычислительно эффективно ILM Mех-зм с мед. Б-Б Mех-зм любой экв.

Результаты Теорема 1: Для любого стандартного Н-Ф механизма M, существует Б-Б механизм B, совершенно имплементирующий M. Теорема 2: Существует линейный-по-времени алгоритм C, который, имея на входе стандартный Н-Ф механизм M, выдает линейный-по-времени Б-Б механизм B, совершенно имплементирующий M.

Точка Отчета: SFE (Надежное вычисление функции) Криптография вкратце: (2 Слайда)

Надежное вычисление функции F GMW 87 x1x1 x4x4 x3x3 x2x2 x1x1 x4x4 x3x3 x2x2 Y F ( x 1, x 2, x 3, x 4 )= Y : x 1 x 2 x 1 x 2 Y Те же Точность Инфо trust (Y86) Не подходит для Дизайна Механизмов !!! Y

Мотивы Y1Y1 Y2Y2 YnYn НВФ Теория Игр Честность Рациональность ( 1 игрока тупо следуют протоколу) Сигнализирование... (Игроки сами за себя) Нет Сигналов... $ $ $

Рациональное НВФ 1.Та же Надежность 2.Та же Инфо 3.Те же Мотивы ! $ $ $ x1x1 x4x4 x3x3 x2x2 x1x1 x4x4 x3x3 x2x2 trust Y Y N F мотивов коалиций

Коррелированное Равновесие (Aumann 74) Могут ли игроки достичь больше, чем NASH? ЖдиИнвестируй Жди 0,07,2 Инвестируй 2,76,6 Могут, с помощью медиатора!

Медиатор секретно выбирает ячейку с p=1/3 секретно посылает рекоммендованное действие Как имплементировать медиатора? Пре-игровые переговоры: Barany, Forges, Ben-Porath, Gerardi, Myerson, Aumann, Hart, Krishna, и другие. Могут ли игроки достичь больше, чем NASH? ЖдиИнвестируй Жди 0,07,2 Инвестируй 2,76,6 Могут, с помощью медиатора! Коррелированное Равновесие (Aumann 74)

КАК? CÓMO? WIE? COME? HOW? COMMENT? ΠΩΣ?

(!!!): Канал коммуникации и кодировка 1. Кодировка 2. Вычисление 3. Объявление (вход. зн.)(коммуникация)(результат) Б-Б Сети, GMW (87) Кодировка ! Общий взгяд на конструкцию Данные и операции над ними представлены пермутациями 5 элементов

g … m1m1 … m2m2 … mnmn Y D $ …

данные пермутации S 5 конверты 1. Кодировка b = 1 0 I 1 (1, 2, 5, 3, 4) Вход. зн.: Для каждого бита создаются 5 конвертов

[ Left Right ] Left [ Left Right ] -1 = Right Пример: [a b] a [a b] -1 = b 2. Вычисление (в S 5 ) = ( a -1 )* a a = (a a a -1 a -1 ) = (a b a -1 b -1 ) = a Биты: 0 I 1 a Вычисление: I a = ( I a I -1 a -1 ) = I =( a a -1 ) =I=I aba -1 b -1 I 6 Констант: [a b][aba -1 b -1 a][a -1 a],,, a, b ¬ 0 = ( I a -1 )* = (a -1 )*= a I = 1 = ( ) = [a b] [a b ] -1 = [aba -1 b -1 a] [aba -1 b -1 a ] -1 [a -1 a][a -1 a] -1 * = 3 Оператора:

2. Вычисление в S 5 (Barrington) Биты: 0 I (1,2,3,4,5) 1 a (1,2,5,4,3) Вычисление : Константы (перестановки):, a, c, d, e I d c c c -1 c -1 d -1 e a -1 e

2. Вычисление p p p = I = инверт. дупл. умнож. случ.бит инверт.

2. Вычисление инверт. дупл. умн. сл.бит инверт. p p r p = r = p -1 r -1 = (r p) -1 = p -1 =

g … m1m1 … m2m2 … mnmn Y ……… … … …… … ………

Объявление Y = ( ) Частные результаты Aукционы П-А модели Корр. Равнов. …

Итого: Стратегическая Эквивалентность: –Для каждой последовательности битов --- единственный способ подготовить последовательность конвертов –Иначе аборт, соответствующий аборт Информационная Эквивалентность: –Только случайные пермутации наблюдаемы Публичный медиатор: –Нет выбора, ничего не узнает Операционная эффективность/ Универсальность: –Б-Б механизм --- трансляция функции, представленой Булевой логической схемой –Каждая элементарная операция требует конечное число элементарных действий с конвертами

Применения ! ! ! ! ! ! Предлагаем: Контроль информационных потоков Доверяемые медиаторы Публичный коммитмент в теории …. Нет ограничений для Принципа Откровенности: решить с доверяемым медиатором; убрать его.

2. Compute invert clone multiply p p, p p -1 = I = p p -1 p, p I =

p, q pq 2. Compute invert clone multiply p p -1 p -1 = q =

p, q pq 2. Compute invert clone multiply p p -1 r p -1 = r q = (r q) -1 = q -1 r -1 = (q -1 r -1 ) r p -1 q -1 p -1 pq