Этот недавний вопрос теории игр заставил меня задуматься (это, конечно, касательно): возможно ли эффективно оптимизировать личную стратегию выбора исследовательских вопросов для работы над теорией игр?
Чтобы перейти к формализации вопроса, я сделаю следующие (неофициально заявленные) предположения:
- Я также «наслаждаюсь» любой конкретной проблемой, над которой я могу работать (чтобы избежать «мягкого» (и правильного!) Ответа «Делай, что тебе нравится!»).
- Я могу или не могу быть успешным в поиске ответа на любую проблему, над которой я хочу работать. Для любой данной проблемы у меня есть некоторая оценка вероятности того, насколько хорошо я буду в решении проблемы (потратив на это время).
- Моя цель - максимизировать свою отдачу при оценке в дальнейшем (подача заявки на работу, подача заявки на пребывание в должности, подача заявки на стипендию и т. Д.), Которая зависит от того, сколько проблем я решаю и насколько важны или трудны проблемы. , У меня нет четкого представления о точных результатах по каждой проблеме, но я могу сделать разумную оценку.
- Существует слабая обратная связь между проблемой вознаграждения и проблемой сложности. Еще одним утверждением моей цели является «игра» различий (то есть поиск «низко висящих фруктов»).
- Пример этой общей проблемы определяется списком исследовательских вопросов (возможно, бесконечное число), к которым я твердо прикрепляю (без вычислительных затрат; он приводится в качестве входных данных) оценку ценности вопроса и сложности вопроса. Я играю в эту игру против противника (человека, который оценивает меня); природа решает, учитывая вероятность того, что я решу данную проблему, успешно ли я ее решу после того, как решу попробовать.
В попытке действительно формализовать происходящее (и обойти неинтересные или аргументированные / дискуссионные ответы), я буду рассматривать эту проблему как игру в расширенной форме с неполной информацией с бесконечным набором действий .
Вопрос : я предполагаю, что игры такого типа не являются эффективно вычисляемыми. Однако, есть ли алгоритм полиномиального времени, чтобы приблизительно максимизировать мою отдачу? Что насчет PTAS?
Или, альтернативно, есть более точная теоретико-игровая модель для этой проблемы? Если так, то остается тот же вопрос: могу ли я (приблизительно) максимально увеличить свою выплату? Если да, то как?
источник
Ответы:
Я постараюсь ответить на ваш вопрос, предложив альтернативную модель для вопроса. Обычно я задаю больше вопросов, чем отвечаю, поэтому надеюсь, что вы простите меня, если мой ответ не будет оптимальным, хотя я делаю все возможное.
Я думаю, что способ сформулировать вопрос, который был бы оптимален для того, чтобы теория игр была полезной, заключался бы в более конкурентном сценарии. Т.е. должна быть конкуренция среди множества разных актеров. Итак, я бы предположил следующее:
Теперь, предполагая, что сотрудничество по какой-либо проблеме невозможно, рассмотрим то, что я буду называть «динамической итерированной игрой». Это игра, в которую играют неоднократно, но она немного меняется каждый раз, когда в нее играют.
Пусть M будет количеством ходов или ходов в игре. Первоначальное проявление игры может быть представлено в виде списка, который содержит каждого актера (исследователя) и каждую проблему, над которой они могут работать, в дополнение ко всем значениям, связанным с каждым актером и каждой проблемой, которые я перечислил выше. (Я предполагаю, конечно, что каждый исследователь знает все, что в настоящее время известно обо всех проблемах и обо всех других исследователях, что делает эту игру идеальной информацией.)
Во время каждой итерации игры данный актер выбирает исследовательский вопрос для работы. Каждому игроку разрешено менять вопросы в любое время, и если проблема решена, выгода для карьеры U падает до 0 для всех остальных игроков. Если игрок потратил достаточно времени и не смог решить проблему, то этому конкретному игроку запрещено пытаться решить эту проблему снова ... хотя любому другому игроку разрешено продолжать работать над проблемой, и другой участник может решить ее. это успешно. Игра заканчивается после того, как все M ходов были сделаны.
Каждый ход, когда исследователь выбирает проблему, заставляет игрока приближаться к «моменту истины» и, возможно, к решению проблемы, если позволяет природа. Проблема, однажды решенная, добавляет определенную выгоду в карьеру исследователя, основанную на л . Исследовательский талант увеличивает вероятность успеха, в то время как свободное время усиливает способность делать успехи в данный ход.
Я сомневаюсь, что существует какой-либо алгоритм полиномиального времени для решения этой проблемы; Я не вижу причин, по которым исследователи должны ограничиваться игрой в равновесия по Нэшу с чистой стратегией, поэтому проблема будет заключаться в равновесии по Нэшу со смешанной стратегией и, таким образом, в худшем случае к PPAD, если вы считаете, что «решение проблемы» означает «поиск Нэша». равновесие для проблемы ". (Можно предположить, что если вы самый активный исследователь из всех, вы можете пойти дальше и рассчитать свое любимое равновесие по Нэшу, а затем подать сигнал всем остальным игрокам ... таким образом, у вас будет некоторая уверенность в том, что никто не изменит стратегии в сторону от стратегии профиль, который вы указали.)
В любом случае, это самый сложный ответ, который я когда-либо писал. Я надеюсь, что это имеет хоть какую-то ценность. Пожалуйста, дайте мне знать, если у кого-то есть ответ или на него или рекомендации по его улучшению.
источник