Diversity with Axiomatic Guarantees in Polynomial Time: Resolving an Open Problem on Diversity Measures

Mironov & Prokhorenkova (2025) formulated three axioms that a measure of the diversity of $n$ objects, given only their pairwise dissimilarities (with no metric assumption), ought to satisfy: monotonicity, uniqueness and continuity. They showed that no measure in their survey satisfies all three, and constructed two measures that do but are $\mathsf{NP}$-hard to evaluate. They asked whether any measure satisfying the axioms can be computed in practice, or whether all of them are hard. We resolve this open problem in the affirmative. We give an explicit measure $\mathrm{Div}\_\mu$, which satisfies all three axioms and is computable to accuracy $\epsilon$ in time polynomial in $n$, $1/\epsilon$ and the input encoding length. It is not an approximation scheme for some other, harder measure: $\mathrm{Div}\_\mu$ is itself the object that satisfies the axioms. The measure is built in two steps. Maximum diversity in the sense of Leinster & Meckes (2016), namely Leinster-Cobbold diversity maximised over abundance distributions, satisfies all three axioms once integrated over the scale of the exponential similarity matrices, but its single-scale evaluation is $\mathsf{NP}$-hard in general. Replacing it by its doubly nonnegative relaxation keeps every axiom and yields a convex optimization problem, that can be solved to prescribed accuracy in polynomial time. The relaxation is exact when the dissimilarity is of negative type, including Euclidean, ${\ell }_1$ and tree distances. On these distances, $\mathrm{Div}\_\mu$ coincides with scale-integrated maximum diversity, and its evaluation reduces to convex quadratic programming with one-dimensional numerical integration. The measure is practical to evaluate: on synthetic Gaussian embeddings of $1000$ objects, evaluation via the convex quadratic formulation takes a median of $1.67$ seconds using $80$ quadrature nodes.