Игры с двумя пруверами в один раунд (2P1R) являются важным инструментом для определения приближенности. В частности, параллельное повторение однокруговых игр с двумя проверками дает возможность увеличить размер пропуска в версии решения задачи аппроксимации. См . Обзорный доклад Ран Раза на КХЦ 2010 для обзора предмета.
Параллельное повторение игры обладает удивительным свойством, заключающимся в том, что хотя рандомизированный верификатор работает независимо, два игрока могут играть в игры независимо, чтобы достичь большего успеха, чем независимая игра в каждую игру. Величина успеха ограничена выше теоремой параллельного повторения Raz:
Теорема : существует универсальная константа так что для каждой игры 2P1R со значением и размером ответа значение игры параллельного повторения не больше .G 1 - ε s G п ( 1 - ε с ) Ω ( п / ев )
Вот схема работы по идентификации этой константы :
- Оригинальная статья Raz доказывает .
- Холенштейн улучшил это до .
- Рао показал, что достаточно (и зависимость от снята) для частного случая проекционных игр.лет
- Раз дал стратегию для игры странного цикла, которая показала, что результат Рао является резким для проекционных игр.
По этой работе мы знаем . Мои два вопроса следующие:
Вопрос 1: Есть ли у экспертов в этой области консенсус относительно точного значения ?
Если считается, что , существуют ли конкретные игры, которые не являются проективными, но также и специфически нарушают дополнительные свойства проекционных игр, которые требуются для доказательства Рао.
Вопрос 2: Если , какие интересные игры нарушают стратегию Рао и могут привести к ярким примерам?
Из моего собственного чтения кажется, что наиболее важным свойством проекционных игр, которые использует Рао, является то, что хорошая стратегия параллельного повторения не будет использовать многие из возможных ответов на определенные вопросы. Это как-то связано с местностью проекционных игр.
источник