OK, so an approximate sorting algorithm in O(n) would do the trick.
The problem then boils down to weither computing the cost of (computing expected cost) is worth the expected gain.
Which goes back to my initial question : is there a rationality paradox ? Maybe simply the fact that 1) computing cost might boils down to the halting problema 2) cost’s cost’s cost… is possibly infinite ?
So P_i/C_i is in [0,1], the precision is unbounded, but for some reason, a radix sort can do the job in linear time ?
There could be pathological cases where all P_i/C_i are the same up to epsilon.
I guess I’m searching for situation where doing cost c, computing c cost c’, etc… Branching prediction comes to mind.
We could dismiss that by saying that if the ratios are the same up to epsilon, then it does not truly matter which one of them we choose.
(Mathematically speaking, we could redefine the problem from “choosing the best option” to “making sure that our regret is not greater than X”.)
OK, so an approximate sorting algorithm in O(n) would do the trick.
The problem then boils down to weither computing the cost of (computing expected cost) is worth the expected gain.
Which goes back to my initial question : is there a rationality paradox ? Maybe simply the fact that 1) computing cost might boils down to the halting problema 2) cost’s cost’s cost… is possibly infinite ?