Choosing a research topic using game theory This recent game theory question got me thinking (this is a tangent, of course): Is it possible to efficiently optimize a personal strategy for choosing research questions to work on using game theory?

In order to head towards a formalization of the question, I'll make the following (informally stated) assumptions:


I equally "enjoy" any particular problem available for me to work on (in order to avoid the "soft" (and correct!) answer of "Do what you like!").
I may or may not be successful at finding an answer to any given problem I choose to work on. For any given problem, I have some estimate of the probability of how good I will be at solving a problem (after investing time in it).
My goal is to maximize my payoff when being evaluated down the line (applying for a job, applying for tenure, applying for a fellowship, etc.), which is a function of how many problems I solve and how important or hard the problems are. I do not have a clear idea of the exact payoffs per problem, but I can make a reasonable estimate.
There is a loose inverse relationship between problem payoff and problem difficulty. Another statement of my goal is to "game" the differences (i.e. look for "low-hanging fruit").
An instance of this overall problem is specified by a list of research questions (possibly infinite in number), to which I firmly attach (at no computational cost; it's given as input) an estimate of the question's worth and the question's difficulty. I am playing this game against an adversary (the person evaluating me); nature decides, given the probability of me solving a given problem, whether I solve it successfully after I choose to attempt it.


In an effort to really formalize what's going on (and sidestep uninteresting or argumentative/discussion-type responses), I will view this problem as an extensive-form game with incomplete information with an infinite action set.



Question: I assume games of this type are not efficiently computable. However, is there a polynomial time algorithm to approximately maximize my payoff? What about a PTAS?

Or, alternatively, is there a more accurate game-theoretic model for this problem? If so, the same question holds: Can I (approximately) maximize my payoff efficiently? If so, how?
I'm going to try to answer you question by proposing an alternate model for the question.  I typically ask more questions than I answer on here, so I hope you'll be forgiving if my answer isn't optimal, although I'm doing my best.

I think that the way to phrase the question that would be optimal for allowing game theory to be useful would be to assume a more competitive scenario.  I.e., there needs to be competition among a variety of different actors.  So, I would assume the following:


There is a large but finite number n of other researchers attempting to pursue the same set of available research questions, which I call Q, that you are interested in.
Each research problem is defined by the following characteristics:

Time investment, or I, required to achieve visibility on whether or not you'll be able to solve the problem
Probability of success, or S, at solving the problem; once you reach the "moment of truth" and have invested enough time, Nature will decide randomly if you're going to be able to solve the problem or not
Benefit to your career, or U (as in utility), provided success is achieved

Each of these researchers have different levels of the following quantities:

Time available for investment in research, t
Talent at research, r
Interpersonal skills and other career-assisting qualities, l (as in likable), which will determine how well the researcher will capitalize on their research successes for their career advancement



Now, assuming no cooperation on any problem is possible, consider what I'm going to refer to as a "dynamic iterated game."  This is a game that is played repeatedly, but that changes slightly each time it is played.

Let M be the number of moves, or turns, in the game.  The initial manifestation of the game could be represented as a list that contains every actor (researcher) and every problem that they could work on, in addition to all of the values associated with each actor and each problem that I listed above.  (I'm assuming, of course, that every researcher knows everything presently known about all of the problems, and about all other researchers, making this a game of perfect information.)

During each iteration of the game, a given actor chooses a research question to work on.  Each actor is permitted to switch questions at any time, and if a problem is solved, the benefit to career U gets dropped to 0 for all other players.  If a player invests sufficient time and fails to solve the problem, then that particular player is prohibited from trying to solve that problem again...although any other player is allowed to continue working on the problem, and another actor may be able to solve it successfully.  The game ends after all M turns have been taken.

Each turn that a researcher has selected a problem will cause that player to get closer to reaching the "moment of truth," and possibly solving the problem, Nature permitting.  A problem, once solved, adds a certain benefit to the researcher's career based on l.  Research talent amplifies the probability of success, while free time amplifies the ability to make progress in a given turn.

I doubt that there is any polynomial time algorithm for solving this; I see no reason why researchers should be restricted to playing pure-strategy Nash equilibria, so the problem would involve mixed-strategy Nash equilibria and thus be at worst PPAD-complete, if you consider "solving the problem" to mean "finding a Nash equilibrium for the problem."  (One could imagine that if you are the most proactive researcher around, you might go ahead and calculate your favorite Nash equilibrium and then signal it to all other players...thus giving you some confidence that no one will change strategies away from the strategy profile you've signaled.)

At any rate, this is the most involved answer I've ever posted.  I hope it is of at least some value.  Please let me know if anyone has any response or to it or recommendations for improving it.