Выбор темы исследования с использованием теории игр

19

Этот недавний вопрос теории игр заставил меня задуматься (это, конечно, касательно): возможно ли эффективно оптимизировать личную стратегию выбора исследовательских вопросов для работы над теорией игр?

Чтобы перейти к формализации вопроса, я сделаю следующие (неофициально заявленные) предположения:

  • Я также «наслаждаюсь» любой конкретной проблемой, над которой я могу работать (чтобы избежать «мягкого» (и правильного!) Ответа «Делай, что тебе нравится!»).
  • Я могу или не могу быть успешным в поиске ответа на любую проблему, над которой я хочу работать. Для любой данной проблемы у меня есть некоторая оценка вероятности того, насколько хорошо я буду в решении проблемы (потратив на это время).
  • Моя цель - максимизировать свою отдачу при оценке в дальнейшем (подача заявки на работу, подача заявки на пребывание в должности, подача заявки на стипендию и т. Д.), Которая зависит от того, сколько проблем я решаю и насколько важны или трудны проблемы. , У меня нет четкого представления о точных результатах по каждой проблеме, но я могу сделать разумную оценку.
  • Существует слабая обратная связь между проблемой вознаграждения и проблемой сложности. Еще одним утверждением моей цели является «игра» различий (то есть поиск «низко висящих фруктов»).
  • Пример этой общей проблемы определяется списком исследовательских вопросов (возможно, бесконечное число), к которым я твердо прикрепляю (без вычислительных затрат; он приводится в качестве входных данных) оценку ценности вопроса и сложности вопроса. Я играю в эту игру против противника (человека, который оценивает меня); природа решает, учитывая вероятность того, что я решу данную проблему, успешно ли я ее решу после того, как решу попробовать.

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


Вопрос : я предполагаю, что игры такого типа не являются эффективно вычисляемыми. Однако, есть ли алгоритм полиномиального времени, чтобы приблизительно максимизировать мою отдачу? Что насчет PTAS?

Или, альтернативно, есть более точная теоретико-игровая модель для этой проблемы? Если так, то остается тот же вопрос: могу ли я (приблизительно) максимально увеличить свою выплату? Если да, то как?

Даниэль Апон
источник
4
Одна потенциальная проблема с формулировкой этого как игры состоит в том, что ваш противник, человек, который оценивает вас, не обязательно играет против вас. Действительно, часто они оказываются на вашей стороне и хотят видеть вас неудачниками, если вы не выполнили минимальный уровень требований. Другим возможным противником являются все другие исследователи , так как они могут работать (возможно, совместно) над той же проблемой и, таким образом, работают против достижения вами успеха, пытаясь получить результаты раньше, чем вы.
Дэйв Кларк
Для целей этого вопроса (я бы хотел обойти как можно больше обсуждений, так что это хороший вопрос ...), давайте предположим, что человек, оценивающий меня, действительно находится под серьезным давлением, чтобы выбрать одного и только одного лучшего человека для особая награда, поэтому они состязательны. Кроме того, давайте предположим, что «что-нибудь действительно оригинальное будет просто оригинальным», поэтому другие исследователи не представляют серьезной проблемы. Я (конечно!) Лично заинтересован в других возможностях, но я думаю, что если оставить его открытым, это вызовет плохие ответы. :)
Даниэль Апон
Один из факторов в проблеме, который может быть достоин другой модели: оценка вероятности успеха / структуры вознаграждения по каждой проблеме, над которой я предпочитаю работать.
Даниэль Апон
2
RTriPi(t)t
2
Конечно, в реальной жизни каждый вопрос, на который вы отвечаете, открывает больше вопросов, которые вы не можете предсказать заранее, но которые, возможно, проще и / или стоят больше, чем набор вопросов, с которого вы начали, но как только вы начинаете создавать деревья стратегий таким образом, шанс найти что-нибудь интересное, что вы можете сказать об игре, резко падает.
Питер Шор

Ответы:

4

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

Я думаю, что способ сформулировать вопрос, который был бы оптимален для того, чтобы теория игр была полезной, заключался бы в более конкурентном сценарии. Т.е. должна быть конкуренция среди множества разных актеров. Итак, я бы предположил следующее:

  • Существует большое , но конечное число п других исследователей , пытающихся проводить один и тот же набор доступных научных вопросов, которые я называю Q , что вы заинтересованы в.
  • Каждая исследовательская задача определяется следующими характеристиками:
    • Времени , или я , требуется, чтобы добиться видимости того, сможете ли вы решить проблему
    • Вероятность успеха или S , при решении проблемы; как только вы достигнете «момента истины» и потратите достаточно времени, Природа будет случайным образом решать, сможете ли вы решить проблему или нет
    • Выгода для вашей карьеры , или U (как в полезности), при условии достижения успеха
  • Каждый из этих исследователей имеет разные уровни следующих величин:
    • Время на инвестиции в исследования, т
    • Талант при исследовании, р
    • Коммуникабельность и другие карьеры, помогая качеств, л (как в симпатичен), который будет определять , насколько хорошо исследователь будет опираться на свои научные успехи в их продвижении по службе

Теперь, предполагая, что сотрудничество по какой-либо проблеме невозможно, рассмотрим то, что я буду называть «динамической итерированной игрой». Это игра, в которую играют неоднократно, но она немного меняется каждый раз, когда в нее играют.

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

Во время каждой итерации игры данный актер выбирает исследовательский вопрос для работы. Каждому игроку разрешено менять вопросы в любое время, и если проблема решена, выгода для карьеры U падает до 0 для всех остальных игроков. Если игрок потратил достаточно времени и не смог решить проблему, то этому конкретному игроку запрещено пытаться решить эту проблему снова ... хотя любому другому игроку разрешено продолжать работать над проблемой, и другой участник может решить ее. это успешно. Игра заканчивается после того, как все M ходов были сделаны.

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

Я сомневаюсь, что существует какой-либо алгоритм полиномиального времени для решения этой проблемы; Я не вижу причин, по которым исследователи должны ограничиваться игрой в равновесия по Нэшу с чистой стратегией, поэтому проблема будет заключаться в равновесии по Нэшу со смешанной стратегией и, таким образом, в худшем случае к PPAD, если вы считаете, что «решение проблемы» означает «поиск Нэша». равновесие для проблемы ". (Можно предположить, что если вы самый активный исследователь из всех, вы можете пойти дальше и рассчитать свое любимое равновесие по Нэшу, а затем подать сигнал всем остальным игрокам ... таким образом, у вас будет некоторая уверенность в том, что никто не изменит стратегии в сторону от стратегии профиль, который вы указали.)

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

Филип Уайт
источник
1
Филипп, спасибо за ответ! Это отличный взгляд на проблему; Я задаюсь вопросом: можете ли вы придумать какой-нибудь способ добавить понятие «частичной информации» в проблему, чтобы она сохраняла свой статус полноты PPAD? Что-то, чтобы смоделировать тот факт, что, будучи игроком в этой игре, я не обязательно знаю, что делают все мои противники (то есть я не обладаю идеальными знаниями о том, какие вопросы они рассматривают, и какую силу они считают в отвечая на каждый вопрос)? Влияет ли это на сложность вычисления равновесия Нэша? (Я не знаю!)
Даниэль Апон
1
@Daniel Apon: Спасибо за комментарий! Я не думаю, что было бы трудно изменить условия, поэтому вы просто не знаете, что делают ваши противники, или каковы их характеристики. Единственное предостережение, я думаю, что гарантия существования равновесия Нэша исчезает, когда вы имеете дело с несовершенной информационной игрой. Я не очень много знаю о том, что известно как «игры Штакельберга», но я думаю, что они могут иметь отношение к вашему предложенному изменению. Я действительно задавался вопросом, какова лучшая концепция решения в несовершенных информационных играх ... Я подумаю над этим.
Филипп Уайт
Я прочитал немного больше об этом ... Я думаю, что байесовские игры могут быть здесь уместны, потому что они используются для игр с несовершенной информацией. Вот ссылка на страницу Википедии, на которую я заглянул: en.wikipedia.org/wiki/Bayesian_game
Филипп Уайт