This demonstrates that an agent can't know its own decision. In this case, predictor can't know its own prediction, and so can't know agent's action, if that action allows to infer the prediction. (And this limitation can't be fought with computational power, so Omega is as susceptable.) For predictors, it's enough to have a fixpoint, to pick any self-fulfilling prediction. But if the environment is playing diagonal, as you describe, then the predictor can't make a correct prediction.
This is not about failure of environment to be decision-determined, the environment you describe simply has the predictor lose for every decision.
(If you consider the question in enough detail, the distinction between the decision-determined problems and other kinds of problems doesn't make sense, apart from highlighting that decision can be important apart from action-instance in the environment or other concepts, that all these are different concepts and decision makes sense abstractly, on its own.)
If the Predictor breaks sometimes, in a way dependent on the algorithm used, not on the decision made, then that's not decision-determined. That's decision-determined-unless-you-play-tit-for-tat, which doesn't count at all.
I think the fact that it's not decision-determined is fairly important, because that means it's not necessarily a Newcomblike problem. Haven't finished the manuscript yet, so I don't know all the implications of that, but I have my suspicions.
I have not seen any place to discuss Eliezer Yudkowsky's new paper, titled Timeless Decision Theory, so I decided to create a discussion post. (Have I missed an already existing post or discussion?)