Aggregating Partial Rankings with Applications to Peer Grading in Massive Online Open Courses (d4-conf-atal-2015-0159)

Given a finite type set \(T\), rational masses \(\mu\), a finitely represented measure-preserving \(k\)-regular bundle graphing \(K\) retaining the relevant overlap structure, and a hidden strict type order ≽★, place types exchangeably on \(K\), form type-averaged Borda scores from integral \(k\)-item local rankings, and decide whether ℼ[\uoperatorname{Acc}μ] ≥ \(1-ε\), where \(\uoperatorname{Acc}μ is weighted agreement on distinct type pairs.

A society is given by its support: \(T\) lists the \(\tau\geq2\) types of positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Fix a strict ground-truth order \(\succ^\star\) on \(T\), unavailable to the aggregation rule.
Represent the bundle graphing on two copies of \(X=\{1,\ldots,m\}\times[0,1)\), each with uniform probability measure, by \(k\geq3\) measure-preserving bijections \(f_i:X_U\to X_V\). Each bijection is specified by finitely many rational interval pieces on which \(f_i(u,x)=(v,x+c)\); their graphs are disjoint. Thus every item belongs to exactly \(k\) bundles, each containing \(k\) distinct items, with overlaps retained.
Supply a binary integer \(D\) divisible by all denominators of interval endpoints, translations and masses. The \(mD\) equal-measure item cells have width \(1/D\); require \(mD\geq3k(k-1)+2\). Place exactly \(mD\mu_t\) cells of each type \(t\) uniformly among all such assignments. Independently choose a uniform strict ordering of cells within each type, consistently across bundles. This defines the exchangeable placement law; labels and cell priorities are constant within cells.
Rank each integral bundle perfectly by \(\succ^\star\), refining equal types by their cell priorities. An item receives \(k+1-r\) points when ranked in position \(r\), and its score \(s(x)\) sums its \(k\) contributions. Define the type-averaged score \(S_t=\mu_t^{-1}\int_{\{x:\ell(x)=t\}}s(x)\,d\nu(x)\).
Define weighted agreement on distinct types by \(\operatorname{Acc}_\mu=\frac{\sum_{t\succ^\star u}\mu_t\mu_u\mathbf{1}\{S_t>S_u\}}{\sum_{t\succ^\star u}\mu_t\mu_u}\); score ties receive no credit. Expectations are over placement and within-type priorities. Any running times are measured in \(m,\tau,k,\log D\) and total input bit length \(L\).

Does a universal constant \(C\) give \(\mathbb{E}[\operatorname{Acc}_\mu]\geq1-C/\sqrt{k}\) for every admissible instance, or does this guarantee fail?
For graphings with no cycle of length four, does a universal constant \(C_6\) give \(\mathbb{E}[\operatorname{Acc}_\mu]\geq1-C_6/k\), or does this guarantee fail?

For discrete items uniformly permuted onto a regular bundle graph, perfect-grading Borda has expected agreement at least \(1-O(k^{-1/2})\), improving to \(1-O(k^{-1})\) without four-cycles, under the stated degree and population restrictions. [Discrete guarantee](https://arxiv.org/pdf/1411.4619).
An infinite-population analysis establishes Borda optimality among rules ordering observed rank-vector types, using independent uniform bundle sampling; it does not address the graphing overlaps and averages over quality types defined here. [Infinite-population analysis](https://cs.au.dk/~iannis/publ/C79-ec16a.pdf). No result settling these precise guarantees was located.

Result

Both guarantees hold. One may take the universal constants \(C=C_6=4\sqrt{3\pi}\).

The proof below handles type averages directly. The cited [discrete result](https://arxiv.org/pdf/1411.4619) concerns agreement between individual items, so applying that theorem alone would not establish the requested conclusion.

1. Exact reduction to a finite bundle graph

Put \(n=mD\) and \(d=k(k-1)\). Each item cell has measure \(1/n\).

Because all interval endpoints and translations are multiples of \(1/D\), each bijection \(f_i\) maps every source cell onto a target cell. Moreover, it preserves the relative coordinate inside the cell: writing the source coordinate as \(a/D+z\), its image has coordinate \(b/D+z\), where \(0\leq z<1/D\).

Consequently, the bijections induce \(k\) perfect matchings between the \(n\) item cells and the \(n\) bundle cells. Their union is a simple, \(k\)-regular bipartite graph \(G\). Indeed, two maps sending the same source cell to the same target cell would agree throughout that cell, contrary to disjointness of their graphs.

For each fixed relative coordinate \(z\), the graphing is a copy of \(G\). Thus a four-cycle in \(G\) would lift to four-cycles in the graphing. In particular, if the graphing has no four-cycle, neither does \(G\).

Write \(n_t=n\mu_t\). Labels and priorities are constant on cells, and every bundle contains distinct cells, so scores are constant on cells. Hence the specified integral average is exactly

\(S_t=\dfrac{1}{n_t}\sum_{\text{cells of type }t}s(v)\).

Order the types as \(t_1\succ^\star\cdots\succ^\star t_\tau\). Assigning these types uniformly with their prescribed counts, then ordering cells uniformly within each type, is equivalent to placing the strict ranks \(1,\ldots,n\) by a uniform random permutation: every complete rank placement has probability

\(\dfrac{\prod_t n_t!}{n!}\prod_t\dfrac{1}{n_t!}=\dfrac{1}{n!}\).

We work with this equivalent finite model.

2. A concentration bound for one ranked item

For distinct item vertices \(v,w\), let \(\lambda_{v,w}\) be their number of common bundle neighbors. Regularity gives

\(\displaystyle \sum_{w\neq v}\lambda_{v,w}=d\).

Also, \(\lambda_{v,w}\leq k\). Without four-cycles, \(\lambda_{v,w}\leq1\). Therefore, uniformly over \(v\),

\(\displaystyle \sum_{w\neq v}\lambda_{v,w}^2\leq B,\qquad B=\begin{cases}kd,&\text{in general},\\ d,&\text{without four-cycles}.\end{cases}\)

Let \(Q_r\) denote the score of the item with strict rank \(r\), where smaller ranks are better. Conditional on that item occupying \(v\),

\(\displaystyle Q_r=k+\sum_{w\neq v}\lambda_{v,w}\mathbf{1}\{\text{rank at }w>r\}\).

Each of the other vertices has probability \((n-r)/(n-1)\) of containing a worse item. Thus, independently of \(v\),

\(\displaystyle b_r:=\mathbb{E}[Q_r]=k+d\,\frac{n-r}{n-1}\).

We prove the exponential-moment bound

\(\displaystyle \mathbb{E}\!\left[e^{\theta(Q_r-b_r)}\right]\leq e^{\theta^2B/8}\qquad\text{for every real }\theta.\)

Fix \(v\). List its positive overlap weights in nonincreasing order as \(w_1,\ldots,w_q\), and put \(N=n-1\). Let \(X_i\) indicate that the vertex carrying weight \(w_i\) contains a worse item. The indicators arise by sampling without replacement from \(N\) positions containing exactly \(n-r\) ones.

Expose \(X_1,\ldots,X_q\), and let \(M_i\) be the conditional expectation of \(\sum_jw_jX_j\) after the first \(i\) exposures. Set

\(\displaystyle R_i=\sum_{j>i}w_j,\qquad p_i=\mathbb{E}[X_i\mid X_1,\ldots,X_{i-1}].\)

A direct conditional-expectation calculation gives

\(\displaystyle M_i-M_{i-1}=\left(w_i-\frac{R_i}{N-i}\right)(X_i-p_i).\)

All denominators are positive: \(q\leq d\), whereas the population restriction gives \(N\geq3d+1\). Since the weights are nonincreasing,

\(\displaystyle 0\leq\frac{R_i}{N-i}\leq w_i.\)

Conditional on previous exposures, the martingale increment therefore has mean zero and lies in an interval of length at most \(w_i\).

We use the elementary bounded-variable inequality: if \(Y\) has mean zero and lies in an interval of length \(c\), then

\(\displaystyle \mathbb{E}[e^{\theta Y}]\leq e^{\theta^2c^2/8}.\)

For completeness, if \(\psi(\theta)=\log\mathbb{E}[e^{\theta Y}]\), then \(\psi''(\theta)\) is the variance under the exponentially tilted distribution. That distribution has the same supporting interval, so its variance is at most \(c^2/4\). Integrating this bound, with \(\psi(0)=\psi'(0)=0\), proves the inequality for either sign of \(\theta\).

Applying it conditionally to each increment and iterating yields

\(\displaystyle \mathbb{E}\!\left[e^{\theta(Q_r-b_r)}\mid r\text{ occupies }v\right]\leq\exp\!\left(\frac{\theta^2}{8}\sum_iw_i^2\right)\leq e^{\theta^2B/8}.\)

Averaging over \(v\) proves the asserted bound.

3. Concentration passes to type averages

For a type \(t\), define its preceding mass and its midpoint by

\(\displaystyle a_t=\sum_{u\succ^\star t}\mu_u,\qquad c_t=a_t+\frac{\mu_t}{2}.\)

Its strict ranks form the consecutive block

\(\displaystyle R_t=\{na_t+1,\ldots,n(a_t+\mu_t)\}.\)

The average rank in that block is \(nc_t+1/2\). Consequently,

\(\displaystyle \overline S_t:=\mathbb{E}[S_t]=k+\frac{d}{n-1}\left(n-nc_t-\frac12\right).\)

In particular, if \(t\succ^\star u\), then

\(\displaystyle \Delta_{t,u}:=\overline S_t-\overline S_u=\frac{dn}{n-1}(c_u-c_t)>0.\)

Let \(H_t=S_t-\overline S_t\). Since

\(\displaystyle H_t=\frac{1}{n_t}\sum_{r\in R_t}(Q_r-b_r),\)

convexity of the exponential gives, without any independence assumption,

\(\displaystyle e^{\theta H_t}\leq\frac{1}{n_t}\sum_{r\in R_t}e^{\theta(Q_r-b_r)}.\)

Taking expectations and using Section 2,

\(\displaystyle \mathbb{E}[e^{\theta H_t}]\leq e^{\theta^2B/8}.\)

For \(\theta>0\), Cauchy–Schwarz now gives

\(\displaystyle \mathbb{E}[e^{-\theta(H_t-H_u)}]\leq\left(\mathbb{E}[e^{-2\theta H_t}]\mathbb{E}[e^{2\theta H_u}]\right)^{1/2}\leq e^{\theta^2B/2}.\)

Markov’s inequality, optimized at \(\theta=\Delta_{t,u}/B\), therefore proves

\(\displaystyle \Pr(S_t\leq S_u)\leq\exp\!\left(-\frac{\Delta_{t,u}^2}{2B}\right)\leq\exp\!\left(-\frac{d^2(c_u-c_t)^2}{2B}\right).\)

This includes score ties, as required.

4. A weighted midpoint lemma

The remaining issue is normalization when a type has almost all the mass.

Let positive numbers \(\mu_1,\ldots,\mu_\tau\) sum to one, and partition \([0,1]\) consecutively into intervals \(I_i\) of these lengths. Let \(c_i\) be their midpoints and put

\(\displaystyle W=\sum_{i<j}\mu_i\mu_j.\)

We claim that, for every \(a>0\),

\(\displaystyle \sum_{i<j}\mu_i\mu_j e^{-(c_j-c_i)^2/a^2}\leq4\sqrt{\pi}\,aW.\)

To prove this, take \(i<j\), \(x\in I_i\), and \(y\in I_j\). The midpoint distance satisfies \(c_j-c_i\geq(\mu_i+\mu_j)/2\), and hence

\(\displaystyle 0\leq y-x\leq(c_j-c_i)+\frac{\mu_i+\mu_j}{2}\leq2(c_j-c_i).\)

It follows that

\(\displaystyle \mu_i\mu_j e^{-(c_j-c_i)^2/a^2}\leq\int_{I_i}\int_{I_j}e^{-(x-y)^2/(4a^2)}\,dy\,dx.\)

Write \(p=\max_i\mu_i\). We distinguish two cases.

Case \(p\leq1/2\). Since \(\sum_i\mu_i^2\leq p\),

\(\displaystyle W=\frac{1-\sum_i\mu_i^2}{2}\geq\frac14.\)

The sum of the preceding integrals is at most half the integral over the whole square, which is bounded by

\(\displaystyle \frac12\int_0^1\int_{\mathbb{R}}e^{-(x-y)^2/(4a^2)}\,dy\,dx=a\sqrt{\pi}.\)

Division by \(W\) proves the claim.

Case \(p>1/2\). Let \(R\) be the complement of the interval with mass \(p\), and put \(q=1-p\). Every pair of distinct type intervals has at least one interval in \(R\). By symmetry and nonnegativity, their summed integrals are at most

\(\displaystyle \int_R\int_0^1e^{-(x-y)^2/(4a^2)}\,dy\,dx\leq2a\sqrt{\pi}\,q.\)

But \(W\geq pq\). The ratio is therefore at most \(2a\sqrt{\pi}/p\leq4a\sqrt{\pi}\), completing the proof.

5. Both agreement guarantees

Apply the midpoint lemma in ground-truth order with

\(\displaystyle a=\frac{\sqrt{2B}}{d}.\)

The pairwise failure bound from Section 3 and linearity of expectation imply

\(\displaystyle 1-\mathbb{E}[\operatorname{Acc}_\mu]=\frac{\sum_{t\succ^\star u}\mu_t\mu_u\Pr(S_t\leq S_u)}{\sum_{t\succ^\star u}\mu_t\mu_u}\leq4\sqrt{\pi}\,\frac{\sqrt{2B}}{d}.\)

The denominator is positive because there are at least two positive-mass types.

For general graphings, \(B=kd\), so

\(\displaystyle \mathbb{E}[\operatorname{Acc}_\mu]\geq1-4\sqrt{\frac{2\pi}{k-1}}\geq1-\frac{4\sqrt{3\pi}}{\sqrt{k}}.\)

For graphings without four-cycles, \(B=d\), so

\(\displaystyle \mathbb{E}[\operatorname{Acc}_\mu]\geq1-4\sqrt{\frac{2\pi}{k(k-1)}}\geq1-\frac{4\sqrt{3\pi}}{k}.\)

The final inequalities use \(k/(k-1)\leq3/2\), valid for every \(k\geq3\). These bounds establish both requested guarantees uniformly over all admissible supports, masses, and graphings.

⟨structured verdict parsed — rendered above⟩

Verdict

Both guarantees are proved. The argument is correct and self-contained. The constants \(C=C_6=4\sqrt{3\pi}\) are valid for every admissible instance. No major or minor mathematical issues were found.

The proof addresses the requested agreement between type averages, including score ties and highly unequal type masses. It does not rely on transferring the cited individual-item guarantee to type averages.

1. Reduction to a finite graph

The reduction is valid.

• Divisibility by \(D\) ensures that every interval piece consists of whole cells and that each translation sends a source cell onto a target cell.
• Translation preserves the relative coordinate within a cell.
• Each bijection therefore induces a perfect matching between the \(n=mD\) source and target cells.
• If two bijections induced the same edge, their translations would agree on that entire source cell. This contradicts disjointness of their graphs. Consequently, the resulting bipartite graph is simple and \(k\)-regular.

A four-cycle in the cell graph lifts to a graphing four-cycle at any fixed relative coordinate. Thus the claimed implication from absence of graphing four-cycles to absence of finite-graph four-cycles is justified.

Because labels and priorities are constant on cells, all rankings and scores are constant on cells. Each cell has measure \(1/n\), while \(\mu_t=n_t/n\), so the integral definition gives exactly
\[ S_t=\frac{1}{n_t}\sum_{\text{cells of type }t}s(v). \]

The equivalence with a uniform permutation of strict ranks also holds. The type assignment has probability \(\prod_t n_t!/n!\), and the independent within-type orderings contribute \(\prod_t1/n_t!\). Every complete strict-rank placement therefore has probability \(1/n!\).

All counts are integral by the stated divisibility condition, and positive masses ensure \(n_t\geq1\).

2. Single-item concentration

The overlap identities and bounds are correct:
\[ \sum_{w\neq v}\lambda_{v,w}=k(k-1)=d. \]
Each of the \(k\) bundles containing \(v\) contributes its other \(k-1\) items, with multiplicities retained.

In general, \(\lambda_{v,w}\leq k\), giving
\[ \sum_{w\neq v}\lambda_{v,w}^2\leq kd. \]
Without four-cycles, two distinct items cannot share two bundles, so \(\lambda_{v,w}\leq1\) and the squared sum is at most \(d\).

The score formula is consistent with Borda scoring: an item receives one point plus the number of worse items in each bundle. Hence
\[ Q_r=k+\sum_{w\neq v}\lambda_{v,w}\mathbf1\{\text{rank at }w>r\}, \]
and its stated expectation
\[ b_r=k+d\frac{n-r}{n-1} \]
is correct.

The sampling-without-replacement martingale calculation is also correct. After exposing \(X_i\), the conditional expected value of each remaining indicator changes by
\[ -\frac{X_i-p_i}{N-i}, \]
which yields the displayed increment formula.

There is no denominator problem: \(q\leq d\) and \(N=n-1\geq3d+1\). Since the weights are nonincreasing,
\[ R_i\leq(q-i)w_i\leq(N-i)w_i. \]
Thus the coefficient of \(X_i-p_i\) lies between zero and \(w_i\), and the conditional increment has support in an interval of length at most \(w_i\).

The bounded-variable exponential-moment inequality is stated with the necessary hypotheses. Its tilted-variance justification is valid for both signs of the parameter. Applying it conditionally and iterating gives the claimed bound
\[ \mathbb E[e^{\theta(Q_r-b_r)}]\leq e^{\theta^2B/8}. \]

The extreme ranks \(r=1\) and \(r=n\), where the indicators are deterministic, cause no exception.

3. Type-average concentration and pairwise failures

The rank block and its average are correct. Its first and last ranks are \(na_t+1\) and \(n(a_t+\mu_t)\), so the average is \(nc_t+1/2\). This gives the stated expected type score.

For distinct types in ground-truth order, their midpoint difference is strictly positive, yielding
\[ \Delta_{t,u}=\frac{dn}{n-1}(c_u-c_t)>0. \]

The passage from item concentration to type-average concentration is rigorous. Jensen’s inequality applies pointwise to the average of the centered item scores for every real \(\theta\); independence is unnecessary.

The subsequent Cauchy–Schwarz calculation has the correct constant:
\[ \mathbb E[e^{-\theta(H_t-H_u)}]\leq e^{\theta^2B/2}. \]
On the event \(S_t\leq S_u\), one has \(H_t-H_u\leq-\Delta_{t,u}\). Markov’s inequality therefore gives
\[ \Pr(S_t\leq S_u)\leq \exp\!\left(-\theta\Delta_{t,u}+\frac{\theta^2B}{2}\right). \]
The stated optimizer \(\theta=\Delta_{t,u}/B\) is positive and produces the claimed exponent.

Replacing \(\Delta_{t,u}\) by its lower bound \(d(c_u-c_t)\) weakens the bound in the correct direction. The event includes ties, exactly as required.

4. Weighted midpoint lemma

The lemma is valid, including the case of one dominant type.

For two ordered intervals, the distance between their midpoints is at least half the sum of their lengths. Consequently, every corresponding pair of points satisfies
\[ 0\leq y-x\leq2(c_j-c_i). \]
This establishes the pointwise kernel comparison and hence the claimed integral bound.

When \(p\leq1/2\), the calculations
\[ \sum_i\mu_i^2\leq p,\qquad W=\frac{1-\sum_i\mu_i^2}{2}\geq\frac14 \]
are correct. Symmetry bounds the sum over distinct unordered interval pairs by half the whole-square integral. The Gaussian integral then gives \(a\sqrt{\pi}\), yielding the claimed factor after division by \(W\).

When \(p>1/2\), every distinct pair has at least one interval in the complement \(R\). The integral over \(R\times[0,1]\) covers each pair involving the dominant interval once, using symmetry where necessary, and covers pairs entirely in \(R\) twice. Thus the asserted upper bound is valid regardless of where the dominant interval lies.

The remaining estimates
\[ \int_R\int_0^1e^{-(x-y)^2/(4a^2)}\,dy\,dx \leq2a\sqrt{\pi}\,q,\qquad W\geq pq \]
are correct. Here \(q>0\), because the support contains at least two positive-mass types, so division is legitimate.

5. Final guarantees and constants

Linearity of expectation correctly expresses expected disagreement as the weighted sum of pairwise failure probabilities divided by \(W\). The denominator is positive.

Substituting
\[ a=\frac{\sqrt{2B}}{d} \]
into the midpoint lemma matches the pairwise exponential bound exactly.

For general graphings, \(B=kd\) gives
\[ 1-\mathbb E[\operatorname{Acc}_\mu] \leq4\sqrt{\frac{2\pi}{k-1}} \leq\frac{4\sqrt{3\pi}}{\sqrt{k}}. \]
Without four-cycles, \(B=d\) gives
\[ 1-\mathbb E[\operatorname{Acc}_\mu] \leq4\sqrt{\frac{2\pi}{k(k-1)}} \leq\frac{4\sqrt{3\pi}}{k}. \]
Both final comparisons follow from \(k/(k-1)\leq3/2\) for \(k\geq3\).

The bounds remain valid when their lower bounds on agreement are negative; those cases simply give vacuous guarantees. No additional restriction on masses, support size, or input encoding was introduced.

Repair feedback

No mathematical repairs or additional clarification are required. The established result is an expected-agreement guarantee, rather than a computational complexity classification.

⟨structured verdict parsed — rendered above⟩