1. Жесткая неаппроксимируемость для графических игр (arXiv)
Автор:Аргириос Делигкас, Джон Фернли, Александрос Холлендер, Фемистоклис Мелиссург
Аннотация: мы даем полную характеристику вычислительной сложности поиска приближенного равновесия в графических играх с двумя действиями. Мы рассматриваем два наиболее хорошо изученных аппроксимационных понятия: ε-равновесия по Нэшу (ε-NE) и ε-равновесия по Нэшу с хорошим носителем (ε-WSNE), где ε ∈ [0,1]. Мы доказываем, что вычисление ε-NE является PPAD-полным для любой константы ε ‹ 1/2, в то время как очень простой алгоритм (а именно, позволяющий всем игрокам равномерно смешивать между своими двумя действиями) дает 1/2-NE. С другой стороны, мы показываем, что вычисление ε-WSNE является PPAD-полным для любой константы ε ‹ 1, в то время как получение 1-WSNE тривиально, поскольку любой профиль стратегии является 1-WSNE. Все наши нижние границы сразу применимы и к графическим играм с более чем двумя действиями на игрока.
2. Расширение теоретико-сложностного анализа манипулятивных атак при групповой идентификации (arXiv)
Автор :Эмиль Юнкер
Выдержка:В задаче идентификации группы нам дается набор людей, и нас просят определить среди них подмножество социально квалифицированных. У каждого человека в наборе есть мнение о том, кого следует считать социально квалифицированным. Существует несколько различных правил, которые можно использовать для определения социально квалифицированного подмножества на основе этих взаимных мнений. При манипулятивной атаке посторонний пытается использовать способ работы используемого правила с целью изменить результат процесса выбора по своему вкусу. В последние годы сложность группового контроля и манипулятивных атак на основе взяточничества в групповой идентификации стала предметом интенсивных исследований. Однако картина далека от полной, и остается много открытых вопросов, связанных с тем, что именно делает те или иные задачи сложными или определенные правила невосприимчивыми к некоторым атакам. Дополняя предыдущие результаты, мы исследуем сложность группового микровзяточничества на так называемых защитных проблемах; то есть случаи, когда все люди из конструктивного целевого набора уже изначально социально квалифицированы. Кроме того, мы изучаем ослабленный вариант группового контроля, исключая отдельных лиц для правил согласия, правила консенсуса-начала-уважения и либерального правила-начала-уважения. Основываясь на существующей литературе, мы также формализуем три новых социальных правила типа итеративного консенсуса и обеспечиваем комплексный теоретико-сложный анализ проблем группового контроля и взяточничества для этих правил.
3. Pure-Circuit: сильная неаппроксимируемость для PPAD(arXiv)
Автор:Аргириос Делигкас, Джон Фернли, Александрос Холлендер, Фемистоклис Мелиссург
Аннотация:Современные современные методы демонстрации неаппроксимируемости в PPAD возникают из проблемы ε-обобщенной схемы (ε-GCircuit). Рубинштейн (2018) показал, что существует небольшая неизвестная константа ε, для которой ε-GCircuit является PPAD-сложной, а последующая работа показала результаты сложности для других задач в PPAD с использованием ε-GCircuit в качестве промежуточной задачи. Мы вводим Pure-Circuit. , новая промежуточная задача для PPAD, которую можно рассматривать как ε-GCircuit, доведенную до предела при ε → 1, и мы показываем, что задача является PPAD-полной. Затем мы доказываем, что ε-GCircuit является PPAD-трудным для всех ε ‹ 0,1 с помощью редукции из Pure-Circuit, и, таким образом, усиливаем всю предыдущую работу, в которой GCircuit использовался в качестве промежуточной задачи от экзистенциально-константного режима к режиму с большими константами . Мы показываем, что более сильные результаты неприближения могут быть получены путем редукции непосредственно из Pure-Circuit. В частности, мы доказываем результаты о точной неаппроксимируемости для вычисления ε-хорошо поддерживаемых равновесий по Нэшу в полиматричных играх с двумя действиями, а также для нахождения приближенных равновесий в пороговых играх.
