Part 4 of 12 · 2 min read
Under a budget, rank by value per cost -- but only as far as the estimate is trustworthy
The smartest-looking priority rule can lose to a dumb one the moment its inputs are noisy.
Think of packing a suitcase with a weight limit. You do not just grab your most valuable items first. You grab whichever combination of value and bulk fits the most worth into the bag. The exception is when you are not sure which items are actually valuable. In that case grabbing light things first is safer.
In plain words: prioritisation is choosing the order to spend a limited budget on tasks, the knapsack problem is choosing items with values and costs to maximise value within a budget, and value per cost is the greedy rule that ranks tasks by estimated value divided by cost -- it is the best rule when estimates are accurate, but it is also the rule most damaged by a bad estimate, because the estimate sits in its numerator.
A worked example. With exact value estimates, ranking by value per cost captures 99 percent of the exact optimal value (computed by dynamic programming), well ahead of highest-value-first at 86 percent and arrival order at 58 percent. But push the estimate error to 100 percent and value-per-cost's share falls to 0.84 -- below cheapest-first's steady 0.88, because cheapest-first never looks at the broken estimate at all.
The key lines. From code/mini-explore/prioritise.py:
# from code/mini-explore/prioritise.py
elif policy == "value_per_cost":
order = sorted(idx, key=lambda i: -est[i] / max(tasks[i][1], 1e-9)) # a free task has the best ratio
Read it as: the ranking key is est[i], the possibly noisy estimate, divided by the task's real cost. So the rule is only ever as good as est is accurate. cheapest_first is sorted purely by tasks[i][1], the real cost. It never touches est at all. That is exactly why it does not degrade when the estimate does.
Prioritisation, knapsack, value per cost
Prioritisation is choosing the order in which to spend a limited budget on tasks. The knapsack problem is choosing items with values and costs to maximise value within a budget. Value per cost is the greedy rule that ranks tasks by estimated value divided by cost.
Example: value-per-cost going from the best rule (0.99 of optimal) to the worst of the four (0.84, below cheapest-first's 0.88) as estimate error rises to 100 percent is the concrete case for calibrating an estimate before ranking by it.