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.

 

What do you mean I don't "need"  O(n log(n)) sorting ?

It's just the asymptotic cost of sorting by comparison...

I'll have a look into bounded rationality. I was missing the keyword.

EDIT : had a look, the concept is too imprecise to have clear cut paradoxes.

 

Are there known "rational paradoxes", akin to logical paradoxes ? A basic example is the following :

In the optimal search problem, the cost of search at position i is C_i, and the a priori probability of finding at i is P_i. 

Optimality requires to sort search locations by non-decreasing P_i/C_i : search in priority where the likelyhood of finding divided by the cost of search is the highest.

But since sorting cost is O(n log(n)), C_i must grow faster than O(log(i)) otherwise sorting is asymptotically wastefull.

Do you know any other ?

In collectible games, after 1/p trials, there is 1/e = 63% chance to get a desired item.

But a full collection is completed in -ln(p)/p trials in average. For p = 1/n, its n*ln(n).

For instance, getting an outcome with 10% frequency requires in average 10*ln(10) = 23.026 trials.
1% is 460 trials
1/1000 is 6900 trials, etc...

In gacha games, developpers can guarantee you a 10% event in every 10 trials. The market fits irrationality, for a price.
 

I don't remember. Maybe the writing of Scott Alexander brought me here ? Back in the slate star codex days?

Hello

I've been lurking on this website for a few months now. I'm interested in logic, computer science, ai, probability, information... I think I'll fit here. I speak French in every language I know.

I hope I'll be able to publish/discuss/coauthor on lesswrong, or somewhere else.