Вопросы с тегом «gt.game-theory»

10
Уточнения парного приближения для сетевого анализа

При рассмотрении взаимодействий в сетях обычно очень трудно рассчитать динамический анализ , и используются приближения. Аппроксимации среднего поля обычно заканчиваются полным игнорированием структуры сети, и поэтому редко являются хорошим приближением. Популярным приближением является парное...

10
Алгоритмы вычисления равновесия по Нэшу.

Я искал на форуме, чтобы узнать, спрашивался ли об этом раньше, и пока обсуждается теория алгоритмических игр, я не смог найти эту конкретную проблему. Я пытаюсь выяснить, каков самый известный алгоритм для вычисления приближенных (смешанных стратегий) равновесий Нэша в конечной игре с n людьми....

10
Равновесие в игре с остановками

Рассмотрим следующую игру для 2 игроков: Природа случайно выбирает программу Каждый игрок играет число в [0, бесконечность] включительно в ответ на движение природы Возьмите минимум чисел игроков и запустите программу для (до) такого количества шагов (если оба игрока не выбрали бесконечность) Если...

10
Эта игра EXPSPACE-завершена?

Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом А . Первоначально A пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MMMAAAAAAxxx Рассмотрим следующую игру Алисы и Боба. Первоначально...

10
В чем сложность этой игры?

Это обобщение моего предыдущего вопроса . Пусть будет полиномиальный детерминированный машина , которая может задавать вопросы некоторым оракулом . Первоначально пусто, но это можно изменить после игры, которая будет описана ниже. Позвольте x быть некоторой строкой.MMMAAAAAAxИксx Рассмотрим...

10
Проблема выбора ключевого слова на аукционе поискового маркетинга

Во-первых, я до сих пор не уверен, хорошо ли подходит этот вопрос для этого вопроса, поэтому я не буду обижаться, если толпа думает, что это не так ... В поисковом маркетинге несколько проблем интересны. Разработка справедливых (и прибыльных) аукционных механизмов и расчет оптимальных стратегий...

9
Упрощенная версия карточной игры Winner

Я задал эту проблему в MathOverflow , без какого-либо удовлетворительного ответа. Рассмотрим следующую игру для двух игроков, которая является упрощением карточной игры Winner . (Следующая формулировка была взята из комментария Гийома Брунери о MathOverflow.) Есть два игрока A и B. У каждого игрока...

9
Секретарь найма игры

Это расширение классической проблемы секретаря . В игре найма у вас есть набор кандидатов C={c1,…,cN}C={c1,…,cN}\mathcal C=\{c_1,\ldots,c_N\}и приказ о том, насколько квалифицирован каждый работник. Wlog, мы предполагаем, что c1c1c_1 самый опытный, а затем c2c2c_2, так далее. Порядок проведения...

9
Когда делать

Равновесия Нэша вообще неисчислимы. ϵϵ\epsilonРавновесие по Нэшу - это набор стратегий, где, учитывая стратегии противников, каждый игрок получает в течение ϵϵ\epsilonмаксимально возможного ожидаемого вознаграждения. Нахождениеϵϵ\epsilon-Наш равновесия, учитывая ϵϵ\epsilon и игра, это...

9
Понимание механизма проектирования Доказательство

Я боролся с техническими деталями доказательства теории аукциона в этой статье: http://users.eecs.northwestern.edu/~hartline/omd.pdf В частности, теорема 2.5: необходимые и достаточные условия для правдивого механизма. Более конкретно, прямое направление доказательства, приведенное на странице 6....

9
Что такое классификация сложности теории портфеля в финансовой экономике?

Как вы все знаете, из-за финансового кризиса 2008 года продолжаются последствия. Я думал о том, как теория сложности вписывается во все это, когда я понял, что не знаю базовых классов сложности, связанных с финансовой экономикой. Поэтому мой вопрос заключается в том, какова классификация сложности...

9
Принуждение к честному поведению

Как вы можете заставить партию быть честной (подчиняться правилам протокола)? Я видел некоторые механизмы, такие как обязательства, доказательства и т. Д., Но они просто не решают всей проблемы. Мне кажется, что структура дизайна протокола и такие механизмы должны выполнять свою работу. У...

9
Какова сложность этой игры с разделением имущества?

Алиса и Боб делят имущество своего покойного дяди Чарли (конечная коллекция отдельных предметов) в соответствии с его пожеланиями. Сначала А выбирает предмет, затем В, затем А и так далее.XXX У Алисы и Боба есть аддитивные вспомогательные функции , так что, если Алиса заканчивает набором Y \...

9
Ограничение скорости роста цены анархии через концепции равновесия

Мы знаем и любим множество вложенных классов концепций решений: PN: Pure Nash Equilibrium MN: Смешанное равновесие по Нэшу CE: коррелированное равновесие CCE: курс коррелированного равновесия. Отношения между этими наборами: PN⊂MN⊂CE⊂CCEPN⊂MN⊂CE⊂CCEPN \subset MN \subset CE \subset CCE Мы можем...