There are O(n) sorting methods for max-sorting bounded data like this, with generalized extensions of radix sort. It’s bounded because C_i is bounded below by the minimum cost of evaluating C_i (e.g. 1 FLOP), and P_i is bounded above by 1.
Though yes, bounded rationality is a broad class of concepts to which this problem belongs and there are very few known results that apply across the whole class.
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 ?
There are O(n) sorting methods for max-sorting bounded data like this, with generalized extensions of radix sort. It’s bounded because C_i is bounded below by the minimum cost of evaluating C_i (e.g. 1 FLOP), and P_i is bounded above by 1.
Though yes, bounded rationality is a broad class of concepts to which this problem belongs and there are very few known results that apply across the whole class.
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 ?