<p>This <a href="https://cstheory.stackexchange.com/questions/2922/is-this-game-solvable">recent game theory question</a> 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?</p>

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

<ul>
<li>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!").
<li>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).
<li>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.
<li>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").
<li>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.
</ul>

<p>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 <strong>extensive-form game with incomplete information with an infinite action set</strong>.</p>

<hr>

<p><strong>Question</strong>: 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?</p>

<p>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?</p>

CC BY-SA 2.5
2010-11-12T12:32:32.300Z
One potential problem with formulating this as a game is that your adversary, the person evaluating you, is not necessarily playing against you. Indeed it is often the case that they are on your side, and only willing to see you fail if you have not passed the bare minimum of requirements. Another possible adversary is *all other researchers*, as they may be working (possibly collaboratively) on the same problem and are thus working against you achieving success by trying to obtain the results before you do.
Dave Clarke
CC BY-SA 2.5
2010-11-12T12:37:50.310Z
For the purposes of this question (I'd like to sidestep as much discussion as possible so this is a good question...), let's assume the person evaluating me is really under some serious pressure to choose one and only one best individual for a particular reward, so they're adversarial. Also, let's assume that "anything truly original will be just that: original", so other researchers are not a serious concern. I'm (of course!) personally interested in other possibilities, but I think leaving it open will invite bad answers. :)
Daniel Apon
CC BY-SA 2.5
2010-11-12T12:39:35.503Z
One factor in the problem that might merit a different model: An evaluation of the probability of success/reward structure per problem that I choose to work on.
Daniel Apon
CC BY-SA 2.5
2010-11-12T12:45:41.910Z
Another comment: I think this question *might* be more interesting (than just a literature search, a *bam* here's the result from such-and-such conference on extensive-games) if it's treated as a "how to model this" question. I'm just concerned since it hits so close to home that that might develop poorly... I'm tentatively open to creative answers though!
Daniel Apon
CC BY-SA 2.5
2010-11-13T07:36:38.823Z
It seems that no one wants to play.
Dave Clarke
CC BY-SA 2.5
2010-11-13T12:20:51.827Z
@Dave: I have hope! :) Although, there really aren't that many [game theory questions](http://cstheory.stackexchange.com/questions/tagged/gt.game-theory) on the site in general, especially relative to, say, complexity questions... Maybe the world (or this site) just needs more game theorists!
Daniel Apon
CC BY-SA 2.5
2010-11-13T13:51:40.657Z
So one way to model the game is: you are trying to collect $R$ research points before the tenure clock expires at time $T$. Each question you might work on is worth $r_i$ research points, and for each question there is a function $P_i(t)$ which gives the probability of solving it if you spend time $t$ on it. Maximize your chances of collecting enough points before the clock runs out. You might be able to say something about the best strategy for this game.
Peter Shor 
CC BY-SA 2.5
2010-11-13T13:53:16.253Z
Of course, in real life, each question you answer unlocks more questions, which you can't predict in advance but which are quite possibly easier and/or worth more than the set of questions you started with, but once you start making strategy trees like this the chance of finding anything interesting you can say about the game goes down dramatically.
Peter Shor 
CC BY-SA 2.5
2010-11-13T14:18:58.430Z
@Peter, interesting insights. I wonder if a scheduling-type perspective would be a better match, since in general with job scheduling, you're handling unknown future jobs with possibly wildly fluctuating costs/values.
Daniel Apon
<soft-question><gt.game-theory>
Choosing a research topic using game theory
Daniel Apon
# Choosing a research topic using game theory

(Asked by: username_0 on 2010-11-12)

This [recent game theory question](https://cstheory.stackexchange.com/questions/2922/is-this-game-solvable) 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?

**Tags:** soft-question, gt.game-theory

> **Comments:**
> **username_1**: One potential problem with formulating this as a game is that your adversary, the person evaluating you, is not necessarily playing against you. Indeed it is often the case that they are on your side, and only willing to see you fail if you have not passed the bare minimum of requirements. Another possible adversary is *all other researchers*, as they may be working (possibly collaboratively) on the same problem and are thus working against you achieving success by trying to obtain the results before you do.  
> **username_0**: For the purposes of this question (I'd like to sidestep as much discussion as possible so this is a good question...), let's assume the person evaluating me is really under some serious pressure to choose one and only one best individual for a particular reward, so they're adversarial. Also, let's assume that "anything truly original will be just that: original", so other researchers are not a serious concern. I'm (of course!) personally interested in other possibilities, but I think leaving it open will invite bad answers. :)  
> **username_0**: One factor in the problem that might merit a different model: An evaluation of the probability of success/reward structure per problem that I choose to work on.  
> **username_0**: Another comment: I think this question *might* be more interesting (than just a literature search, a *bam* here's the result from such-and-such conference on extensive-games) if it's treated as a "how to model this" question. I'm just concerned since it hits so close to home that that might develop poorly... I'm tentatively open to creative answers though!  
> **username_1**: It seems that no one wants to play.  
> **username_0**: @Dave: I have hope! :) Although, there really aren't that many [game theory questions](http://cstheory.stackexchange.com/questions/tagged/gt.game-theory) on the site in general, especially relative to, say, complexity questions... Maybe the world (or this site) just needs more game theorists!  
> **username_2**: So one way to model the game is: you are trying to collect $R$ research points before the tenure clock expires at time $T$. Each question you might work on is worth $r_i$ research points, and for each question there is a function $P_i(t)$ which gives the probability of solving it if you spend time $t$ on it. Maximize your chances of collecting enough points before the clock runs out. You might be able to say something about the best strategy for this game.  
> **username_2**: Of course, in real life, each question you answer unlocks more questions, which you can't predict in advance but which are quite possibly easier and/or worth more than the set of questions you started with, but once you start making strategy trees like this the chance of finding anything interesting you can say about the game goes down dramatically.  
> **username_0**: @Peter, interesting insights. I wonder if a scheduling-type perspective would be a better match, since in general with job scheduling, you're handling unknown future jobs with possibly wildly fluctuating costs/values.  

---

## 0 answers

