Here's yet another problem whose proper formulation I'm still not sure of, and it runs as follows. First, consider the Prisoner's Dilemma. Informally, two timeless decision agents with common knowledge of the other's timeless decision agency, but no way to communicate or make binding commitments, will both Cooperate because they know that the other agent is in a similar epistemic state, running a similar decision algorithm, and will end up doing the same thing that they themselves do. In general, on the True Prisoner's Dilemma, facing an opponent who can accurately predict your own decisions, you want to cooperate only if the other agent will cooperate if and only if they predict that you will cooperate. And the other agent is reasoning similarly: They want to cooperate only if you will cooperate if and only if you accurately predict that they will cooperate.

But there's actually an infinite regress here which is being glossed over - you won't cooperate just because you predict that they will cooperate, you will only cooperate if you predict they will cooperate if and only if you cooperate. So the other agent needs to cooperate if they predict that you will cooperate if you predict that they will cooperate... (...only if they predict that you will cooperate, etcetera).

On the Prisoner's Dilemma in particular, this infinite regress can be cut short by expecting that the other agent is doing symmetrical reasoning on a symmetrical problem and will come to a symmetrical conclusion, so that you can expect their action to be the symmetrical analogue of your own - in which case (C, C) is preferable to (D, D). But what if you're facing a more general decision problem, with many agents having asymmetrical choices, and everyone wants to have their decisions depend on how they predict that other agents' decisions depend on their own predicted decisions? Is there a general way of resolving the regress?

Yes. You can condition on two prior probabilities: that an agent will successfully predict your actual action, and that an agent will respond in a particular way based on the action they predict you to take. For the solution in the case of the Truly Iterated Prisoner's Dilemma, see here.

(EDIT, 6/18/2011:

On further consideration, my assertion -- that the indicated solution to the Prisoner's Dilemma constitutes a general method for resolving infinite regress in the full class of problems specified -- is a naive oversimplification. The indicated solution to a specific dilemma is suggestive of an area of solution space to search for the general solution or solutions to specific similar problems, but considerable work remains to be done before a general solution to the problem class can be justifiably claimed. I'll analyze the full problem further and see what I come up with.)