Escolhendo um tópico de pesquisa usando a teoria dos jogos

19

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?

Daniel Apon
fonte
4
Um problema potencial ao formular isso como um jogo é que seu adversário, a pessoa que o avalia, não está necessariamente jogando contra você. De fato, geralmente é o caso deles estarem do seu lado e só querer vê-lo falhar se você não tiver passado o mínimo necessário de requisitos. Outro possível adversário são todos os outros pesquisadores , pois eles podem estar trabalhando (possivelmente de forma colaborativa) no mesmo problema e, assim, estão trabalhando contra você para alcançar o sucesso, tentando obter os resultados antes de você.
Dave Clarke
Para os propósitos desta pergunta (eu gostaria de evitar o máximo de discussão possível, então essa é uma boa pergunta ...), vamos supor que a pessoa que está me avaliando está realmente sob uma séria pressão para escolher uma e apenas a melhor pessoa para uma recompensa em particular, então eles são contraditórios. Além disso, vamos supor que "qualquer coisa verdadeiramente original será exatamente isso: original", para que outros pesquisadores não sejam uma preocupação séria. Estou (é claro!) Pessoalmente interessado em outras possibilidades, mas acho que deixá-lo em aberto convidará respostas ruins. :)
Daniel Apon
Um fator no problema que pode merecer um modelo diferente: uma avaliação da probabilidade de sucesso / estrutura de recompensa por problema em que eu escolho trabalhar.
achou
2
RTrEuPEu(t)t
2
Obviamente, na vida real, cada pergunta que você responde libera mais perguntas, que você não pode prever com antecedência, mas que são possivelmente mais fáceis e / ou valem mais do que o conjunto de perguntas com as quais você começou, mas depois que você começa a criar árvores de estratégia assim, a chance de encontrar algo interessante que você possa dizer sobre o jogo diminui drasticamente.
quer

Respostas:

4

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:

  • Há um número grande, mas finito n de outros pesquisadores que tentam perseguir o mesmo conjunto de questões de pesquisa disponíveis, que chamo de Q , que você está interessado.
  • Cada problema de pesquisa é definido pelas seguintes características:
    • Investimento de tempo , ou eu , necessário para obter visibilidade sobre se você conseguirá ou não resolver o problema
    • Probabilidade de sucesso , ou S , na resolução do problema; quando você chegar ao "momento da verdade" e tiver investido tempo suficiente, a natureza decidirá aleatoriamente se você será capaz de resolver o problema ou não
    • Beneficie sua carreira , ou U (como em utilidade), desde que o sucesso seja alcançado
  • Cada um desses pesquisadores possui níveis diferentes das seguintes quantidades:
    • Tempo disponível para investimento em pesquisa, t
    • Talento na pesquisa, r
    • Habilidades interpessoais e outras qualidades de assistência na carreira, l (como é provável), que determinarão o quão bem o pesquisador capitalizará seus sucessos de pesquisa para avançar na carreira

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.

Philip White
fonte
11
Philip, obrigado pela resposta! Essa é uma ótima perspectiva sobre o problema; Eu me pergunto: você pode pensar em alguma maneira de adicionar uma noção de "informações parciais" ao problema, para que ele mantenha seu status de integridade do PPAD? Algo para modelar o fato de que, como jogador neste jogo, eu não sei necessariamente o que todos os meus adversários estão fazendo (ou seja, eu não tenho um conhecimento perfeito de quais perguntas eles estão considerando e que força eles acreditam ter). respondendo a cada pergunta)? A adição disso afeta a complexidade da computação de um Equilíbrio de Nash? (Eu não sei!)
Daniel Apon
11
@ Daniel Apon: Obrigado pelo comentário! Eu não acho que seria difícil alterar as condições para que você simplesmente não saiba o que seus adversários estão fazendo ou quais são suas características. A única ressalva é que eu acho que a garantia da existência de um equilíbrio de Nash desaparece quando você está lidando com um jogo de informações imperfeitas. Não sei muito sobre o que é conhecido como "jogos Stackelberg", mas acho que eles podem ser relevantes para a alteração proposta. Na verdade, eu me perguntei qual é o melhor conceito de solução em jogos de informações imperfeitos ... Vou pensar um pouco.
Philip White
Eu li um pouco mais sobre isso ... Eu acho que os jogos bayesianos podem ser relevantes aqui, porque são usados ​​para lidar com jogos com informações imperfeitas. Aqui está um link para a página da Wikipedia que eu olhei: en.wikipedia.org/wiki/Bayesian_game
Philip White