ective sample size is approximately $n_1\ell_1$, i.e. pairwise comparisons coming from small set size do not contribute without proper normalization. This gap in MSE corroborates bounds of Theorem \[thm:main\]. Normalization constant $C$ is $10^{3}/d^2$.

The Role of the Topology of the Data {#sec:role}
====================================

We study the role of topology of the data that provides a guideline for designing the collection of data when we do have some control, as in recommendation systems, designing surveys, and crowdsourcing. The core optimization problem of interest to the designer of such a system is to achieve the best accuracy while minimizing the number of questions.

The Role of the Graph Laplacian
-------------------------------

Using the same number of samples, comparison graphs with larger spectral gap achieve better accuracy, compared to those with smaller spectral gaps. To illustrate how graph topology effects the accuracy, we reproduce known spectral properties of canonical graphs, and numerically compare the performance of data-driven rank-breaking for several graph topologies. We follow the examples and experimental setup from [@SBB15] for a similar result with pairwise comparisons. Spectral properties of graphs have been a topic of wide interest for decades. We consider a scenario where we fix the size of offerings as $\kappa_j=\kappa=O(1)$ and each agent provides partial ranking with $\ell$ separators, positions of which are chosen uniformly at random. The resulting spectral gap $\alpha$ of different choices of the set $S_j$’s are provided below. The total number edges in the comparisons graph (counting hyper-edges as multiple edges) is defined as $|E|\equiv{\kappa \choose 2}\,n$.

-   Complete graph: when $|E|$ is larger than ${d \choose 2}$, we can design the comparison graph to be a complete graph over $d$ nodes. The weight $A_{ii'}$ on each edge is $n\,\ell/(d(d-1))$, which is the effective number of samples divided by twice the number of edges. Resulting spectral gap is one, 