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 ?
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 ?