Choisir un sujet de recherche en utilisant la théorie des jeux

Cette récente question sur la théorie des jeux m'a fait réfléchir (c'est une tangente, bien sûr): est-il possible d'optimiser efficacement une stratégie personnelle pour choisir des questions de recherche sur lesquelles travailler en utilisant la théorie des jeux?

Afin d'avancer vers une formalisation de la question, je ferai les hypothèses suivantes (formulées de manière informelle):

• J'apprécie également tout problème particulier sur lequel je peux travailler (afin d'éviter la réponse "douce" (et correcte!) De "Faites ce que vous aimez!").
• Je peux ou non réussir à trouver une réponse à un problème donné sur lequel je choisis de travailler. Pour tout problème donné, j'ai une estimation de la probabilité que je réussisse à résoudre un problème (après y avoir investi du temps).
• Mon objectif est de maximiser mon gain lors de l'évaluation en aval (postuler à un emploi, postuler, postuler à une bourse, etc.), qui est fonction du nombre de problèmes que je résous et de leur importance ou de leur difficulté. . Je n'ai pas une idée claire des gains exacts par problème, mais je peux faire une estimation raisonnable.
• Il existe une relation inverse lâche entre la résolution du problème et la difficulté du problème. Un autre énoncé de mon objectif est de «jouer» les différences (c'est-à-dire de chercher des «fruits bas»).
• Un exemple de ce problème global est spécifié par une liste de questions de recherche (éventuellement infinies), à laquelle j'attache fermement (sans frais de calcul; il est donné en entrée) une estimation de la valeur de la question et de sa difficulté. Je joue à ce jeu contre un adversaire (la personne qui m'évalue); la nature décide, étant donné la probabilité que je résolve un problème donné, si je le résous avec succès après avoir choisi de le tenter.

Dans un effort pour vraiment formaliser ce qui se passe (et contourner les réponses inintéressantes ou argumentatives / de type discussion), je considérerai ce problème comme un jeu de forme étendue avec des informations incomplètes avec un ensemble d'actions infini .

Question : Je suppose que les jeux de ce type ne sont pas calculables efficacement. Cependant, existe-t-il un algorithme de temps polynomial pour maximiser approximativement mon gain? Et un PTAS?

Ou bien, existe-t-il un modèle de théorie des jeux plus précis pour ce problème? Dans l'affirmative, la même question se pose: puis-je maximiser (approximativement) efficacement mon gain? Si c'est le cas, comment?

Je vais essayer de répondre à votre question en proposant un modèle alternatif pour la question. Je pose généralement plus de questions que je ne réponds ici, alors j'espère que vous pardonnerez si ma réponse n'est pas optimale, même si je fais de mon mieux.

Je pense que la façon de formuler la question qui serait optimale pour permettre à la théorie des jeux d'être utile serait de supposer un scénario plus compétitif. C'est-à-dire qu'il doit y avoir une concurrence entre une variété d'acteurs différents. Je suppose donc ce qui suit:

• Il existe un nombre important mais limité n d'autres chercheurs qui tentent de poursuivre le même ensemble de questions de recherche disponibles, que j'appelle Q , qui vous intéressent.
• Chaque problème de recherche est défini par les caractéristiques suivantes:
  • Investissement en temps , ou moi , requis pour obtenir une visibilité sur la capacité ou non à résoudre le problème
  • Probabilité de succès , ou S , pour résoudre le problème; une fois que vous avez atteint le «moment de vérité» et que vous avez investi suffisamment de temps, la nature décidera au hasard si vous allez pouvoir résoudre le problème ou non
  • Profitez de votre carrière , ou U (comme dans l'utilité), à condition que le succès soit atteint
• Chacun de ces chercheurs a différents niveaux des quantités suivantes:
  • Temps disponible pour investir dans la recherche, t
  • Talent à la recherche, r
  • Compétences interpersonnelles et autres qualités d'aide à la carrière, l (comme en sympathique), qui détermineront dans quelle mesure le chercheur tirera parti de ses succès en recherche pour son avancement professionnel

Maintenant, en supposant qu'aucune coopération sur aucun problème n'est possible, considérez ce que je vais appeler un "jeu itéré dynamique". C'est un jeu qui se joue à plusieurs reprises, mais qui change légèrement à chaque fois qu'il est joué.

Soit M le nombre de coups ou de tours dans la partie. La manifestation initiale du jeu pourrait être représentée comme une liste qui contient chaque acteur (chercheur) et chaque problème sur lequel ils pourraient travailler, en plus de toutes les valeurs associées à chaque acteur et à chaque problème que j'ai énuméré ci-dessus. (Je suppose, bien sûr, que chaque chercheur sait tout ce qui est actuellement connu sur tous les problèmes et sur tous les autres chercheurs, ce qui en fait un jeu d'information parfaite.)

À chaque itération du jeu, un acteur donné choisit une question de recherche sur laquelle travailler. Chaque acteur est autorisé à changer de question à tout moment, et si un problème est résolu, l'avantage pour la carrière U passe à 0 pour tous les autres joueurs. Si un joueur investit suffisamment de temps et ne parvient pas à résoudre le problème, il est alors interdit à ce joueur particulier d'essayer de résoudre à nouveau ce problème ... bien que tout autre joueur soit autorisé à continuer à travailler sur le problème et qu'un autre acteur puisse le résoudre avec succès. Le jeu se termine après que tous les tours M aient été effectués.

Chaque tour qu'un chercheur a sélectionné un problème amènera ce joueur à atteindre le "moment de vérité" et éventuellement à résoudre le problème, si la nature le permet. Un problème, une fois résolu, ajoute un certain avantage à la carrière du chercheur basé sur l . Le talent en recherche amplifie la probabilité de réussite, tandis que le temps libre amplifie la capacité de progresser dans un tour donné.

Je doute qu'il existe un algorithme de temps polynomial pour résoudre ce problème; Je ne vois aucune raison pour laquelle les chercheurs devraient être limités à jouer des équilibres de Nash à stratégie pure, donc le problème impliquerait des équilibres de Nash à stratégie mixte et donc au pire PPAD-complet, si vous considérez "résoudre le problème" pour signifier "trouver un Nash équilibre pour le problème. " (On pourrait imaginer que si vous êtes le chercheur le plus proactif du monde, vous pourriez aller de l'avant et calculer votre équilibre Nash préféré, puis le signaler à tous les autres joueurs ... vous donnant ainsi la certitude que personne ne changera de stratégie loin de la stratégie profil que vous avez signalé.)

En tout cas, c'est la réponse la plus impliquée que j'ai jamais publiée. J'espère que cela a au moins une certaine valeur. Veuillez me faire savoir si quelqu'un a une réponse ou des recommandations pour l'améliorer.