The Pareto Threshold

A point in d-dimensional space is Pareto-optimal if no other point beats it in every coordinate simultaneously. Scatter n random points in the d-dimensional unit cube. Some will be Pareto-optimal; some won’t. The question: as n and d both grow, when do non-Pareto points — dominated points — vanish?

There is a critical growth rate for d as a function of n. Below this rate, the number of dominated points diverges. Above it, every point is Pareto-optimal. At the critical threshold, the number of dominated points converges in distribution to a Poisson random variable — the signature of a sharp phase transition.

The transition means that in high enough dimensions, random points are almost always incomparable. No point dominates any other because there are too many criteria to be simultaneously best at all of them. This is the “curse of dimensionality” for multi-objective optimization: as objectives multiply, the concept of Pareto dominance loses its discriminating power.

A finer structure appears when counting points that dominate exactly r others. For r = 1 (points that dominate exactly one other point), the critical dimension is the same as for non-Pareto points. But for every fixed r ≥ 2, the critical dimension changes — and surprisingly, it’s the same for all r ≥ 2. Dominating exactly two others and dominating exactly a hundred others become equally common at the same dimensional threshold.

The phase transition is universal: it depends on the relationship between n and d, not on the distribution of the points (as long as it’s sufficiently regular). The geometry of dominance is controlled by dimension alone.