Hypothesis Testing for Generalized Thurstone Models
Authors: Anuran Makur
Japneet Singh
Venue: ICML 2025 poster (2025)
Keywords: generalized Thurstone model
hypothesis testing
minimax risk
cycle decomposition.
Primary area: theory->learning_theory

Abstract: In this work, we develop a hypothesis testing framework to determine whether pairwise comparison data is generated by an underlying *generalized Thurstone model* $\mathcal{T}_F$ for a given choice function $F$. While prior work has predominantly focused on parameter estimation and uncertainty quantification for such models, we address the fundamental problem of minimax hypothesis testing for $\mathcal{T}_F$ models. We formulate this testing problem by introducing a notion of separation distance between general pairwise comparison models and the class of $\mathcal{T}_F$ models. We then derive upper and lower bounds on the critical threshold for testing that depend on the topology of the observation graph. For the special case of complete observation graphs, this threshold scales as $\Theta((nk)^{-1/2})$, where $n$ is the number of agents and $k$ is the number of comparisons per pair. Furthermore, we propose a hypothesis test based on our separation distance, construct confidence intervals, establish time-uniform bounds on the probabilities of type I and II errors using reverse martingale techniques, and derive minimax lower bounds using information-theoretic methods. Finally, we validate our results through experiments on synthetic and real-world datasets.

Hypothesis Testing for Generalized Thurstone Models
Anuran Makur" 12 Japneet Singh"
22
Abstract
choice theory (Luce, 1959; Yellott, Jr., 1977). The class of generalized Thurstone models (GTMs) (Thurstone, 1927; Nelder & Wedderburn, 1972; McCullagh & Nelder, 1989), which fall under the broader framework of random utility models, is a widely adopted framework for ranking agents, items, or choices based on given preference data. GTMs include many other models as special cases, most notably the Bradley-Terry--Lun (BTL) model (Bradley & Terry, 1952; Luce, 1959; McFadden, 1973), which has been widely studied. Given n agents [v] = (I....,,). GTMs can be construed as likelihood models for pairwise comparisons between pairs of agents. In particular, a GTM Tr assumes that each agent i is endowed with an unknown utility param- eter w; E R and the probability that agent is preferred over agent (c.g.. i beats j game) is given by F(w, - wy). where F represents known choice funetion which is cumulative distribution function (CDF).
In this work, we develop hypothesis testing framework to determine whether pairwise com- parison data is generated by an underlying gen- eralized Thurstone model Tr for given choice function F. While prior work has predominantly focused on parameter estimation and uncertainty quantification for such models, we address the fun- damental problem of minimax hypothesis testing for TF models. We formulate this testing problem by introducing a notion of separation distance be- tween general pairwise comparison models and the class of TF models. We then derive upper and lower bounds on the critical threshold for testing that depend on the topology of the observation graph. For the special case of complete observa- tion graphs, this threshold scales as (((x))-112)) where n is the number of agents and & is the number of comparisons per pair. Furthermore, we propose a hypothesis test based on our separa- tion distance, construct confidence intervals, es- tablish time-uniform bounds on the probabilities of type I and II errors using reverse martingale techniques, and derive minimax lower bounds us- ing ceermattion-hhoreete methods. Finally, we validate our results through experiments on syn- thetic and real-world datasets.
While GTMs have been utilized in many contexts, e.g., (Thurstone, 1927; Elo, 1986), they are parametric models where n utility parameters characterize the model. Indeed, the assumption that pairwise comparison data governed by a small number of parameters forms the basis of most results on GTMs (Cattelan et al., 2013; Vojnovic & Yun, 2016; Shah et al., 2016; Jadbabaie et al., 2020; 2024). How- ever, such parametric models can sometimes be too restric- tive, failing to capture intricacies in real-world applications (Davidson & Marschak, 1974; McLaughlin & Lucc,, 1965; Tversky, 1972). Notably, GTMs struggle to accommodate context-dependent effects, such as the home-advantage ef- fect observed in sports tournaments (Clarke & Norman, 1995; Morley & Thomas, 2005), where teams may per- form differently when playing at home versus away. Fur- thermore, GTMs assume transitive relationships, which may not hold in real-world datasets. To accurately capture the complex and diverse behaviors observed real-world data, non-parametrie models, e.g.. (Chatterjee, 2015; Shah et al., 2016), have been studied as alternative. This conversation raises an important question: Given pairwise comparison data,
1. Introduction
Learning rankings from data is a fundamental problem un- derlying numerous applications, including recommendation systems (Jannach et al., 2016), sports tournaments (Bradley Terry, 1952: Cattelan et al., 2013), fine-tuning large lan- guage model (LLMs) (Ouyang et al., 2022), and social
"The author ordering alphabetical. 'Department Com- puter Science, Purdue University, West Lafayette. IN, USA "Elmrre Family School of Electrical and Computer Engineer- ing, Purdue University, West Lafayette, IN, USA. Correspon- dence to: Anuran Makur <amakur wwrdeeuuuuuudieee edu>, Japnect Singh <sing 1041 @ @urrduc.edu>.
determine whether it is comes from specific GTM? it does, then we can rely on the vast GTM literature for learning and interpretation, and if it does not, then we can resort to using other parametric models, such as the Mallows model (Mallows, 1957), or non parameeeteii models (Seshadri al., 2020; Mania et al., 2018; Bong al., 2020).
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Hypothesis Testing for Generalized Thurstone Models
Despite extensive research in the area, there is systematic answer to the above question in the literature, i.e., there is no rigorously analyzed hypothesis test to determine whether given pairwise comparison data conforms to an underlying GTM model. To address this, we study the composite hy- pothesis testing problem of whether data obeys a GTM Ty for a given choice function F (which is a special kind of CDF):
Table I: Bounds in this work on critical threshold Ec for
various induced observation graphs, where n represents the number of agents and & is the number of comparisons per pair of agents.
Graph Type
Upper Bound
Lower Bound
Complete graph
Vnk
Vnk
Ho : 2 ~ TF for some choice of w E W,
1
d-Regular graph
Ω
H1: : 2 ~ pairwise comparison model that is not TF,
Vnk
V n
1
where Z denotes the pairwise comparison data, Hg and Hi are the null and alternative hypotheses, respectively, and W denotes the parameter space for the parameters w.
Single cycle
0
Ω
Vnk
v vn 1
Toroidal grid
Vnk
Vn2/4k
1.1. Main Contributions
We analyze the composite hypothesis testing problem out- lined in (1). Our main contributions include the following:
Early foundational works, e.g., (Thurstone, 1927; Luce, 1959; Yellott, Jr., 1977), explored different cumulative dis- tribution functions F for modeling choice probabilities, in- cluding Gaussian (Thurstone, 1927), logistic (Bradley & Terry, 1952), and Laplace (Dawkins, 1969). These models and their extensions underlie popular rating systems, such as Elo in chess (Zermelo, 1929; Elo, 1986) and TrueSkill in video games (Herbrich et al., 2006). Several recent works have actively explored estimation techniques for Thurstone models. For instance, (Vojnovic & Yun, 2016) estimated parameters of Thurstone models when the preference data is derived from general subsets of agents (not specifically pairs), and (Shah et al., 2016) focused on parameter esti- mation for GTMs and the effect of graph topology on the estimation accuracy.
1. We frame the hypothesis testing problem in minimax sense (Section 2) by developing a rigorous notion of separation distance to the class of all GTMs that admits tractable analysis (Section 3, Theorem 3.1).
2. We derive upper and lower bounds on the critical threshold for our test (Section 3, Theorem 3.2 and Proposition 3.5). These bounds exhibit a dependence on the graph induced by the pairwise comparison data (see Table 1) and are tight for complete graphs. 3. We use the separation distance to propose a hypothesis test and establish various theoretical guarantees for our test. Specifically, we prove "time-unifone" type and type II error probability upper bounds for our test (Section 3, Theorems 3.4 and 3.7), and also provide minimax lower bound.
Furthermore, a significant portion of the literature has fo- cused on parameter (and skill distribution) estimation in the special case of the BTL model, e.g., (Simons & Yao, 1999; Negahban et al., 2017; 2012; Chen et al., 2019; Jadbabaie et al., 2020; 2024), where two prominent algorithms are spectral ranking (Negahban al., 2017: 2012) and maxi- mum likelihood estimation (Zermelo, 1929; Hunter, 2004). Another related line of work is on uncertainty quantification for estimated parameters (Gao et al., 2023; Han et al., 2024; Fan et al.. 2024; Liu et al., 2023). For example, (Gao et al., 2023) established the asymptotic normality of estimated parameters in the BTL model for both spectral ranking and maximum likelihood estimation, and (Han et al., 2024) gen- eralized the asymptotic normality results a broader class of models, such as GTMs and Mallows model. In different vein, (Chierichetti et al., 2022) provided sharp sample com- plexity bounds for A/B testing needed to distinguish similar alternatives.
4. Additionally, we obtain auxiliary results like e-error bounds on parameter estimation for general pairwise comparison models (Theorem 3.3) and "time-uniform" confidence intervals under the null hypothesis (Propo- sition 3.8).
5. Finally, we validate our theoretical findings through synthetic and real-world experiments, proposing a data- driven approach to determine the test threshold and using the test to determine different choice functions' fit to the data (Section 4).
1.2. Related Literature
The class of GTMs has rich history in the analysis of preference data. Initially proposed by Thurstone (Thur- stone, 1927), these models are widely used in various fields, ranging from psychology (Thurstone, 1931), economics (Marschak, 1974), and more recent applications like align- ing L.MSs with human preferences (Ouyang et al., 2022).
Despite the extensive work on parameter estimation, rela- tively few studies have rigorously investigated hypothesis
2

---

Hypothesis Testing for Generalized Thurstone Models
testing for such parametric models. Notably, (Rastogi al., 2022) developed two-sample tests for preference data, while (Busa-Fekete et al., 2021) studied hypothesis testing for the Mallows model. (Seshadri & Ugander, 2019) studied lower bounds for testing the independence of irrelevant alterna- tives (IIA) assumption (i.c., BTL and Plackett-Luce models (Luce, 1959; Plackett, 1975)), and (Makur & Singh, 2023; 2024) developed hypothesis tests for BTL models based on spectral methods. In contrast to these works, we develop hypothesis testing for GTMs using maximum likelihood framework, complementing the work in (Makur & Singh, 2023; 2024).
2.1. Comparison Models
Pairwise comparison model: Given the above preamble, now formally present general pairwise comparison mod- els (which encompass BTL models (Bradley & Terry, 1952; Luce, 1959; McFadden, 1973), Thurstone models (Thur- stone, 1927), non-parametric models (Chatterjee, 2015; Shah et al., 2016), etc., as mentioned above).
Definition 2.1 (Pairwise Comparison Model), Given an observation graph G over the agents [n], we refer to the collection of probability parameters (Pi : (i,5) E E as a pairwise comparison model.
Furthermore, we can represent pairwise comparison model by pairwise comparison matrix P E [o, 1|mxnn with
2. Formal Model and Setup
We begin by introducing a general pairwise comparison model that provides a flexible framework encompassing broad range of established probabilistic models, including
Pij. (i,j) E 0, otherwise.
Pij
(2)
the BTL model (Bradley & Terry, 1952; Luce, 1959; Mc- Fadden, 1973), the Thurstone model (Thurstone, 1927), and non paraammmttticc models (Chatterjee,, 2015; Shah et al., 2016). In this framework, we consider n E Nf11 agents (or items or choices) [n]] engaged in pairwise comparisons. For agents i [n]] with i + j. let Pij E (0, 1) denote the probability that is preferred over j in an "i vs. j" pairwise comparison. This model inherently captures the asymmetric nature of pairwise comparisons, as the outcome of an "ivs. vs. com- parison may differ from that of a "j vs. i" comparison. This reflects real-world phenomena like home-advantage that are commonly observed in sports (Clarke & Norman, 1995; Morley & Thomas, 2005).
We remark that our ensuing analysis can be easily special- ized to a symmetric setting where "i vs. j" and "j vs. i" comparisons are equivalent. In this case, E is automatically symmetric as assumed. On the other hand, the symmetry assumption on E is needed in asymmetric settings because GTMs inherently treat "i vs. j" and "j vs. i" comparisons as equivalent, which is not true in general models.
GTM model: Next, we describe a GTM for choice func- tion F: IR + [0, 1J. which is a special kind of CDF (to be explained in the sequel).
Definition 2.2 (Generalized Thurstone Model). Given an observation graph G. pairwise comparison model is said to be generalized Thurstone model (GTM) TF with choice function F ; R- - [0, 1] if there exists a weight (or utility) vector w E W such that:
To model the fact that not all pairwise comparisons may be observed, we assume that we are given an induced obser- vation graph g = ([n), E), where an edge (i,j) E & (with i A j) exists if and only if comparisons of the form "i vs. are observed. Let E {0. 1>>x be the adjacency matrix of G. with E.g- 1 if (i.j) E E and otherwise. Further- more, we assume that the edge set & is symmetric (i.e., g is undirected), implying that if "i vs. j" comparisons are observed, then "j vs. i" comparisons are observed as well. Additionally, we assume that G is connected and is fixed a priori (see Proposition 2.4), independent of the outcomes of the observed pairwise comparisons.
V(i.j) E Pi = F(w;- 100--w.. wy),
where W C B" is a specified convex parameter space (usu- ally ER"" or a compact hypercube in R)).
The GTM (Nelder & Wedderburn, 1972; McCullagh & Nelder, 1989) posits that every agent i has latent util- ity wy, and uncertainty in the comparison process is mod- eled by independent and identically distributed (i.i.d.) noise random variables XI...., Xn with absolutely continu- R + 1]. The discriminant variables (w) + XI,..., Wi + X,) formed by combining utilities with the noise random variables are then compared de- termine the outcomes of pairwise comparisons. Hence, the probability of preferring agent over j is given by
We also let D Rax= be the diagonal degree matrix with DH Σ/= Esy for E [ni, and L e D E be the graph Laplacian matrix. L can be expressed as L = x where X E (((11/2)x) is the matrix formed by collecting row vectors zzy -ey for (i.j) E E and j > i, with e being the ith standard basis vector in R". For the Laplacian L, we define the semi-norm with respect to L as ||æ/| Vx Lar for all x E R" (which is a remi-norm since L has a zero eigenvalue).
ous CDF G
Pi preferred over j) = P(w; + > wy + X,)
(3)
Gly w - w. ( dy = F F(w: - -,,)
3

---

Hypothesis Testing for Generalized Thurstone Models
As noted earlier, GTMs also encompass wide range of known parametric models as special cases, e.g., Thurstone models with F(t) - 1 pe-""" -²/2 dr (complemen- v2n tary Gaussian CDF) (Thurstone, 1927). BTL models with F(1) = 1/(1 + " (sigmoid function, which stems from Gumbel CDFs) (Bradley & Terry, 1952; Luce, 1959; Yellott, Jr. 1977), Dawkins models (Dawkins, 1969), etc. We can also define a pairwise probability matrix F(w) E [0, _|mx"n
Assumption 2.3 (Dynamie Range). There exists constant
8 0 such that for any pairwise comparison model under consideration, Pij E [ō. 1 6] for all (i,j) E E.
Note that under the null hypothesis, the Assumption 2.3 is satisfied by all Tf models with weights bounded by (1 8)/2. Subsequently, we assume that the constant satisfies b F- (1 6)/2. For any given pairwise com- parison model (Pij (i,j) E E}, define w² E W2 be the weights of Tr model that best approximates this pairwise comparison model in the maximum likelihood sense:
for a GTM TF with weight vector w via
{ F(we wy); (i,)) 0.
(F(w));s A
(4)
otherwise.
".* - arg min Iwu; {pis : (1.5) E EE)..
(8)
wEW,
We next describe the data generation process for GTMs and general pairwise comparison models alike. For any pair (i,j) E &, define the outcome of the mth "i vs. j" pairwise comparison between them as the Bernoulli random variable
Finally, we also assume in the sequel that the given choice function F exhibits strong log-concavity and has a bounded derivative on [-2b, 2b). i.e., there exist constants 3 > 0 such that:
1, preferred over j (with probability Ptj):
d2
z &
Va [- 26),
log(F(z)) 2 a and F( S B. dr²
0, j preferred over i (with probability 1 - Pt)),
(9) Several popular GTMs, including the BTL and Thurstone (Case V) models, satisfy both the above assumptions. The following proposition highlights that w" always exists and is unique for a strongly log-concave function F on W..
(5)
for m E [Rag]. where kij denotes the number of observed "i vs. j" comparisons. The given pairwise comparison data is
then a collection of these independent Bernoulli variables
Z A {Zi) (i.j) E E, m E [kg]]] For convenience, we also let Zig A E m== Z.J and Pij A Zij/ky.
Proposition 2.4 (Existence and Uniqueness of Maximum Likelihood). Suppose the observation graph 9 is connected, the choice function F IR [0, 1] satisfies (9), and Assump- tion 2.3 holds. Then, there exists unique optimal solution w" E W/ satisfying (8).
Parameter estimation for GTM: To present our testing formulation in the sequel, we explain how the parameters of a Tr model are estimated given pairwise comparison data Z (Shah et al., 2016). First, we define the weighted negative log- likelihood function? [ W [0. 1| R. U {+o0} as
The proof is provided in Appendix A.2. It follows from Proposition 2.4 and Gibbs' inequality that when the pairwise comparison model is indeed a TF model with weight vector w, then we have w² w.
I(w; Lig: : (i-j) {)) A Σ Púj log( (((:: w;))
(LE)
+ (1 piy)) log(1 F(w; w;))-
(6)
2.3. Minimax Formulation
Note that this function represents a weighted variant of the typical log-likelihood function used in parameter estimation (Shah et al., 2016; Vojnovic & Yun, 2016). The weights of the Tp model are estimated by minimizing I:
Given any fixed graph G. separation level > 0. choice function F, and constants 8 >> 0 and b 2 F- (1-(())))))))))) 5)/2, de- fine the sets Mu and My(e) of Tr and pairwise comparison models:
è e arg min Iww; (pig : (1,5) E ET), WEW,
Mo - (P: Assumption 2.3 holds and
where the constraint set W. A {w E W || I b, wT1 0} for some (universal) constant b, 1 E RD de- notes an all-ones vector, and the constraint w='100 allows
3 w E Wb such that / F(w)), (10)
M2(c) A P Assumption 2.3 holds and
for identifiability of the weights.
11p- F(w)llF 2 ze). (11)
inf NEW, n
2.2. Assumptions on Comparison Models
where || l|e denotes Frobenius norm. Now, we formalize the hypothesis testing problem in (1) as:
To facilitate the analysis of the hypothesis testing problem in (1), we introduce a simplifying assumption on the class of general pairwise comparison models. We assume that the pairwise probabilities Pij are bounded away from 0 and 1.
Ho ~~ P E Mo,
(12)
H1 Z ~ P Mi((

---

Hypothesis Testing for Generalized Thurstone Models
We will discuss the separation distance inf wew, P| F(w)]lr later. For now, note that we only test the set of observed comparisons & as it is not possible to determine whether the comparisons on E would conform to a TF model or some other pairwise comparison model. Next, for any fixed graph G, choice function F', and constants e, 6, b, we define the minimax risk as
The proof is provided in Appendix A.3. The upper bound is immediate, and the lower bound utilizes the information- theoretic bounds between f-divergences.
Test statistic: We now introduce our test statistic based on the approximation derived in Theorem 3.1. First, we partition the observed comparison data 2 into two (roughly) equal parts 2 {Z (i.j) E &, m E [[kky/20 /2]]} and Z2 Z \ Z1. The first half of the dataset Z is used to estimate the parameters è as shown in (7). Then, we use Zg to calculate the test statistic T via
R(G,e) e) - inf
sup PEMo
Pho (0(2))
+
P~PP under Ho
}. (13)
Zig 11 + F(uo; P(ūo=-ú0z) (K4 1)
sup PEMi(e)
PH, -
T (iJ))E
2 under H1
Zz Kiss
-2F(w; x
LK (15)
where the infimum is taken over all randomized decision rules (2 E {0. 1} (with 0 corresponding to Hy and to H)), and PH, and fr, denote the probability measures under hypotheses Hg and H1, respectively. Intuitively, this risk minimizes the sum of the worst-case type I and type II error probabilities. Finally, we define the critical threshold of the hypothesis testing problem in (12) as the smallest value of e for which the minimax risk is bounded by 1 (cf. (Rastogi et al., 2022)):
1k///21 where Ki = k.- |k,y Zij Em>sky, Em>
Z is
computed as before but using only the samples in Zz, and 1 denotes the indicator function on A. For an intuitive explanation of the definition of this statistic, consider the quantity
T'= Σ 2ig(Zi1-1 + -2 (K.))E
Zij R4)
-FF (w::[w/) ww)
Ky (K 1)
Ec a (>0: 11
(14)
(16)
obtained by substituting w" in place de in (15). Then, the expected value of T' is ||P F F(w")
Note that the constant here is arbitrary and can be replaced by any constant in (0, 1).
)(w>)] )|? This is because the expected value of the first term is pry and the last term -2 - wÿ Ptj. Hence, T' constructed by plugging in à in place of w" in an unbiased estimator of || P FP=F(w") I|? Our proposed hypothesis test thresholds T to determine the unknown hypothesis; H1 is selected if T exceeds a certain threshold. There is some resemblance between the test statis- tic T and those in (Makur & Singh, 2023; 2024; Rastogi et al., 2022) since all these statistics are "estimators" for squared Frobenius distances of pairwise comparison mod- cls. However, the techmiques used to analyze them are very different. For example, our theoretical analysis crucially relies on sample splitting, while the other two do not. We will discuss analytical expressions for the threshold next and a data-driven approach to determining the threshold in Section 4.
3. Main Results
In this section, we present the main results of the paper. We first show that our notion of separation distance can be simplified for analysis, then proceed to bound the critical threshold and minimax risk, and finally, establish type and error probability bounds in the sequential setting.
3.1. Separation Distance and Test Statistic
Recall that to formalize (12), we defined the separation distance of a pairwise comparison model to the class of TF models as infwew; P F(w) ]|F (for fixed F). To make this separation distance more amenable theoretical analysis, we approximate it in the next theorem with the simpler quantity P [[w"")]rr where w" is given in (8). Theorem 3.1 (Separation Distance to TF Models). Let P be a pairwise comparison matrix satisfying Assumption 2.3. Then, there exists a constant e1 > 0 (that does not depend on n) such that the separation distance between P and the class of Te models satisfies
3.2. Upper Bound on Critical Threshold
In this section, we make the simplifying assumption that kaj 2k (with k E N) for all (i,j) E E. The ensuing theorem, proved in Appendix B, establishes an upper bound on the critical threshold of the hypothesis testing problem defined in (12).
e (PP-F(w") )Ie < inf ||P=F(w)]l=- S (I-=F(w)) "Ie,
Theorem 3.2 (Upper Bound on Critical Threshold). Con- sider the hypothesis testing problem in (12), and assume that Assumption 2.3 holds and k 2 2. Then, there exists a
weW.
where wn is given by (8).
5

---

Hypothesis Testing for Generalized Thurstone Models
constant 0g such that the critical threshold defined in (14) is upper bounded by
- w where X2(L) is the second smallest eigen- value of the Laplacian L. The connectedness of the graph ensures that (2( > 0, and the value of X² (L) is known for various classes of graphs (cf. (Chung, 1997)).
2 c S
nkk
Moreover, it is worth emphasizing that our error bounds in || ll semi-norm (in Theorem 3.3) remain valid even when the observation graph is disconnected. Furthermore, since the proof of Theorem 3.2 relies only on these bounds, the results of Theorem 3.3 hold regardless of graph connectivity. When the graph G is disconnected, solutions vi and w" of (7) and (8) may not be unique, but the error ||20 - w llz is well- well-defined as the non-unique component lies in the null space of L. Thus, our upper bounds on critical thresholds still hold. This ensures that our testing framework for Tr models remains applicable even in settings where parameter estimation is infeasible due to disconnected observation graph, highlighting a fundamental distinction between test- ing and parameter estimation of TF models. Moreover, we also note that our results lead to bounds on critical thresh- olds even when the separation distance is defined in other norms; see Appendix G for more details.
In our analysis, we select H, if > and Hg otherwise, where y an appropriate constant independent of n, k (see (37)). The analysis relies on establishing non-trivial error bounds (in || l|z semi-norm) for parameter estimation of Tr models when the data is generated by a general pairwise comparison model, which is not necessarily a GTM (i.e., deriving error bounds under a potential model mismatch). The error bounds allow us to prove bounds on the mean and variance of the test statistic T under both hypotheses Hn and H1. Then, using Chebyshev's inequality, we can bound the probabilities of error of our test under each of the hypotheses, which induces an upper bound on the critical threshold.
We also note that in the special case where TF is a BTL model, our upper bound on & recovers the bound in (Makur& & Singh, 2023; 2024) for complete graphs. But our likelihood-based proof is quite different to the spectral ideas in (Makur& & Singh, 2023; 2024). Finally, we present the key error bounds for parameter estimation when data is generated by general pairwise comparison model needed to prove Theorem 3.2.
3.3. Information-Theored Lower Bounds
We now establish coormatiion-hhorretii lower bounds on the minimax risk and critical threshold for the hypothesis testing problem in (12). For simplicity and analytical tractability, assume that k;j k N for all (i, E E, and assume that the observation graph is Euper-Eulerian (Catlin, 1992), i.e., it has an Eulerian spanning sub-graph 9 (mn), so that every vertex of ς has even degree. Then, & has a cycle decomposition C by Veblen's theorem (Biggs et al., 1976; Seshadri & Ugander, 2019), where is a collection of simple cycles a that partitions the undirected edges of G. The ensuing theorem, proved in Appendix C, presents our minimax risk lower bound.
Theorem 3.3 (Error Bounds for Parameter Estimation). Consider any pairwise comparison model satisfying As- sumption 2.3 with w" given by (8) and i constructed ac- cording to (7) from data generated by the model. Then, for some constant 63 > the following tail bound holds on the estimation error of w":
C2n a aF
Vt 21
P 1 w0 w'll
S Set
Theorem 3.4 (Minimax Lower Bound). Consider the hy- pothesis testing problem in (12) and assume that the obser- vation graph G is super- Eulerian with spanning Eulerian sub-gruph G. Then, there exists a constant C4 >> such that for any >> the minimax risk in (13) is lower bounded by
where a is defined in (9). Moreover, for any p 2 1, there ex- ists a p-dependent constant d(p) > such that the expected pth moment of the error is bounded by
dp))
E|| - 100--11133 1E
a²kF(-26)2
e( 22 2 exp
cakerete 1812
Σ
|a13
aEC
The proof is provided in Appendix A.4. In the special case where the pairwise comparison model is a GTM, our bounds recover the bounds derived in (Shah et al., 2016, Theorem 3) up to constants. However, our result is much more general because it holds for any pairwise comparison model; this requires a careful formulation and development of the proof techniques.
where |o| denotes the length of a cycle a E C, and C is the cycle decomposition of g.
Our argument utilizes the Ingster- -ustiin--Ssinaaa method (Ingster, 1994; Ingster & Suslina, 2003), which is similar to Le Cam's method, but provides a lower bound by considering a clev- erly chosen point and a mixture on the parameter space instead of just two points. Our specific construction is in- spired by the technique introduced in (Seshadri & Ugander,
We remark that these eтror bounds can be readily con- verted into error bounds using the relation ||v tú--op w0 2
6

---

Hypothesis Testing for Generalized Thurstone Models
2019), which establishes a lower bound for testing the IIA assumption (i.e., BTL models) for Fulerian graph structures. We extend their approach in three ways. First, we generalize their method to accommodate any GTM rather than just the BTL model. Second, we use a different technique based on Theorem 3.1 to lower bound separation distance from the class of TF models. Moreover, our work quantifies separa- tion using Frobenius norm instead of sums of total variation (TV) distances. Third, our argument holds for broader class of graphs, namely, super-Eulerian graphs. Note that the question of algorithmically constructing Fulerian sub- graphs of graphs has been widely studied (Haghparast & Kiani, 2019).
and II error probabilities. We will do this in the sequen- tial setting, where data is observed incrementally com- mon practical scenario which subsumes the standard fixed sample-size setting, cf. (Manole & Ramdas, 2023; Howard et al., 2020). In the sequential testing framework, at each time step, we observe a single "i J" comparison for every (i,3) E &. (The subsequent analysis can be extended to a general setting where we observe only one comparison for some pair (i.j) E & or even a variable number of compar- isons at every time step.) At time kn + k with k1, k E N, we define Thi to be the value of the test statistic T in (15), where comparisons from kj time-steps have been used to build the dataset 21 to estimate parameters using vù and k time-steps have been used to build the dataset 2g to calcu- late the statistic T. Note that Z and Z no longer need to be similar in size. Then, we can decide based on threshold- ing T (see Theorem 3.7) whether to collect more data or stop and reject Ho while controlling the probabilities of error. If the testing process ends without rejecting Ho. then we can accept Ho. A key observation underlying our analysis is the following reverse martingale property (see, e.g., (Howard et al., 2020; Manole & Ramdas, 2023)).
The following proposition simplifies Theorem 3.4 to obtain lower bounds on the critical threshold for several classes of graphs.
Proposition 3.5 (Lower Bounds on Critical Threshold). Un- der the assumptions of Theorem 3.4, the following lower bounds hold for the critical threshold defined in (14):
1. If G is complete graph with odd n vertices, then e² = =S(1/nk)).
2. If 9 is a d-regular graph with constant d 2 2, then
Proposition 3.6 (Reverse Martingale), Fix any hn E N. and let FR 8 (i.i)e a (Z (m==++1 Z.j. 4, t Z 1t,tk+22.... be a non non-increasing sequence of a-algebras, where 2 denotes the product a a-algebra. Then, the sequence of statistics {Th,. k 2 2} is a reverse martingale with respect to the reverse filtration (Fi: :k 2 2), i.e., for h 2 1hikk is Fa-measurable and IE B [ .+1
=C = =S)(1/nkk).
3. G is single cycle graph with n vertices, then = Q(1/n2k).
4. I is a two pro-dimensional v x vn toroidal grid on n vertices formed by the Cartesian product of two cycles of length VT, then e² = (11/n//4)))
The proof is presented in Appendix D.I. This observation allows us to develop time-uniform bounds in terms of on the probabilities of type I and II errors, i.e., they hold for all l larger than a constant. The next theorem, proved in Appendix D.3, presents our bounds on the probabilities of type I and II errors.
The proof of Proposition 3.5 is provided in Appendix C.I. It involves calculating the number of simple cycles and the individual cycle lengths in the cycle decompositions C. The lower bounds on & are then obtained from Theorem 3.4. We remark that our minimax upper and lower bounds on Ec match for the complete graph case, demonstrating the min- imax optimality of the threshold's scaling (up to constant factors). Moreover, they also match with respect to & for other classes of graphs as well. It is worth mentioning that in the special case of BTL models with single cycle graphs, our lower bound on &e improves the high-level scaling be- havior in (Seshadri& & Ugander, 2019) from 22(1/ / // k to ((1/V/2k) (when Ec is quantified in terms of Frobenius norm). Lastly, we remark that for single cycle graphs, the gap between the upper and lower bounds in terms of n intu- itively holds because our lower bounds become larger when there are more cycles in C, which is only in this case.
Theorem 3.7 (Type I and Type Error Probability Bounds). Under the sequential setting discussed above, the following bounds hold on the extremal type I and type II error proba- bilities. There exist constants co, ca, Cr, 0g such that for all t 2 1, V 1/c), kn E N. and E 2 csvt/ / we have
+ c 0718 Ex.
sup PHo PEMo
3k 2, Think 2 col
n kn
k
ntlk Su+et,
+ +C&V
k
sup PHI 3k 2, Thk - -(D czl ( /n/)2 (c)
3.4. Upper Bounds on Probabilities of Type I and II Errors
Pn c7 c -AD (4D + n / /k/))///// )
To complement the minimax risk lower bound in Theo- rem 3.4, we establish upper bounds on the extremal type
k Suto"
k
7

---

Hypothesis Testing for Generalized Thurstone Models
where D A |P F(w")lle and CKy (1..5looo222)/////
in Appendix F to validate our threshold estimation proce- dure, compare our performance with the spectral method of (Makur & Singh, 2023; 2024) for the BTL model, and provide additional experiments on real-world datasets.
We now make several remarks. Firstly, our error probability bounds encode the scalings of the thresholds to accept or reject Ho (see (37)). Secondly, our bounds hold regardless of how the decision-maker assigns data collected different time-steps to 21 and Z2. Moreover, they provide insights on how to split the data based on the topology of the obser- vation graph, e.g., the bounds suggest an equal split of the data for complete graphs, whereas for a single cycle, achiev- ing better type error control requires a larger value of ki To illustrate this and help parse Theorem 3.7, we present corollaries of Theorem 3.7 for the complete and single cycle graph cases in Appendix E.
Estimating the threshold: Given a pairwise comparison dataset 2 _ {z : (i.j) E &, m E [kx]]], we em- ploy an umpirical-quantte based approach to determine the critical threshold for our hypothesis testing problem. We generate multiple Tp models with random skill scores w E IR drawn independently and uniformly in [-b, bj and translated to satisfy w=1 = O, and simulate ky "i vs. j" comparisons by sampling binomial random variables { {Zig ~ Bin(kss, F(w; test statistic T for each simulated dataset, repeating the pro- cess a sufficient number of times to build distribution of test statisties. Finally, we extract the 95th percentile value from this distribution as our empirical threshold.
(y))Joeee We then compute the
Thirdly, our bounds clearly hold in the non-sequential fixed sample-size setting, as we can just fix a particular value of k. Hence, adding the two extremal probabilities of error yields upper bounds on the minimax risk. Notably, the proof of Theorem 3.7 requires us to develop a time-uniform version of the well-known Vershynin, 2013) specialized for our setting (see Lemma D.2 in Appendix D.2). Additionally, as an intermediate step in the proof, we also obtain time-uniform confidence inter- vals under the null hypothesis Ho, as demonstrated in the following proposition.
In our first experiment, we investigate the behavior of the thresholds for T based on this empirical-quantil-- -baee ap- proach for various values of n and & and for different graph topologies and Tr models. We considered values of rang- ing from 15 55 with intervals of 10, and set k;-- = & for all (i.j) E E with k E {12, 20}. graph topologies includ- ing complete graphs, [vn x [vn toroidal grids, and sparse graphs generated from Erdós-Rényí ((n, p) models with parameter = 2 log" (n)/ /n, and Tr models such as standard Thurstone (Case V) and BTL models. For each choice of parameters, we generated 400 models by ran- domly sampling weights with b = F-1((0.8). and gen- erated synthetic comparison data. The scaled test statistic k T'nn was computed for every parameter choice, and the 95th percentile value of this scaled T was identified as the threshold 7. Figure plots these 95th percentile values with respect to n for various parameter choices. Notably, the value y remains roughly constant with n, k and model TF for complete graphs. For all these cases, the values stabi- lize approximately to certain constant, illustrating that the thresholds obtained via the empirical-quuntil--be proach follow the same high-level scaling as the theoretical threshold in (37).
-rinht inequality (Rudelson &
Proposition 3.8 (Confidence Interval for T)). Suppose w is estimated as in (7) from the comparisons over kn time- steps. Then, there exists a constant e7 > O such that for all E (0, 1/e) and 1 EN,
VEER lx.
PH
3k 2 2, 1r. 2 [IF(i) - F(w")ll + C7
k
(kN k
+ 4|| ( - F(w"))l
S V.
Proposition 3.8 is established in Appendix D.2. We remark that the distribution of [F(()) - [IF above can be approximated either by leveraging the asymptotic normal- ity of œ w² (Gao et al., 2023; Han al., 2024), or by utilizing bootstrapping techniques; this gives (1 2v) time- uniform confidence intervals. Additionally, the constant e here is also the constant in our specialized version of Hlanson-rright inequality (noted above) and can be approx- imated via simulations for our setting. An empirical inves- tigation into estimating the constant e7 and the subsequent confidence intervals can be found in Appendix F.3.
ap-
In our next experiment, we apply our test to the LMSYS chatbot leaderboard (Chiang et al., 2024), a widely used benchmark for evaluating the performance of LLMs. The dataset contains collection of pairwise comparisons be- tween various L.MSs based on their response to prompts, which are then used to obtain Elo ratings. We retain the directional nature of comparisons, where an "i vs. j" com- parison indicates model as the first response and j as the second during the evaluation. We rank the LLMS based on their frequency of appearance in the dataset and perform the test repeatedly on the top-n LLMs in this ordering, with ranging from 5 to 21 with gaps of 2, for both Thurstone and
4. Experiments
In this section, we develop a data-driven approach to se- lect the threshold for our test and conduct simulations to validate our theoretical results on synthetic and real- world datasets. We include several additional experiments
8

---

Hypothesis Testing for Generalized Thurstone Models
system (Brams & Ismail, 2024), group size of approxi- mately leads to accurate modeling for the top-n models, ranked based on their total available data.
95th Percentie Value
5. Conclusion
In this work, we developed a rigorous testing framework to determine whether pairwise comparison data is generated by underlying generalized Thurstone model with given choice function F. We derived both upper and lower bounds the critical threshold of our testing problem, which de- pended on the topology of the observation graph. These bounds were shown to be tight for certain graph classes, such as complete graphs. In addition, we proposed a hy- pothesis test based on our notion of separation distance and established theoretical guarantees for this test, including time-unifone bounds type I and II error probabilities as well minimax lower bound on the risk of the test- ing problem. Alongside this, auxiliary results such as error bounds for parameter estimation and confidence intervals under the null hypothesis were derived. To validate our findings, we conducted experiments on both synthetic and real-world datasets and introduced data-driven approach for determining the test threshold.
0.4
2D Grd,
Completee k=12
02-
Thurstone. din.ol,
-8- Thurstons, Oin.pl, k-20
Thurstone, Complete, k-12
- RTL,, Gin.nh, nl, k-12
Thurstone, Complete k-20
-- BTIL. Gin.al dl. k=20
0.
Figure I: Estimated scaled threshold for various values of n, k graph topologies, and Ty models.
Kavg T/n for BTL
2.-
Kaug T/n for Thurstone
Threshold for BTL
Normalized Values
3.5
Threshold for Thurstone
98
1.0
0.5
0.0
This study opens up several avenues for future research. For instance, extending the hypothesis testing framework to handle general multi-way comparisons rather than pair- wise comparisons is one such direction. Another direction is developing active testing techniques within the frame- work of generalized Thurstone models that optimize test performance. Finally, extending the testing and estimation frameworks for such models to dependent data is also im- portant avenue real-world data often exhibits correlations that could affect inference results.
Figure 2: Scaled test statistics and the estimated thresh- olds evaluated on the LMSYS dataset.
BTL models. For each n, we plot the values in Figure 2 of the (scaled) test statistic kavg T/n and the obtained (scaled) thresholds using the quantile approach (with the same pa- rameters as above), where kavg is the average of kiy over all (i.j) E E. By randomizing over the partitioning of the dataset Z into Z1 and Z2 and computing T each time, we essentially obtain distribution of T and plot these values in Figure 2 as scatter plot. The figure highlights that both BTL and Thurstone models perform well in modeling for smaller values of n with only 10% of samples above the threshold, but exhibit significant deviations for larger values of n as around 60% of samples are above the threshold for = 21. The 60% of samples above the threshold can be interpreted as a bootstrapped estimate of the test's power indicating 40% chance that the model lies within 95% sta- tistical deviations from BTL. The figure also shows that deviation from Thurstone increases as n increases, a top-9 batch size provides a statistically accurate to the Thur- stone model, and the deviations are significant for n 2 21. The results suggest that when using multi-tier Elo rating
Acknowledgements
This work supported by the National Science Founda- tion (NSF) CAREER Award under Grant CCF-2337808.
Impact Statement
This work is primarily theoretical and does not have im- mediate societal consequences. However, if practitioners apply our approaches to make decisions in real-world set- tings, there could be both positive and negative implications. On the one hand, our methods can help determine accurate models for comparison data, such as whether data conforms to a Tr model, or help detect certain kinds of biases in data. On the other hand, our methods concern ranking models and using any ranking mechanism without due care in the real- world may unintentionally exacerbate existing inequalities, such as unequal access resources and opportunities.
9

---

Hypothesis Testing for Generalized Thurstone Models
References
Davidson, D. and Marschak, J. Experimental tests of stochastic decision theory (1959). In Economic Informa- tion, Decision, and Prediction, volume 7-1 of Theory and Decision Library, pp. 133-171, Dordrecht, Netherlands, 1974. Springer.
Biggs, N. L., Lloyd, E. K., and Wilson, R. J. Graph Theory 1736-1936. Oxford University Press, Oxford, UK 1976.
Bong, H.. Li, W., Shrotriya, S., and Rinaldo, A. Nonpara- metric estimation in the dynamic Bradley-Terry model. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 3317- 3326, Palermo, Italy, August 26-28 2020.
Dawkins, R. A threshold model of choice behaviour. Animal Behaviour, 17(1):120-133, February 1969.
Durrett, R. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cam- bridge University Press, New York, NY, USA, fifth edi- tion, 2019.
Bradley, R. A. and Terry, M. E. Rank analysis of incom- plete block designs. I. The method of paired comparisons. Biometrika, 39(3/4):324-345, December 1952.
Brams, S. J. and Ismail, M. S. Multi-tier tournaments: Matching and scoring players. arXiv:2407.18845 [econ.TH], July 2024.
Elo, A. E. The Rating of Chessplayers, Past and Present. Arco Publishing, Inc., New York, NY, USA, second edi- tion, 1986.
Busa-Fekete, R., Fotakis, D., Szörényi, B., and Zampetakis, M. Identity testing for Mallows model. In Advances in
Fan, J., Hou, J., and Yu, M. Uncertainty quantification MLE for entity ranking with covariates. Journal of Muchine Learning Reseurch, 25(358):1-835 August 2024.
Neural Information Processing Systems 34 (NeurIPS), pp- 23179-23190, December 6-14 2021.
Catlin, P. A. Superculerian graphs: A survey. Journal of Graph Theory, 16(2):177-196, June 1992.
Feder, T. and Subi, C. Packing edge-disjoint triangles in given graphs. Electronic Colloquium on Computational Complexity (ECCC), (13):1-12, February 2012.
Cattelan, M., Varin, C., and Firth, D. Dynamic Bradley-
Terry modelling of sports tourmaments. Journal of the Royal Statistical Society, Series (Applied Statistics), (1):135-150, 2013.
Gao, C., Shen, Y., and Zhang, A. Y. Uncertainty quantifica- tion in the Bradley- -erry-Terr---eee model. Information and Inference: A Journal of the IMA, 12(2):1033-114 140, June 2023.
Chatterjee, S. Matrix estimation by universal singular value thresholding. The Annals of Statisties, 43(1):177-214, February 2015.
Haghparast, N. and Kiani, D. Spanning Eulerian subgraphs of large size. Graphs and Combinatorics, 35(1):201-206. January 2019.
Chen, Y., Fan, J., Ma, C., and Wang, K. Spectral method and regularized MLE are both optimal for top-K ranking. The Annals of Statistics, 47(4))2204 2235,223552020 2019.
Hahn. G. and Meeker, W. Q. Statistical Intervals:
Guide for Practitioners. Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., New York, NY, USA, 1991.
Chiang, W.-L.., Zheng, I.., Sheng, Y., Angelopoulos, A. N., Li, T., Li, D., Zhang, H., Zhu, B., Jordan, M., Gon- zalez, J. E., and Stoica, I. Chatbot arena: An open platform for evaluating LLMs by human preference. 2Xiv:2403.04132 [cs,AI], March 2024.
Han, R., Tang, W., and Xu, Y. Statistical inference for pair- wise comparison models. arXiv:2401.08466 [math.ST], January 2024.
Chierichetti, F., Kumar, R., and Tomkins, A. On the number of trials needed to distinguish similar alternatives. Pro- ceedings of the National Academy of Sciences (PNAS), 119(31), July 2022.
Herbrich, R., Minka, T., and Graepel, T. TrueSkil A Bayesian skill rating system. In Advances in Neural Information Processing Systems 19 (NeurIPS), pp. 1-8, Vancouver, BC, Canada, December 4-9 2006.
Chung. F. R. K. Spectral Graph Theory, volume 92 of Conference Board of the Mathematical Sciences (CBMS) Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, USA, 1997.
Howard, S. R., Ramdas, A., McAuliffe, J. D., and Sekhon, J. S. Time-uniform Chernoff bounds via nonnegative su- permartingales. Probability Surveys, 17:257-317, 2020.
Clarke, S. R. and Norman, J. M. Home ground advantage of individual clubs in english soccer. Journal of the Royal Statistical Society, Series D (The Statistician), 44(4):509- 521, 1995.
Hunter, D. R. MM algorithms for generalized Bradley- Terry models. The Annals of Statistics, 32(1):384-444 February 2004.
10

---

Hypothesis Testing for Generalized Thurstone Models
Ingster, Y. I. Minimax detection of signal in e metrics. Journal of Mathematical Sciences, 68(4):503-515, Febru- ary 1994.
Mania, H., Ramdas, A., Wainwright, M. J., Jordan, M. I., and Recht, B. On kernel methods for covariates that rankings. Electronic Journal of Statistics, 12:2537-2577, 2018.
Ingster. Y. I. and Suslina, I. A. Nonparametric Goodness- of-Fit Testing Under Gaussian Models, volume 169 of Lecture Notes in Statistics. Springer, New York, NY,
Manole, T. and Ramdas, A. Martingale methods for sequen- tial estimation of convex functionals and divergences. IEEE Transactions on Information Theorr, 69(7))4641- 4658, July 2023.
USA, 2003.
Jadbabaie, A., Makur, A., and Shah, D. Estimation of skill distribution from tournament. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 8418- 8429, Vancouver, BC, Canada, December 6-12 2020.
Marschak, J. Binary-choice constraints random utility in- dicators (1960). In Economic Information, Decision, and Prediction, volume 7-1 of Theory and Decision Library, pp. 218-239, Dordrecht, Netherlands, 1974. Springer.
Jadbabaie, A., Makur, A., and Shah, D. Estimation of skill distributions. IEEE Transactions on Information Theory, 7009):6447-6480, September 2024.
McCullagh, P. and Nelder, J. A. Generalized Linear Mod- els, volume 37 of Monographs on Statistics and Applied Probability. Chapman and Hall, New York, NY, USA, second edition, 1989.
Jannach, D., Resnick, P., Tuzhilin, A., and Zanker, M. Rec- ommender systems- -yyted matrix completion. Commu- nications of the ACM, (9(1)):94-)1)))))) November 2016.
McFadden, D. Conditional logit analysis of qualitative choice behavior. In Zarembka, P. (ed.), Frontiers in Econometrics, Economic Theory and Mathematical Eco- nomics, pp. 105-142, New York, NY, USA, 1973. Aca- demic Press.
Kirkman, T. P. On a problem in combinations. The Cam- bridge and Dublin Mathematical Journal, 2:191-204, 1847.
Lauga, N. NBA games data. Kaggle, 2023. URL
McLaughlin, D. H. and Luce, R. D. Stochastic transitiv- ity and cancellation of preferences between bitter-sweet solutions. Psychonomic Science, 2(3):89-990 90, January 1965.
https: / /wwww kaggle. com/ datasets/ nathanl aaceallugaaaaaa nba- aaraaa-gamss/daee data. Accessed:
January 2025.
Liu, Y., Fang, E. X., and Lu, Lagrangian inference for ranking problems. Operations Research, 71(1):202-223, January 2023.
Morley, B. and Thomas, D. An investigation of home ad- vantage and other factors affecting outcomes in english one-day cricket matches. Journal of Sports Sciences, 23 (3):261-268, March 2005.
Luce, D. Individual Choice Behavior: A Theoretical Analysis. John Wiley & Sons, Inc., New York, NY, USA, 1959.
Negahban, S., Oh, S., and Shah, D. Iterative ranking from pair-wise comparisons. In Advances Neural Informa- tion Processing Systems 25 (NeurIPS), pp. 2474-2482, Lake Tahoe, NV, USA, December 3-8 2012.
Makur, A. Information Contraction and Decomposition. Sc.D. thesis in Electrical Engineering and Computer Sci- ence, Massachusetts Institute of Technology, Cambridge, MA, USA, May 2019.
Negahban, S., Oh, S., and Shah, D. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1): 266-287, January 2017.
Makur, A. and Singh, J. Testing for the Bradley-Terry. Luce model. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 1390-1395, Taipei, Taiwan, June 25-30 2023.
Nelder, J. A. and Wedderburn, R. W. M. Generalized linear models. Journal of the Royal Statistical Society, Series (General), 135(3):370-384 1972.
Makur, A. and Singh, Minimax hypothesis testing for the Bradley-Terry-Luce model. arXiv:2410.08360 [cs.LG], October 2024.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems 35 (NeurIPS), pp. 27730- 27744, New Orleans, LA, USA, November 28- December 9 2022.
Makur, A. and Zheng, L. Comparison of contraction co- efficients for f-divergences. Problems of Information Transmission, 56(2); 103-156, April 2020.
Mallows, L. Non-null ranking models. I. Biometrika, 44 (1/2):114-130, June 1957.

---

Hypothesis Testing for Generalized Thurstone Models
Plackett, R. L. The analysis of permutations. Journal of the Royal Statistical Society, Series C (Applied Statisties), 24 (2):193-202, 1975.
Zhao, S., Zhou, E., Sabharwal, A., and Ermon, S. Adaptive concentration inequalities for sequential decision prob- lems. In Advances in Neural Information Processing Systems 29 (NeurIPS), pp. 1351-1359, Barcelona, Spain, December 5-10 2016.
Rastogi, C., Balakrishnan, S., Shah, N. B., and Singh, A. Two-sample testing on ranked preference data and the role of modeling assumptions. Journal of Machine Learning Research, 23(225): 1::44,,,4,, September 2022.
Rudelson, M. and Vershynin, R. Hanson Wright inequality and sub-Gaussian concentration. Electronic Communica- tions in Probubility, 18:1-9, 2013.
Seshadri, A. and Ugander, J. Fundamental limits of testing the independence of irrelevant alternatives in discrete choice. Proceedings of the 20th ACM Conference on Economics and Computation (EC), pp. 65-66, Phoenix, A7. USA, June 24-28 2019.
Seshadri, A., Ragain, S., and Ugander, J. Learning rich rankings. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 9435-9446, Vancouver, BC, Canada, December 6- 12222222 2020.
Shah, N. B., Balakrishnan, S., Bradley, J., Parekh, A., Ram- chandran, K., and Wainwright, M. J. Estimation from pairwise comparisons: Sharp minimax bounds with topol- ogy dependence. Journal of Machine Learning Research, 17(58):1-47, 2016.
Simons, G. and Yao, Y.-C. Asymptotics when the number of parameters tends to infinity in the Bradley-Terry model for paired comparisons. The Annals of Statistics, 27(3): 1041-1060, June 1999.
Thurstone, L. L. A law of comparative judgment. Psycho- logical Review, 34(4):2733285) 1927.
Thurstone, L. I.. The indifference function. The Journal of Social Psychology, 2(2):139-167, 1931.
Tversky, A. Elimination by aspects: A theory of choice.
Psychological Review, 79(4):281-299, July 1972.
Vojnovic, M. and Yun, S. Parameter estimation for general- ized Thurstone choice models. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 498-506 506, New York, NY, USA, June 19-24 2016.
Yellott, Jr., J. The relationship between Luce's 's choice ax- iom, Thurstone's 's theory comparative judgment, and the double exponential distribution. Journal of Mathematical Psychology, 15())1109-144, April 1977.
Zermelo, E. Die berechnung der turnier-ergebnisse als ein maximumproblem der waahscheenlickkisseecnnng Mathematische Zeitschrift, 99(1):436-466 December 1929.
12

---

Hypothesis Testing for Generalized Thurstone Models
A. Proofs of Proposition 2.4 and Theorems 3.1 and 3.3
A.I. Additional Notation and Preliminaries
We begin by introducing some additional notations and discussing some necessary preliminaries that will be used throughout our proofs. To simplify our notation, we use f(w) to denote I(w; (Pig (i.j) E E}) where Pij are computed based on the partitioned dataset 21. Similarly, use (w) to denote I(w; (Pij (i, E}) where Piy are the actual underlying pairwise comparison probabilities. When w: = w" or w = i we simplify the notation by using F and to denote the matrices F(wx) and F(xØ) (cf. (4)) respectively, for brevity. We say that a random variable X μ² --suu--aausian, if satisfies the condition, log (og(E(exp(sxX)
$ 2²²s2 for all R.
Notably, i is computed as in (7) even though the data may not conform to an underlying TF model. Throughout the appendices, we denote various constants using overlapping labels, such as c, C1, C2,... to simplify our notation and facilitate readability. Moreover, we define E+ to denote the set [(i,j) E:J: }= i}.
A. PRELIMINARIES
Recall that, as defined in (8), w" represents the weights of a TF model that best approximates the pairwise comparison model {pij. j) E E). Now, we show that any pairwise comparison model can be converted into its eemmmmyymtttic counterpart p (i. } such that both of them share the same optimal weights.
Lemma A.1 (Skew-symmetrized Model). For a symmetric edge set E, the pairwise model {piz (i,j) E E} and and its
|pp Ppt (1.5) E E} has the have the same optimal TT weights wt as defined (8).
skew-symmetric counterpart
2
Proof: Note that the weighted negative log-likelihood objective can be written as
(w))=
arg min wEW:uTI00
Σ
Pig looo(F(uus - wy)) + (1 Piş) log(1 F(w; w;))
(i.))E
arg min NEWWTlIs)
Σ
Pij log(1
F(w, w;)) + (1 - Pis) log( (P((F F011((1000 - wi))
(K,))E
arg min w wwW 110 1=
Σ
Pij +1
Pji log(F(us - (F(()( + (1 Pij + Pjs
1
(og(F(w; - -w;))
2
2
(1,))E
where Çi follows since F(-x)= = F()) and (2 follows by adding the first two equations and dividing by two.
Therefore, for any pairwise comparison model {ps: : (i, E E}, we can define its skew-symmetrized counterpart {gg; (f.j) E E} where
A (1.1) E E,
Pij Pjs
(17)
2
We call these transformed probabilities yi as skew-symmetrized probabilities because we have di + qjz = 1, and thereby this transformation effectively removes any distinctions between "i vs.j" j" and "j vs. i" comparisons. Also, note that for any pairwise comparison model satisfying Assumption 2.3, its skew-symmetrized model also satisfies In a similar manner, we can define Úij f as the skew-symmetrized version of the empirical probabilities. With this notation in place, we are ready state the proof of Proposition 2.4 below.
A.2. Proof of Proposition 2.4
The uniqueness of wr follows directly from the strong log-concavity of F(-). This is because if o*, 0", w² E W are any two non-unique solutions of (8) such that ("²) = (w)), then by strong log-concavity F and the fact that Kg 0 for (i, E E along with connectedness of graph, for any 0 (0, 1), we have
Uniqueness:
01 (1 (w²" --20 Σ Mi log( (F( of)) 2(1 0) Σ (KJ)EE
4h log( (F(w) -wz))
(i.))EE
13

---

Hypothesis Testing for Generalized Thurstone Models
> - Σ Ti log (F(O(1) 13)) + (1 - (1-0)(w} - wj)))
(i.))EE
1" (0v" + (1- O)w-)
This gives a contradiction since Ov* + (1 - 0)w" achieves a higher likelihood (or a lower objective value). The existence of w" under Assumption 2.3 and finite follows from the extreme value theorem since a continuous function is being optimized over compact set. Notably, the existence of w" also holds for disconnected graphs. As a bonus, we provide a proof of existence even when the parameter 6 = oc, but for a connected graph g.
Existence: Now, we will utilize the connectedness of graph 9 and Assumption 2.3 to show the existence of w". Define sequence {w(m) I²" E N {0}}
w (m) argmin w;=0: (ww).
[ Sm
Clearly, (m)) exists as the optimization of a convex function (*()) is being performed over a compact set. Define the following sets as the components of we that potentially diverge to oo:
S+ = { i E [n] lim sup (wo(m)), - + S_ 5- i [n] lim inf (wllm)), = -00] m
We will show that S+ S_ Ø. Notably, if S+ * Ø, then consider the partition of [r|] as S+ U St. Clearly, 1 E S + Ø. Since the observation graph G is connected, for some i E S+ there exists j E St. such that Ojz > (by Assumption 2.3). This implies that ーqi log( (ww) (m)) -w: such that on the set (w:- - w 2 A}, we have
)) + toc as m + too. Hence, we can find constant >>> 0
Yj log(F(w; wz)) 1" (v)
Equivalently, for any with wj > A, we have
(w)) 2 2zt log(F(A)) > (w(w(()) 2 1" (m)(m)
where the first inequality follows since each term in (-) is non-negative. Therefore, we must have v((m)) < (m) + A for all & N. Since i E S4, it follows that S_ by definition, which contradicts the assumption that j S Hence, conclude that S+ 0. A similar argument shows that S_ = Ø. The fact that S+ S_ Ø implies that the sequence (m)) m NNU U } admits convergent subsequence, which proves the existence of w".
A.3. Proof of Theorem 3.1
The upper bound is trivial to prove
inf |P- F(w)lFF S |P - F(w")(l= )|(F = ||P Fllr, WEW,
where F the pairwise probability matrix associated with the optimal weights. Now to prove the lower bound, observe that
inf WEW, (..))E
Σ (piy F(w, - w,))²
(Pij F F(w: w)))) F(w; w)y F(w; - w)))
2 inf F(- F(-2bb(11 F(-2b)) wEW;
Σ
(i.))
@ inf weWh
Σ
x [[Bernoull(i::)))erroollll w);))
(i.))E
inf wEW Wh
Σ
DKL (Be
w,)))
(K,))S
inf weW,
Σ (i.j)EE
Pij log
Pij F(w; - w,y +11 Piiz)ogg - Pij
F(w; w.)
14

---

Hypothesis Testing for Generalized Thurstone Models
Pij + (1 - pis)) log 1 F( wz))
Pei
Pij log
F(w, wwz)
(EJ)EE
2c
[ernoulli(ps) - Bernoulli -F - -w)))lfvv (i,))E
Σ
2c
Σ
(Pij F(w, -wz))²
(i,))E
where, in (1 c F((2b)(1 F(-26) and (-1l-) denotes the divdiregee between Bernoulli random variables and in <2 we utilize the fact that (2 2 DKL (R) for two distributions R and Q and where ( denotes the Kullback-Leibler (KL) divergence between two distributions, Ça follows since w" are the optimal weights maximizing (8) for the TF model. Finally, Ç1 follows by Pinsker's 's inequality DKL (R(P)) 2 2 Plfvv and thereby completing the proof.
A.4. Proof of Theorem 3.3
We begin by recalling the definition of w E arg min [(w) in terms of the symmetrized probabilities Z5 defined in (17)
as
i(w) 2
Σ deg log F(w; - wy)) wy) + (1 4:y) log(1
F(w; - wy)).
(t.))E&+
Observe that since á is an optimal solution and w" is feasible point for the problem in (7), therefore we have i(w) S i(w*).
Moreover, since w* is the optimal solution of a convex function 1* (w)), therefore we have the optimality condition VI )T("T(( w²) 2 0 for all Wo Now, by subtracting the quantity Vi(w=)T w*) from both sides of
((w)= ((w") gives
((10) - -(w") - vi(w") -w= - - vi(ww) -w"
(18)
SV 3
-(Vi(w*)- - ()² - w²)
vi(w") VI" Mll 1| w" w0|lL,
(19)
where Çi follows since (w") 2 0 for all w W and (2 follows from (Shah et al., 2016, Lemma 16) where -I- ll is the semi-norm induced by the Laplacian matrix of graph G and Lt is the Moore-Penross pseudoinverse of L. Now observe that by the chain rule, the Hessian of / is given by
&
)
vi(w)) = Σ
The ara log( (((FF())ttwll)) + (1 - (:5) dt2
log(1 - F F(t))le= Zi5u1z
(K,)EE,
Since by our assumption that F(t) is a-strongly log-concave on the set [-2b, 26), this implies & 2 a. Moreover, since F(-t)- = F(), also have with TT 0, have
& de log(1 F(t) 2 for all E [62 26). Therefore, for any R.
V 2 2a X v 20
Thus, by definition of strong- the left side of (18) be lower bounded by allu w 112. Therefore, utilizing the bound in (19), obtain the following inequality
ael|u w'1 112 livi("") VI" (w" (l)+)ll
w w"lle-
Canceling || w² r.. and squaring both sides leads the following error bound on 1| - w= 1|r.
| "/ w0 < o [ vl"
(20)
Now, it remains to bound the term [|vi(**) - VI" (w" Mlrt. Note that we can express the respective quantities as:
4ij F' F' (wogTaag) (1 (1));)
F'(w* xiiz)
vi(w") - Σ
).)) 1 F F( xzz)) Izj
F(w=Faz))
(1S)EE+
15

---

Hypothesis Testing for Generalized Thurstone Models
(1 Flw; (w) - wÿ)
=-2 Σ (EJ)EE
Dig.
(21)
F(w? -w] F(ws w(])
(bj Flu; - F' - -W]) F(w w1) F(w? wI))
(1" - Σ
(22)
(LJ)EE
Therefore, subtracting the two equations gives
(hg F' - w.)
vi(w")- V1'
Σ (KJ)EE,
Jij -2X
(23)
F(ws - w (1 F - wz))
where u R|El/2 is vector formed by entries vig for (i.j) E E.. and quantities Vig are defined as F( - w.)
Viy (ăis q3) F(w; (1)(11 F(w; - w
Note that the entries of the vector v are independent and have a mean of zero. Furthermore, we also have:
3 ((=)( S F(-2b)(1 F(-2b))
((r
_ B.
sup E 26
Additionally, for any (i,j) E an application of the Hoeffding's inequality on dis qú yields the following tail bound
k
k Σ m=1
t 0, P( - qul t) 1
(2)) - pj1) 21)
(2 - Pij) +
2k
m=
< 2 exxp( (xk((-2k(")
82 i
Consequently, v is a vector whose each entry is independent with zero mean and -ub-gaaaassi.. Now, observe that we can express [[" Vi" [I2 in quadratic form as
(v((w)) - (w" = 4 xuTxLtxT
(24)
Now, combining (20) and (24) we can upper-bound Blllu w² w²1 [2 as
1
Elll2
w0 11211
Bil
v((w) - Vl (2')
a
a2 B x
32
(n 1).22
(25)
ka
ko²
where tr denotes the trace operator and we have - = tr(Li)) -r(ti) Hanson-Wright
Hence, by an application of Hanson- Wright inequality (Rudelson & Vershynin, 2013) combined with usage of (20) and (24) above, we have the following concentration bounds on || w01
n2
3 XIXXL 3 ))
22
lha2
Vt > T. 1| w/ 122
ka 1)
<2
-emin
tka?
}).
2
-emin
[3 -
32
Hence, by a simple calculation, we can conclude that for some constant we have
for all t 2 1, P P(I0 1000-w133
cn,3²
w1 >
se-
(26)
ka²
16

---

Hypothesis Testing for Generalized Thurstone Models
Bounding the pth moment: Let denote the quantity: A V cn3² /ka². Now the bound on the pth moment obtained by integration and utilizing the tail bound in (26)
Blll w0 [1P] - p
1P 1P-1P( P( w'll, > 1)dl
to P((1 - 1ll > 1) dt + pp/ / 1 80 P( - w wille > t) dt
< / to- dt t 1 (tt)--1((100 - > tA)Adt
w'll,
S AP + pAP / p0te- S
App) s
Substituting the value of A in the above expression completes the proof.
B. Proof of Theorem 3.2
We begin by recalling the test statistic T from (15)
Zij Zij(Zij - 1) + F(u: +F(i0--ū,) -ū,)² (K 1)
2Zi
T= Σ
F(wo; wz)) Kg
(LEEE
where w is calculated based on the data in 2, and Zij are calculated based on the data in Ez. The expected value of T conditioned on the weights vi or equivalently conditioned on the data 21 is given by
(2g - 1) 21 1)
7 K/s
E T
211 =
Σ
E
+ F(u; x²²² 2B
Z1
F(u: - -
K.
(EJ)EE
Σ
- -1²)²² + F(ū;-10j)
-p,,, F(u;; - -ū²))
(i,))E
=
Σ (Pig
F(U;- - -,,))²
(27)
(UJ)EE
where in Ç we have utilized the fact that E
Zi 11 Ky 11)
|2| = přj. Hence, the expected value of T is given by
B
E
Σ E[(pij F(U; (0
(SEEE
Σ (p.j - F(wF - -w²)²² + E[ - w0) F(w;; w
(KJEEE
+ +2El(pg FF - =z))
- w3} F(wo, +5))
P + B|||F FI1:1 2|| FIIF Fllr),
(28)
where F. F E R are matrices defined in Appendix A.1. In order find bounds estimation error (such terms like B[[[F - FI()), we will utilize our simplifying assumption that kiz = 2k for all (i,j) E E. Now the ensuing lemma provides the bounds on the pth moments F[[[F-F[I?"'
Lemma B.1 (pth Moment Bound). For matrices F and defined as in Appendix A.I and 2 1, there exists a constant Cp. possibly dependent p, a. B, b, such that the following bound holds on the pth moment of the Frobenius norm E [[[F FIIP:
p/2
||F - FII S co
Moreover, there exists a constant e. such that we have the following tail bound:
Vt 2 1, P P(FF-
FI 2 t en
< c -t
k
17

---

Hypothesis Testing for Generalized Thurstone Models
The proof is provided in Appendix B.1. Thus, utilizing Lemma B.1 and (28), have obtain the following bound for some constant Cj and o2:
< P + C2 n + 201V
v " - F
E
Let E and Eh, [:] denote the expectation operators under hypotheses Ho and H1, respectively. essence, we have established the following bounds on Eg, (T):
C2 T
E
(29)
K
In a similar manner, we can obtain complementary lower bounds on EH, [T] (ef. (28)). Consequently, we have the following lower bound on Eh, [
H [T] 2 FIl
201 V 7 PP P Flle.
(30)
Bounding variance: Now we will find bounds on var under the two hypotheses. For this, we will make use of the law of total variance by conditioning 7 with respect to 2 as
vTr E[var(T) 21) + var (E[T) Zı)).
(31)
First, we will examine the term [[[va([T]2]]] Note that conditioned on 21, the term F(u;; - ú constant and does not contribute to 2)). Moreover, Zig for (i,j) are mutually independent, and hence, we can analytically find the expression for var 21)
Zij(Zi) 1)
Zii Kgy
var(T (T)) 21) & Σ var
+ 4F - 2
(ky - -1)
(L,))EE
B3 TE[23,( (Zej 1)]
1[Zr,(155 - 1)] E[ K2y - KK
-FF(10; - w
(Kly) (
2p1, + +4(Kg)
2) + (6 - AKg))pp
4F(w; (0,))pss(( pij)
C
Ki (Kg -)
kis
(K,))EE
2(p25 P31
-4F(w; w)))
K-
where Çi follows from the variance of sum technique and {2 follows from the expressions for the first four moments of Binomial random variables and some basic algebra. Now, in order to bound E[var(T) [1)], we will substitute all K, for all (i,j) and simplify the above expression as:
2r 4p²; + 2p
[[var(T)) Z1)] = Σ
k(k -1)
(J))E
App k
4E -b0y)
SE[F(Lù - (b;))Pis
+ Pis (1 - Pij))
+
k
k
2p; (1 - Pij)2
4pip (1 Pij))
(pig [E[F(L; x;,)))
k(k 1)
k
(1,)EE
7idmax
1
+
|p BFF
8k(k 1)
k.
nidnax
+
Flle + || )(
8k(k 1)
k
niduax
1
(||P
Flle E||[ F) 2
8k(k 1)
&
ndmax
1
+
|P-
|P
Fllr + a ke
(32)
8k(k 1)
k
18

---

Hypothesis Testing for Generalized Thurstone Models
where dmaax max EjEMy Byy is the maximum degree of the graph, and the last inequality follows from Lemma B.1. Now we will bound the second term of (31), i.e. var(E Recall that by (27), we have B[T = EEts)e
F(u; .. Therefore, upper bound var(BB[T) 21))
(ar(B 21]) var
Σ (Pt F(u;; - -b,))² var([| FI1
(L,))ES
= |BIl| - FIli: - Bl| P- F11???
- [[[ FILF || - - FIle -I| F
where the last inequality follows from the triangle inequality in the first term and the reverse triangle inequality the second term. Under hypothesis Ho. the above expression simplifies trivially as
var Ho (E(T)
21])
S C4
71 k
(33)
where varH, (-) denotes the variance under hypothesis / for / 10, Now, we turn our attention to bounding varæ, (E 21)). This bound can be established through a relatively mechanical process described as follows
varæ, (E[T)Z]) S P Fili =
FI1
+ 4| - F
F11
(IIP F + -
-
-
8 - -
B[[[F -[1x)=)
+ +4|
F [F
11
-
[[[[F F1
-
E[[[F -1
< 8c,
FIL
V
4c2
P
FIlE n
4(cs + c2 Fllr (1()) 3/2
c4 k.
(34)
Thus, by combining Equations (32) and (33) and (34) we obtain the following bounds on var (T) and varæ, (T) based on (31)
ndmaxx
2 n2
n2
varH, (E(T)) <
+
+
(35)
8k(k 1)
42
varm (E(T) <
ndduax
+ 1/ ||p
FIlF
Ci
11
2
+ 8c1
P
F
8k:(k: -
To
3/2
n2 2
+ 4c2
F F n
4cs
4ès
FILr
n2
+ C4
(36)
k
We define the decision rule follows: select hypothesis H, the test statistic T exceeds the threshold:
Select H, if: T 7 + 02
(37)
where 5 suitably chosen constant (selected below). Consequently, we can employ the one-sided Chebyshev's inequality
19

---

Hypothesis Testing for Generalized Thurstone Models
to bound the probability of error under hypothesis Ho. yielding:
PHo
T
T2 + c2
n2 PHo (T EH [T] >
T
n2
+ T
n
EHo (21)
I PHo (T- BFO (o) > T
m
varH, (T)
varh, (T) + {
ndmmax 4k
+ of + c,(
+ 1 + 22 + 5Z())
4k"
Amns + + +
1
dmax 4n
+ 7
4'
where the last bound holds by the fact that dmaax S n, and for an appropriate constant y 2 max(4v/ca, 4, 401 /vn-.
Now, we will find an upper bound on the probability of error under hypothesis H1. Observe that an error is made under H1 if the value of the test statistic T S 7 C
n + C2 k
PH,
T
k
PH,
T-EEr Eir, [T] S T/T + +22
n1
Em, [T]
EH [T] S 5 n2
+
02
n
+
201 V K
n
P || FI1
k
k
IA
varH, (T)
6
S
var (T) + (D2 - A)
4
where Si follows from (30), Se follows by one-sided Chebyshev inequality and defining = P FIle F and A
3E + C2 + 2e1 2r.e. D. The step Sa holds 4var (T) S (D2 A)² or equivalently if D2 2 2v var (T) A. Using
the sub-additivity of v operator, the following condition necessitates that for this to be true:
Vndmmxx
n (D
D2 2 2
+
D
+2 20, +2222,
D3/2
+ +2Vo2D
2k
Vb
k
n
Ca n
n k
n
71
+
+
02
+
201
D.
k
k
k
Substituting D = 00 / T in the above expression, for some ag we obtain:
Vdmax a
+ 2(as + / [ / + 44220100 Vn
3/2 + 44/0200 + 4 22yaa + 2c, + 7 + 02 + -2001-
Now, we can conclude that the above expression is true for some large enough constant dg independent of n and k thus establishing that for D ao / T and ag large enough our decision rule achieves type I and type II sum error of at most 1/2. Utilizing Theorem 3.1 we obtain that inf |P F(w)llr = O[] Flle). Combining this fact along with the definition of critical threshold (cf. (14)), we have the following bound on Ec:
6 S 50
(
nk
This completes the proof.
Notably, from the above result, we have that & + as n or k goes to infinity. Therefore, for any fixed n and e > 0, our decision rule is guaranteed to achieve a non-trivial minimax risk (strictly less than 1) for any pairwise comparison model P in the class Mo or Mi(e) as long as the number of observed samples for each pair (i.e. k) are sufficiently large.
20

---

Hypothesis Testing for Generalized Thurstone Models
Moreover, there do exist pairwise comparison models (Pij (i,j) E E) whose (normalizedd separation is constant with Consequently, for such models, we can argue that for any fixed lt and large enough, our decision rule will achieve non-trivial minimax risk. One such example of pairwise comparison model represented by its pairwise comparison matrix (on a complete graph) is
P = { + + ( - -1), for any E 0. 1
It is easy to verify that for this comparison model, we must have inf 11IP F(w) |F 2 17. This is because any matrix F(ww must satisfy the constraint (F)ig + (F),s 1 for every i & j. which immediately leads to the lower bound of ry on the separation distance.
B.1. Proof of Lemma B.1
Observe that by definition of F and F, we have
Σ
(F(w) - w3) F(U; - (k))) < 82 Σ (I(w) - wz) - (d0; (0,)))
(K)E
(K,))E
< 4,3² -0 w I1
(38)
Taking the power p/2 on both sides and then taking the expectation, obtain
FIlE s 3" w 121 S cp m p/2 (
E
where the last incquality follows by plugging in the bounds on pth moment from Theorem 3.3 and absorbing the constants a,, 3 in Cp. The tail bound follows directly from (38).
C. Proof of Theorem 3.4
Without loss of generality, we assume that the graph G is Eulerian. If not, we can reduce the problem to an Eulerian graph by considering the largest Fulerian spanning sub-graph & of g so that every vertex of 9 has even degree, which exists by our assumption that super-Eulerian.
Under the null hypothesis, we assume that the pairwise comparison model P corresponds to equal utilities for all items, i.e., Pij 1. v (i, & and let Po denote the probability measure corresponding to this pairwise comparison model P. Under the alternative hypothesis, we will set our pairwise comparison model R to be perturbed version of P (sharing the same observation graph 9). Specifically, every perturbation will have the following property:
v(I.J) E. rij = 2
+ nbij, where E [0, - o]. bij E(- bij + bbz Vi [n].
1
and Σ bi = 0, Vi E [n].
(39)
J:(,))E8
where by represents the signs of the perturbation by parameter 17. Note that we set by = for (i, & E. Let any such sequence perturbations by is represented by a matrix B (,1,0, 1)xx..
As we delve deeper into the perturbation structure, we will carefully select a subset of perturbations satisfying the constraints in (39), as well additional constraints to be specified later
B bij E 1-1,1) for (i,j) E E bij bj: O, Σ 0, [ml
(40)
f:(3,))EE
Based this selection, under the alternative hypothesis, let the pairwise comparison model R be generated from mixture distribution such that R = P B/B and B Unif(B), i.e., R is generated by adding the perturbation sequence selected uniformly at random from 8. Let Pis denote the measure corresponding to the overall mixture distribution.
As we examine the perturbation structure, we make our first observation: for any perturbation B satisfying (39), the corresponding pairwise comparison model belongs to the class Mi(e). for some e as a function of 17. Specifically, we will show that the perturbation guarantees minimum separation distance of e from the class of Mo-
21

---

Hypothesis Testing for Generalized Thurstone Models
Bounding separation: Our first observation is that any such perturbation R P B has sufficiently large (and more importantly, tractable) separation distance. In order to lower bound this separation distance, will utilize Theorem 3.1. But first, we need to find the optimal TF weights w* (as in (8)). This is addressed in the following lemma.
Lemma C.1 (Optimal Weights for Perturbed Matrix), For the TF model and any B E B defined in (40), the perturbed pairwise comparison matrix P + B has a unique optimal TF weights given by w² = 0 (all zeros vector).
The proof is provided in Appendix C.2. We now utilize Theorem 3.1 to obtain the following lower bound on separation distance as
|| n/ B F(w)ll: 2 c F(()) WEW,
inf
= = E
where ej is the lower bound constant in Theorem 3.1 and the last equality follows sinde (P)s (F(0));s 1/2 for all (i.5) e E. Therefore, we have ne 2 /nvvEE [E] by definition of M1(e).
Having established lower bound on the separation distance for each of the perturbations, our next step is carefully select special subset B of perturbations that allows perturbation set, while also taking into account the constraints imposed by the graph topology.
approximate the "degrees of freedom" in the structure of our
To this end, we leverage the assumption that our observation graph G is Eulerian, meaning every node has an even degree. This property enables us to decompose G into a collection of edge-disjoint cycles, denoted by C. In addition, we introduce a comparison incidence graph Gr, which represents the comparison structure as an undirected bipartite graph. This graph has item nodes on one side and E//2 nodes on the other side, each representing a pairwise comparison (i. j) E & for j > i. The edges in 97 connect items their respective comparison nodes. Since every node in G has even degree, this ensures that the incidence graph G7 is Eulerian, and therefore G₁ also has cycle decomposition denoted by Ct. Notably, each cycle in Gy is of even length and we can establish one-to-one correspondence between the cycles in C and C,. Now, we orient the edges in the undirected comparison incidence graph G7 based on the values bij in the perturbation B. Specifically, we will orient the edges in 9, as follows: if by = 1, the edge will point from the item node to the comparison node for pair (i, and if bi = 1, the edge will have the opposite direction. The constraints in (40) ensure that each node in G7 has equal in-degree and out-degree.
To specify the construction of B, we consider any fixed cycle decomposition C₁ (since it may not be unique). Let the number of eycles in the eycle decomposition be denoted by [Cr]. Let o; E C₁ represents the ith cycle in C₁ and |o denotes the length of this ith cycle. Observe that we can independently orient the edges of any cycle E Cr in either clockwise or counterclockwise direction, yielding 2/rrl distinct Eulerian orientations for Gz. We then construct the structured collection of perturbations B by associating each perturbation with one of the 2/Cr distinct Eulerian orientations of the cycle decomposition Cy. This establishes a one-to-one correspondence between valid perturbations in and distinct Eulerian orientations of C,. Thus, in summary we define B correspoding to decomposition C₁ as
B A bij E (-1,1)) bij + bbj = E.,
Σ bij = 0, [n]. J:(.))E
14 - bet1 = 2, E Gi Vo; E Cr }
where, is used for indexing sequential edges of the cycle o;.
Bounding risk: Now, we will utilize the Ingster-Suslina method to compute lower bound on R(G, e) (cf. (13)). The standard testing inequality by Le Cam (Ingster& & Suslina, 2003) states that
R(G,e) 2 11 |IPo PBllTV 21 (Pp(
(41)
We calculate the chi chi-squared divergence 2P [Px) by expressing it as an expectation with respect to two independent pairwise models corresponding to permutations B and B' drawn independently and uniformly at random from as
/
dF JPPdPP B
(TPs = Ep, Bi Unif(()
dPu
22

---

Hypothesis Testing for Generalized Thurstone Models
We will leverage the tensorization property of 1 x*Pl)))))) which enables to decompose the chi-squared divergence between product distributions into product of individual divergences. Specifically, for distributions P1, Qi...... Pr. Qn. we have
1 1+x"
II P.
II
+1+x((P)10)))
Consequently, the chi-squared divergence (PPPP) simplifies as
+ (PPslPPP)) =
h (mn) 2 + m)bb)) (T( mees) ) (5 m,,,,, -
EB -Bi(BB
II (LF)EE
m=0
m nbb,) (m2 mbey) m ( mp66,) (m( -7/665 )m
II (1,))
(42)
m==
We direct our attention to the (ih term of the product in (42), for (i,j) and denote it as h(bsg. Ky))
( + m)be)) )mm ( myb, ) (1 + nbb,, mbb,,)*m
h(bej, b/g)) =
(43)
m==
2
Now since we have biy. by { (-1,1), therefore whenever bi and by agree, by (43) we have h(1,1) = h(-1,-11111 1). And moreover, we can calculate h(1, 1)
k
2k-2m
A(1, 1)
2
2 -1
m
&
k
m
(1
k-m
2*
+
172
-17
m
= (1 + 4n7²) k
Σ
1
+
n
1
77
R-m
2
21j²
2
2Ty²
m=0
= (1 + 4
Additionally, by (43) we also have fi11, -1) = h( 6(-1, 1) and it simplifies to
k m
2k
1
2h = =1 27
h(1,-1) =
+ 7
-7)
2
17
For any two perturbations B, B' ~ Unif(B), let random variables A₁ denotes the number of agreements between B, B' respectively, i.e., number of (i,j) E E where by b/y in randomly drawn permutation B and B'. And similarly let A₃ denotes the number of disagreements between B, B' i.e. number of (i, E &4 where bij = -by--- Consequently, we obtain
+ (PB((Po) EB, EB,
(11,1)2A1pa h(1, -1),-1
4m²) (1 4 2
EB, Unir(B
exp(S1) k(A, A2))
(44)
23

---

Hypothesis Testing for Generalized Thurstone Models
In addition, we define vectors a, a' {-1,1]
1).lel represent the orientations of the |Cz] eycles in G induced by B. The subsequent calculation will now be used complete the proof:
(Ps|(Po) +
Σ
A2))
- Σ
exp
81f*
Σ
loylara
22|ca1
221cr1
B,
a,a'
0:E02
II LoyeC,
exp (())(())
< II
0
1 + exp(- (81 k|ozl) ko0os)))(oss))
II o,EC2
exp(817k((s))
2
II o,EC,
exp 32n (((:))))))) exp 321 k22
Σ (0s)))
OLEC,
where Çi follows from (44) and the fact that there are 2/ perturbations which are sampled uniformly from B, S2 follows from definition of ag and the fact that number of agrrements/dissgreemnnt can be represented in terms of the agreements/disagreemnntt of the cycle orientations 0,, a4- <3 follows from the fact that the orientations of the cycles are independent of one another. Finally, utilizing the fact that / & nc and by combining the resulting bound along with (41) and the fact that cycle lengths in G, are twice the size completes the proof.
C.1. Proof of Proposition 3.5
- comparison nodes. When is odd, all nodes have an even degree equal to 1; therefore, G is Eulerian. Notably, can take the forms n = 6m + 1, = 6m + 3, and n = 6m + 5, where m E N. As established by (Kirkman, 1847), for n 6m + and n = 6m + 3, g can always be decomposed into cycles of length 3. Meanwhile, for n 6m + 5, 9 can be decomposed into a cycle of length 4 and remaining cycles of length 3 (Feder & Subi, 2012). Therefore, we have |g| O(n") and Erec la O(n²), giving = ((1/kk)
Part I: For complete graph, the comparison incidence graph Gr has item nodes and m(n-1)
Part 2: Consider d-regular graph with constant even degree d. The associated comparison incidence graph has item nodes and nd/2 comparison nodes. By applying (Seshadri & Ugander, 2019, Lemma 9), we can decompose the edge set of the comparison incidence graph into cycles of size at most [2 log. (n)]. with at most min + +nd, 4n} = 4n edges remaining. Since the graph is Eulerian, removing cycles does not affect this property. Therefore, the remaining 4n edges can be further decomposed into cycles of length at most 2n (since cycles can have a maximum length of 2n, and this reflects a worst-case scenario). This yields Eoec | On?)), which in turn implies = = Q(1/n2k).
Part 3: For graphs comprising single cycle, it is easy verify that the number of cycles is and the cycle has length of
Part 4: For toroidal grid of size v x Vn, we can generate cycle decompostion of G consisting of vn horizontal edges and Vn vertical edges. Clearly, each of these edges has length of vn. Therefore, Ex,ec la,12 2n n. And since it is a toroidal grid we have |3] 2n. Plugging in these values obtain e2 [(1/n7/4k).
C.2. Proof of Lemma C.1
To find the optimal weights w", our objective to solve the following optimization problem with parameter b:
(ww)= = min- - weW,
Σ
Tay log(F(w; wy)) + (1 - rey)) log(1 - F(w; - wwy)).
(K,))E
Our initial observation is that, due to the skew-symmetrizzation of the model rij + rrj 1, we can express the gradient of 1* (w) as:
F'ww; w))) (rij F(w: wy)) F(w; - w/) F F(w; -w,))
(VI' (w)); = -2 Σ
J:(.))EEE
24

---

Hypothesis Testing for Generalized Thurstone Models
Furthermore, the gradient is zero at w 0. To see this, note that for all E [nl,, we have:
(V(())) -2
2 2 2 ):(6,))
Σ
F' + nb. F(O)) F(O) - F(O)) F8 (0)
Σ
bij =0;
j:(.))EE
where the last step is followed by construction of the perturbation sequence in (39). Considering that the gradient is zero at 0 and the optimization objective is convex over W/ (in fact strongly convex over Wo), coupled with the uniqueness of the optimal Tr weights as indicated by Proposition 2.4, we conclude that w² = 0 is indeed the optimal and unique solution for any 2 0.
D. Proofs of Time-Uniform Bounds on Probabilities of Type I and II Errors
In this appendix, we will establish bounds on type and II error probabilities as described in Theorem 3.7. First, we will introduce essential notation to facilitate analysis and present our proof of Proposition 3.6. Then, we will establish few auxiliary lemmata such as which are needed to derive the bounds type I and type II errors. Finally, combining these results, we will proof of Theorem 3.7 in Appendix D.3 and a few corollaries based on these results in Appendix E.
Additional notation: We introduce YiJ for 1 E N and (f,j) E E to denote the observed comparisons that are used for estimating Zij- Ei= Z: i.e., we let Y = z for 1 [k] Also, define the statistic V 83 - Em=1 Ym Moreover, define 1, as all-ones vector of length n and I, the identity matrix of size n..
D.1. Proof of Proposition 3.6
We will focus on the following sequence (T NN ( {1)}
defined as
1 A (Y -)
k(k 1 + D2 2bi5 k
Note that with biy F(ù;- -by), the term Ty reduces the (i, term of the test statistic T (based on the notation defined above) and we will now show that it is indeed reverse martingale. To do this, we will demonstrate that both the
(V: and ye k are indeed reverse martingales. First, we focus on the former term. Observe that we can write the
terms
k(k-1) 1)
product 7 (Y 1) as
( 1j 1) A:kk 1)
(>h= m=m y2n Σk m=
m 6j
1
Σ
Y My
k(k 1)
k:k
1)
1,m 1:
where the last equality follows because Em= Y (Y:j - 1) = 0 as Y. {0, 1J. Also, observe that E mm Y
[itt1]
E ( Fa+1] for I a m # r and where F& is the canonical reverse filtration defined as the sigma algebra generated
by Fa 2 (i.)) o k+1 yk+2 ........ This is because for any A Fa+1 and m, [b] and + m r, we
have
fj Y 1A]
and E
1 = E Y LA)
(1 k(k-1)
Utilizing the above relations, we can show that
is indeed a reverse-martinglee as:
E
Y 1
19
- 1) k(k 1)
Fe+1
E
Σ k ylym
Eimm=1.4m
Fx+1
k+1
1:4mm
E Ely.Jy, Fat1
kilk -
k(k -
Σ k+1
l.m= l Y mm
y (
E
Fx41
E
ij
F
kikk + 1)
k(k +
yk+ (Vk+1 1)
k(k + +1)
25

---

Hypothesis Testing for Generalized Thurstone Models
where the last equality follows since - is measurable with respect Fk+11 Similarly, can also show that also reverse martingale as:
V
m= E S
[k+1]
Em=1
E Y 1j
Fk+1]
E Fa+1
k
1 +
Y
yk+1
E
FR+1
k
k
Finally, the proposition follows by the linearity of conditional expectation and substituting by = F(i;; w.n)) as:
E Tkr. .k
[R+i]]
= E
Σ
Fa+t1
(t,))E
Y
(
Yk Fx+1
=
Σ
E
k(k 1)
Fx++1
+ 12 - 2b;r 1E
k
(iJ)EE
(y
- 1)
yk+1
E (iJ)E
fj
+ b2g
2bbj k +
Σ
T T+1.
k(k +
(i.))E
This completes the proof.
D.2. Intermediate Lemmata
In order derive the proof of Theorem 3.7, will first prove the following intermediate lemma that gives bounds on type I and type II errors where the threshold is function of the estimated weights w. Additionally, the lemma relies on a variant of the Hanson- Wright inequality that is time-uniform (see Lemma D.2) and specialized to our specific setting.
Lemma D.1 (Conditional Bounds on Type and II Error Probabilities). For any E (0. 1] and for v estimated from the first 1n pairwise comparison for each pair in E, there exist a constant e such that for v E (0, 1/e), the following bounds hold under hypothesis Ho and H, respectively:
E
||F |IF
Fllr Vi
P Ho
3k 2 2, khin
|
FIBE
4
VlEN
SV,
F HH
3k 2 2, kk.
FI
| F-
FII
2 -Flee|1 [itl||P-Fll -FFIE
P - FIlF + ||F
FIlE
VEE
SV,
k
where lx. log (3.5 (o, (k)
Proof:
Part 1: We will first prove the bound under hypothesis Hg. Based on the additional notation defined at the beginning of the Appendix, we can simplify the (i,j))th term T.5uk of the test statistic kki,k as:
Yk Y. 1) + F(w; -0,)²² -0 -2F(1;; -wy)
Thisk
kik -1
k
Σ t Eim=z Ymy! yl
+ F(w; -,,²² 2- F(u; - w
mm
ij
k(kk 1)
k
1 (utt)" A y// 1 A 1, -w²²² - 2F 2F - w A() +
(F( - w))) - F Fww wz))² 2( 2 - w))) - F(u w())
F(w; - -w3)
h
26

---

Hypothesis Testing for Generalized Thurstone Models
k Vg
F(w; - wz)l(a) (0ll))AAA ( F(w, w))1a)) + +F((;; -ū,) F(wî - wz})
Y F(w, -wj)
2(F((t; - x))) - F(w] w3))
where in (i have A(k) A 1x1F I and vtj RR is vector such that vř} 1Y ....... YiJi and in S2 the term 12j follows k(k-1)
by observing that
(uf - F(w] w))]&)
A0t) (ut) - F(w -wf)ls) (utt)) (ia)TAA A
A yij + +1 15 -03e 2p yty-
(45)
Now, we will upper bound the quadratic variation term Ennee 1i For this will utilize Lemma D.2 to obtain the tail bounds for any E (0, 1/e) to obtain (for some constant e):
E
3k 2: Σ
T >
EK S 2
(3,))E
straightforward to show that Ei.j)ee 12,4 (4 F -tll://k--ubbgauusssl Therefore, by utilizing time-uniform
version of Hoeffding inequality (Manole & Ramdas, 2023, Corollary 8) for the user-defined (<k) = (TT))² //6 (also used for the stitching argument in the proof of Lemma D.2), we obtain for any " (0, 1)
12 > F log(h(log2(k))) + log (2/v)
P
3k
2:
2:
Σ
k/2
(t,))E
Combining the two tail bounds and simple calculation completes the proof for type I error. Part 2: Observe that under hypothesis Hi we have
1 1)
T3 (p.j Fwu3- -w;))
k(k -1) płz + F(w; - -0,)² F(w, wz)²
+ 2 F(w3 - w/) )iis F(w; : 4/
E (T (1)) u/z 1f (A) + F(w: -ū²)² - F(w -w
Y
+ 2pij F Fwo - wj) - F(u: - w))) + 2 Pij k
F( w))))
(46)
where in Ei we have A 1-17-14 R(K-1)
and vty E R is avector vtj = -Vly....... ... -,y1 as before. Now, observe that the term
( - 11 1 = (Vt Pig 1x) T (A)) A (1 Piilla)
1(3)
+ 2pts (3/j Pij P,)li)
T (A(1)
(v/) Pis 1a) (( (uts pis 1o) + 2pzj
Pij
27

---

Hypothesis Testing for Generalized Thurstone Models
Substituting the above bound in (46), we obtain
T (pis
-w))- = (v. Piyls) T *A()) (u/j Pişla)
1
+ 2(pis F(ū;; - -(ūz))
Psj
1,
(F(i; w) -F - (FF)((((i; - (03) + F(ws - wz) 2prs)
Now the term E(E))E 3. is bounded by utilizing Lemma D.2 to obtain the tail bounds for some constant e
P
3
2
2:
Σ
3.k
E
V
k
(i.j)EE
And the term Easee 1.k is bounded by utilizing adaptive Hoeffding'ss 's inequality (Manole & Ramdas, 2023, Corollary 8) to obtain the tail bounds
k 2 2: Σ <
S
(KJ)EE
An application of the triangle inequality to the above equation yields
Flle + 1 -IF=-Fle)) EK
3k 2:
Σ 1 <
2
(KJ)EE
Finally, the term Eases
5. is bounded using Cauchy-Schweer incquality as: 13
Σ 1
Σ (F(d; - (bz) F(w, -w,)) w;))²
(K
(NJ)EE
Σ 2(F(20; - -ū²) - F(w - (F))(((() -wz) -Pis)
+
(i.))EE
|F F11 2 - Pl
Combining the three bounds for 12/h 11 15.k completes the proof for type II error.
Lemma D.2 TTme--Unfome Quadratic Bound). For any element in finite set V. consider sequence of independent
random variables (1)
(2)
(3)
such that (1()) ~ Bernoulli(p.) for E and some p. E (0, 1). Define the random
It IV
vector =(k) Ev
(1)
_21) 3..., (11)
(k) I2t and let (A(k) 1gk*k k N} be sequence of matrices such that
(b)) (1+1 1k)/(k(k - 1)). Then, there exists a constant e such that for all E (0,1/e), we have
VIVl k
3k 2 2, Σ (x(1k) - p. A (x) p.ls)) >
log (3.5 (3.5lgg((4)/v) $ v.
NEV
Proof: Denote s
= (- (k)
p. 1x) (1)) 1.).) Recall that we had shown that (k)
k E N (1}) forms
reverse-martingale with respect to canonical reverse filtration {o (h xe xe for k > 2, we have
(m) (k+1)
(R+2)
,....
(x(()) 1T) (=()((
(
A ((++1)
Pe 14t1
po pol4+1)-
28

---

Hypothesis Testing for Generalized Thurstone Models
This fact follows from an expansion of the corresponding terms (similar to (45)), and then the proof follows in Appendix D.1. Now, for any E V, define richer class of filtration known exchangeable filtration (Fr E (T)) (Durrett, 2019), which denotes the o-algebra generated by all real-valued Borel-measurable functions of De (2) ( xx
which permutation-symmetti in the first arguments. It follows directly that (k) is also reverse seveers-martingall with respect to Fg. Therefore, by (Manole & Ramdas, 2023, Theorem 4), we have that the mapping exp(Ax) for E (0), when applied to se Now, for any ko 2 2 and ko N, we have that
(k) yields a e with respect to filtration FR. Define the product o-algebra Fx = vev Fl.
I
3K
ku
Se (K)
PPkk
P 3k
ko
InEV o!
2 Edas
VEV
exp (A E 86 (K0))
Av
where the last step follows from Ville's inequality for nonnegative reverse submartingales (Manole & Ramdas, 2023, Theorem 2). Also note that se (R) for all k with probability therefore Ele always exists. Now note that
(xr po) (3) Po) k(k-1)
E NEV
1cl (x! pola))
Σ
E.EE(M):Ef
(a) YT A (1) (1)
where (I= = [
1P,,) . (Fely 1 ) is a vector in A formed by concatenating the vectors (A) | formed by stacking the matrices A as diagonal block structure.
.....
for all E V and E [[V]]. And A
Now by (Rudelson & Vershynin, 2013, Theorem 1.1). we have that there exists constants c, c' such that we have
E e Eveea!to)
S exp(-c>>114 (Ku) IP:) for À S d//1AA (ko) 112,
where || denotes the spectral nomm. Therefore, we have that
P
3k
Kp
(k)
S exp(->xu + cd211A (ho) 11:)) ( for A S (c/114
BEV
Now, by optimizing over \ and for some constant ē we can conclude that
-ēmin I u2
|| 1| })
P
3k
2 Ko
Σ
(k) exp
<
u
(47)
[|
NEV
By the block structure of A (ka)
we have the following
IV]
| (k))
and ||A
[AA
max VEV
| 1|2
ko - 1)"
Ko
Substituting, the above values in (47) we obtain that for all (0, 1/e), we have the following result for some constant
V Log(L/v)
IP
kk
kn
<
ko
The rest of the proof follows by a stitching argument (Zhao al., 2016) and is provided below for completeness. For any
29

---

Hypothesis Testing for Generalized Thurstone Models
V/ E (0, 1/e), define function h(k) = (mk))
Now, observe that
hloog k)
P k 2 :: Σ 88 2 c
log
k
BEV
h(t))
PP
7k
2
2
8
(k)
C
log
2
1=1
DEV
V
h(1)
1=1
Finally, the statement in the lemma follows by a simple calculation.
D.3. Proof of Theorem 3.7
Fix & 2 1, and recall that from Lemma B. for some constant Co we have that with probability at most e e ||F [fll 2 Veytn/ky. This implies that with probability at least --r we have
VIEL LN
|| 1IF-Fllr FIlF Vk
cotn |81
cotnex.
F F +
VeNu
LE + 4
K1
kk1
Therefore, by using basic union-bound argument the bound under null hypothesis in Lemma D.I, we have
P 3k 2 2, Tk:
cotn
+ c 18 AV
lK. +
cotula kk1
Sutel.
k1 k
The bound on type II error follows by similar argument. First, using basic algebra, and using D to denote |P - FllE, we obtain from the bound under H, in Lemma D.1 that:
g88à ko
4. - 4 (D + |F [IF 4
Ри, 3k 2 2, -D- Fll))
VeEw Sv.
V
Now utilizing the fact that the D z / /eotu/ki and the same union bound technique as above, we obtain that
PH, 7k 2 2, Thisk
(D. (D-
cntn h1
2
ctE)
lnp
k
4
cotn kik
Veaw Sutc
+
Vk
Since the above bounds for any pairwise comparison matrix P satisfying Assumption 2.3 and since ne = O(D) by Theorem 3.1, hence we can taking supremum with respect to pairwise comparison P in class M1 (M/tt//////n on type and type error bounds respectively, and thus completing the proof of the theorem.
E. Simplified Expressions for Type I and II Error Probability Bounds
We obtain the following corollaries by plugging in the parameter values in Theorem 3.7 for a complete graph and a single cycle on n nodes.
Corollary E.1 (Type and II Error Probability Bounds for Complete Graph). For the setting Theorem 3.7 assume that we have complete graph nodes, then there exists (different) constants C1 C2 Cz2 C4, Cg such that for 2 ca/ Vnki, such that for all (0, 1/e) and 1, we have
citn
Conlx. b
ntlk,v kki
PHo
3k > 2,7 21.k
+
C3
Sute
Pır,
3k 2, 2,7 >
D D-
caj
En
2
conlax
(4 +
tn c5v
Vtnu
S Suter,
VT.
ki
30

---

Hypothesis Testing for Generalized Thurstone Models
Corollary E.2 (Type and II Error Probability Bounds for Single Cycle Graph). For the setting in Theorem 3.7, assume that have a single cycle graph on nodes, then there exists (different) constants e, C22 C3, Ca, cs 0 such that for 2 ca/ vkk, such that for all v E (0, 1/e) and t Z 1, we have
ci
C2 CaVnlk
nttkke lin
Ho
3k 2 2,
Tkink
+ caV
SU+E
k
k
P
3k 2 2, Tki,k
2
D
CAV
tn
2
02VnlR k
(1 V/b
D
+
co
tn kkj
VLEN Sutet.
F. Experimental Details and Additional Experiments
In this appendix, we begin by providing additional details of the experiments corresponding to Section 4 in Appendix F. Furthermore, we perform several additional experiments in Appendix F.2 to support and extend our main findings. These include: (i) performance comparisons with the spectral method of (Makur & Singh, 2023) for the BTL model (see Appendix F.2.I), (ii) analysis of type I and II errors for different thresholding strategies (see Appendix E.2.)) and empirical validation of our threshold estimation approach under different settings (e.g., clustered versus randomly sampled skill scores), and (iii) experiments real-world datasets (see Appendix F.2.3). Finally, we illustrate method of computing confidence intervals in Appendix F.3 based on the expression in Proposition 3.8.
F.1. Additional Details for Experiments
Below we provide additional details on the experimental setup and methodology for the experiments in Section 4.
Error bars and estimation of w: To estimate the 95th quantile of the test statistics T, we used 400 samples. The eπror bars were based on the two-sided distribution-fre conservative estimates presented in (Hahn & Meeker, 1991). Specifically, for the 95th quantile, the upper 96% confidence interval was computed as the 97th quantile of the computed tests T, and the lower confidence interval was computed as the 92.5% quantile. Moreover, in all of our experiments, the estimation of th was performed using a standard gradient descent algorithm with a learning rate of 0.01 and for a maximum of 3000 iterations, or until the norm of the gradient was less than 10
Testing on LMSYS dataset: In our experiment on the LMSYS dataset, we used a maximum of 200 samples per pair and discarded pairs with fewer than 30 observed comparisons to reduce the imbalance in the data across pairs. The observation graph was a complete graph except for the larger values of n, which had a few edges missing.
Computational overhead of empirical quantile approach: approach can be expensive due to repeated simulations, we remark that the procedure highly parallelizable and is fast even with a naive implementation (without any parallelization); indeed, each of our experiments can be done within 5 minutes normal CPU for n as large as 60. Additionally, to speed up computing úi on the simulated dataset, one can initialize the iterates at the optimal values that generated the simulated dataset and then apply few iterations of gradient descent. Moreover, when all kij are equal to & (or roughly the same), our simulation results in Figure 2 suggest that 0.75n/ kk and 0.4n/k k are good approximations of the thresholds for complete graphs and 2D grids, respectively. On the other hand, Appendix F.3 provides a faster asymptotic alternative based on Proposition 3.8.
While computing the threshold using the empirical quantile
F2. Additional Experiments
1.2.1. COMPARISONS TO BASELINE METHODS
We now conduct experiments to compare the performance of our test with the test proposed in (Makur & Singh, 2023) by fixing the choice function F to be the logistic function (i.e., BTL model). We assume that the observation graph is complete and define the pairwise comparison matrix under the null and alternative hypotheses as the one used to prove the lower bound in (39) and (40). We set 17 = 0.06 and ki = 10 for all i + j. We evaluate the empirical type I and II error probabilities, averaged over 400 trials, for three testing methods: splitting (Max. Likelihood), the same statistic without any sample splitting (Max. Likelihood2), and the spectral approach from (Makur & Singh, 2023) (Spectral). The threshold for all three methods is determined using the empirical quantile approach as detailed in Section 4. Our results in Figure 3 indicate that the proposed method performs comparably to the spectral approach, while Max. Likelihood2 achieves even lower type I and II sum error rates. Various parameters, such as the number of simulated datasets and construction of error bars, are the same as those used in Section 4.
proposed likelihood-based statistic with sample
31

---

Hypothesis Testing for Generalized Thurstone Models
F.2.2. COMPARISON OF EMPIRICAL AND ANALYTICAL THRESHOLDS
To evaluate the reliability of empirrcal-uuantie--asss threshold, we compare the empirical-quaniil-bess threshold with the "optimal" theoretical threshold in well-crafted setting, Specifically, consider the same setting in Appendix F.2.1 and set the theoretical threshold as n 1)/2 across range of values of Specifically, vary [0.08, 0.16) and {15, 25, 35, 45), while fixing kij = 10 for all i j. For each configuration, we compute type and II error probabilities using the empirical-quan ampiriiallqqunniee-baaed threshold (cf. Section 4) and the theoretical thresholds averaged over 400 trials. As shown in Figure 4, the empirical threshold achieves type error rates that closely track the nominal 0.05 level and achieves nearly identical type and Il sum-error rates as that of the analytical threshold. This suggests that the empirical threshold, despite being derived from random samples of skill scores, provides performance comparable that of the theoretically optimal threshold.
Max Likellhood
Empirical Quantile Threshol old
0.06
Max: Likelihood2
0.5
Theoretical Threshold
Spectral
Empirical Type EEror
Empleical Type Error
0.04
0.03
0.3
0.01
0.00
n-0.08
n-0.08
n-0.08
n-0.08
n-0.16
n-0.16
n-0.16
items
n)
Max. Likellhood
Empirical
Max Likellhood2
Theoretical Threshold
Spectral
Empirical Type II Error
Empirical Type 1I Error
6.4
0.4
0.3
0.2
n-15
n=
n-35
n-45
n-15
n-25
n-35
n-45
15
25
35
45
n=0.08
n=0.08
n=0.08
n=0.08
n=0.16
n=0.16
n=0.16
q=0.16
Number of Items (n)
(n, n) Combinations
Sum of Empirical Type and Error
Max. Likelihood
Sum of Empirical Type and Error
Empirical Quantile Threshal
Spectral
Theoretical Threshold
0.6
4.4
0.4
0.2
0.2
25
35
45
n=15
n-25
n-35
n-45
n=15
n-25
n-35
n-45
Number items
n=0.08
9=0.08
1=0.08
n=0.08
n=0.16
n=0.16
n=0.16
n=0.16
(n, nl Combinations
Figure 3: Performance comparison of spectral method in (Makur & Singh, 2023: 2024) and our proposed method with (Max. Likelihood) and without partitioning (Max. Like- lihood2) of dataset.
Figure 4: Empirical type and Il error rates along with their sum for the Empirical Quantile method compared to a well- crafted threshold.
32

---

Hypothesis Testing for Generalized Thurstone Models
Threshold BTL
Threshold for Thurstone
Test Statisti-6TT
Test Stalistic- -huusic-
Percettle Volue
0.6
0.5
0.4
88t
0.3
0.2
BT. 20 Grd mandom
51L Compbeu rundom
66d cuntere
10 12 Number Years
15
Campiea custerel
0.0
10
20
30
40
50
60
70
Figure 6: Scaled test statistic n T for BTL and Thurstone models computed on NBA dataset on cumulative data of t recent years and thresholds computed using empirical-quantile- based approach.
Figure 5: Threshold computation using random versus clus- tered skill scores.
To address potential coverage concerns arising from the use of uniformly sampled skill scores in empirical quantile thresholding approach, we conduct an additional experiment to test the sensitivity of the threshold. In our main setup, scores are sampled uniformly from the interval [-b, b]. which may not fully reflect more structured or clustered configurations. To evaluate the impact of this assumption, we construct a clustered distribution by assigning half of the skill scores uniformly at random in the range [-0.7, -0.4) and setting the remaining half be their exact negatives, thereby introducing a symmetric bimodal structure. As shown in Figure 5, the empirical thresholds derived from the uniform and clustered settings are nearly identical.
F.2.3. ADDITIONAL EXPERIMENTS ON WORLD DATASET
In addition to our LMSYS dataset analysis, we apply our testing procedure to historical NBA match outcomes using the publicly available dataset from Kaggle (Lauga, 2023). We focus on games played until the 2022 season and restrict attention to the 12 teams with the highest number of games played since 2002. Each data point corresponds to a comparison between a home and an away team, and we evaluate our hypothesis test on cumulative game data aggregated over rolling window of recent years. As shown in Figure for small values of (approximately the first 10 seasons), the data consistent with the BTL and Thurstone models. However, increases, the hypothesis is increasingly rejected, suggesting that single latent skill score per team fails to adequately represent team strength over long horizons of time.
E3. Confidence Intervals under Null Hypothesis
In this subsection, will discuss a method approximately calculate the confidence intervals under the null hypothesis, with focus on the BTL model. While our discussion is specific to the BTL model, it can be easily generalized to other Thurstone models. Specifically, our goal is to approximately calculate the constants in Proposition 3.8 and as well as approximate the distribution of |F - while for the latter, we will be utilizing Gaussian approximation based on the asymptotic normality of い - =w, which was proved for the BTL model (Gao et al., 2023, Proposition 4.1). Similar results have been established for the general Thurstone models as in (Han et al., 2024).
Fllp. For the former, we will estimate the constants by conducting some simulation,
Estimating constant e7 in Proposition 3.8: To estimate the constant, we plot several trajectories of the normalized stochastic process [V] ( (k) p.1c)) (T (=( p,l1)) with (k( generated as in Lemma D.2 and the p. selected uniformly at random from (0, 1). The values of [V] varied from 10 to 100 with gaps of 10. Figure 7 plots the various trajectories of the (normalized) stochastic process as a function of k and also plots the 95th quantile for the stochastic process for all l: E [100]. The figure suggests that ey ss 0.45 is a good approximation to the value of ey (in the fixed sample setting).
Estimating the quantile of || FIle: In order to estimate ||F - File. we will utilize the asymptotic normality of vector A w Let de be computed as (7), then under mild regularity conditions, it was shown in (Gao et al., 2023,
33

---

Hypothesis Testing for Generalized Thurstone Models
95th Percentile
Bootstrapped F|- Gaussian approximation
Quadratic deviation
Empirical Density
10
10th
Figure 7: Plot of various trajectories of stochastic pro- cess in Lemma D.2.
Figure Histogram of ||- versus asymptotic approximation.
F12 based on bootstrapping
1.2
Estimated Threshold Value
0.8
0.6
Complete, k=12
Complete, k=20
0.2
Toroidal Grid, k=12
Toroidal Grid, k=20
0.0
20
30
40
50
60
Figure 9: Estimated threshold based on Proposition 3.8.
Proposition 4.1) that
(1)) - wi).... P. - x;)) 4 N( Ix),
where (: k Ej(LDeE F'i;;; ())) and S denotes the convergence in distribution. We will utilize this asymptotic
normality result to approximate the distribution of |F FIlr using the delta method as:
F FIl
Σ (F(w: - w.) F(w;; x)²))
(KJ)E
Σ F'(i; ((w; w. (w) =;²))²
(iJ)E
Σ F'(m; - ú; -,))² -4- (
(5)
where define LF (w) be the following matrix
(Lr(w));g = {
F w Extissee F' wz)²
if (i,j) E 3 if otherwise.
Since A is asymptotically normal It oo), therefore we approximate the distribution of ||F Fllß with distribution
34

---

Hypothesis Testing for Generalized Thurstone Models
of 2A (w) (T))(()) where (w) ~(00, & & Estte,ac (") In Figure 8, we plot the empirical distribution of [F()) - F(w")), IF calculated by randomizing over the choice of partitioning of 2 into 2 and 22. We also plot its asymptotic approximation, i.e., the empirical distribution of 22 2 Lr ( ( Clearly, as can be seen in Figure 8, our asymptotic approximation does indeed well approximate the empirical distribution even for small number of samples. Finally, based on the the 95th percentile of the empirical distribution of 2A LF ( we compute the expression for 6 = 0.45 and plot the estimated confidence intervals in Figure 9. It is worth noting that the estimated threshold values for complete graphs converge towards the theoretical value of 0.8, while those for toroidal grids approach 0.4. These findings are consistent with the threshold values computed via the empirical quantile method presented in Figure I for the respective graph topologies. Together, these observations suggest that while the exact distribution of T' is difficult to characterize, its tail can be asymptotically approximated using a quadratic function of Gaussian random variables via Proposition 3.8.
G. Testing for TF Models in TV and Spectral Norms
In Section 2, we framed the hypothesis testing problem using the Frobenius norm due to its analytical tractability, particularly in the context of maximun-likelihood-yye estimators. There is also significant precedent for employing quadratic distance measures in classical statistical testing for instance, the -test essentially utilizes a squared weighted ég-distance. However, in some applications, alternative notions of separation may be more desirable. One such example is the TV distance, which has appealing propertics, such as Le Cam's 's relation and the data processing inequality (cf. (Makur, 2019; Makur & Zheng,
2020)).
Recall that in (11), we defined the separation distance from the class of Tr models using the Frobenius norm. Alternatvelly for any pairwise comparison matrix P [0, 1|mx", we can define the TV separation distance from the model class TF
TV(P,Tr) & inf WEW,
Σ (EJ)EE
Ipg
F(w; wy)l-
E
Using TV(P, in (11) leads to an equivalent hypothesis testing problem, but with the separation measured in TV distance. Utilizing standard norm- commeeqvivleenee inequalities, such as ||x||| S Vallarl2 for x e IR"", we can relate this the Frobenius norm as
TV(P,TF) S inf
P F(w)ll.
WEW,
Therefore, if the TV separation satisfies TV(P, Tr) 2 c, it follows that
inf 1 - - F(w)le 2 VI wEW, 71
(48)
Recall from the minimax formulation in (12) that our test distinguishes between the null and alternative hypotheses with minimax risk at most 1/2. provided the Frobenius separation exceeds c/v nk (see Theorem 3.2). Utilizing the inequality (48), this implies that our test retains minimax risk at most 1/2 whenever
c/vnk
SVE 2
Vnk
which implies that the TV separation distance TV(P, TF) 2 //////////l/l is sufficient for testing (yielding an upper bound on critical threshold for TV distance). Notably, for complete graphs, this reduces to the critical threshold of O(1 (/)/kk)) which also matches the lower bound established by (Seshadri & Ugander, 2019) for the same notion of TV separation distance.
Finally, similar arguments allow our upper bounds to be extended to the spectral norm, using the inequality ||A||2 < || for any matrix A. Consequently, our test also guarantees small minimax risk under spectral norm separation. However, obtaining corresponding lower bounds under the spectral norm remains open problem.
35


Reviews:
[{"review_id": "vPLKVAvJFr", "reviewer": "Reviewer_MqJu", "summary": "The paper addresses the problem of hypothesis testing for whether a given pairwise comparison dataset follows a Generalized Thurstone Model (GTM), which is formally stated in equation (12). It proposes a test statistic along with a corresponding testing threshold that matches the lower bound on the critical threshold $\\epsilon_c$ in the case of a complete observation graph, as defined in equation (14), thereby establishing its minimax optimality in this setting.\n\nAdditionally, the paper derives information-theoretic lower bounds on $\\epsilon_c$ for different graph types, as shown in Table 1 and stated in Proposition 3.5. It also provides time-uniform bounds on Type I and Type II errors in a sequential testing framework, where at each time step, a single comparison is observed, as presented in Theorem 3.7. Furthermore, the paper constructs confidence intervals for the test statistic under the null hypothesis and validates the theoretical results through experiments on both synthetic and real datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and for dedicating time to review our paper! We respond to the specific questions as follows:\n\n**Comparisons to other methods for testing of Thurstone models**: Minimax testing for generalized Thurstone models (for a fixed choice function $F$) has not been studied much in the literature. The case of logistic $F$, which corresponds to BTL models, is the only case that has baselines [Makur, Singh 2023]. So, it is difficult to provide accurate baselines for general functions $F$. However, to address this concern, we have included an additional experiment to compare the proposed method (Max. Likelihood) with [Makur, Singh 2023] for complete graphs (See response to Reviewer smfn for details). Our results show that the proposed method has a similar performance to the spectral method in [Makur, Singh 2023]. We have also added other experiments as outlined in the response to Reviewer smfn. We will add details of all experiments to the manuscript to make it more informative.\n\n\n**Estimating threshold can be computationally expensive**: Yes, we agree that the computational complexity of estimating threshold will depend on the number of simulated datasets generated. However, we remark that: \n1) This procedure is efficiently parallelizable. \n2) Even with a naive implementation (without any parallelization), the running time is small as each of our experiments can be done within 5 minutes on a normal CPU for $n$ as large as $60$. To speedup computing $\\hat{w}$ on the simulated dataset, one can initialize the iterates at the optimal values that generated the simulated dataset, followed by a few iterations of gradient descent. \n3) Moreover, when all $k_{ij}$ are equal (or roughly the same), our simulation results in Figure 1 suggest that $0.75n/k$ as the threshold for complete graphs and $0.4n/k$ for 2D grid is a good approximation.\n4) Using an asymptotic approximation and an intermediate result (Proposition 3.8), we can approximate the threshold as detailed in Appendix F.2. Approximating the threshold in this way is much faster than the empirical quantile approach. \n\n\n**Motivation for using the weighted log-likelihood**: We chose to use weighted negative log-likelihood for the following reasons: \n1) To define the minimax composite hypothesis testing problem, we first introduced a separation distance. For analytical purposes, we chose to represent this separation distance using the (unweighted) Frobenius norm. The weighted likelihood expression in Eq. 8 arises when we relate the separation distance in Frobenius norm to the cross-entropy term, as detailed in the Proof of Theorem 1. As a result, our definitions in Eq. 6,7 naturally inherited the weighted property. \n2) If we were to use the unweighted version of maximum likelihood, we would need to employ a weighted Frobenius norm with weights $k_{ij}$ to define separation distance, which did not seem a natural choice to us. Alternatively, we would need to add an extra assumption that different $k_{ij}$ are within constant factors of each other, which we also chose not to do.\n\n\n\n**Expression for F for the BTL and Thurstone models**: We remark that we have used $F(t) = \\frac{1}{1 + e^{-t} }$ (sigmoid function) for the BTL model and $F(t) = \\int_{-\\infty}^t  \\frac{1}{\\sqrt{2\\pi}} e^{-x^2/2} dx$ (complementary-CDF of normal) for the standard Thurstone model. We will include this information in the revised manuscript.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "Yes, however, I think the experiment section could be improved by adding comparisons to other methods that perform hypothesis testing for Thurstone models, particularly in terms of Type I and Type II errors. For instance, some of the methods mentioned in the last paragraph of Section 1.2 could be included as baselines, even if they only apply to specific models, to provide a more informative comparison.", "theoretical_claims": "I checked the general ideas in the proofs but I haven't verified each step.", "experimental_designs_or_analyses": "yes, see the comment above in the methods evaluation and criteria", "relation_to_broader_scientific_literature": "The key contribution is the proposed hypothesis test for the Generalized Thurstone Model using a maximum likelihood approach. This complements previous work in (1), which developed hypothesis tests for the Bradley-Terry-Luce (BTL) model based on spectral methods.\n\n\n---\n\n(1) Makur, A., and Singh, J. (2023). \"Testing for the Bradley-Terry-Luce Model.\" In IEEE International Symposium on Information Theory (ISIT).", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths: \n\n- The paper addresses an interesting problem within a general framework that encompasses many Generalized Thurstone Models.\n- The paper’s theoretical results are promising and well-developed, providing a thorough investigation into the minimax optimality of the proposed test. Additionally, it offers bounds within the sequential testing framework.\n\n\nWeaknesses: \n\n- I believe the experimental study could be enhanced by providing more informative results and comparing the proposed test with other methods.\n- The approach used in Section 4 to estimate the threshold—by generating numerous simulated datasets under the null hypothesis to compute the testing threshold—can be computationally expensive.", "other_comments_or_suggestions": "For completeness, it would be helpful to provide the expression for $F$ that was used in the experiments for the BTL and Thurstone models.", "questions_for_authors": "Is there a specific motivation for using the weighted log-likelihood in equation (6) instead of the typical log-likelihood, which I assume would involve $Z_{ij}$ instead of $p_{ij}$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "525k9CY8yk", "reviewer": "Reviewer_smfn", "summary": "This work develops a hypothesis testing framework to determine whether pairwise comparison data follows a generalized Thurstone model for a given choice function, introducing a minimax separation distance to quantify deviations from such models. The study establishes theoretical bounds on the critical threshold based on the observation graph's topology, proposes a hypothesis test with confidence intervals, and establish time-uniform bounds on type I and II errors using reverse martingale techniques.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and for dedicating time to review our paper! We respond to the specific questions as follows:\n\n**Intuitive explanation for definition of test statistic**: In addition to our existing discussion after Eq 15 in the paper, we provide here with an additional intuitive explanation: Consider the statistic \n\n$$T^{\\prime} =  \\sum_{(i,j)\\in \\mathcal{E}}\\frac{Z_{ij}(Z_{ij}-1)}{k_{ij}'(k_{ij}'-1)}+F(w_i^*-w_j^*)^{2}-2F(w_i^* -w_j^*)\\frac{Z_{ij}}{k_{ij}' }$$ \nobtained by substituting $w^*$ in place $\\hat{w}$ in Eq. 15. Then, the expected value of $T'$ is $||P- F(w^*) ||_F^2$. \n\nThis is because the expected value of the first term is $p_{ij}^2$, and the last term is $-2 F(w_i^* - w_j^*) p_{ij}$. Hence, $T$ is constructed by plugging in $\\hat{w}$ in place of $w^*$ in the unbiased estimator $T^{\\prime}$ of $||P- F(w^*)||_F^2$.\nWe will add additional clarification in the manuscript. \n\n**Relationship between this test statistic and those in [Rastogi et al. 2022] and [Makur, Singh 2023]**:\n* The test statistic proposed in [Rastogi et al. 2022] is for a two-sample testing problem (i.e., testing whether two sets of samples are drawn from the same pairwise comparison model or not) which is a very different problem to that in our work. \n* The test statistic in [Makur, Singh 2023] is for testing the BTL model, which is a special case of our model. Furthermore, their test statistic is based on spectral techniques, while ours is based on maximum likelihood techniques and is applicable for general Thurstone models\n* There is some resemblance between the three test statistics since all three statistics are ``estimators” for squared Frobenius distances of pairwise comparison models. However, the techniques used to analyze them are very different. For example, our theoretical analysis crucially relies on sample splitting, while the other two do not. We will expand on this discussion in the final version. We comment on the experimental concerns below.\n\n**Comparisons with state-of-the-art methods/Additional Experiments**: Except [Makur, Singh 2023], we are not aware of any work that addresses the same minimax problem as ours for a general Thurstonian model in a non-asymptotic regime. The tests based on likelihood ratio do not consider the general hypothesis testing problem considered in this work. However, we have performed following additional experiments for the BTL model. The figures for these experiments can be found at http://anonymous.4open.science/r/something-E6CB/ALLFigures.pdf\n\n1. **Performance Comparison with [Makur, Singh 2023] (Exp1)**: We assume the observation graph to be complete and define the pairwise comparison matrix $P$ under the null and alternative hypothesis as the one used to prove the lower bound in Eq. 39. We set $\\eta = 0.06$ and $k = 10$. We evaluate the empirical Type I and Type II errors for three methods: the proposed test statistic based on maximum likelihood estimation (Max. Likelihood), the same test statistic without sample splitting (Max. Likelihood2), and the spectral method from [Makur, Singh 2023] (Spectral). Our results in Fig. 1 indicate that the proposed method performs comparably to the spectral approach, while Max. Likelihood2 achieves even lower error. The threshold for all three methods is determined using the empirical quantile approach.\n\n2. **Type I and II Errors: Empirical Quantile vs. Optimal Threshold (Exp2)**: We extend our previous experiment by comparing the empirical quantile threshold with the \"optimal\" threshold $\\eta^2n(n-1)/2$. We evaluate Type I and II errors for $\\eta\\in[0.08,0.16], n\\in[15,25,35,45], k=10$. Fig. 2 shows that the empirical quantile approach performs similarly to the optimal threshold, with Type I error control close to the nominal 0.05 level, despite the threshold being computed from randomly sampled skill scores.\nTo address Reviewer 3Nsw concerns regarding threshold computation using clustering, we also compare thresholds derived from random and clustered skill scores, where clustering is based on assigning half the player's scores randomly in [-0.7,-0.4] and the rest with their exact negative. Fig 3 shows that both approaches yield nearly identical thresholds.\n\n3. **Experiment on real-world datasets**: In addition to our LMSYS dataset experiment, we also analyzed the NBA dataset from https://www.kaggle.com/datasets/nathanlauga/nba-games/data. Using data from 2022 onward, we applied our test to the 12 teams with the most matches since 2002. Each comparison involved a home and away team, and we tested on cumulative data over t recent years. Fig. 4 shows that for the first ~10 years, the BTL and Thurstone models fit well, but for larger intervals, the hypothesis is rejected, as a single BTL score cannot capture team strength over extended periods.\n\nVarious parameters, such as number of simulated datasets, are the same as those used in our paper for previous experiments. We will include these experiments in the final version", "claims_and_evidence": "My primary concern is the definition of the test statistic in Equation (15), as the paper lacks an intuitive explanation for its formalization. Furthermore, the relationship between this test statistic and those proposed in Rastogi et al. (2022) (Equation 8) and Makur & Singh (2023) (Equation 11) remains unclear, **requiring further clarification regarding its advantages in both theoretical analysis and experimental performance.**\n\nReferences:\n\nRastogi, C., Balakrishnan, S., Shah, N. B., and Singh, A. Two-sample testing on ranked preference data and the role of modeling assumptions. Journal of Machine Learning Research, 23(225):1–48, 2022.\n\nMakur, A. and Singh, J. Testing for the bradley-terry-luce model. In 2023 IEEE International Symposium on In\u0002formation Theory (ISIT), pp. 1390–1395, 2023. doi:10.1109/ISIT54713.2023.10206450.", "methods_and_evaluation_criteria": "See Claims And Evidence part.", "theoretical_claims": "The paper establishes a strong theoretical framework with rigorous proofs.", "experimental_designs_or_analyses": "Lack of comparisons with state-of-the-art methods. All experiments present only test statistics and thresholds; explicitly reporting key evaluation metrics such as test power and Type-I error would be highly appreciated.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SleOwJttLO", "reviewer": "Reviewer_3Nsw", "summary": "Covers “Generalized Thurstone models,” in which each player has a utility, and the probability of winning is a function of the difference in utilities – but this choice function is an arbitrary CDF. Nice motivation to observe that GTMs do not capture certain types of choice dynamics, so asking whether data are consistent with any GTM is a useful question. The general question regarding whether *any* GTM is consistent with a dataset is very interesting, and also technically intricate -- this is an excellent question to ask, and the authors make significant progress.\n\n## update after rebuttal\n\nNote that my questions below have been addressed in the authors' rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for detailed feedback. Due to 5000 character limit, our responses are concise. We will incorporate the addressed points and new experiments in the final version\n\n**Experimental Concerns**\n* Experiments not explored in detail: Our focus was on theoretical aspects of the testing problem. To clarify, our first synthetic experiment shows that the threshold obtained via the empirical quantile approach follows the same high-level scaling as the theoretical threshold in Eq 37 (see Fig1). We also showed how to obtain a threshold using an asymptotic approximation in App F.2. **To address concerns, we added new experiments on real & synthetic data (see response to Reviewer smfn)** \n* Interpreting Exp 1 findings: See response above\n* Broader application: Validating the BTL model is crucial due to its wide applications(eg. in RLHF), where flexible ranking models are preferred. We believe our test could extend to RLHF where BTL scores are given by neural network/linear models.\n* Connection b/w theory and practice: Our results on critical threshold and confidence intervals (CI), which follow from Type I & II error bounds, connect to our 1st synthetic experiment and App F.2 (see above).\n* Validating empirical quantile approach: We have designed an experiment to validate its effectiveness in a synthetic setting. See Exp2 in response to Reviewer smfn\n* Interpretation of LMSYS Results: The 60% above-threshold rate is a bootstrapped estimate of the test's power indicating ~40% chance that the model lies within 95% statistical deviations from BTL. The figure shows that as n increases, deviation from Thurstone increases, a top-9 batch size provides a statistically accurate fit to the Thurstone model, and the deviations are significant for $n\\geq21$.\n* Sparsity of $p_{ij}$: There is no sparsity as the graph is nearly complete\n\n**Necessity of Bound b**: This restriction arises from our techniques for bounding separation distance. While we believe the bound b can be removed for certain cases (eg.complete graph) the analysis is significantly more complex. For general graphs, it is unclear whether b is fundamental; this is an interesting future problem. Additionally, assuming bounded weights is standard in literature on parametric models [Shah et al. 2016]. \n\n**Non-uniqueness of w in Disconnected Graph**: Our analysis uses error bounds in Laplacian semi-norm. When $G$ is disconnected, solutions $w^*,\\hat{w}$ of Eq 7,8 may not be unique, but the error $||\\hat{w}-w^*||_L$ is well-defined as the non-unique component lies in the null space of $L$. Thus, our upper bounds on critical thresholds still hold. Additionally, our lower bounds do not assume connectivity and hold for disconnected super-Eulerian graphs. \n\n**Interpretation of Thm. 7 & Tightness of CIs**:  \n* Thm. 7 can be reduced from the sequential setting to the standard testing where data is available upfront.\n* It implies Type I & II errors decay exponentially when separation distance $\\gg1/\\sqrt{nk}$.\n* The bounds apply to any partition of data into $\\mathcal{Z}_1$ and $\\mathcal{Z}_2$, offering guidance on split-size based on graph topology (e.g., equal split for complete graphs, larger $k_1$ for better type I control in cycle graphs). See Appendix E for details\n* To see tightness of CIs, we can compare Figs 1 and 5 for complete and grid graphs, with scaled threshold values of ~0.75 & ~0.45.\n\n**Random Skill Scores**: Yes, the scores are drawn independently and uniformly in [-b,b] and translated to satisfy $w^T1=0$. While we acknowledge concerns about coverage with random sampling, in the context of finding thresholds, our experiments show that the resulting threshold exhibits the same scaling as theory predicts and achieves good empirical type I and II errors compared to a well-crafted threshold in a synthetic setting (see Exp2).\n\n**Notational Confusion**:\n* Definition 2.2: Sure, we will remark that F is a special CDF and add examples.\n* Universal constant: Once graph $G$ choice function $F$, parameters $\\delta,b$ are fixed, all the constants are universal as they depend only on these entities. We will remove 'universal' to avoid confusion. Note:$\\epsilon$ is not constant as it can depend on $n,k$\n* LYMSYS/LMSYS: Yes, it is LMSYS\n\n**Test statistic**:\n* Distribution: The distribution of $T$ is indeed hard to characterize, but using Prop. 3.8, we can asymptotically approximate its tail by a quadratic function of Gaussian random variables (see App F.2)\n* Intuition: See response to Reviewer smfn. Our statistic may not be optimal in the sense you propose, but it is analytically tractable and does characterize the critical threshold.\n \n**Essential References**: We will discuss it in final version.\n\n**Other statistical tests** Our problem is a minimax composite hypothesis testing problem, which lacks a non-asymptotic theory in general. The only direct comparison of our bounds is with [Makur, Singh 2023] in the BTL case; both results have the same critical threshold scaling.", "claims_and_evidence": "The abstract claims that the results are \"validated\" through experiments on synthetic and real-world datasets. I don't think is quite accurate. It seems that, instead, the synthetic experiments (basically just one in the main paper body) show empirically how the test statistic is distributed for a particular distribution over in-class tournaments, while the real-world datasets (also just one) also pursue the same methodology to estimate the test statistic, and show that the statistic is distributed roughly as expected for GTM models for the most popular models, but not for comparisons that involve less popular models. This is a suggestive finding, but does not seem to be explored in more detail.", "methods_and_evaluation_criteria": "I feel that the empirical evaluation is less thorough than the theoretical parts of the paper. There are some interesting findings, but I don't come away with a strong understanding of applying the techniques developed here to a broad range of settings. See some more specific points in the general comments and questions below.", "theoretical_claims": "I did not check proofs. For the supplementary material in particular, I just scanned at a very high level.\n\nHere is my rough understanding of the flow of the theoretical parts of the main paper body, with a few notes for suggestions inlined:\n1. Model: each directed comparison (i,j) is either present or not. If present, the probability of winning is known fully. The graph is fixed in advance, not dependent on outcomes.\n2. Note: Some confusion in notation: Definition 2.2 places no restrictions on F beyond R → [0,1], but then in Equation 3 it’s defined in terms of noise distribution G.\n3. Pairwise comparison data is then (Equation 5) defined as bernoulli random variables parameterized by the winning probability of a competition.\n4. The authors then define likelihood of observations, assume winning probabilities are bounded away from 0 and 1. The estimation problem is given with a bound b of magnitude of weights – seems unnatural, and shouldn’t be necessary with this assumption on winning probabilities, but later sections make clear that there are some technical issues for which this is necessary. Question for authors: is this restriction necessary because of the techniques, or is it fundamental?\n5. Add some assumptions on strong log-concavity and bounded derivatives for F – this guarantees a unique solution for the likelihood estimation problem, and holds for some common GTMs.\n6. Note: Section 2.3: why are the constants \"universal\" when they depend on F? Assuming it’s just \\delta,\\epsilon that are universal? Possible to clarify this in the text?\n7. The authors then define their testing problem to differentiate between H_0, in which the winning probabilities come from some utilities under F, and H_1, in which any utilities result in a winning matrix bounded away from the actual one. They then show this is approximated by the frobenius norm difference between the true winning matrix, and the one under the likelihood-maximizing utilities.\n8. From here, they define a test statistic, and ask what properties of the graph and observations are needed for the “minimax risk” (a measure of the probability of type-1 and type-2 errors) to be bounded by a constant. \n9. They study the “critical threshold,” which is the distance lower bound in the H_1 null hypothesis. They show first there is an upper bound like c/sqrt(nk) on the critical threshold, where n is #players, and k is (half) number of games per observed pair. Their test uses half the data to estimate the utilities, and the other half to compute the statistic.\n10. Their test holds even when the observation graph is disconnected – but I wonder what happens with their utility estimation procedure since it’s no longer identified? Possible to comment on this?\n11. Next they consider lower bounds on the critical threshold. The lower bound is based on Seshadri&Ugander, but extends to GTM and more general observation graphs. These seem to be tight to within constants for complete graphs.\n12. They also consider some upper bounds on type 1 and 2 error probabilities when comparisons arrive by “rounds” of games, each round containing a bernoulli draw per edge. I have to say, I’m not confident how to interpret the results of Theorem 7, including how tight the resulting confidence intervals might be. Perhaps the authors could include some more discussion about this -- I'd love to hear what is possible in the rebuttal.", "experimental_designs_or_analyses": "See below for some comments.", "relation_to_broader_scientific_literature": "The authors do a good job of laying out the landscape for this area.", "essential_references_not_discussed": "Perhaps consider this reference at PNAS on sample complexity where your assumption of winning probabilities bounded away from {0,1} does not hold: https://www.pnas.org/doi/10.1073/pnas.2202116119", "other_strengths_and_weaknesses": "Please see below under comments and suggestions", "other_comments_or_suggestions": "Slight confusion: equation 1) speaks to a specific choice function F, while main contribution 1) speaks to the distance to the family of GTMs. At this point in the draft, I was uncertain whether the focus was examining a null hypothesis regarding a single GTM, versus the entire family. This became clear later on.\n\nMy summary and some comments on the theoretical section is given above under \"Theoretical Claims.\"\n\nHere are some comments, questions, and thoughts regarding the Experiments section:\n\n“Random skill scores” – does this mean uniform in [-b,b]? This is a good strawman, but not a broad coverage of what happens in settings where utilities are not drawn uniformly (eg, what happens if there are clusters of utilities, etc). Could the authors please comment about this assumption? I discuss next that the synthetic experiments are quite tightly tied to this assumption, as it induces the distribution over test statistic values (unless I am misunderstanding).\n\nThe first experiment as I understand it measures the distribution of the test statistic induced by the very specific underlying model (random skill scores) – I’m not sure how to read the finding from this experiment, as I can’t imagine an actual experimental setting in which this is a good probabilistic model of reality…? Related to this, on the idea of “repeating the process a sufficient number of times to build a distribution of test statistics” – is anything known about the true distribution of the test statistic for a GTM?\n\nPerhaps my biggest question on the experiments is that I seem to be missing something high level. I don’t see the connection between the empirical test statistics and the various upper and lower bounds from the rest of the paper. Could the authors please clarify this, and whether anything more can be done experimentally to tighten the connection of the theoretical results to the questions that practitioners might face?\n\nRelated to this, there are no experiments that test whether the empirical quantile approach can actually distinguish between, say, a random skill scores GTM model, and a related model chosen to be a certain known distance from any GTM model. Is it possible to perform such an experiment? It’s hard to know how to interpret \n\nFor the LMSYS results, what does it mean that 60% of values are above the threshold, beyond the fact that the estimation procedure underestimates the critical value? Is this an issue of the increased variance of estimating p_{ij} due to sparsity of results for each (i,j) pair? Or, as I read it, is the idea that somehow less popular language models do *not* have a fundamental \"quality\" that can be used to estimate their likelihood of generating a better answer than a competitor? If the latter, this seems like a somewhat startling finding, and would benefit from more discussion (and analysis), as it now speaks more centrally to LLM testing, an issue of great importance right now.\n\nNote: Figure 2 caption references LYMSYS (as does later text) -- is this supposed to be LMSYS? Otherwise, please clarify.", "questions_for_authors": "In addition to the questions above, two more things:\n\n1. What is the intuition behind your test statistic? Is there some reason to think this is the best or approximately best (ie, variance-minimizing) test statistic for GTM or specific choice functions? \n\n2. Are there other simplifications that would allow considering your bounds relative to other standard statistical tests? Perhaps a step function choice function?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Jp1X7YdxXg", "reviewer": "Reviewer_gx7K", "summary": "In this paper, the authors look at the problem of hypothesis testing of generalized thurstone models. The later models are used to model ranking among several entities based on pairwise comparisons. Extensive research has been done to learn the parameters of such a model. However, an important questions is given a set of empirical pairwise comparisons does the observations correspond to an underlying GTM? This hypothesis question apparently has not been looked so far. The authors initiate a formal theoretical study of this testing problem and came up with a formalism and test statistic which is the main contribution of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback and for dedicating time to review our paper! We respond to the specific questions as follows:\n\n**Testing problem with respect to other norms**: We believe the Frobenius norm is a natural choice for our problem as it allows tractable analysis of maximum-likelihood-type methods. There is some precedent to utilizing such quadratic distances in hypothesis testing, such as the classical chi-squared test. Another popular choice for separation distance is the sum of total variation (TV) distances. Using the equivalence of norms ($||x||_1 \\leq \\sqrt{n} ||x||_2$), our results can be translated to TV distance, and they again turn out to be tight for complete graphs. For the TV separation distance $TV(P, \\mathcal{T}_F)$, a simple calculation gives:\n\n$TV(P, \\mathcal{T}_F) =$\n\n$\\inf_{w \\in \\mathcal{W}_b }$\n\n$\\sum_{(i,j) \\in \\mathcal{E}}$\n$\\frac{1}{|\\mathcal{E}|} |p_{ij} - F(w_i - w_j)| \\leq  \\inf_{w \\in \\mathcal{W}_b } \\frac{1}{\\sqrt{|\\mathcal{E}|} } ||P - F(w)||_F$\n\nRecall that our test can distinguish whether $P = F(w)$ for some $w \\in \\mathcal{W}_b$ or \n\n $\\inf_{w \\in \\mathcal{W}_b} \\frac{1}{n}  ||P - F(w)||_F \\geq c/\\sqrt{nk}$ \nwith a minimax risk at most 1/2. If $TV(P, \\mathcal{T}_F) \\geq \\epsilon$, then using above equation, we can conclude that \n\n$$\\inf_{w \\in \\mathcal{W}_b } \\frac{1}{n} ||P - F(w)||_F \\geq  \\frac{\\epsilon}{n} \\sqrt{|\\mathcal{E}| }$$\n\nThus our test has small minimax risk if  $\\frac{\\epsilon}{n} \\sqrt{|\\mathcal{E}| } \\geq c/\\sqrt{nk}$, which is equivalent to $\\epsilon \\geq c\\sqrt{n/(|\\mathcal{E}| k)}$. This implies that the critical threshold for our test for the quantity $TV(P, \\mathcal{T}_F)$ is  $O(\\sqrt{n/(|\\mathcal{E}| k)})$ which reduces to $O(1/\\sqrt{nk})$ for complete graphs. Interestingly, this bound matches the lower bound in [Seshadri & Ugander, 2020] for complete graphs, derived for the same notion of TV separation distance.\n\nMoreover, using the inequality $||A||_2 \\leq ||A||_F$ for any matrix $A$ and the same argument as above, we can translate our upper bounds to the spectral norm. However, we don't have lower bounds for the spectral norm. \nWe will incorporate these comments into the manuscript.", "claims_and_evidence": "The main claim is that the proposed hypothesis questions is useful in checking whether a given set of samples of pairwise comparisons correspond to a GTM or not. They also give experimental evidence to support the theoretical guarantees.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, in my opinion. The formalism of the testing problem is as follows\n\nA good weight vector w must be orthogonal to the all ones vector and must have bounded values. The hypothesis testing problem distinguishes the following two cases.\n- there exists a good weight vector w such that the probability of pairwise comparisons follow a cumulative probability according to some distribution F with respect to the difference of w values\n- the pairwise comparisons is eps far in Frobenius norm from any such good weight vector\n\nI didn't check the proof but here are the main theoretical claims.\n \n- we roughly need n/eps samples to answer the above testing problem \n- the upper bound is supported with a suitable lower bound based on LeCam method\n- confidence intervals have been derived for the test statistic", "experimental_designs_or_analyses": "The experiments were conducted on both synthetic and benchmark data. For both cases it shows that the proposed methods works well to determine the test threshold using a data-driven approach.", "relation_to_broader_scientific_literature": "This works initiates the hypothesis testing of GTMs. However some special cases appeared in the literature before. The proposed method generalized beyond these special cases.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "I think the proposed testing problem is novel and the techniques proposed are sound.", "other_comments_or_suggestions": "NA", "questions_for_authors": "What happens if we define the testing problem with respect to other matrix norms such as the spectral norm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary.**

The topic of this paper is goodness-of-fit testing for pairwise comparison models.
Specifically, the objective is to test whether pairwise comparison data was generated by a Generalized Thurstone Model (null hypothesis; henceforth “GTM”) or by a pairwise comparison model which is not GTM (composite alternative hypothesis).

In a GTM, it is assumed that each agent $i$ is assigned a latent utility value $w_i$ and the probability $p_{ij}$ that agent $i$ compares favorably with $j$ (or is "preferred") is given by $F(w_j-w_i)$ where $F$ (the so-called “choice function”) is a CDF, whereas in a more general pairwise comparison model, the $p_{ij}$ probabilities may be unstructured and are recorded in a matrix.

Under a selected notion of distance to the sub-class of GTMs and chosen minimax formulation (where the risk is the sum of the type I and type II errors), the authors derive lower bounds on the so-called critical threshold of the problem (14) which depend on the topology of the underlying observation graph. Conversely, they propose and analyze a test statistic to obtain upper bounds on this critical threshold. In particular, their results are tight when the underlying graph is complete. They further derive time-uniform bounds on the error probabilities in a sequential testing framework and provide an experimental evaluation of their test.

**Strengths.**

* The problem had not been considered before in its generality (only the more restricted BTL model was previously considered in this framework).
* The problem is technically difficult and leaves questions for further investigation to the community.
* They perform comparably to Makur & Singh, 2023 for the more restricted BTL models.
* Sufficient technical novelty (MqJu, 3Nsw) compared to Makur & Singh, 2023.

**Weaknesses.**

* Not clear how much interest there is for non-BTL models in practice (3Nsw).
* The results are not tight for most observation graphs.

**Discussion and reviewer consensus.**

The author response successfully addressed the reviewers’ concerns. 
However, while the referees acknowledged its contributions, none seemed to be particularly excited about the paper.

**Additional remarks.**

Originally, the referees had numerous concerns:

* Experiments are insufficient: no baselines, missing relevant evaluation metrics (MqJu, smfn, 3Nsw).
* Computing the testing threshold is expensive (MqJu).
* There is no intuition for the propose test statistics (smfn).

However, the authors have done an honest effort in their response, and ran additional experiments. As a result, the above concerns were dispelled.

**Overall evaluation.**

I trust that the authors would be able to make the promised changes in their final version. Due to its theoretical nature, I do not think that remaining experimental limitations of the paper warrant rejection; quite on the opposite, I think the authors went the extra mile. I am recommending this paper for acceptance.
Decision: Accept (poster)