betaFeedback

WorksMathematics

Scalable Inversion of Contests with Correlated Performances, Including Softmax and Multinomial Probit

Abstract

Multinomial probit choice probabilities over n alternatives are Gaussian orthant integrals, computed by simulation for thirty years, one expensive integral per alternative. Inversion, which is to say determining item attractiveness consistent with a prescribed choice probability vector, is even more difficult and has been considered impractical for correlated contests when n is large. Yet here, for families lying within a grammar including factor, block and hierarchical covariance structures, we exhibit a calibration tested at n = 1,000,000 reproducing probabilities to very high accuracy, even in the extreme tail. We must return to much smaller problems for any performance comparison to be possible due to limitations of the prior art. The Geweke-Hajivassiliou-Keane simulator is the standard (and still appropriate for high rank) but is two hundred times slower already at n = 200, and its measured cost grows roughly as n^2.8 while ours is linear. Furthermore our approach applies to any continuous performance distributions within reason: the Thurstone-Mosteller model families thereby become a practical alternative to logit at modern scale.

Introduction

In a classic setup cutting across many fields, a decision maker faces nn alternatives. Her choice is modeled as a stochastic contest, where each item has some inherent attractiveness (utility) to which noise, often Gaussian, is added to arrive at a random score. The probability of her choosing an item is synonymous with the probability that said item will have the largest score.

The races we consider in this paper come with an additional complexity because the random component for one item is assumed to be correlated with that of another. We are asserting a covariance on performances within a family to be described. It is natural that choice can be influenced by variables common to some or all participants. Sprinters in a bike race might prefer a slower pace. Vacation choices might co-vary with exchange rates.

In psychology an underlying model for choice is required for the computation of counterfactuals: such as the probability that a child will choose waffles if their favorite option, pancakes, were to be removed from the breakfast menu. Increasingly, vision and text machine learning applications present new kinds of selection and routing conundrums, many of which demand choosing from very large collections, such as picking the best model checkpoint from thousands. Indeed, it could be said that the generation of a token is a race, and by that measure, perhaps billions of contests are being held in the time it takes to read this paragraph.

Nature holds races at all scales, such as activation pathways in the brain, reaction sites or lightning strikes. Simulations of physical systems, such as material breaking points, can also be approximated as correlated races. There is a close connection between winning probabilities and local times in Atlas models (ranks of stochastic processes), for another day.

We initially consider the multinomial probit model (an example of the race we speak of) as a point of reference to prior art, even though our method does not impose an assumption of normal performance, nor any particular distribution family for that matter. Write

Ui=μi+εi,ε∼N(0,Σ);(1)U_i = \mu_i + \varepsilon_i,\qquad\varepsilon\sim N(0,\Sigma); \tag*{(1)}

the probability that alternative ii is chosen is

pi=Pr⁡{Ui≥Uj for all j}=Pr⁡{U~≥0},U~j=Ui−Uj,(2)p_i = \Pr\{U_i \ge U_j\ \text{for all }j\} = \Pr\{\widetilde{U} \ge0\},\qquad\widetilde{U}_j = U_i - U_j, \tag*{(2)}

an (n−1)(n-1)-dimensional Gaussian orthant integral. The appeal of this inherently natural generative model has been understood since Thurstone (1927). The Σ\Sigma allows alternatives to be close substitutes, but even for Σ=I\Sigma= I this departs from the choice axiom of Luce (1959) when treated as a model for preference revealed by item removal. The axiom would mandate a simple linear renormalization of probability. But if (2) is calibrated to known pip_i and then one runner is removed, the new race speaks otherwise except for very special situations (such as a symmetric contest).

Although it is out of scope, most readers would not be surprised if the disagreement between counterfactuals implied by (2) in this manner and Luce’s Choice Axiom is often in the right direction for a diverse list of applications (Cotton, 2026).2 Practitioners in signal processing and demand estimation have had their own reasons for preferring Gaussian races. Often, this form is independently motivated. It may be demanded by closure. It is consistent with continuous time models and plays better with linear gaussian networks and rating systems. It may simply make more sense.

It is possible to reverse into generative race models that satisfy Luce’s Choice Axiom. For instance, we might assume runners have exponential performances (not offset, but with different hazard rates), or we can choose Gumbel-noise variants of (2), or any monotonic transformation of the same. This is often done unwittingly, however, when simple linear renormalization of probability is applied. It is desirable to develop numerical methods that support all possibilities to remove the evidenced temptation to select a model based on its analytical tractability.

An important part of providing that utility is the share inversion: a partial calibration (fixing the covariance). As a finer point, the inversion is a map from a probability vector back to an equivalence class of races that yield the same probabilities. The raw covariance is over-parameterized, and there is an even more obvious translation symmetry since only relative performance matters.

A key integral

Unfortunately, the computational curse has been understood since Thurstone himself, and it already bites in his simplest case. In the original psychometrics terminology, (2) with equal discriminal dispersions and zero correlations is Thurstone’s Case V. Later Mosteller (1951) showed that the correlations may be relaxed from zero to any common value without changing the method, and supplied the estimation and testing apparatus, which is why the family carries both names.3 The integral (2) has no closed form, and estimation needs it and its derivatives at every trial value of the parameters. It is no surprise that the considerably easier logit models tend to be far more popular than probit, not only for calculations such as their obvious extension to permutation probability, but also in the very architecture of most of the world’s neural networks.

The workhorse answer to the challenge posed by (2) and calibration in particular (for which raw Monte Carlo is clearly problematic) is the GHK simulator of Geweke (1989), Börsch-Supan and Hajivassiliou (1993), Keane (1994) and Hajivassiliou et al. (1996). For the focal alternative ii, GHK Cholesky-factors the covariance of the (n−1)(n-1) utility differences Ui−UjU_i-U_j and writes the orthant probability as a nested sequence of one-dimensional truncated normal probabilities, each conditioning on draws for the previous coordinates — the very recursion Domenich and McFadden (1975) wrote down deterministically (their eq. 4.32) and set aside as too cumbersome for estimation.

GHK’s contribution was to simulate it. Averaging RR such importance weights gives an unbiased, smooth estimate of one pip_i at cost O(n2)O(n^2) per draw. The estimator made maximum simulated likelihood practical and it remains the default in textbooks (Train, 2009). Its costs are also well appreciated. Error shrinks as O(R−1/2)O(R^{-1/2}) and the log of a simulated probability is biased at O(1/R)O(1/R). The gradients inherit the simulation noise too and a full probability vector costs nn separate runs. A single likelihood contribution needs only the chosen alternative’s probability, so the nn-fold cost falls not on the individual log-likelihood but on everything else estimation touches: share inversion, aggregate-share and market models, prediction and welfare across the menu, and the derivative of any of these with respect to all nn utilities.

This paper takes a different route to the same object, following [17] initially. Also in keeping with that paper, we will adopt once and for all a min-wins convention. Performances are to be considered golf scores, or running times where the smallest is the winner. To avoid confusion with utility, we write

Xi=−UiX_i=-U_i

and we consider the probability that any given XiX_i takes the lowest value.

Our numerical approach requires, but does not stop with, an old idea: conditioning on the winning performance. Indeed Domenich and McFadden (1975) write the general random-utility choice probability as a one-dimensional integral over the winning utility (their eq. 4.7, restated as eq. 4.26 although they did not take the step to turn that into a method as with [17]). Without special structure, the integrand conceals a multivariate calculation, only the Weibull case yields a convenient form, and the multiple-choice probit generalization was, in their words, “computationally intractable.”

Under independence the integrand remarked on in [23] really is a density times a product of univariate distribution functions, and they price exactly that form for independent Cauchy shocks (their eq. 4.38) one alternative at a time, concluding it is obtainable by “straightforward, but costly” numerical integration. The sequential-conditioning decomposition that GHK later simulates (their eqs. 4.27–4.32, set aside as too cumbersome for iterative estimation) was present in 1975, and judged impractical.

The expression of winning probability for the case of independent performances is standard in competing-risks calculus: G=∏kSkG = \prod_k S_k is the all-causes survival and fi/Sif_i/S_i the cause-specific hazard, so pi=∫G(fi/Si)p_i = \int G\left(f_i/S_i\right) is the classical cause-probability formula ([28]). [19] considering random-utility models treat the expected maximum as potential and its gradient as probabilities. Choice probability is an integral along the common maximum level.

Our starting point is similarly this well-beaten integral:

pi=∫fi(x)Pr⁡{Xj>x for all j≠i∣Xi=x} dx,(3)p_i = \int f_i(x)\Pr\{X_j > x\text{ for all }j \ne i \mid X_i = x\}\,dx, \tag*{(3)}

where fif_i is the density of XiX_i. The simple interpretation is that we integrate over the winning time xx, requiring every rival to come in slower. When performances are independent, the conditional probability factorizes into a product of marginal survivals.

pi=∫fi(x)∏j≠iSj(x) dx,(4)p_i = \int f_i(x)\prod_{j\ne i} S_j(x)\,dx, \tag*{(4)}

with SjS_j the survival of XjX_j. Under the covariance grammars developed below the same product holds conditional on a few shared variables and is then averaged over them, so the winning-value integral stays one-dimensional and correlation adds only a low-dimensional outer integral.

Contribution

For independent performances [17] computed (4) for all nn on a lattice in a novel manner by building the field ∑jlog⁡Sj\sum_j \log S_j once and dividing each alternative out, and inverted the map from probabilities back to μ\mu. Because performances were atomic distributions represented on a lattice a “multiplicity calculus” that tracked the expected number of ties conditioned on the winning score was required. That method is robust to reasonably pathological choices of performance distributions defined on a lattice (lumpy, gaps and so on) so it is preserved in our software.

The present approach trades some of that flexibility for an implicit assumption that performances are smoothly varying (in the loose sense) in order to lean more heavily on quadrature and achieve, empirically, much tighter inversion. The present paper also extends the field construction to correlated performances by conditioning. Whenever Σ\Sigma makes performances independent given a few shared variables, the field factorizes and all nn probabilities cost O(nLQ)O(nLQ) for a lattice of LL points and QQ quadrature nodes. The conditioning technique per se is standard, needless to say.

It tends to be the case in financial practice and elsewhere that structured covariance is assumed. We do not claim a general solution for arbitrary covariance matrices, but nor do these tend to be advocated [49]. Our intent is that the grammars here cover the structured families in typical use. The first six rows of Table 1 are represented without covariance fitting.

modelcovariance grammarsource
Luce / softmaxindependent, minimum-Gumbel base, D=π2/6D = \pi^2/6exact identity
Thurstone–Mosteller (Mosteller, 1951)independent, normal baseCotton (2021)
factor multinomial probitVV′+diag⁡(D)VV^{\prime} + \operatorname{diag}(D)§4.1
teams, conferencesblocks: rank-rr effect per cluster§4.2
market plus sectorsnested: blocks ×\times global factor§4.2
hierarchiestree: uniform shared effects§4.3
dense Σ\Sigmafitted grammar + residual factors (approx.)§6

Table 1. The covariance grammar.

equal groupsleading multiplicityrank cuts the tieTV against grammar
21no2.4×10−42.4 \times10^{-4}
32no2.8×10−42.8 \times10^{-4}
43no1.8×10−41.8 \times10^{-4}
65yes1.0×10−21.0 \times10^{-2}
87yes3.7×10−23.7 \times10^{-2}
1211yes4.0×10−24.0 \times10^{-2}

Table 1.

ensemblemed TVq90 TVworst TVmed ∣p−p^∣|p - \hat{p}|
block equicorrelation2.5×10−32.5 \times10^{-3}3.0×10−33.0 \times10^{-3}3.2×10−33.2 \times10^{-3}1.4×10−51.4 \times10^{-5}
factor + sparse links2.9×10−32.9 \times10^{-3}6.7×10−36.7 \times10^{-3}1.6×10−21.6 \times10^{-2}1.9×10−51.9 \times10^{-5}
sparse-precision graphical4.5×10−34.5 \times10^{-3}5.6×10−35.6 \times10^{-3}6.0×10−36.0 \times10^{-3}1.5×10−51.5 \times10^{-5}
Wishart1.2×10−21.2 \times10^{-2}1.4×10−21.4 \times10^{-2}1.5×10−21.5 \times10^{-2}2.6×10−52.6 \times10^{-5}
AR(1)4.6×10−24.6 \times10^{-2}8.4×10−28.4 \times10^{-2}1.5×10−11.5 \times10^{-1}7.0×10−57.0 \times10^{-5}
residuals (dense-strong)6.8×10−26.8 \times10^{-2}8.6×10−28.6 \times10^{-2}9.2×10−29.2 \times10^{-2}2.5×10−42.5 \times10^{-4}

Table 1.

methodn=10n = 10 timen=10n = 10 TVn=30n = 30 timen=30n = 30 TVtail
lattice race2.5 ms1.8×10−41.8 \times10^{-4}4.7 ms8.3×10−48.3 \times10^{-4}0.07
Genz, full vector46 ms1.8×10−41.8 \times10^{-4}1.40 s8.3×10−48.3 \times10^{-4}0.07
frequency, matched time—3.8×10−33.8 \times10^{-3}—1.0×10−21.0 \times10^{-2}0.45, 2 zeros
frequency, 10× time—9.2×10−49.2 \times10^{-4}—2.0×10−32.0 \times10^{-3}0.21
Mendell–Elston2.0 ms1.8×10−31.8 \times10^{-3}18 ms3.2×10−23.2 \times10^{-2}1.30
Clark-type1.4 ms1.1×10−21.1 \times10^{-2}17 ms1.6×10−21.6 \times10^{-2}1.33

Table 1.

nnlattice raceGHK, R=103R = 10^{3}GHK, R=104R = 10^{4}
timeTVtailtimeTVtailtimeTVtail
102.3 ms1.8×10−41.8 \times10^{-4}—1.0 ms8.4×10−38.4 \times10^{-3}—8 ms2.1×10−32.1 \times10^{-3}—
507.0 ms1.7×10−31.7 \times10^{-3}0.1121 ms4.2×10−24.2 \times10^{-2}1.10214 ms1.2×10−21.2 \times10^{-2}0.29
20025 ms2.4×10−32.4 \times10^{-3}0.15436 ms3.2×10−23.2 \times10^{-2}1.504.8 s1.2×10−21.2 \times10^{-2}0.35

Table 1.

estimatorRMSE (median)RMSE (mean ±\pm s.e.)median fit time
analytic-gradient smoothed inversion0.01680.0168 ±\pm 0.00062.4 s
MSL, R=100R = 1000.02860.0280 ±\pm 0.00063.5 s
MSL, R=1000R = 10000.01840.0185 ±\pm 0.000539.9 s

Table 1.

Within such a class of covariance matrices (we will term it the factor grammar) the derivatives are computed in the same pass at the same cost. This yields Jacobian–vector products and own-survival curves. The cost is also O(nLQ)O(nLQ), where again LL dictates the lattice size and QQ the number of quadrature points.

We will show that the Jacobian is a weighted graph Laplacian. It is applied as an operator and is never materialized in the code. The block and nested kernels materialize their Jacobians, and the tree’s cross-cluster block is approximate. The most important distinction from the prior art is that there is no need to run the entire algorithm for each choice of ii, a point we will return to shortly when discussing the existing methods.

The error is controlled by quadrature. It is deterministic for the Gauss–Hermite rules and reproducibly randomized for scrambled-Sobol nodes.

Our caveats aside regarding the general covariance problem, we provide in the accompanying code a method for fitting arbitrary covariance to the grammar we specify, as developed in §6. However, for truly high rank problems where accuracy is paramount, we make no claim of superiority over GHK; on the contrary, it should remain the appropriate choice if the problem at hand fails to establish otherwise.

Our chief contribution is scaling. We seek to bring probit modeling to a qualitatively different problem space. To put it in perspective, we note that on one laptop, the forward computation of all-nn probabilities from known utilities, assuming a rank-one factor and using the Rust kernels, takes 0.18, 2.7, and 29 seconds respectively for n=104,105,106n = 10^4, 10^5, 10^6. That speed was unthinkable previously.

The inversion is the tougher problem yet at n=106n = 10^6 this takes not much more than a minute for the independent case, and the rank-one factor problem can be solved at this extreme scale also, in around 20 minutes.

Comparisons die well before this scale, as far as we know. Other approaches are considered in detail presently, but briefly, if the comparison set is taken to be those approaches providing smoothness suitable for inversion, GHK is generally regarded as leading that category.

It cannot compete. We estimate a two order of magnitude speed gap at n=200n = 200 that is steadily worsening with nn. GHK’s empirical complete-vector cost is superquadratic and steepening as we pass beyond that scale.4 In fact in our tests, the gap to our method grows almost quadratically with nn beyond n=200n = 200 because in that regime GHK scales at roughly n2.8n^{2.8} while our shared-field pass is approximately linear in nn at fixed lattice and node budgets. We have provided in Appendix A some brave extrapolations of GHK performance to 10410^{4}–10610^{6} alternatives and the wall clock time ratios, so dramatic as to not be reproducible in any reasonable time.5

We proceed as follows. Section 2 places the method among the alternatives. Section 3 gives the independent lattice race, which is the same problem considered in [17] solved slightly differently, as noted. Then Section 4 extends this across the covariance grammar. The grammar allows the set of covariance matrices to include block and tree structures with global and local factors, each one written out as a recursion. It may be of interest to those in the financial community that this structure includes that assumed in Hierarchical Risk Parity.6

Section 5 carries the key analytical insight and presents the Jacobian operator and its inversion. Section 6 reduces dense covariance to the grammar family, approximately, and reports accuracy per named random-correlation ensemble. Section 7 contains the benchmarks.

The alternatives

Deterministic quadrature. [24] transformed the orthant integral to the unit cube and integrated by adaptive and quasi-Monte Carlo rules. This is somewhat of a standard in R because mvtnorm chooses this path, presumably for accuracy. It certainly is accurate. The benchmark below confirms that: its answers agree with our lattice to within the sampling noise of the simulation that both are checked against. However, the disadvantage lies in what a single call returns. Genz’s method evaluates one orthant probability only, which is the win probability of one alternative. Pricing a contest requires all nn of them, so the routine must be called nn times, and each of those calls is itself an (n−1)(n - 1)-dimensional integral over the focal alternative’s difference orthant. At n=30n = 30 the complete vector therefore costs about three hundred times what the lattice costs, and since the work per call also grows with nn, that ratio widens as the field grows.

Frequency simulation. The crude frequency estimator of [31] counts argmax draws. It is unbiased for the whole vector at once but not smooth in parameters, and its per-entry relative error explodes for small πi\pi_i. Measured below: at wall clock matched to the lattice it carries twelve to twenty times the total-variation error, records zero counts on tail alternatives at n=30n = 30, and at ten times the budget remains a factor of two to four behind.

GHK. As described above. It is smooth in parameters but like Genz it prices one alternative per run. Despite this, GHK is seemingly the most widespread. Stata’s cmmprobit manual states that the likelihood evaluator “implements the Geweke–Hajivassiliou–Keane (GHK) algorithm to approximate the multivariate distribution function” (StataCorp, 2023; [21]), and the command’s entire intmethod menu (Hammersley, Halton, or pseudorandom point sets) selects only the sequence feeding the same simulator. The market-leading implementation offers no non-GHK method at all. R’s mlogit and mvProbit also default to GHK (Croissant, 2020), and the GHK-based mvprobit of Cappellari and Jenkins (2003) carried the method into applied Stata work at large.

Stern. Stern (1992) is the closest ancestor of the construction used here. He split the error into an independent normal component and a correlated remainder, observed that conditional on the remainder the alternatives are independent so that the choice probability is an analytic product of univariate normal c.d.f.s, and averaged that analytic expression over Monte Carlo draws of the remainder. The motivation was also smoothness, and similarly, Stern is testimony to a common willingness to accept a substantial per-draw cost to buy a simulator that could be differentiated. Our work differs because the conditioning variables here are a low-dimensional factor structure chosen so that the outer integral is quadrature rather than simulation: deterministic Gauss–Hermite by default, and seeded scrambled Sobol when the integrand is sharp, which replaces Monte Carlo noise with reproducible randomized-quadrature error rather than eliminating integration error outright. Either way there is no per-draw sampling noise in the returned probabilities, and, as we will discuss, the conditional problem is solved on a lattice that returns all nn alternatives from a single sweep rather than one probability per run, with derivatives coming out of that same sweep.

Distributionally robust choice. A different escape from the orthant integral fixes only the first two moments of the utilities and prices the extremal joint distribution: the cross-moment model of Mishra et al. (2012) computes, by semidefinite optimization, the choice probabilities under the moment-feasible distribution that maximizes expected agent utility, and Ahipasaoglu et al. (2019) reformulate that computation as a convex program that scales to many alternatives. This answers a genuinely different question from ours — the worst case over a moment class rather than a specified law, with representative-agent rather than distributional semantics — so the two are complements: that family avoids ever specifying the joint distribution, while this paper prices and inverts the distribution the modeller actually specifies.

Bayesian data augmentation. Albert and Chib (1993) and McCulloch and Rossi (1994) sidestep the integral entirely by Gibbs sampling the latent utilities; Imai and van Dyk (2005) implement the marginal data-augmentation version in the MNP package, and Loaiza-Maya and Nibbering (2022) carry the Bayesian route to large choice sets by variational methods. For Bayesian inference this is a complete and often excellent answer. It is simply answering a different question than the one benchmarked here: the cost moves into the Markov chain, the likelihood surface is never formed, and choice probabilities appear only as posterior functionals, so there is no pricing call to time or to check.

Analytic approximations. Clark (1961) matched moments of pairwise maxima; Mendell and Elston (1974) and Solow (1990) approximate by sequential conditioning on first and second moments. These are fast, sometimes startlingly accurate, and carry no error control, and the benchmark below measures all three properties at once: Mendell–Elston prices the n=10n = 10 vector in two milliseconds within 2×10−32 \times10^{-3} of the reference, then drifts to 3×10−23 \times10^{-2} at n=30n = 30 with tail probabilities off by a factor of nearly four, and nothing in the output announces the change. The Clark-type recursion behaves alike. The family is current practice, not history: Bhat (2011) builds the MACML estimator on precisely these approximations, and the Rprobit package implements it (Bauer, 2024), with its asymptotics examined by Batram and Bauer (2019). Expectation propagation is the modern member of the same family. We benchmark representative sequential moment approximations through the classical members; MACML’s composite-likelihood construction around its analytic ingredient is its own estimator and is not itself benchmarked here.

Minimax tilting. [6] computes single Gaussian rectangle probabilities with bounded relative error deep into the tails, in dimensions up to roughly a thousand. It is the accuracy reference, and we use it as the referee for our own tail claims. Like GHK it prices one alternative per run, so a whole race costs nn runs, and which method is preferable depends on the question. For a single tail probability Botev’s is the right tool and this paper defers to it. For the all-nn vector it is both slower and less accurate than the lattice at every size measured: at n=50n = 50, 0.25 s against 0.07 s and 2.5×10−32.5 \times10^{-3} error against 2.9×10−52.9 \times10^{-5}; at n=200n = 200, 25.8 s against 0.29 s and 1.4×10−31.4 \times10^{-3} against 4.1×10−54.1 \times10^{-5}. Raising the tilting sample to R=104R = 10^{4} narrows the accuracy gap and widens the time one: at n=200n = 200 that is 37.9 s, a hundred and thirty times the lattice’s cost and still an order of magnitude short of its error.

The reader will note the common thread. Smoothness has been, and continues to be, bought at a significant performance cost. The cost, compared to Monte Carlo, is that one alternative is computed at a time, and this cost seems to have been accepted as unavoidable. We will show that it is not, at least within the covariance grammar we specify.

We offer a different Faustian bargain that will often, but not always, be preferable. In exchange for the assumed covariance structure, which is very often assumed anyway, the user does not have to choose between speed, accuracy, scale, or smoothness. They can have all four, and very often they need them for downstream modeling tasks beyond share inversion, such as welfare analysis, game theory, and propagation of derivatives to other parts of a system (for ratings or belief networks).

The lattice race

The application programming interface for [17] asked for numerical representation of performance densities on an equi-spaced lattice. The current method instead requires this assumption in the form of user-supplied functions.7

Emphasizing again our lowest-score-wins convention (arguably somewhat unfortunate for the special case of probit), let Xi=μi+σiϵiX_i = \mu_i + \sigma_i \epsilon_i with ϵi\epsilon_i i.i.d. from a standardized base density (normal, Gumbel, or any density supplied as code), and write fif_i, SiS_i for the density and survival of XiX_i. From here on, μi\mu_i is to be considered a running time location, the negative of the introduction’s utility location. For avoidance of any doubt, raising it makes contestant ii worse and lowers pip_i. Inversion returns time locations, and utility coefficients are their negation.

The algorithm evaluates (4) on a lattice x1<⋯<xLx_1 < \cdots< x_L:

  1. compute log⁡Sj(xℓ)\log S_j(x_\ell) and log⁡fj(xℓ)\log f_j(x_\ell) for all j,ℓj,\ell;

  2. accumulate the field L(xℓ)=∑jlog⁡Sj(xℓ)L(x_\ell) = \sum_j \log S_j(x_\ell);

  1. for each ii, form the integrand fi(xℓ)eL(xℓ)−log⁡Si(xℓ)f_i(x_\ell)e^{L(x_\ell)-\log S_i(x_\ell)}, which is contestant ii’s density times everyone else’s survival, with ii divided out of the shared field in log space;

  1. sum times the lattice spacing, and normalize the vector.

The cost is O(nL)O(nL): the field is built once, not once per contestant.

Details of an adaptive lattice choice

We write

L(x)=∑jlog⁡Sj(x)L(x) = \sum_j \log S_j(x)

for the log survival field, evaluated once per lattice point across all contestants, each contestant’s leave-one-out product is a subtraction rather than a division:

∏j≠iSj=exp⁡(L−log⁡Si).\prod_{j \ne i} S_j = \exp(L-\log S_i).

This is what makes one sweep price the whole field, since the alternative is to re-form an (n−1)(n-1)-fold product for each of nn contestants. It is also what keeps the far tail finite. There, every SjS_j is small enough that ∏jSj\prod_j S_j underflows to zero in double precision, and the division form returns 0/0 for any contestant whose own survival has underflowed; a single such point makes the integral undefined. As a sum of logarithms LL is an ordinary negative number of order −103-10^3, and L−log⁡SiL-\log S_i is a finite difference.8

We are economical with the lattice points. The lattice must cover the winning time, not the spread of abilities. However hopeless a contestant is, it wins only by finishing in the range where winning times fall; thus, outside that range, the integrand is negligible. In contrast, a lattice that was stretched across the whole ability span would waste compute as most of its points lie where nothing happens.

There is a key defensive measure taken, however. Let

G(x)=1−∏jSj(x),G(x) = 1-\prod_j S_j(x),

the probability that somebody has finished by xx, which is the distribution function of the winning time. It is built from the caller’s own base survival (rather than a normal surrogate, say), and it is made conservative. For the lower endpoint every contestant is placed at its most favourable conditional location, and for the upper endpoint at its least favourable.

Those componentwise extremes need not occur at any single factor node, which is what makes the result an envelope: wider than any one conditional race requires, and covering every conditional race represented by the retained factor nodes.9

Factor realizations outside the node set belong to the outer quadrature error, not to the lattice window. Solving G(x)=δG(x)=\delta and G(x)=1−δG(x)=1-\delta by bisection gives the two ends of the region the race is decided in. The lattice is placed there with two standard deviations of padding at each end for safety. At the achieved δ\delta (which may be relaxed, as described next), the truncated tails are controlled separately from the bulk discretization error, and in the benchmark configurations they lie below the accuracy floors reported shortly.

We also need a starting interval known to contain the answer. Bisection halves an interval repeatedly and finds the point where GG crosses a given level only if that point lies inside the interval it began with. A fixed starting interval does not always contain it. Nine standard deviations beyond the outermost contestant is wide enough for a Gaussian race, whose survival decays exponentially, but not for a base with polynomial tails: with Student-tt performance at four degrees of freedom, the point where GG falls to 10−1210^{-12} lies 1456 standard units out.

Bisecting an interval that excludes the crossing neither fails nor warns. It converges to whichever endpoint is nearer and returns that instead. Each endpoint is therefore moved outward, doubling the distance each time, until GG at the lower endpoint is at most δ\delta and GG at the upper endpoint is at least 1−δ1-\delta. Only then is the interval bisected.

A finer point is that δ\delta cannot always be honoured. The lattice has a fixed number of points, chosen by the caller, spread evenly across whatever window the quantiles ask for, so a wider window means coarser spacing. The two error sources therefore move in opposite directions: shrinking δ\delta removes truncated tail mass but adds discretization error in the bulk, where nearly all of the probability is.

An example is instructive. For a Student-tt race, δ=10−12\delta=10^{-12} asks for a window some 1456 standard units wide, which at the default 257 points places them 5.7 standard units apart. That is far coarser than the scale the integrand varies on. This coarseness causes much more error than would be sustained by missing the tiny tail.

So δ\delta is treated only as a request. If the window it asks for cannot be covered at a spacing of half the smallest performance standard deviation in the field, δ\delta is multiplied by one hundred and the window recomputed, repeating until the spacing is affordable.10

We determined that it is very important to use the caller’s own survival rather than a normal surrogate. Continuing the Student-tt example, a base at ν=2.5\nu=2.5 has polynomial tails, and a normal envelope cuts the window short of them: at n=40n=40 that costs 5×10−35 \times10^{-3} of total variation, against 5×10−55 \times10^{-5} when the true survival sets the window.

Placing the lattice on the bulk is also what makes small lattices work. Thirty-three points on this window reach an accuracy that five hundred points spread across the ability span cannot, because the span window truncates the winner’s tail and its error cannot fall below about 6×10−116 \times10^{-11} however many points are added to it. We found that on fields with a large number of extreme longshots, the bulk window is a hundred times more accurate for the same number of points.

Derivatives

A key output of the pass is the derivative of winning probability with respect to ability:

∂pi/∂μj.\partial p_i/\partial\mu_j.

This can be used in several ways. A full Newton method can wield the entire Jacobian, although we do not recommend that for large nn. The diagonals can be used to precondition. And a single row of the Jacobian can be used for an estimation score. Section 5 interprets the matrix; what matters here is how it is computed.

Prior to that we mention a lesson from the implementation, albeit one that might strike some readers as obvious: a derivative is accurate only if it differentiates the map that was actually evaluated, rather than the continuum integral that map approximates. This is not a fine point. The lattice should be the very same one. Both the full Jacobian and the single-row version build their window through the routine the forward pass uses, so the two integrate over identical points.

Another potential trap lies in the fact that the diagonal should be integrated rather than assumed. Raising μi\mu_i moves contestant ii’s own density, contributing ∂fi/∂μi\partial f_i/\partial\mu_i to the integral. In the continuum this need never be computed, because a common shift moves no probability, so each row sums to zero and the diagonal follows from the off-diagonal entries. However, on a finite lattice that identity holds only to quadrature accuracy. For this reason, we determined that the diagonal should be computed directly.

In a similar vein, the normalization must be differentiated too. The lattice masses do not sum to one exactly. The returned probabilities are p=a/Tp = a/T with T=1TaT = \mathbf{1}^{\mathsf{T}}a. Differentiating that quotient gives (A−p1TA)/T(A - p\mathbf{1}^{\mathsf{T}}A)/T, where A=∂a/∂μA = \partial a/\partial\mu. The correction term vanishes in the continuum, where TT is constant. It does not vanish on a lattice.

The test is finite differences of the forward map itself: shift μj\mu_j, re-price the field, and compare the change in pp against the computed column. Write JJ for the Jacobian built as above, and J0J_0 for the continuum version, which takes its diagonal from the zero-row-sum identity and omits the normalization correction.11

Columns and row sums do not behave the same numerically. Columns sum to zero identically. The quotient divides by the lattice total, so 1TJ=0\mathbf{1}^{\mathsf{T}}J = 0 whatever the lattice does, at 6×10−176 \times10^{-17} from the coarsest grid to the finest. Rows sum to zero only as the quadrature converges (translation invariance is a property of the integral, but not the actual sum as implemented). The row sum discrepancy is a useful diagnostic.12

Benefits of maintaining the survival field

Two byproducts are cheap once the field is built.

The first is the density of a dead heat, which is to say the chance that ii and jj finish together, per unit of finishing time. It is one more sum over the same lattice. Section 5 shows that this quantity is exactly the off-diagonal entry of the derivative matrix ∂p/∂μ\partial p/\partial\mu, so one computation answers both questions.

The second is a removal counterfactual: the probability that jj wins once ii is taken out of the field. In the continuum this is one more division, since deleting ii simply drops SiS_i from the product. However, numerically, to continue our theme, care is required. Suppose the lattice is placed where the original winner finishes, but the survivors of a deletion need not finish there. So, for example if we remove a dominant favourite, the race is decided where the original runner-up would have finished and it is entirely possible that the winner-bulk lattice would not reach that zone.13

The covariance grammar

Now we turn to a fixed set of covariance choices that can be accommodated with extremely high accuracy. Naturally, some structures make contestants conditionally independent given a few shared variables. Without that, we have no algorithm so, in increasing order of hierarchy, we consider:

  1. a global factor,

  2. factors per cluster, and

  3. a tree of uniform shared effects.

Each keeps the shared field and the O(nLQ)O(nLQ) volumetrics but they come with additional numerical lattice considerations, the topic of this section. Each is exact given its structure; estimating that structure from data is a separate problem we do not address here. The approximate reduction of a dense covariance to this family is considered, but deferred to §6.

Factor covariance with sharpness as a guide

Let X=μ+Vf+diag⁡(D)ϵX = \mu+ Vf + \operatorname{diag}(\sqrt{D})\epsilon with f∼N(0,Ik)f \sim N(0,I_k) independent of ϵ\epsilon, so Σ=VV′+diag⁡(D)\Sigma= VV^{\prime} + \operatorname{diag}(D). Conditional on ff the performances are independent with means μ+Vf\mu+ Vf, and

p=∑qwqpind⁡(μ+Vfq),(5)p = \sum_q w_q p^{\operatorname{ind}}(\mu+ Vf_q), \tag*{(5)}

a QQ-node quadrature over runs of the independent algorithm at a cost of O(nLQ)O(nLQ).

We are merely averaging the independent race over the shared luck, so to speak. This device is far from new, of course; indeed Butler and Moffitt (1982) built exactly this quadrature for the one-factor random-effects probit. The lpRR/slpRR interfaces of mvtnorm integrate over the factor dimensions of BB′+diag⁡(D)BB^{\prime} + \operatorname{diag}(D) by Monte Carlo. As we noted at the outset, each of those integrals returns only one alternative’s probability, which is one reason their performance dies at scale.

The survival field changes that: one pass shares the survival product across all nn alternatives, and §7 measures the difference against the per-alternative version of this same quadrature. The same pass returns the own-parameter slopes ∂pi/∂μi\partial p_i/\partial\mu_i at no extra cost (negative in this min-wins convention: raising a time mean lowers the win probability), which §5 uses to precondition the inversion.

However, we must pay attention to numerical issues and lattice choice in particular. The integral over ff is kk-dimensional, and experiments have taught us that the rule that discretizes it has to depend on kk and the shape of the integrand.

Gauss–Hermite is the natural rule for a single Gaussian dimension. Applying it in kk dimensions means taking every combination of its nodes, which costs qkq^k of them. At the default q=15q=15 that is 3,375 nodes at rank three and 50,625 at rank four, but 759,375 at rank five. So the product rule is used while it stays under 10510^5 nodes, which in practice means rank four and below.

The other consideration is sharpness. What decides the race is not how far the factor moves a contestant but how far it moves contestants apart: a factor loading every contestant identically shifts the whole field and changes nothing, however large it is. The intrinsic statistic is therefore pairwise,

sΔ=max⁡i<j∥Vi−Vj∥Di+Dj,s_{\Delta} = \max_{i<j} \frac{\lVert V_i - V_j\rVert}{\sqrt{D_i + D_j}},

the shared variation available to a contrast against that contrast’s own noise, but computing it is O(n2k)O(n^2 k). The implementation first gauge-fixes the loadings, V←PVV \leftarrow PV with P=I−1n11TP = I - \frac{1}{n}11^{\mathsf{T}} — a common loading column adds the same draw to every contestant and cannot move an argmin, so the centered matrix prices the identical race, and every downstream decision becomes invariant under V↦V+1cTV \mapsto V + 1c^{\mathsf{T}} — and then dispatches on the linear-time bound

strigger=2max⁡i∥(PV)i∥Di≥sΔ,s_{\mathrm{trigger}} = \sqrt{2}\max_i \frac{\lVert(PV)_i\rVert}{\sqrt{D_i}} \ge s_{\Delta},

which follows from the triangle inequality on centered rows. Notice that the bound cannot miss a pair whose contrast sharpness exceeds the threshold as false positives cost extra nodes, not error.

We also remark that the centered maximum is a common-shift-invariant proxy for factor-space smoothness, but not intended as a complete characterization of it. The dispatcher is therefore wise to use the conservative side of it. But nothing needs to be guessed and everything follows from VV and DD before any integration is done.

When the trigger is large the factor draw all but decides some pairwise contest, the quantity being averaged over ff is close to a step function, and a rule built for smooth integrands converges slowly on it.14

A fixed rule of fifteen nodes per dimension can then miss up to five percent of the total variation, and the error is easy to overlook because the usual check does not see it. Adding lattice points does not reduce it: the lattice discretizes the finishing time, while the loss is in the average over ff, so refining LL returns a stable answer that is stably wrong.

We implement two remedies. The node order scales with the trigger rather than staying fixed, within the rank limit above. And past a trigger of 3 at rank two or more the family changes, scrambled Sobol points replacing the product rule, since more nodes of a smooth rule is the wrong medicine for a near-step integrand. Rank one with extreme sharpness gets a third treatment, an equal-weight grid on quantiles, because Gauss–Hermite clusters its nodes near the centre and that is the wrong place when the integrand is nearly a step.

Blocks and nested covariance

The implementation also supports groups. Assign contestant ii to cluster c(i)c(i) with loading vi∈Rrv_i \in\mathbb{R}^r and let

Xi=μi+vi′ac(i)+Di ϵi,ac i.i.d. N(0,Ir).(6)X_i = \mu_i + v_i'a_{c(i)} + \sqrt{D_i}\,\epsilon_i,\qquad a_c\ \text{i.i.d. }N(0,I_r). \tag*{(6)}

This is a block-diagonal rank-rr-plus-diagonal covariance. It can be useful for teams, conferences, and sibling products, for example. And it falls into our framework because, conditional on its own cluster’s effect, a contestant is independent of its teammates. Distinct clusters are independent altogether so the joint survival factorizes across clusters,

Pr⁡{Xj>x for every j}=∏cGc(x),Gc(x)=Ea∏j∈cSj(x∣a)=∑qwqeSc(x,aq),(7)\Pr\{X_j > x\ \text{for every }j\} = \prod_c G_c(x),\qquad G_c(x) = \mathbb{E}_a \prod_{j\in c} S_j(x\mid a) = \sum_q w_q e^{S_c(x,a_q)}, \tag*{(7)}

with Sc(x,a)=∑j∈clog⁡Sj(x∣a)S_c(x,a) = \sum_{j\in c} \log S_j(x\mid a) the cluster’s conditional log-survival. To say this another way, Gc(x)G_c(x) is just the probability that every member of cluster cc survives past xx, with the cluster’s shared luck integrated out.

Contestant ii then wins against a “cavity” field (ii removed):

pi=∫hi(x)∏c≠c(i)Gc(x) dx,hi(x)=∑qwqfi(x∣aq)eSc(i)(x,aq)−log⁡Si(x∣aq).(8)p_i = \int h_i(x)\prod_{c\ne c(i)}G_c(x)\,dx,\qquad h_i(x) = \sum_q w_q f_i(x\mid a_q)e^{S_{c(i)}(x,a_q)-\log S_i(x\mid a_q)}. \tag*{(8)}

The term hih_i couples ii’s win density to its own teammates within the shared draw of ac(i)a_{c(i)}; the cavity product supplies the rest of the field.15 The cost is O(nLQa)O(nLQ_a) whatever the number of clusters, because the per-cluster factors are accumulated once. Rank two is special: the conditional integrand is smooth and a tensor Gauss–Hermite rule beats scrambled Sobol at equal nodes by a wide measured margin.

One limitation of the hierarchical kernels is stated here but we aim to remove it. Their quadrature is a fixed-order rule, without the sharpness heuristic of §4.1 being applied. So when a cluster loading is large against the idiosyncratic noise the conditional integrand is a near-step and Gauss–Hermite fails at any order (measured at cluster sharpness 18: 5×10−25 \times10^{-2} of total variation against a four-million-path referee).16

The hierarchical kernels place their lattice by the same envelope principle as §3: for the lower endpoint every contestant sits at its most favourable retained conditional location, for the upper at its least favourable, and the idiosyncratic scale alone sets the bisection.17 The raw lattice mass is therefore treated as a diagnostic rather than a nuisance: the kernels check it and raise an error on a material defect instead of normalizing it away.

Nested. Add one global factor with couplings gig_i and a dial γ∈[0,1]\gamma\in[0,1]: conditional on the global draw fqf_q the model is a block race at shifted abilities, so p=∑qwqpblock(μ+γgfq)p = \sum_q w_q p_{\mathrm{block}}(\mu+ \gamma g f_q), a finite mixture of block races. At γ=0\gamma= 0 the clusters are isolated, at γ=1\gamma= 1 fully coupled, and the covariance contribution scales as γ2gg′\gamma^2 gg'.

Trees

Let a rooted tree have the leaf clusters at its bottom and internal nodes tt above, and give node tt a scalar effect bt∼N(0,1)b_t \sim N(0,1) applied with uniform strength λt\lambda_t to every leaf beneath it:

Xi=μi+viac(i)+∑t∈anc⁡(c(i))λtbt+Diϵi,(9)X_i = \mu_i + v_i a_{c(i)} + \sum_{t \in\operatorname{anc}(c(i))} \lambda_t b_t + \sqrt{D_i}\epsilon_i, \tag*{(9)}

with the leaf-cluster construction of §4.2 restricted to scalar loadings, vi∈Rv_i \in\mathbb{R} and ac∼N(0,1)a_c \sim N(0,1): the shipped tree kernels take rank-one leaf-cluster effects, where the block kernels support rank rr, and they refuse a rank-rr leaf loading.

The implied covariance is hierarchical. Two contestants share the variance of exactly their common ancestors. The root’s effect is common to every contestant; hence, it is choice-irrelevant (this is the recurring invariant), and the pricing kernel gauge-fixes it to zero.18

The uniform strength is the crucial restriction, because a shared effect that hits every subtree member equally moves the whole subtree’s field by a translation of its argument. Messages therefore remain functions of one variable. Per-leaf loadings on internal effects would force two-dimensional message tables.

The algorithm is two passes over the same lattice.

Upward. Each leaf cluster carries its block factor Gc(x)=∑qwqeSc(x,aq)G_c(x) = \sum_q w_q e^{S_c(x,a_q)} from (7). Each internal node, visited deepest first, combines its children under its own effect:

Gt(x)=∑qwq∏c∈children⁡(t)Gc(x+λtaq).(10)G_t(x) = \sum_q w_q \prod_{c \in\operatorname{children}(t)} G_c(x + \lambda_t a_q). \tag*{(10)}

The interpretation: Gt(x)G_t(x) is the probability that every leaf below tt survives past xx, with tt’s effect integrated by quadrature and each child’s message shifted because the effect moves that child’s whole subtree at once. Shifted evaluations are linear interpolations on the lattice.

Downward. The root’s cavity is one. Each node, visited shallowest first, receives the field of everything outside its subtree:

Rt(x)=[∑qwqRparent⁡(t)(x−λparent⁡(t)aq)]∏s∈siblings⁡(t)Gs(x).(11)R_t(x) = \left[\sum_q w_q R_{\operatorname{parent}(t)}(x - \lambda_{\operatorname{parent}(t)}a_q)\right] \prod_{s \in\operatorname{siblings}(t)} G_s(x). \tag*{(11)}

The sibling messages sit outside the parent-factor quadrature. This placement is correct but not obvious: the parent effect shifts the candidate and every sibling subtree by the same amount, so it cancels from every candidate-versus-sibling comparison; only the cavity from outside the parent must be shifted and averaged. Contestant ii then races against its own leaf cavity, pi=∫hi(x)Rc(i)(x) dxp_i = \int h_i(x) R_{c(i)}(x)\,\mathrm{d}x with hih_i as in (8). The cost is O(nLQ)O(nLQ) plus O(LQ)O(LQ) per tree node.19

Remark 1 (A connection to top-down portfolio construction). Long-only portfolio weights can be read as choice probabilities, and we make the further connection to dendrogram-inspired wealth bisection (the hierarchical risk parity construction of [36]). There is a tree race whose implied correlation is exactly the floored cophenetic correlation of a dendrogram: for a linkage built from the correlation distance dij=(1−ρij)/2d_{ij} = \sqrt{(1-\rho_{ij})/2}, invert the distance transform at each merge height and floor at zero. Give internal node tt strength λt2=ρt−ρparent⁡(t)\lambda_t^2 = \rho_t - \rho_{\operatorname{parent}(t)}, with ρt=max⁡(1−2ht2,0)\rho_t = \max(1-2h_t^2,0) at merge height hth_t, and leaf ii idiosyncratic variance 1−ρfirst⁡(i)1-\rho_{\operatorname{first}(i)}.20

Concentration limits stated on a dendrogram therefore become contest inversions. We do not pursue the application here.

Jacobians, tie densities, inversion

We now arrive at the central object of the algorithm: the Jacobian. An outcome of the race is a vector xx of finishing values, one per contestant. Contestant ii wins on the set

Ri={x:xi≤xk for every k},R_i = \{x : x_i \le x_k \text{ for every } k\},

a convex cone: the outcomes in which nobody beats ii. These cones tile the space, one per contestant, and each win probability is the mass the joint density puts on its own cone,

pi(μ)=∫Riqμ,qμ(x)=q0(x−μ).p_i(\mu) = \int_{R_i} q_\mu,\qquad q_\mu(x) = q_0(x-\mu).

Where two cones meet, two contestants dead-heat ahead of the field. So we refer to the shared boundary

Fij={x:xi=xj≤xk, k≠i,j}F_{ij} = \{x : x_i = x_j \le x_k,\ k \ne i,j\}

as the photo-finish face between ii and jj.

Now differentiate. Abilities enter the density only as a translation, so raising μj\mu_j slides the density rather than reshaping it, and sliding the density one way is the same as sliding the coordinate the other: ∂qμ/∂μj=−∂qμ/∂xj\partial q_\mu/\partial\mu_j = -\partial q_\mu/\partial x_j. The region RiR_i does not depend on μ\mu at all, so for j≠ij \ne i the whole derivative falls on the integrand,

∂pi∂μj=−∫Ri∂qμ∂xj dx.\frac{\partial p_i}{\partial\mu_j} = -\int_{R_i} \frac{\partial q_\mu}{\partial x_j}\,\mathrm{d}x.

We recognize this as a derivative integrated over a region, so the divergence theorem applies to the vector field qμejq_\mu e_j. This lets us compute over the boundary instead of the volume:

∂pi∂μj=−∫∂Riqμnj dS,\frac{\partial p_i}{\partial\mu_j}=-\int_{\partial R_i}q_\mu n_j\,\mathrm{d}S,

with nn the outward unit normal.

However for this we take q0q_0 continuously differentiable with q0q_0 and ∇q0\nabla q_0 integrable and ∣x∣n−1q0(x)→0|x|^{n-1}q_0(x)\to0, conditions any Gaussian law satisfies outright. Integrability alone would license neither differentiating under the integral sign nor discarding the flux at infinity. With them the contribution over the sphere at infinity vanishes, and only the faces of RiR_i remain.

The observation: those faces are the photo-finish surfaces FikF_{ik}, one for each rival kk, and on FikF_{ik} the outward normal is (ei−ek)/2(e_i-e_k)/\sqrt{2}. Its jj-th component is zero unless k=jk=j. Every face therefore drops out except FijF_{ij}. What is left is the statement the proposition makes precise: slowing jj pushes probability out of jj’s winning region into ii’s, and all of it crosses at the surface where the two dead-heat.

Proposition 1 (Photo-finish derivatives are a boundary flux). For j≠ij\ne i,

∂pi∂μj=12∫Fijqμ dS≥0,(12)\frac{\partial p_i}{\partial\mu_j}=\frac{1}{\sqrt{2}}\int_{F_{ij}}q_\mu\,\mathrm{d}S\ge0, \tag*{(12)}

the probability flux across the surface on which ii and jj dead-heat ahead of the field. Parametrizing that face by the common value xi=xj=tx_i=x_j=t contributes a surface factor 2\sqrt{2} which cancels, giving, with ϕij\phi_{ij} the joint density of (Xi,Xj)(X_i,X_j),

∂pi∂μj=∫ϕij(t,t)Pr⁡{Xk>t ∀k≠i,j∣Xi=Xj=t} dt,(13)\frac{\partial p_i}{\partial\mu_j}=\int\phi_{ij}(t,t)\Pr\{X_k>t\ \forall k\ne i,j\mid X_i=X_j=t\}\,\mathrm{d}t, \tag*{(13)}

and under independence

∂pi∂μj=∫fi(x)fj(x)∏k≠i,jSk(x) dx.(14)\frac{\partial p_i}{\partial\mu_j}=\int f_i(x)f_j(x)\prod_{k\ne i,j}S_k(x)\,\mathrm{d}x. \tag*{(14)}

Under conditional independence the same factorization holds node by node and is averaged over the shared variables. Each row of the Jacobian sums to zero.

Everything else follows from the geometry. Symmetry is Fij=FjiF_{ij}=F_{ji}: one surface, one number, so wij=∂pi/∂μjw_{ij}=\partial p_i/\partial\mu_j is symmetric and nonnegative. The zero row sum is translation invariance, a conservation law: what leaves one cone enters its neighbours. Writing BB for the oriented incidence matrix of the photo-finish graph and WeW_e for the diagonal of edge conductances wijw_{ij},

J=−B⊤WeB,(Jh)i=∑j≠iwij(hj−hi),J=-B^\top W_eB,\qquad(Jh)_i=\sum_{j\ne i}w_{ij}(h_j-h_i),

the discrete analogue of −div⁡(a∇h)-\operatorname{div}(a\nabla h): BhBh takes differences across photo-finish boundaries, WeBhW_eBh is the flux across them, B⊤WeBhB^\top W_eBh the net flow into each winning region. The mass-one identity is the same theorem in dimension one, since ∑ifi∏j≠iSj=ddt(1−∏jSj)\sum_i f_i\prod_{j\ne i}S_j=\frac{\mathrm{d}}{\mathrm{d}t}(1-\prod_jS_j) integrates to one; this is why the implementation’s unnormalized mass checks are diagnostics rather than cosmetics, a material defect meaning the lattice missed the region, not that normalization was needed.

The Jacobian structure has prior art we were unaware of when this work was done. [43] (2022), differentiating the Williams–Daly–Zachary gradient identity ∂E/∂ui=Pr⁡{i wins}\partial E/\partial u_i = \Pr\{i\ \text{wins}\} for general joint laws, derive the cross-Hessian as the density that two alternatives tie for the maximum, and observe that the resulting matrix is symmetric with signed off-diagonals and zero row sums.

They draw no graph and build no algorithm from it, their object being convexity moduli for prox-functions, and their cross-derivative remains an (n−2)(n-2)-fold integral of the joint density. Our face parametrization reduces the same object to a one-dimensional integral of a pair density against the conditional survival of the field, which is the form in which the lattice works.

The two paths are valid. We prefer to keep the literal interpretation: probability flux through the boundary between winning regions. This gives the formula, the symmetry, the conservation law, and the graph structure in one geometric picture. On the computational side, §5.2’s identity lets the dense matrix act in linear work, as we now discuss.

Jacobian computation

Scalability rests on never materializing the matrix. Full Newton needs the Jacobian only as an operator applied to a vector; a likelihood score needs one row of it; and the shipped inversion below needs only the own-coordinate preconditioning slopes.

Per factor node, write Ai(x)=fi(x)/Si(x)A_i(x)=f_i(x)/S_i(x) for contestant ii’s hazard and G(x)=∏kSk(x)G(x)=\prod_k S_k(x) for the field. The tie density factors through the field,

wij=∫G(x)Ai(x)Aj(x) dx,j≠i,w_{ij}=\int G(x) A_i(x) A_j(x)\,\mathrm{d}x,\qquad j\ne i,

so the apparently dense Laplacian is a continuous sum of rank-one contributions, and its action collapses: substituting into (Jh)i=∑j≠iwij(hj−hi)(Jh)_i=\sum_{j\ne i}w_{ij}(h_j-h_i), the j=ij=i terms cancel between the two sums, leaving

(Jh)i=∫G(x)Ai(x)[∑jAj(x)hj−hi∑jAj(x)]dx.(Jh)_i=\int G(x) A_i(x)\left[\sum_j A_j(x)h_j-h_i\sum_j A_j(x)\right]\mathrm{d}x.

The two inner sums are shared across every ii, so the whole product costs O(nL)O(nL) per node — the same order as pricing — rather than the O(n2L)O(n^2L) of assembling edges. This, more than the Laplacian structure itself, is what turns the tie-density Hessian into a scalable object. Observe that a graph with (n2)\binom{n}{2} potential edges is applied without ever being constructed.

Both a single entry and a Jacobian–vector product come out of the same field pass that produced the probabilities, by the identity above (in the log domain, with hazards clipped as §3 describes). Forming all n2n^2 entries is possible, but it is a choice with Ω(n2)\Omega(n^2) cost in output alone, and nothing downstream requires it.

Numerical considerations In keeping with our previous lattice remarks we delineate four objects. The first is the continuum derivative, equation (14), the exact derivative of the integral that defines pp. The second is that formula evaluated by quadrature on a lattice, with the diagonal imposed from the zero-row-sum identity. The third, call it the grid derivative, is the exact derivative of the normalized rectangle sum holding the selected grid fixed: with unnormalized masses aa, total T=1⊤aT = \mathbf{1}^{\top}a and A=∂a/∂μA = \partial a/\partial\mu, it is (A−p1⊤A)/T(A - p\mathbf{1}^{\top}A)/T. The fourth is the exact derivative of the full adaptive map, which adds a grid-motion term, since the window itself depends on μ\mu.

The factor implementation returns the third. It differentiates the rectangle sum itself, then applies the normalization quotient: a directional derivative vv of the unnormalized masses is returned as (v−p1⊤v)/T(v - p\mathbf{1}^{\top}v)/T. It does not differentiate the adaptive window, and we measured the residual arising from that omission.

That quotient is critical. Without it, the returned directional derivative disagrees with central finite differences of the returned map by 2×10−32 \times10^{-3} at L=25L = 25 lattice points. With it the two agree to 3×10−113 \times10^{-11} from L=101L = 101 upward, which is the production range.

At L=25L = 25 a residual of 6×10−46 \times10^{-4} survives, and it is not a defect in the quotient. It is the grid-motion term, the difference between the third object and the fourth: a finite difference recomputes the window at each perturbed μ\mu and therefore sees a contribution the fixed-grid derivative does not contain. It falls below the agreement figure by L=101L = 101, so in the production range the grid derivative serves as the derivative of the adaptive map to the accuracy reported.

The materialized Jacobians of the block, nested and tree kernels are the second object, not the third. They are continuum tie densities evaluated by quadrature with the diagonal imposed, ignoring both the normalization quotient and the window. They are consistent estimates of the continuum derivative, and they are not exact derivatives of the normalized discrete maps.21

The continuum form is implemented alongside the grid form because it is symmetric by construction and can be used as a preconditioner without further checking. The grid form is symmetric only to the accuracy of its row sums, for the same reason: at 25 points it is off by 3×10−43 \times10^{-4} and at 65 by 7×10−117 \times10^{-11}, but at the 257-point default the two forms agree to machine precision, so the distinction is one of guarantee rather than of observed values in production.

A comment on finiteness. The photo-finish integrand is factored as

[fieL−log⁡Si]×[fj/Sj].\left[f_i e^{L-\log S_i}\right] \times\left[f_j/S_j\right].

The first factor is bounded by a density. The second is a hazard rate, which grows linearly under the normal base and exponentially under the Gumbel base; the exponent clip absorbs either. The symmetric square-root split, which looks more natural, overflows wherever survivals vanish.

As a final remark, the block Jacobian is exact for rank-one cluster loadings. The nested Jacobian is the mixture of block Jacobians. The tree Jacobian is exact within a cluster and Gram-approximate across clusters. That approximation is safe for Newton because the residual is always computed from the exact forward map, so an approximate Jacobian can slow convergence but cannot change the answer to which it converges.

Inversion

The inversion rests on a convex program.

Theorem 1 (The inverse exists and is unique on contrasts). *Fix a covariance of full support (any member of the grammar with every Di>0D_i > 0) and let W(μ)=Emin⁡i(μi+ϵi)W(\mu) = \mathbb{E}\min_i(\mu_i + \epsilon_i), ϵ∼N(0,Σ)\epsilon\sim\mathcal{N}(0,\Sigma). Then WW is concave and differentiable with ∇W(μ)=p(μ)\nabla W(\mu) = p(\mu), and its Hessian is −L(μ)-L(\mu), the negative of the graph Laplacian whose edge weights are the correlated tie densities (13), reducing to (14) under independence. Every tie density is strictly positive, so WW is strictly concave on the contrast space 1⊥\mathbf{1}^{\perp}. For any target with pi⋆>0p_i^\star> 0 and ∑ipi⋆=1\sum_i p_i^\star= 1, the program

max⁡μ  W(μ)−⟨p⋆,μ⟩\max_{\mu}\; W(\mu) - \langle p^\star,\mu\rangle

is constant along 1\mathbf{1}, strictly concave and coercive on 1⊥\mathbf{1}^{\perp}, and its unique mean-zero maximiser is the inverse: p(μ⋆)=p⋆p(\mu^\star) = p^\star. If some pi⋆=0p_i^\star= 0 the supremum is approached only as the contrast μi−min⁡j:pj⋆>0μj→+∞\mu_i-\min_{j:p_j^\star>0}\mu_j \to+\infty (the raw coordinate statement depends on the gauge); no finite inverse exists, and any floored target yields a finite point on that diverging contrast.

Proof. A minimum of affine functions of μ\mu is concave and expectation preserves this. Ties have measure zero under full support, so the minimiser is almost surely unique, and Danskin’s theorem [18] gives ∂W/∂μi=Pr⁡{i wins}\partial W/\partial\mu_i = \Pr\{i\ \text{wins}\} — the identity known in discrete choice as the Williams–Daly–Zachary theorem [38].22

The Hessian is given by Proposition 1, which assumed no independence: its off-diagonals are the boundary fluxes (13) under the full correlated law, and its rows sum to zero by the same translation invariance W(μ+c1)=W(μ)+cW(\mu+c\mathbf{1})=W(\mu)+c that fixes the diagonal without further computation. The Hessian is therefore −L(μ)-L(\mu) with LL the weighted graph Laplacian of the photo-finish graph; under full support (Di>0D_i>0, so every pairwise difference has positive variance) each edge weight is strictly positive, the tie graph is complete, and L≻0L\succ0 on 1⊥\mathbf{1}^{\perp}: WW is strictly concave there.

Coercivity follows from the elementary bound W(μ)≤min⁡iμiW(\mu)\le\min_i\mu_i: for each ii, min⁡k(μk+ϵk)≤μi+ϵi\min_k(\mu_k+\epsilon_k)\le\mu_i+\epsilon_i, and Eϵi=0\mathbb{E}\epsilon_i=0. For a nonconstant unit contrast dd and interior target, ⟨p⋆,d⟩>min⁡idi\langle p^\star,d\rangle> \min_i d_i, because p⋆p^\star puts positive mass on a coordinate where dd exceeds its minimum; hence

W(td)−t⟨p⋆,d⟩≤t(min⁡idi−⟨p⋆,d⟩)⟶−∞W(td)-t\langle p^\star,d\rangle\le t\left(\min_i d_i-\langle p^\star,d\rangle\right)\longrightarrow-\infty

linearly in tt. The decay is uniform, not merely raywise: d↦⟨p⋆,d⟩−min⁡idid\mapsto\langle p^\star,d\rangle-\min_i d_i is continuous and strictly positive on the compact unit sphere of 1⊥\mathbf{1}^{\perp}, so it attains a positive minimum κ\kappa, and the displayed inequality at t=∥μ∥t=\lVert\mu\rVert gives F(μ)≤−κ∥μ∥F(\mu)\le-\kappa\lVert\mu\rVert for every μ∈1⊥\mu\in\mathbf{1}^{\perp}, writing FF for the objective, which is coercivity for arbitrary diverging sequences. (The bound is on FF itself, not on FF relative to F(0)F(0): the objective may climb toward its maximizer before the linear decay takes over.) Constancy along 1\mathbf{1} is translation invariance again, exactly when the target sums to one. A strictly concave coercive function on 1⊥\mathbf{1}^{\perp} attains a unique maximum, where the gradient vanishes: p(μ⋆)=p⋆p(\mu^\star)=p^\star.

For the boundary claim, suppose pi⋆=0p_i^\star=0 for ii outside S={j:pj⋆>0}S=\{j:p_j^\star>0\}. Under full support pi(μ)>0p_i(\mu)>0 at every finite μ\mu, so no finite point inverts the target. Invert the target restricted to SS, then send each excluded μi→+∞\mu_i\to+\infty holding the SS-contrasts fixed: by dominated convergence the race converges to the restricted race and the objective to its restricted optimum, so the supremum is approached along exactly those diverging contrasts. Conversely, on any maximizing sequence an excluded contrast that remained bounded would admit, after gauge fixing, a convergent subsequence whose limit gives alternative ii strictly positive probability, and the objective, continuous in μ\mu, would sit strictly below the restricted optimum there — contradicting maximality.

We remark on the connection to economics. We are considering the Legendre dual of the social surplus function of [38]. Share inversion has frequently been viewed as a convex problem: [3] inverts market shares in logit-family demand, [20] identify the general random-utility inversion with optimal transport, [12] compute it by linear programming in the discrete case, and [43] state the inversion as the subdifferential of the conjugate surplus, u∈∂E∗(p)u \in\partial E^*(p), en route to their prox-functions.

Closest is [33], who for arbitrary non-atomic bases writes the inversion as an unconstrained convex minimization whose objective gradient is the share map, with globally convergent superlinear methods. That is a formulation of the optimizer, but without a fast evaluator of the shares and their Jacobian at large nn, which is what we supply. The shared field is that evaluator, so the two are complements. What the field representation adds is not the convex program but its oracles: the shipped solver preconditions with the field’s own-coordinate slopes. The Hessian is available as a matrix-free operator at O(nLQ)O(nLQ) per application for Newton–Krylov methods.

Fitting objective

Because choice probabilities are invariant to a common utility shock (as noted the model depends on Σ\Sigma only through PΣPP\Sigma P with P=I−11⊤/nP = I - 11^\top/n) a factor proportional to 11, or a tree-root effect applied to every leaf, will not change any choice probabilities. Therefore the right fitting objective for a dense covariance is the projected residual,

min⁡V, D≥0∥P(Σ−VV′−diag⁡D)P∥F2\min_{V,\,D \ge0} \left\|P\left(\Sigma- VV^\prime- \operatorname{diag} D\right)P\right\|_{F}^{2}

not a fit of VV′+diag⁡(D)VV^\prime+ \operatorname{diag}(D) to PΣPP\Sigma P (the projection of a rank-plus-diagonal matrix is no longer rank-plus-diagonal, so the second problem has some manufactured error compared to the first). The reference implementation minimizes that objective in factor_model_projected, alternating two steps. The VV-step takes the top kk eigendirections of the current residual in the contrast basis. The DD-step solves for the diagonal exactly, subject to a lower bound, from the normal equations

(P∘P)d=diag⁡(P(Σ−VV′)P),(P \circ P)d = \operatorname{diag}\left(P\left(\Sigma- VV^\prime\right)P\right),

whose Gram matrix is closed form, so the step is O(n)O(n) rather than a least-squares solve (§6).

Everything downstream works from projected residuals, so a matrix already of the form VV′+diag⁡(D)VV^\prime+\operatorname{diag}(D) passes through whenever its factor rank lies within the fitted grammar’s budget — up to the common-shock equivalence, factor-quadrature error, and a diagonal floor of 10−610^{-6} of each runner’s own variance.23

Inversion algorithm

The implemented inversion (abilities_from_race) runs as follows.

Inversion (all grammars; min-wins). Given a target p⋆p^\star with positive entries summing to one, set t=log⁡p⋆t = \log p^\star and initialize μ0=−(t−tˉ)/2\mu^0 = -(t-\bar{t})/2. Repeat until max⁡i∣ri∣<10−8\max_i |r_i| < 10^{-8}:

  1. one field pass: p^=p(μ)\hat{p}=p(\mu), and negative preconditioning slopes s~i\tilde{s}_i (factor grammar: the own-coordinate grid slopes ∂pi/∂μi\partial p_i/\partial\mu_i of the same pass; block/nested/tree: the own-slopes of an independent race at matched total variances, one extra O(nL)O(nL) pass — an approximation used only to precondition, never to form the residual);

  2. log residual ri=log⁡p^i−tir_i=\log\hat{p}_i-t_i; log-domain slope di=min⁡(s~i/p^i,−10−6)d_i=\min(\tilde{s}_i/\hat{p}_i,-10^{-6});

  3. damped, clipped preconditioned step μi←μi−clip⁡(αri/di,±2)\mu_i\leftarrow\mu_i-\operatorname{clip}(\alpha r_i/d_i,\pm2), then recenter μ←μ−μˉ\mu\leftarrow\mu-\bar{\mu}.

Damping: α=1\alpha=1 (0.7 at n=2n=2, where the undamped update on the K2K_2 photo-finish graph is a two-cycle); for the structure grammars α=0.7\alpha=0.7, halved whenever the residual fails to shrink.

Each sweep is a diagonally preconditioned residual iteration on the log-probability residual ri=log⁡pi(μ)−log⁡pi⋆r_i=\log p_i(\mu)-\log p_i^\star.24

Interactions are not ignored (every re-pricing includes them); they are just not consulted when choosing each step. The JvJv oracle is the more powerful tool: propose changing all abilities at once by vv and it returns the resulting change in all win probabilities, without constructing the million-by-million Jacobian’s 101210^{12} entries. A Newton–Krylov solver would repeatedly ask it what coordinated change removes the current errors most efficiently. That more sophisticated solver is not what produced the reported million-runner result; the own-slope iteration did, and making Newton–Krylov beat it is future solver work.

Thus in contrast to a full Newton step solving a linear system in the Jacobian, here each coordinate is instead divided by a preconditioning slope s~i\tilde{s}_i, which for the factor grammar is the own-coordinate slope, and for the other grammars an independent-race approximation to it. The residual, by contrast, always comes from the exact structured forward map, so the preconditioner does not change the root equation; it can affect convergence and the finite-tolerance point returned.

Working in logs rather than in probabilities matters because win probabilities span many orders of magnitude, and an absolute residual would effectively ignore everything but the front of the field. A step clip and a recentering keep the iterate in the contrast space.

Theorem 1 says the inverse exists and is unique for the Gaussian grammars, which is where it is stated. For a general base the same proof goes through when the location family has finite first moments, an everywhere-positive sufficiently regular density and no atoms: concavity and coercivity of WW use nothing Gaussian, and strict concavity needs only positive tie densities, which full support supplies. We have not written that generalization out formally, so for non-normal bases the uniqueness claim should be read as proved under those conditions rather than universally. The theorem also does not say that this clipped iteration finds the inverse.

Rationale for defaulting to a diagonal solver

The solver’s convergence, as implemented, stands on empirical evidence, which is strong on the benchmark families but not universal. We can try to break the algorithm and construct strongly correlated fields on which the damped iteration stalls at a residual near 10−410^{-4} instead of converging.

A matrix-free Newton–Krylov solver using the exact grid Jacobian–vector product is provided also but is work in progress. Naively assembled it lost badly to the damped diagonal iteration25. Assembled properly (log-residual system symmetrized by the p\sqrt{p} scaling and using integration-by-parts form of the product, conjugate gradients preconditioned by the own-slopes and also a null vector projected out) it does converge on the benchmark fields (9.6×10−109.6 \times10^{-10}, but at roughly sixty times the wall clock). On the constructed stall case it diverges where the diagonal iteration stalls.

So, for this reason the diagonal iteration is the production solver we recommend, whereas a robust Newton–Krylov remains solver engineering. The nearest proven result we know for a problem of this shape is the damped Newton method of [30] for semi-discrete optimal transport: prescribe the mass each Laguerre cell must capture and adjust one weight per cell, with a Hessian assembled from source mass on shared cell boundaries much as our Jacobian is assembled from tie density on shared win-region boundaries. They prove global linear convergence under regularity conditions on the cost and source. [32] run the method at ten million cells. Whether a race-market analogue of their conditions yields a convergence proof here is open.

We tested the round trip at n=400n = 400, with twenty clusters and a tree of depth three (the committed bench.py invert). Timing for independent was 0.04 s, tree 0.37 s, and blocks 0.67 s. A factor rank-two took 1.7 s and nested 3.7 s. In each case the maximum log-probability residual was below 10−810^{-8}.

The implementation does not hide errors. A zero or negative entry raises rather than being quietly repaired, since by Theorem 1 it has no finite inverse. Flooring small entries is available but must be requested by the user. For an entry whose target is exactly zero, the theorem says every finite-floor solution is a finite point on a contrast that diverges as the floor is removed, so the floored answer understates that contrast in the direction where the theorem indicates. For entries that are merely small and positive, reading the floored-and-renormalized solution as a coordinatewise bound on the true contrasts would need a monotonicity argument we do not make here.26

Every grammar gets that same contract. The target is validated once, before the call splits by structure, and all five paths return through a single exit, so a block or tree inversion reports floored entries, iteration count and convergence exactly as the factor path does.

Structure matters at inversion time, and not by a little. Inverting block-generated probabilities under an assumed independent model mislocates abilities by up to three tenths of the field’s spread.27

Approximate results for dense covariance

We ship a fitting procedure as follows for the general case. It comes with several caveats. We use the following notation. Let

si=Σiis_i = \sqrt{\Sigma_{ii}}

, S=diag⁡(s)S = \operatorname{diag}(s), and

C=S−1ΣS−1C = S^{-1}\Sigma S^{-1}

the correlation matrix. Every fit, residual and closing solve below is carried out in Σ\Sigma. Correlations appear only once, as the distance used for clustering in stage 3.

That choice is apparently forced, as we discovered. The tempting alternative is to standardize to CC, fit there, and restore the scales afterwards, which would let the fitter work on a matrix with unit diagonal. It did not work, for a reason related to the same under-specification of covariance we have encountered several times already.

Choices depend on Σ\Sigma only through PΣPP\Sigma P, so the residual that matters after restoration is PS(C−M)SPPS(C-M)SP, not P(C−M)PP(C-M)P, and those differ because PP does not commute with SS unless every scale is equal. Put another way: the direction choices ignore is the constant vector in covariance coordinates, but S−11S^{-1}\mathbf{1} in correlation coordinates. Fitting in correlation space with the ordinary projection removes the wrong direction.28 A single global rescaling of Σ\Sigma for conditioning is harmless but unequal scales break the commutation.29

Heuristic fitting algorithm

The stages, in order:

  1. Global factors: the quotient fit of §5 (factor_model_projected), k=3k = 3 throughout, returning (V,D0)(V,D_0) by alternation. Each half-step is optimal in its own block, so the projected objective descends monotonically to a coordinatewise-stationary point.30 The objective is evaluated each sweep at O(n2)O(n^2). A sweep that fails to improve it is discarded, and the alternation returns the best iterate.

  1. The working residual is then projected once, R=P(Σ−VV′−diag⁡D0)PR = P(\Sigma- VV^{\prime} - \operatorname{diag} D_0)P: the raw residual still contains the choice-irrelevant common component the quotient fit rightly ignored, and letting later stages chase it manufactures projected error (measurably: the raw-residual variant distorts an input already of the form VV′+diag⁡(D)VV^{\prime} + \operatorname{diag}(D) by 1.7×10−21.7 \times10^{-2} of total variation; the projected pipeline returns it at the 2×10−42 \times10^{-4} node-noise floor).

  1. Blocks: average-linkage clustering on (1−C)/2\sqrt{(1-C)/2} cut to at most 20 clusters; for each cluster, the leading eigenvector of the within-cluster block of RR with its diagonal zeroed, one rank-one loading per cluster (clusters are disjoint).

  1. Residual promotion: the top m=5m = 5 eigencomponents of what remains of RR, diagonal zeroed, appended as further factor columns; negative eigenvalues are not promoted; numerically dead columns are dropped.

  1. The closing diagonal solves the projected problem’s own normal equations, (P∘P)d=diag⁡(P(Σ−VallVall′)P)(P\circ P)d = \operatorname{diag}(P(\Sigma- V_{\mathrm{all}}V_{\mathrm{all}}^{\prime})P) subject to di≥ℓid_i \ge\ell_i, where the floor is relative to each runner’s own variance, ℓi=10−6Σii\ell_i = 10^{-6}\Sigma_{ii}. Relative matters: an absolute floor at a multiple of the mean variance destroys nearly singular contrasts, and Σ=diag⁡(10−8,10−8,1)\Sigma= \operatorname{diag}(10^{-8},10^{-8},1) makes the failure vivid — it forced Var⁡(X1−X2)\operatorname{Var}(X_1-X_2) from 2×10−82 \times10^{-8} up to 6.7×10−46.7 \times10^{-4}, turning a near-certain head-to-head into a coin flip (choice error 0.48) while the projected covariance residual sat one hundred times below the warning threshold. The Gram is exactly (1−2n)I+1n211⊤(1-\frac{2}{n})I+\frac{1}{n^2}11^{\top}, so the constrained solve is closed form in O(n)O(n): substituting d=ℓ+xd=\ell+x componentwise with x≥0x\ge0, writing ℓ\ell for the vector of per-runner floors, leaves the same Gram with a shifted right-hand side, and the KKT conditions make the active set a threshold set, solved by water-filling. It is the constrained minimizer, not an unconstrained solve with a floor applied afterwards, which the Gram’s off-diagonal coupling would leave suboptimal. At n=2n=2 the Gram is rank one, only d1+d2d_1+d_2 is identified, and the symmetric representative is returned.

  1. A second candidate, a pure eigenfit at the same total rank, closed by the same diagonal solve, is computed, and whichever candidate leaves the smaller choice-relevant residual is kept, the pipeline winning ties: the greedy factor-plus-blocks allocation is the wrong shape for globally smooth covariance, and the kernel battery below measures the repair.

The constants kk, the cluster count and mm are fixed, not tuned per ensemble; a spectral rule for mm was tested and rejected (it saturates its cap for marginal gains and does not repair the failure case below). What results is a factor-plus-blocks race priced in one seeded, reproducible call (deterministic under Gauss–Hermite nodes, seeded scrambled Sobol past the tensor budget), and the pipeline is the shipped one-call (fit_covariance; race_probabilities accepts cov= directly), not a research script.

The alternation is nonconvex and its default start can stall on easy inputs (an exactly in-grammar matrix at n=12n=12 with variances spread across two decades sat at objective 0.88 where zero was attainable), so when the first start’s objective is materially above zero, two further deterministic starts are tried — diagonal-heavy and eigen-residual — and the best kept; each rescues that case to 10−1310^{-13}.

The shipped function also reports its own quality and warns on failure modes. In particular it flags a well-fitted matrix whose pricing needs a high-rank, sharp factor integral. The quadrature, not the fit, is then the binding constraint. A nearly singular contrast can also cause problems. The report therefore carries

max⁡i<j∣(ei−ej)TR(ei−ej)∣(ei−ej)TΣ(ei−ej)\max_{i<j}\frac{\left|(e_i-e_j)^{\mathsf{T}}R(e_i-e_j)\right|}{(e_i-e_j)^{\mathsf{T}}\Sigma(e_i-e_j)}

the worst pairwise difference-variance error in units of that difference variance, which is 0.49 on the diagonal example above (where the global residual is 5×10−45 \times10^{-4}) and 10−810^{-8} once the relative floor restores the fit.

The objective is nonconvex in (V,D)(V,D), so no global optimization can be assured. The residual report exposes the value reached.

Multistart dispersion is the natural diagnostic, but it has to be measured in the right coordinates, and the obvious choice is the wrong one. Across four ensembles at n=300n = 300, with eight random diagonal starts spanning two decades of assumed idiosyncratic share, every start reaches the same objective to 4×10−164 \times10^{-16} relative, and no random start ever beats the shipped one. On three of the four the fits agree in choices as well, to a total variation of 10−1410^{-14}.

Symmetry, and its challenges

Block equicorrelation is the exception, and it was an instructive one. There the starts agree on the objective and on DD to every digit, and still price races that differ by a total variation of 0.25. The cause is degeneracy rather than optimization. Centering a six-block matrix leaves a five-fold tied leading eigenvalue, so a rank-three fit selects an arbitrary three-dimensional subspace of a five-dimensional one. Every selection is exactly optimal and each implies a different race. Raising the rank to the multiplicity makes the fit exact and collapses the disagreement to 8×10−48 \times10^{-4}.

These experiments convince us of two things. First, disperse the priced race across starts, not the objective, which is blind to precisely the case that matters. And when dispersion does appear, the remedy is rank rather than a better optimizer. So the shipped fitter warns when the chosen rank splits a tied eigenvalue of the centered covariance, and tells the user which rank that would take the whole tied group.

The extreme case is also the oldest model in the subject. Under equicorrelation PΣPP\Sigma P is a multiple of PP, so its spectrum is (n−1)(n - 1)-fold degenerate. A great many representations are exactly optimal. They are all choice-equivalent, so none can be said to be wrong. But they do not cost the same to price. A representation carrying three factor columns is priced by a three-dimensional quadrature, where the equivalent pure diagonal needs none.

Group structures degenerate the same way. One can arrange equal-sized groups with equal within-group correlation. This leaves one tied leading direction per contrast among the groups, so gg equal groups give multiplicity g−1g - 1, with equicorrelation the case g=ng = n. The default k=3k = 3 is therefore exactly right for four equal groups but otherwise wrong, or should we say, inefficient. Measured at n=24n = 24 and within-group correlation 0.7, against the same race priced through the block grammar directly: The first three rows sit at the fitter’s ordinary approximation error. The last three are the rank cutting a tied group, and the cost grows with how much of the group is cut. The warning fires on all three, and on the three-group row as well, where the error is harmless: erring toward the false positive is the right direction here.

To emphasize, all of these issues apply to the dense covariance usage where the package is being asked to fit. A user can supply a structure they prefer without ambiguity. And symmetry is presumably known in advance. It is exchangeability among runners that produces the tie, and a caller who knows the group structure knows the rank to ask for, namely one less than the number of exchangeable groups.

Accuracy

The one-call fit-and-price takes four seconds (0.6 of them the fit) against thirty-six for a 10610^{6}-draw simulation, and agrees with it at its noise floor on the resolved bulk.

The tail is harder to check, and we are careful about what the check establishes. For the 82 percent of alternatives with zero simulation wins, agreement is unverifiable entry by entry. Worse, that set is selected by the same simulation that would have to certify it, so a fixed-set binomial bound does not apply to it.

Sample splitting does apply, and we run it as a separate experiment (its field is configured differently, which is why its zero-win fraction differs from the one above). Fix the zero-win set on one half of the draws, then count the wins an independent second half places anywhere in that set. Because the set is fixed before the second half is looked at, its count is binomial in the set’s true mass, and a Clopper–Pearson interval is valid.

On a dense n=2000n = 2000 correlation with three global factors and a forty-block layer, priced in a wide field where 63.6 percent of alternatives take no win in the first million paths, the model puts 1.13×10−41.13 \times10^{-4} of mass on that set. The second million paths place 111 wins in it, a 95 percent interval of [9.13×10−5,1.34×10−4][9.13 \times10^{-5}, 1.34 \times10^{-4}]. The model’s mass is inside it.

Scored on the second half alone, so that no statistic is evaluated on the draws that selected its own target, full-vector total variation is 4.4×10−34.4 \times10^{-3} against a split-half noise floor of 5.4×10−35.4 \times10^{-3}: at the referee’s own resolution. Tail exactness at small nn still comes from the Botev referee, which prices individual orthant probabilities rather than counting wins.

Testing the choice of objective

Fitting VV′+diag⁡(D)VV^{\prime} + \operatorname{diag}(D) to PΣPP\Sigma P is the wrong objective (eq:85). With the identified objective and projected residuals throughout, the ensemble study below ran a raw top-kk eigenfit pipeline and the identified pipeline over twenty seeds per ensemble. On thirteen of fifteen named ensembles the arms are statistically indistinguishable and none favors the raw arm. On block equicorrelation the identified arm is eight times better at the median (2.5 ×10−3\times10^{-3} against 2.0×10−22.0 \times10^{-2}), with a worst seed of 3.2×10−33.2 \times10^{-3} against the raw arm’s 0.162: the raw eigenfit spends its rank on a near-common component, as the identification argument predicts.

Testing against different covariance generation families

Accuracy depends on the family. We used the named collections of the randomcov library (pinned at commit 0d27a51), over twenty seeds per ensemble at n=300n = 300, each seed refereed by its own 10610^6-path simulation (the committed run_ensembles4.py and run_kernel4.py regenerate everything).

The TV columns are full-vector total variation against the empirical frequency vector, zeros included, so the referee’s own counting noise and any unresolved tail mass contribute to the reported number. That makes the statistic upward biased in expectation, by convexity, but not a realization-wise upper bound: on a single seed sampling error can cancel part of the model error. Only the per-entry column is restricted, to entries with at least 25 referee wins. TV is reported as median, ninth decile and worst over seeds; the last column is the median per-entry absolute error on those resolved entries.

Re-running any fixed covariance seed moves its score only at the referee’s noise scale; the medians themselves are aggregates over the twenty distinct covariance seeds, whose genuine spread the q90 and worst columns report. Eight further named ensembles (LKJ, onion, vine, elliptope walk, animals, Marchenko–Pastur and spiked spectra, hierarchical) fall between the third and fifth rows; Archakov–Hansen sits with AR(1) at 4.9×10−24.9 \times10^{-2}.

Kernel covariance as a weakness

Testing identified a type of covariance where the user should not expect our fitting procedure combined with the lattice technique to yield good results, and they would be advised to use the alternatives.

A stratified battery (kernel type ×\times length scale ×\times budget, twenty seeds per cell, unit-square inputs) separates two distinct mechanisms that a single “kernel” row had conflated:

kernellength scalemed TV, m=5m=5m=12m=12m=5m=5, 2142^{14} nodes
RBF0.083.4×10−23.4 \times10^{-2}3.1×10−23.1 \times10^{-2}3.3×10−23.3 \times10^{-2}
RBF0.22.6×10−22.6 \times10^{-2}2.6×10−22.6 \times10^{-2}1.2×10−21.2 \times10^{-2}
RBF0.41.6×10−21.6 \times10^{-2}1.7×10−21.7 \times10^{-2}8.2×10−38.2 \times10^{-3}
Matérn-32\frac{3}{2}0.082.9×10−22.9 \times10^{-2}2.5×10−22.5 \times10^{-2}2.4×10−22.4 \times10^{-2}
Matérn-32\frac{3}{2}0.22.5×10−22.5 \times10^{-2}2.3×10−22.3 \times10^{-2}1.6×10−21.6 \times10^{-2}
Matérn-32\frac{3}{2}0.42.1×10−22.1 \times10^{-2}1.7×10−21.7 \times10^{-2}1.2×10−21.2 \times10^{-2}

Table 2.

At short length scale the bottleneck is representation. Correlation is locality, the rank needed grows with the number of correlation lengths in the domain, and accordingly extra rank helps (3.4→3.1×10−23.4 \to3.1 \times10^{-2}) while extra quadrature does not.

At long length scale the fit is not the problem at all. A rank-27 eigenfit holds the RBF draw at length scale 0.4 to a projected residual of 10−310^{-3}. But pricing a well-fitted smooth kernel means a twenty-seven-dimensional sharp factor integral, since the closing diagonal is nearly zero and the conditional races are nearly deterministic. There the node budget is the binding constraint: raising the residual-factor budget from m=5m = 5 to m=12m = 12 does little, while 2142^{14} nodes halve the error and 2162^{16} nodes reach 6×10−36 \times10^{-3} on the diagnostic draw.

Stage 6 of the pipeline is what reaches this regime at all. The greedy factor-plus-blocks allocation leaves a projected residual of 0.14 on the same draw that the matched-rank eigenfit holds to 10−310^{-3}, a misallocation worth up to 7×10−27 \times10^{-2} of total variation, and not a limit of the grammar.

The dispatch conclusion stands. Genuinely local covariance wants sequential conditioning with cheap sparse-precision draws, and Matérn is exactly the family with the SPDE route ([34]). Near-singular smooth covariance wants either a larger node budget or plain simulation. A production front door should dispatch on the structure it detects, and the shipped call’s warnings distinguish the two regimes.

Benchmarks

The structure-aware per-alternative comparator. The fairest rival is not GHK but this paper’s own conditioning run the literature’s way: for each alternative separately, integrate the conditional independent-race integrand over the same Gauss–Hermite factor nodes (the construction of Butler and Moffitt (1982); mvtnorm’s lpRR/slpRR are its Monte Carlo form). With the same nodes and the same lattice the two computations are algebraically identical, and the measurement confirms it: at n=200n = 200, rank 2, the per-alternative version agrees with the shared field to total variation 3×10−153 \times10^{-15} and costs 601 times as much (22 s against 36 ms; the committed bench.py bm). The comparison isolates the paper’s contribution exactly: not the conditioning, which is forty years old, but the field shared across alternatives.

Against the field. All-nn choice probabilities under the rank-2 factor covariance family of §4.1, against a 2202^{20}-point QMC reference. Tail is the maximum absolute log-error over reference probabilities in [10−4,10−3][10^{-4}, 10^{-3}]; the n=10n = 10 draw has none. Frequency simulation is run at wall clock matched to the lattice and at ten times that budget; “zeros” counts tail alternatives that received no draws.

Genz and the lattice agree to the reference’s noise and to each other. Of the 300×300 \times cost ratio at n=30n = 30, the one-at-a-time interface supplies an unavoidable nn-fold component; the remainder reflects the differing integral representations, tolerances and implementations, and we do not apportion it further.

At the paper’s headline scale the nn-fold component alone is decisive. One probability at n=200n = 200 costs 0.43 s at maxpts =2.5×105= 2.5 \times10^{5}, agreeing with the lattice to four or five digits, and six digits needs multi-second budgets (the committed bench.py genz200). The full vector therefore costs 86 s against 26 ms for the lattice, a factor of 3×1033 \times10^{3} before any accuracy matching.

The Mendell–Elston and Clark-type moment recursions are the only entries whose error grows silently: its tail entries are off by e1.3≈3.7e^{1.3} \approx3.7 with nothing in the output to say so. The race’s tail figure is the reference’s own noise, and lattice self-convergence places its error near 10−810^{-8}.

Referee agreement. A replay harness maps each benchmark probability to its difference orthant and prices it through the two field-standard R implementations. mvtnorm’s Genz–Bretz agrees with the lattice to within its own reported error bound in every family: 3.8×10−73.8 \times10^{-7} against a bound of 8.1×10−78.1 \times10^{-7} at n=10n = 10, and 2.7×10−82.7 \times10^{-8} against 5.8×10−85.8 \times10^{-8} on a case whose smallest probability is 3×10−103 \times10^{-10}. Botev’s minimax tilting agrees to its own Monte Carlo noise, which in relative terms is 2.2×10−42.2 \times10^{-4} at p≈3×10−10p \approx3 \times10^{-10}: the tail claim rests on the named accuracy reference, not only on self-convergence. On the independent family an adaptive-quadrature referee reaches machine precision and the lattice matches it to 1.9×10−151.9 \times10^{-15}. An invariance battery (two-runner closed form, translation, permutation, symmetry) holds to 10−1610^{-16} throughout, except the two-runner comparison at 7×10−97 \times10^{-9}, which is the lattice discretization itself.

Stress boundaries. An adversarial battery pushes each failure axis until something gives. Depth: against pure-relative adaptive quadrature, relative error is 4×10−134 \times10^{-13} at p≈10−30p \approx10^{-30} and 2×10−82 \times10^{-8} at p≈10−50p \approx10^{-50}, with the first genuine breakdown near p≈10−119p \approx10^{-119}, a laggard twenty-five standard deviations behind. Inversion: the round trip p→μ→pp \to\mu\to p holds 10−910^{-9} in log even when the target contains a 10−1010^{-10} entry or ties at the 10−910^{-9} level. The Gumbel base reproduces softmax to 10−1510^{-15} at n=1000n = 1000; exact duplicates split exactly, and an ϵ\epsilon perturbation moves the split linearly.

The one operative boundary is factor strength. When loadings make implied correlations exceed roughly 0.9, the argmax integrand loses smoothness in factor space and Gauss–Hermite converges slowly in the node count: at loading scale 4 the 25-node rule still sits at 8×10−38 \times10^{-3} total variation. Scrambled-Sobol factor nodes restore reference-level accuracy (4×10−44 \times10^{-4}) at the same call: heavy correlation wants quasi-Monte-Carlo nodes, not deeper polynomial rules. The default escalates the family automatically past sharpness 3, in both the Python and R implementations (scrambled Sobol and Halton respectively), which agree to 5×10−45 \times10^{-4} on the worst case; the figures above are measured with that escalation disabled, to expose the boundary itself.

Against GHK. All-nn choice probabilities under a rank-2 factor covariance, against a 2202^{20}-point QMC reference. TV is a bulk metric and blind to the tails, so the same tail column as above is reported: the maximum absolute log-error over reference probabilities in [10−4,10−3][10^{-4}, 10^{-3}], which for probabilities this small is the log-odds error, and which the reference’s own counting noise floors near 0.1.

The n=10n = 10 draw has no reference probability in the tail band. The lattice’s tail figures equal the reference’s own noise; GHK’s are two to ten times larger in log terms even at ten times the draws, which is the tail blindness the TV column cannot show.

Self-convergence places the lattice error near 10−810^{-8}. GHK error contracts as O(R−1/2)O(R^{-1/2}) and its measured complete-vector cost grows superquadratically, with exponent 2.15 to 2.8 across the measured range. The lattice is deterministic under Gauss–Hermite nodes and seeded-reproducible under scrambled Sobol, supplies smooth matrix-free derivatives free of simulation noise, and prices the tails. Simulated likelihoods can of course be differentiated, but they inherit the noise.

Our claim is bounded as follows. For complete-vector pricing and inversion under the factor, block, nested and tree covariance grammars, the shared-field construction removes the per-alternative repetition intrinsic to standard GHK implementations, and dominates the per-alternative GHK implementation tested here in both accuracy and cost. GHK implementations with antithetics, quasi-random sequences or reordering heuristics would move the constants, not the nn-fold shape. Estimation pipelines built around GHK are a larger object than this loop, and the estimation paragraphs below report where simulation remains competitive at face value. GHK also retains general rectangle probabilities and locality-structured covariance, and Botev (2017) remains the reference for single extreme tail probabilities. [6]

Share inversion under sampling noise. The first estimation exercise is deliberately the saturated case. Simulate T=50,000T = 50{,}000 choices from one fixed menu of n=30n = 30 alternatives under a known rank-2 factor covariance and estimate the mean-zero utilities. With the menu fixed the model is saturated over the simplex interior, so the analytic-gradient maximizer is the inversion of the observed shares and the exercise measures how faithfully each method performs that inversion under multinomial noise.

Each count is smoothed by one half before any arm sees it, which is the posterior-mean share vector under the multinomial Jeffreys prior, E[pi∣c]=(ci+12)/(T+n/2)\mathbb{E}[p_i \mid c] = (c_i + \frac{1}{2})/(T + n/2). (It is not the Jeffreys MAP: the Dirichlet(12\frac{1}{2}) posterior has exponents ci−12c_i - \frac{1}{2}, whose mode leaves empty cells on the boundary. Read as a penalized likelihood in simplex coordinates, add-half is the Dirichlet(32\frac{3}{2}) mode.) In the saturated model the estimator is the race inverse of that smoothed vector, and the simulated arms maximize the same add-half-smoothed criterion, so the comparison stays like for like.

This is not cosmetic. The unpenalized saturated likelihood has no finite maximizer when any count is zero, which Theorem 1 states and this design would otherwise walk into: the smallest alternative here has p=2.5×10−5p = 2.5 \times10^{-5}, so its expected count is 1.27 and it is empty with probability e−1.27=0.28e^{-1.27} = 0.28, so about eleven of forty replications should see that cell empty. Thirteen of the forty do, and in this design it is the only cell that ever empties: every empty-cell replication is that alternative. On those thirteen an unpenalized optimizer returns a tolerance-dependent point on a boundary sequence rather than a maximizer. Forty replications, with the arms paired by construction since every method sees the same draw:

The exact path is both faster and more accurate than the R=100R = 100 simulator here, and beats the R=1000R = 1000 accuracy in a sixteenth of its time. Because the arms share every draw, the paired differences are the sharper statement: against R=100R = 100 the exact arm is better by 0.0112 ±\pm 0.0006, nearly nineteen standard errors, winning 39 of 40 replications; against R=1000R = 1000 by 0.0017 ±\pm 0.0002, seven standard errors, winning 33 of 40.

The R=1000R = 1000 margin is small in absolute terms, which is the honest characterization: enough simulation draws do approach the exact answer, at forty times the cost per fit, and the surviving paired gap is consistent with finite-RR simulation bias rather than multinomial sampling noise, though pairing alone cannot rule out another systematic implementation effect. The timing column is from an unloaded machine at the original eight replications; the accuracy columns are from all forty and are insensitive to load.

Covariate estimation. The overidentified case behaves differently, and we report it as we found it. Draw observation-specific design matrices XtX_t (n=10n = 10 alternatives, d=3d = 3 covariates, T=800T = 800 observations), utilities μt=Xtβ\mu_t = X_t\beta, one choice per observation, covariance known, and estimate β\beta by individual-level maximum likelihood: the exact path uses lattice probabilities with the analytic score (one Jacobian row per observation, a single field pass); the simulated path uses this paper’s own Rust GHK with common random numbers and finite-difference gradients. Eight replications, means with standard errors:

estimatorRMSE(β^\hat{\beta})median fit time
analytic-gradient MLE0.0363 ±\pm 0.006641.3 s
MSL, R=100R = 1000.0380 ±\pm 0.00735.4 s
MSL, R=1000R = 10000.0367 ±\pm 0.006739.6 s

Table 2.

All three estimators reach the statistical floor. With three parameters and eight hundred observations the simulation error averages out, and a well-implemented simulator at R=100R = 100 is the fastest of the three at this size. The exact path’s time is dominated by per-observation Python overhead: the compiled kernel accounts for under a second of the 41, so the comparison at n=10n = 10 measures plumbing, not method.

What the exact likelihood buys in estimation is not this row of the table. It is freedom from the choice of RR, gradients without simulation noise, the cost law as nn grows, and diagnostics that simulation smooths over.

That last point is not hypothetical. On the classic Fishing data, the unrestricted-covariance MNP likelihood evaluated exactly is boundary-seeking, still rising at loading norms near 4000: a ridge that the finite-RR simulated objective had obscured. The behavior is reproducible from the committed estimator (winning.mnprobit), which detects the ridge and reports it as a boundary diagnostic rather than returning the interior point simulation would have manufactured.

For interpretability of that norm: the parameterization is rank-2 loadings with the reference alternative’s rows fixed at zero and unit idiosyncratic variances, so global scale is pinned by the idiosyncratic normalization and the growing norm is a genuine choice-relevant direction, not the scale gauge. A profile likelihood along that normalized direction is the diagnostic a full treatment would add.

The Genz–Bretz score. Our quadrature comparator used pmvnorm, which exposes no score, with finite-difference gradients (31 vector evaluations per step at n=30n = 30, roughly eight times the entire exact-gradient share-inversion fit). The mvtnorm manual (v1.4-2) also documents slpmvnorm and, for the reduced-rank covariance BB′+diag⁡(D)BB^{\prime} + \operatorname{diag}(D) of this paper’s benchmarks, lpRR and slpRR: simulated log-likelihoods and score functions that integrate over the KK factor dimensions. That interface is itself the conditioning construction of §4.1 with Monte Carlo in place of quadrature and no shared field across alternatives, which makes it the natural structure-aware comparator for a fuller estimation study.

GHK protocol. The GHK figures throughout use this paper’s own Rust implementation: per-alternative sequential conditioning on the reference-differenced covariance with a fresh Cholesky factorization per alternative, pseudorandom draws (xoshiro family) with a per-alternative seed offset so that parameter evaluations share common random numbers, no antithetics, no quasi-random sequence, no variable-reordering heuristic, parallelized across alternatives. Cost figures are complete-vector; the large-nn columns of the introduction are extrapolations of the measured law and are displayed as such.

Scale. Ten million contestants price in 245 seconds under the block grammar (ten thousand clusters, 257-point lattice, the streaming field pass; the committed bench.py tenmillion), and the Rust classic-calibration kernel runs 232 times the speed of the pure-Python implementation. Throughput at this size is a systems statement; the accuracy evidence lives at the scales the referees above can reach.

Parity. One vector file embeds the inputs and outputs of 22 scenarios spanning the principal implemented grammars, boundary cases and numerical identities used above. The four language implementations of §9 replay them: nineteen to within 10−710^{-7} (most to 10−1010^{-10}), and the three fit- or optimizer-mediated scenarios to between 5×10−45 \times10^{-4} and 5×10−35 \times10^{-3}.

Summary

The pieces of this paper are individually old. The one-dimensional representation of the choice event is in Domenich and McFadden (1975), who judged it computationally intractable for correlated probit. The convex duality of calibration is in Li (2018). The tie-density derivatives and the surplus function’s Laplacian structure are in Müller et al. (2022), albeit independently arrived at from a different direction. A Hessian vector product at the cost of a gradient is Pearlmutter (1994). Building the survival field once and dividing each contestant out to collapse the forward vector to O(nL)O(nL) is performed here differently than Cotton (2021), but that is where the idea is borrowed and crucially, this is the point of departure from other smooth methods that require iteration over all items.

Herein we have organized the pieces into an efficient algorithm where a single shared survival field renders probabilities for all nn alternatives at once and supplies the own-coordinate slopes that precondition the million-alternative calibrations reported here.

We have applied and interpreted the dense tie-density Jacobian: a weighted graph Laplacian and a probability flux through the boundary between winning regions computable in linear work per lattice point. We have supplied a covariance grammar that, subject to its self-described limitations, lifts probit models and their cousins out of the small-to-medium scale domain and makes them practical for a variety of modern problems where previously, only logit was deemed to be a starter.

Availability

pip install winning is pure Python; winning[fast] adds the Rust kernels as one abi3 wheel per platform. A base-R package mirrors the full interface, and a zero-dependency browser port drives a live demonstration at winning.microprediction.org.

Extrapolated GHK cost brackets

The lattice column below is measured; the GHK column is an extrapolation of the two measured exponents (2.152.15 and 2.82.8) far beyond any regime in which GHK has been run, and cache effects, parallelism, Cholesky reuse or a change of regime would move it.

nnlattice, measuredGHK at 10410^{4} draws, cost-law bracketmultiplier
10410^{4}0.18 s20 hours – 3.7 days4×1054 \times10^{5} – 2×1062 \times10^{6}
10510^{5}2.7 s0.3 – 6.5 years4×1064 \times10^{6} – 8×1078 \times10^{7}
10610^{6}29 s46 – 4,100 years5×1075 \times10^{7} – 4×1094 \times10^{9}

Table 3.

Nobody prices a million-alternative field with GHK; the brackets say what the measured law implies about why. The ten-million forward-field benchmark of §7, which is actually run, is the meaningful systems demonstration.

References

  1. [3]S. Berry. Estimating discrete-choice models of product differentiation. RAND Journal of Economics 25(2):242–262, 1994.
  2. [6]Z. I. Botev. The normal law under linear restrictions: simulation and estimation via minimax tilting. Journal of the Royal Statistical Society B 79(1):125–148, 2017.DOI
  3. [12]K. Chiong, A. Galichon, M. Shum. Duality in dynamic discrete-choice models. Quantitative Economics 7(1):83–115, 2016.DOI
  4. [17]P. Cotton. Inferring relative ability from winning probability in multi-entrant contests. SIAM Journal on Financial Mathematics 12(1):295–317, 2021.
  5. [18]J. M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathematics 14(4):641–664, 1966.
  6. [19]M. Fosgerau, D. McFadden, M. Bierlaire. Choice probability generating functions. Journal of Choice Modelling 8:1–18, 2013.
  7. [20]A. Galichon, B. Salanié. Cupid’s invisible hand: social surplus and identification in matching models. Review of Economic Studies 89(5):2600–2629, 2022.
  8. [21]R. Gates. A Mata Geweke–Hajivassiliou–Keane multivariate normal simulator. Stata Journal 6(2):190–213, 2006.
  9. [23]T. A. Domenich, D. McFadden. Urban Travel Demand: A Behavioural Analysis. North-Holland, Amsterdam, 1975.
  10. [24]A. Genz. Numerical computation of multivariate normal probabilities. Journal of Computational and Graphical Statistics 1:141–149, 1992.
  11. [28]J. D. Kalbfleisch, R. L. Prentice. The Statistical Analysis of Failure Time Data. 2nd ed., Wiley, 2002.
  12. [30]J. Kitagawa, Q. Mérigot, B. Thibert. Convergence of a Newton algorithm for semi-discrete optimal transport. Journal of the European Mathematical Society 21(9):2603–2651, 2019.
  13. [31]S. Lerman, C. Manski. On the use of simulated frequencies to approximate choice probabilities. In Structural Analysis of Discrete Data, MIT Press, 1981.
  14. [32]B. Lévy, R. Mohayaee, S. von Hausegger. A fast semidiscrete optimal transport algorithm for a unique reconstruction of the early Universe. Monthly Notices of the Royal Astronomical Society 506(1):1165–1185, 2021.
  15. [33]L. Li. A general method for demand inversion. arXiv:1802.04444 (2018).arxiv.org/abs/1802.04444
  16. [34]F. Lindgren, H. Rue, J. Lindström. An explicit link between Gaussian fields and Gaussian Markov random fields. Journal of the Royal Statistical Society B 73(4):423–498, 2011.
  17. [36]M. López de Prado. Building diversified portfolios that outperform out of sample. Journal of Portfolio Management 42(4):59–69, 2016.
  18. [38]D. McFadden. Econometric models of probabilistic choice. In C. Manski, D. McFadden, eds., Structural Analysis of Discrete Data, MIT Press, 1981.
  19. [43]D. Müller, Y. Nesterov, V. Shikhman. Discrete choice prox-functions on the simplex. Mathematics of Operations Research 47(1):485–507, 2022.
  20. [49]K. Train. Discrete Choice Methods with Simulation. 2nd ed., Cambridge, 2009.

Paper details

vlnc:W_4eszypn6
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents