Теоретический вопрос, связанный с информатикой и теорией игр
Существует часто цитируемое философское обоснование полагать, что P! = NP даже без доказательств. Другие классы сложности имеют доказательства того, что они различны, потому что если нет, то будут «удивительные» последствия (например, крах полиномиальной иерархии). Мой вопрос: на чем основано...
Решение, если количественная логическая формула, такая как ∀ х1∃ х2∀ х3⋯ ∃ хNφ ( х1, х2, … , ХN) ,∀Икс1∃Икс2∀Икс3⋯∃ИксNφ(Икс1,Икс2,...,ИксN),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), всегда оценивается как истина - это классическая PSPACE-полная проблема....
Я был (и до сих пор) действительно заинтересован в ответе на этот вопрос, потому что это интересный вариант сложности игр, который не был решен, поэтому я предложил вознаграждение. Я подумал, что исходный вопрос, скорее всего, слишком сложный, поэтому я опубликовал три связанных вопроса, которые...
В последние несколько месяцев я начал читать лекции о социальном выборе, теореме стрелы и связанных с ней результатах. Прочитав об исходных результатах, я спросил себя о том, что происходит с предпочтениями частичного порядка, ответ в статье Pini et al. : Агрегирование частично упорядоченных...
Это повторение предыдущего вопроса . Рассмотрим следующую беспристрастную идеальную информационную игру между двумя игроками, Алисой и Бобом. Игроки получают перестановку целых чисел от 1 до n. На каждом ходу, если текущая перестановка увеличивается, текущий игрок проигрывает, а другой игрок...
Этот недавний вопрос теории игр заставил меня задуматься (это, конечно, касательно): возможно ли эффективно оптимизировать личную стратегию выбора исследовательских вопросов для работы над теорией игр? Чтобы перейти к формализации вопроса, я сделаю следующие (неофициально заявленные) предположения:...
Мафия - популярная ролевая игра на вечеринках, подробное описание доступно на википедии http://en.wikipedia.org/wiki/Mafia_%28game%29 . В основном это работает следующим образом: В начале каждому из игроков тайно отводится роль, связанная либо с мафией, либо с городом. Каждая роль может иметь...
Я ищу примеры методов доказательства цены границ анархии, которые способны отделить цену анархии от грубого коррелированного равновесия (ограничивающий набор динамики без внешнего сожаления) от цены анархии над коррелированным равновесием (ограничивающий комплектация без своп-сожалений). Известны...
Я использую заглавный термин в очень свободном смысле. Существует значительный объем работ по эволюционной теории игр, включая ее математические основы. Мне порекомендовали «Эволюционные игры и динамика населения», но я еще не углубился в это. Существует также значительный объем работ по теории...
Популярная игра на праздничных вечеринках в Северной Америке - обмен подарками белых слонов . Вкратце (без учета вариаций) это работает следующим образом: Есть людей и упакованных подарков. Игроки заказаны произвольно. В раунде , игрок либоNNnNNnягоiгоi^{\text{th}}яяi выбирает завернутый подарок и...
Какие предположения и основные открытые проблемы являются наиболее важными в алгоритмической теории игр (или теории игр в целом применительно к CS)? Например, разрешение NASH как PPAD-полного, я думаю, было бы самым большим до тех пор, пока оно не было решено. (Добавлено: разрешение отношения PPAD...
Будучи студентом, изучающим информатику, я познакомился с теорией игр, но не видел подробностей по этому вопросу. Я искал в Google и просмотрел несколько книг по теории игр, и они предоставили подтверждение ее использования в информатике. Я начал формальное изучение теории игр с точки зрения...
Мне интересно, существует ли вычислительно ограниченная версия концепции равновесия по Нэшу, что-то вроде следующего. Представьте себе какую-то идеальную информационную игру для двух игроков, в которую играют на доске , и которая сложна в том смысле, что оптимальная игра трудна для ОПЫТА....
Я столкнулся со следующей игрой. Я перенесу это в соответствии с просьбой. Ошибка заключается в посещении кругов, и противник хочет максимально увеличить время своего путешествия. Противник ставит круг на каждом шагу. Жук идет от своей текущей позиции прямо к центру нового круга, затем...
Рассмотрим следующую игру на ориентированном взвешенном графе гGG с чипом в некотором узле. Все узлы гGG отмечены буквой A или B. Есть два игрока Алиса и Боб. Цель Алисы (Боба) - сдвинуть фишку к узлу, обозначенному буквой A (B). Первоначально Алиса и Боб имеют мAmAm_A и мВmBm_B долларов...
Учитывая детерминированную игру с нулевой суммой частичной информации только с конечным числом состояний, чьи возможные результаты [проиграть, сыграть, выиграть] со значениями [-1,0, + 1] соответственно, какова сложность аппроксимации значения такого игра аддитивно в ?ϵϵ\epsilon В частности, я не...
У Конвея очень приятная конструкция из сюрреалистических чисел. Это «числа», которые содержат как действительные числа, так и порядковые числа, полностью упорядочены и имеют все свойства поля (за исключением того, что они образуют не множество, а класс). Смотрите, например, этот PDF или Википедию...
Для полиномиальной задачи локального поиска мы знаем, что должно существовать хотя бы одно решение (локальный оптимум). Тем не менее, может существовать гораздо больше решений, насколько сложно сосчитать количество решений для PLS-полной задачи? Меня особенно интересует проблема решения: есть ли у...
Я начинаю свои исследования теории алгоритмических игр, и кажется, что обычно принимается концепция равновесия с неподвижной точкой на графе. Однако смотрели ли люди на альтернативные концепции равновесия, такие как предельные циклы? Я могу себе представить, что «жесткий» предельный цикл, то есть...
Как упомянул @Marzio, следующая игра называется Generalized Geography . Для графа и начальной вершины игра определяется следующим образом:G = ( V, E)гзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv \in V На каждом ходу (чередуются два игрока), игрок выбирает , и тогда происходит следующее:u ∈ N( v )U∈N(v)u\in N(v)...