Essa recente questão da teoria dos jogos me fez pensar (isso é tangente, é claro): É possível otimizar eficientemente uma estratégia pessoal para escolher questões de pesquisa para trabalhar no uso da teoria dos jogos?
Para avançar para uma formalização da pergunta, farei as seguintes suposições (declaradas informalmente):
- Eu "aprecio" igualmente qualquer problema específico disponível para eu trabalhar (a fim de evitar a resposta "suave" (e correta!) De "Faça o que quiser!").
- Posso ou não ser bem-sucedido em encontrar uma resposta para qualquer problema em que opto por trabalhar. Para qualquer problema, tenho uma estimativa da probabilidade de ser bom em resolver um problema (depois de investir tempo nele).
- Meu objetivo é maximizar minha recompensa ao ser avaliado abaixo (candidatar-me a um emprego, candidatar-se a uma vaga, candidatar-se a uma bolsa de estudos etc.), que é uma função de quantos problemas eu resolvo e da importância ou dificuldade dos problemas. . Não tenho uma ideia clara dos pagamentos exatos por problema, mas posso fazer uma estimativa razoável.
- Existe uma relação inversa frouxa entre retorno do problema e dificuldade do problema. Outra afirmação do meu objetivo é "brincar" com as diferenças (ou seja, procurar "frutas baixas").
- Uma instância desse problema geral é especificada por uma lista de perguntas de pesquisa (possivelmente em número infinito), às quais anexo firmemente (sem custo computacional; é dado como entrada) uma estimativa do valor da pergunta e da dificuldade da pergunta. Estou jogando esse jogo contra um adversário (a pessoa que está me avaliando); a natureza decide, dada a probabilidade de eu resolver um determinado problema, se eu o resolvo com sucesso depois de optar por tentar.
Em um esforço para realmente formalizar o que está acontecendo (e evitar respostas desinteressantes ou argumentativas / do tipo discussão), verei esse problema como um jogo de formato amplo, com informações incompletas e um conjunto de ações infinitas .
Pergunta : Presumo que jogos desse tipo não sejam eficientemente computáveis. No entanto, existe um algoritmo de tempo polinomial para maximizar aproximadamente minha recompensa? Que tal um PTAS?
Ou, alternativamente, existe um modelo teórico de jogo mais preciso para esse problema? Nesse caso, a mesma pergunta se aplica: Posso (aproximadamente) maximizar meu pagamento com eficiência? Se sim, como?
fonte
Respostas:
Vou tentar responder à sua pergunta propondo um modelo alternativo para a pergunta. Normalmente faço mais perguntas do que respondo aqui, por isso espero que você perdoe se minha resposta não for ótima, embora esteja fazendo o meu melhor.
Penso que a maneira de formular a pergunta que seria ótima para permitir que a teoria dos jogos fosse útil seria assumir um cenário mais competitivo. Ou seja, é preciso haver concorrência entre uma variedade de atores diferentes. Então, eu assumiria o seguinte:
Agora, supondo que nenhuma cooperação seja possível, considere o que chamarei de "jogo iterado dinâmico". Este é um jogo que é jogado repetidamente, mas que muda um pouco cada vez que é jogado.
Seja M o número de jogadas ou turnos no jogo. A manifestação inicial do jogo pode ser representada como uma lista que contém todos os atores (pesquisadores) e todos os problemas com os quais eles poderiam trabalhar, além de todos os valores associados a cada ator e a cada problema que eu listei acima. (Suponho, é claro, que todo pesquisador saiba tudo sobre todos os problemas atualmente conhecidos e sobre todos os outros pesquisadores, fazendo deste um jogo de informações perfeitas.)
Durante cada iteração do jogo, um determinado ator escolhe uma pergunta de pesquisa para trabalhar. É permitido que cada ator troque de pergunta a qualquer momento e, se um problema for resolvido, o benefício para a carreira U será reduzido para 0 para todos os outros jogadores. Se um jogador investe tempo suficiente e não consegue resolver o problema, esse jogador em particular é proibido de tentar resolvê-lo novamente ... embora qualquer outro jogador possa continuar trabalhando no problema e outro ator possa resolver com sucesso. O jogo termina depois de todos os M turnos.
Cada turno que um pesquisador seleciona um problema fará com que o jogador se aproxime do "momento da verdade" e, possivelmente, resolva o problema, conforme a Natureza permitir. Um problema, uma vez resolvido, agrega certo benefício à carreira do pesquisador com base em l . O talento em pesquisa amplia a probabilidade de sucesso, enquanto o tempo livre amplia a capacidade de progredir em um determinado turno.
Duvido que exista algum algoritmo de tempo polinomial para resolver isso; Não vejo razão para que os pesquisadores devam se restringir a interpretar equilíbrios de Nash de estratégia pura, para que o problema envolva equilíbrios de Nash de estratégia mista e, portanto, na pior das hipóteses, completo com PPAD, se você considerar "resolver o problema" como "encontrar um Nash equilíbrio para o problema ". (Pode-se imaginar que, se você é o pesquisador mais proativo, pode calcular o seu equilíbrio favorito de Nash e depois sinalizá-lo para todos os outros jogadores ... dando assim a você certa confiança de que ninguém mudará as estratégias da estratégia. perfil que você sinalizou.)
De qualquer forma, esta é a resposta mais envolvida que eu já postei. Espero que seja de pelo menos algum valor. Informe-me se alguém tiver alguma resposta ou recomendações para melhorá-lo.
fonte