Pareto Calibration for Pairwise Learning

When learning a score from pairwise comparisons by minimizing a surrogate margin loss, one naturally expects the learned ranking to respect the data: if all comparisons, or even only a strict majority of them, prefer $a$ to $b$, then the score should prefer $a$ as well, known in classical social choice theory as Pareto optimality (PO) and pairwise majority consistency (PMC). Somewhat unexpectedly, recent results show that, unless the comparisons are spherically symmetric, no reasonable convex loss can enforce either axiom, even in the simple setting of linear social choice ge2024axioms,hollender2026enforcing. We reexamine these negative and positive results and identify the missing link as classification calibration. Spherical symmetry is special precisely because it decomposes the pairwise objective into a mixture of such classification problems, so calibration of the loss transfers to PO and PMC. In contrast, without posing restrictions on data, we show no condition on the surrogate alone can restore PO. Then, we introduce Pareto calibration, a joint condition on the loss and the comparison measure that is necessary and sufficient for PO. We give a sufficient condition that can be checked from the observed pairs and the slope of the loss, and show that any surrogate that is calibrated for the classification task can be made to satisfy it on every distribution, either by truncating the loss or by reweighting the data. Based on the theoretical insight build off from this condition, we introduce loss truncation and data reweighing, which improves empirical Pareto calibration result across different model sizes and learning objectives.