@leon_p_smith when we speak of the optimality of sorting functions in complexity theoretic terms, we assume a basic cost model to operations such as comparison. if we seek to modify the comparison operation to account for failure, we must then consider that failure typically in real terms is not a simple decontextualized binary event, but something with a more complex measurement apparatus applied to it, particularly since failure is something that interrupts and indeed invalidates the unit cost assumptions applicable to complexity theoretic analysis.

probability theory then comes into play to codify observed events and infer the state of the system. this interplay between complexity theory and probability (or "information") theory is a central debate in the field of cryptography, in which complexity theoretic assumptions are used to describe an imposed cost model, while probabilistic noise is capable of jumping the gap from exponential to undecidable problems, as you may be familiar with from the one-time pad.

randomness generation (and other related operations) in cryptography must seek to—at the same time—resist complexity-theoretic and probabilistic cryptanalysis. this is in fact possible, but it gets to the core of modern knowledge of secrecy. so cryptographic protocols are often framed as a "game" in order to model the interactive nature of exploratory analysis in an online system.

what leads us onwards into infinity here is the reactivity to events and behavior, which generalize the static distributional assumptions common to simple statistics and "information" theory. this is a stateful process—the single bit of information leaked per failure is stateless, which is why it's trivially decidable. it's also not realistic, as no measurement is truly stateless, because every measurement makes a statement not just about itself but about the entire set of observations, and failing to ever update an inferred distribution after observing an event is a trivially suboptimal strategy.

if you begin with the assumption of independent (stateless) dice rolls (which is a hidden source of infinity introduced into a finite system), and to construct a system that assumes the existence of such rolls, then you can get something without undecidability, which is to say, without an infinity. but you most certainly cannot introduce independent dice rolls into a finite system and expect to apply simple complexity theoretic analysis, which is not just a finite system but a deterministic one without hidden state.

i mean, you can, but i don't really accept it as a useful problem. typically game theory has the concept of distinct equilibria instead of optimality, where optimality is not global but given a strategy, which can be observed but not known in advance. and i'm not terribly such a big fan of incorporating concepts like pareto optimality from economics into this space anyway, since i find the swiss bank nobel prize even more of an attempt to frustrate real scientific endeavor than the regular nobel prizes