Highest-Marginal-Gain-First Rule¶
A selection rule — instantiates Greedy Stepwise Commitment
At each step adds the option with the largest immediate improvement per unit of cost it consumes — scoring the gain against what's already been chosen, not in isolation.
Highest-Marginal-Gain-First Rule is the bare selection rule at the heart of greedy: at each step, add the available option that yields the largest immediate improvement per unit of the cost or capacity it consumes. Its distinguishing commitment is that the score is marginal — measured against everything already chosen, not in isolation — so an option's value falls as related options are picked before it. That single property makes the rule both powerful and fragile: when gains genuinely diminish (they rarely reinforce), taking the biggest marginal step each time is provably near-optimal; when the marginal score is a noisy proxy for what you actually want, the rule confidently marches somewhere else.
Example¶
A team is building a model to predict customer churn from 300 candidate features but wants a compact, interpretable model of about ten. Forward selection applies the highest-marginal-gain rule: start empty, and at each step add the single feature that most improves cross-validated accuracy given the features already in the model. "Days since last login" enters first with a large jump. The next round re-measures every remaining feature's gain conditional on that one — and "sessions this week," which looked strong on its own, now adds almost nothing, because it overlaps with what login-recency already captures. Its marginal gain has collapsed even though its standalone value hasn't.
The rule keeps adding the current best-marginal feature until the tenth, watching the size of that best gain as it goes. When the top available gain flattens into noise, that is the signal the score has stopped tracking real predictive value and further picks would be chasing overfit — the moment to stop, not push on.
How it works¶
- Score marginally. Rate each option by the improvement it adds given what is already committed, divided by the cost or capacity it consumes.
- Select the maximum and commit it; break ties by a secondary rule — lower cost, or greater robustness.
- Recompute the marginal gains against the new state; a diminishing-returns objective means most scores drop.
- Watch the top gain. When the best available gain flattens toward noise, the rule has hit the point of diminishing — or spurious — return.
What distinguishes it: the score is recomputed marginally every step, and the rule watches its own gains for the moment they stop meaning anything.
Tuning parameters¶
- Cost/capacity denominator — gain per dollar, per slot, per unit of risk. Changes which "efficient" step wins; the numerator alone ignores what a step consumes.
- Marginal versus standalone scoring — score against the committed set (true marginal) or in isolation (cheaper, but double-counts overlap). The former is what makes the rule correct on diminishing-returns problems.
- Lazy re-evaluation — recompute every option each step, or exploit diminishing returns to skip options whose stale gain already sits below the current best — a large speed-up when the objective is submodular.
- Stopping rule — a fixed budget, or stop when the best marginal gain drops below a threshold: the drift signal that further picks aren't earning their cost.
- Proxy trust — how far to believe the score when it is an estimate, and how large a gain counts as real rather than noise.
When it helps, and when it misleads¶
Its strength is that it is the simplest rule that gets diminishing-returns problems right. On the well-behaved case — a monotone, submodular objective under a size budget — greedy marginal selection is provably within a constant factor, about 63%, of the best possible set.[n1] It is fast, explainable step by step, and exploits diminishing returns for large speed-ups.
Everything rests on the marginal score tracking true value. When gains are supermodular (options reinforce one another), the biggest single step is often the wrong one and greedy walks into a local optimum. When the score is a proxy — a validation metric, a learned estimate — it can drift from the real objective, and the rule dutifully optimises the proxy instead. The tidy per-step gain also invites stopping too late, adding options whose apparent gain is overfit noise. The classic misuse is trusting the marginal ranking without checking whether the objective actually has diminishing returns — or re-running it to rationalise a shortlist chosen in advance. The discipline is to verify the diminishing-returns assumption and to treat a flattening or noisy top-gain as a stop signal.
How it implements the components¶
local_priority_score— the marginal gain per unit cost is the score, recomputed against the committed set at each step.selection_and_tie_break_rule— take the maximum marginal gain, breaking ties toward lower cost or greater robustness.score_drift_monitor— watching the top marginal gain for the point it flattens into noise, or diverges from the true objective, is how the rule knows its score has stopped meaning what it should.
It is the ranking core only: it does not maintain a routing state (Dijkstra-Style Frontier Expansion), track consumable multi-sided capacity or a coverage benchmark (Greedy Assignment Pass, Greedy Set-Cover Heuristic), or enforce a structural invariant (Kruskal-Style Edge Acceptance).
Related¶
- Instantiates: Greedy Stepwise Commitment — the abstract "best marginal step now" core the pattern is built on.
- Sibling mechanisms: Greedy Set-Cover Heuristic · Sorted Candidate Sweep · Greedy Assignment Pass · Nearest-Neighbor Route Extension · Shortest-Processing-Time-First Rule
Editorial Notes¶
Form Classification¶
Form family: Decision, Gate & Allocation
Rationale: Highest-Marginal-Gain-First Rule operates as a case-specific gate, selection, routing, prioritization, or resource disposition because it at each step adds the option with the largest immediate improvement per unit of cost it consumes — scoring the gain against what's already been chosen, not in isolation
Independent corroboration: The frozen evidence defines Highest-Marginal-Gain-First Rule as 'At each step adds the option with the largest immediate improvement per unit of cost it consumes — scoring the gain against what's already been chosen, not in isolation', so its operative form is Decision, Gate & Allocation.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Convergent development
Present-day reach: Multi-domain
Rationale: Greedy selection by marginal gain under a resource constraint, including submodular approximation guarantees, is canonical operations research.
Related originating lineages:
- Computer Science & Software Engineering — Greedy algorithms and algorithmic complexity materially standardized the executable rule.
- Mathematics — Combinatorics and submodular set-function theory provide the guarantee.
Review resolution: Both reviewers independently assign operations_research as the primary originating domain, so that shared primary is retained. Alternate domains are the union of reviewer-identified formative or independently originating lineages; later application settings alone are excluded. The record preserves independently developed forms rather than treating every alternate as mere application. It has established independent use across several domains, but that does not make it domain-free. The encyclopedia entry generalizes the established mechanism without creating a new composite lineage.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
Several sibling mechanisms are this rule with a fixed score plugged in: set-cover uses marginal coverage, nearest-neighbour uses proximity, shortest-processing-time uses job length. The rule itself is silent on which gain to maximise. Choosing a marginal score that genuinely composes toward the global objective is the whole design problem — and the part the rule cannot check for you.
[n1] For maximising a monotone submodular objective under a cardinality constraint, greedily adding the highest-marginal-gain element returns a set within a factor of 1 − 1/e ≈ 0.63 of optimal (Nemhauser, Wolsey & Fisher). The guarantee depends on submodularity — diminishing returns — and does not hold when options reinforce one another. ↩