18
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ 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. $\endgroup$
    – Dave Clarke
    Nov 12, 2010 at 12:32
  • $\begingroup$ 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. :) $\endgroup$
    – Daniel Apon
    Nov 12, 2010 at 12:37
  • $\begingroup$ 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. $\endgroup$
    – Daniel Apon
    Nov 12, 2010 at 12:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Nov 13, 2010 at 13:51
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Nov 13, 2010 at 13:53

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Philip, thanks for the answer! This is a great perspective on the problem; I wonder: Can you think of any way to add a notion of "partial information" into the problem so that it keeps its PPAD-completeness status? Something to model the fact that as a player in this game, I don't necessarily know what all of my adversaries are doing (i.e. I don't have perfect knowledge of what questions they are considering, and what strength they believe they have at answering each question)? Does adding this affect the complexity of computing a Nash Equilibrium? (I don't know!) $\endgroup$
    – Daniel Apon
    Nov 22, 2010 at 16:57
  • 1
    $\begingroup$ @Daniel Apon: Thanks for the comment! I don't think it would be difficult to alter the conditions so you simply don't know what your adversaries are doing, or what their characteristics are. The only caveat is, I think that the guarantee of the existence of a Nash equilibrium goes away when you are dealing with an imperfect-information game. I don't know very much about what are known as "Stackelberg games," but I think they may be relevant to your proposed change. I have actually wondered what the best solution concept is in imperfect information games...I'll give it some thought. $\endgroup$
    – user1338
    Nov 22, 2010 at 17:09
  • $\begingroup$ I read a little more on this...I think that Bayesian games may be relevant here, because they are used to deal with games with imperfect information. Here's a link to the Wikipedia page that I glanced at: en.wikipedia.org/wiki/Bayesian_game $\endgroup$
    – user1338
    Nov 22, 2010 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.