CS Paper Radar

Social Learning of Ranking: Getting the Top Right despite Local Herding

Shahrzad Haddadan, Jie Gao

cs.DS ·submitted 2026-10-11 20:25 UTC · v1
hot direction

Abstract

In sequential learning, a group of agents sequentially receives a noisy private signal and observes the predictions of prior agents to estimate a hidden ground truth. While extensively studied for binary signals, we formalize and analyze sequential learning when the hidden ground truth is an ordering of $n$ items, and both private signals and inferences involve pairwise comparisons. A key focus in sequential learning is herding, where agents disregard their private signals to follow the crowd. We show that, while local herding in our model may lead agents to make incorrect pairwise inferences, the global hidden order can still be approximated. Specifically, by aggregating all pairwise comparison outputs, the highest-ranked items can be retrieved. We investigate top-$k$ retrieval across three scenarios: (1) passive aggregation, where information is gathered from the social learning process without intervention; (2) strategic selection, where agents choose their pairwise comparisons dynamically; and (3) aggregation with stubborn nodes, where a very small set of stubborn agents, who base their inferences solely on their private signals, join the mechanism. With query complexity as the number of agents needed for a high-probability estimation, we propose top-$k$ retrieval algorithms with query complexities sublinear in $O(n^2)$, the total number of pairs.

Closest papers

Nearest neighbours by meaning across the whole index.

Sorting from Counterexamples

cs.LG cs.CCcs.CGcs.DS+1 ·2026-08-21 ·Noga Alon, Shay Moran, Shlomo Moran
publishedtheory similarity 0.63
Abstract

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

0.37

Non-Bayesian Social Learning with Heterogeneous and Time-Varying Aggregation Rules

cs.SI ·2026-10-09 ·Sammy Oukaci, Pol Rodríguez Farrés, Jesus Cerquides
similarity 0.61
Abstract

People constantly form opinions by combining what they observe with what friends, collegues, and communities tell them. Following this idea, this article generalizes earlier results in Non-Bayesian social learning on strongly connected social networks, where agents repeatedly update their beliefs by combining their own private signals with the beliefs of their neighbors. Previous work assumed that every agent aggregates information in the same way and often does not change in time, assuming agents never change how they reason and listen to others. We show that agents' beliefs still converge almost surely to the true state when agents use heterogeneous and time-varying (non-stochastic) aggregation rules under certain conditions. That is, even when people change their way to aggregate others opinions, the community can still reach the truth as long as information flows among its members. We also provide convergence rate results under this scenario and show that, for some of these functions, it is at least equal to the best convergence rate we have found in the literature. We present the widely used aggregation functions in the Constant Elasticity of Substitution (CES) family as a specific case of our general model, which include rules such as the log-linear, DeGroot, and the harmonic rules, and provide a simple illustrative example to show the capabilities of the model.

0.33

Contagious Misinterpretations: Social Learning with Shared Interpretations

cs.SI ·2026-10-14 ·Pol Rodríguez Farrés, Jesus Cerquides
similarity 0.60
Abstract

When people discuss which of several hypotheses is true, they share not only their beliefs but also their interpretation of each one, that is, the distribution of signals each hypothesis is expected to produce. This interpretation is an opinion about what each hypothesis means and what evidence it predicts, and it is revised only through conversation, not by confronting it with the observed data. Standard non-Bayesian social learning captures only belief-sharing and keeps the likelihoods private. We study what happens when agents share both beliefs and likelihoods under static networks. We show that interpretations converge geometrically to a common reading shaped by the most influential agents. Then, beliefs concentrate, almost surely and at an exponential rate, on the hypothesis that, under this consensus interpretation, best explains the signals privately observed by all agents taken together. As a result, sharing interpretations can lead a population to adopt, unanimously and confidently, a hypothesis it would have rejected if it had shared only beliefs. Whether this helps or hurts when a true hypothesis exists depends on how accurately agents initially read the data they observe. When every agent initially interprets the true hypothesis exactly as the data it would observe, sharing interpretations cannot strictly improve learning and can strictly harm it when agents observe different data distributions. When interpretations are logically coherent and some agents misread their own data, sharing can either rescue the population, leading it to learn the true hypothesis, if an accurate reading dominates the interpretation network, or corrupt it, leading it to a wrong hypothesis, if a misreading one does.

0.23

Learning a Ranking from Human Feedback in Log-Concave Random Utility Models

cs.LG ·2026-10-06 ·Diego Alovisetti, Marco Mussi, Alberto Maria Metelli
theory similarity 0.60
Abstract

We study the problem of recovering the ranking of a fixed set of items according to their unknown numerical utilities. At each interaction with the environment, a learner presents the item set to a human and receives comparative feedback of two types. Under full-ranking feedback, each interaction reveals a noisy ranking of all items, whereas under winner-only feedback, it reveals only the item ranked first. In both settings, we model human feedback using a random utility model with log-concave noise and study the number of observations needed to recover an $ε$-accurate ranking with high probability. This novel criterion tolerates ordering errors only between items whose utilities differ by less than $ε$. For both feedback types, we establish worst-case sample-complexity lower bounds and develop algorithms that match these bounds up to logarithmic factors. Neither algorithm requires knowledge of the noise distribution, while only requiring an upper bound on its variance. Our results show that the ranking problem under winner-only feedback is intrinsically harder by exposing the sample complexity dependence on the minimum winning probability across the item set.

0.34

Online Learning with Ordered Experts (via Two-point Feedback)

cs.LG ·2026-11-05 ·Shiliang Zuo
similarity 0.59
Abstract

We study adversarial online learning with expert recommendations in a totally ordered action space, where the experts' recommendations may change and be reordered arbitrarily. Our focus is two-point feedback: on each round the learner plays two current recommendations, observes both, and pays their average. We study two problems. In the separated monotone problem, the loss is the sum of a hidden nondecreasing component and a hidden nonincreasing component, and a query reveals the two components separately. In the BV problem, the losses are bounded and have bounded variation (BV) along the order, and a query reveals only the loss. In the separated monotone problem, two paid observations achieve \[ O\bigl(\log(|\cF|T)\sqrt{T\log|\cF|}\bigr) \] regret against the best of $|\cF|$ experts, within a logarithmic factor of the classical full-information bound. For the BV problem, we obtain $\wtO(\sqrt T+|\cF|)$ regret. We give an application in dynamic pricing with expert advice, showing that two-option menus matches the full information rate up to $\log$ factors. The main technical ingredient is a marginal-preserving endpoint flow estimator. Two observations reveal a loss increment along the order; random paths supply telescoping identities that turn this local information into unbiased loss estimates for all current recommendations. A reversible pair sampler preserves the learner's intended marginal at both played actions. The estimator's second-moment and stability bounds support online updates for both feedback models.

0.17

The Art of Calling the Winner by Asking Just Enough Questions: Competitive Preference Elicitation with Next-Best Queries

cs.GT ·2026-08-29 ·Nisarg Shah, Ziqi Yu
hot direction similarity 0.59
Abstract

We study active elicitation of agent preferences for collectively choosing among $m$ alternatives using prominent voting rules. We focus on the next-best query model, in which an agent responds to a query by revealing their next favorite alternative, and measure the competitive ratio, which is the worst-case ratio between the number of queries made by the active elicitation algorithm and the minimum number of queries needed to reveal the winning alternative(s) in hindsight. We show that sublinear competitive ratios are achievable for many positional scoring rules, whereas every Condorcet-consistent rule has competitive ratio linear in $m$. For Borda count, we develop two complementary techniques: level-wise pruning, whose analysis extends to general concave scoring rules, and multi-scale score thresholding, which gives an $O(\sqrt m)$ worst-case guarantee for Borda. We also demonstrate strong empirical performance of level-wise pruning on real data.

0.50

Learning from a Mixture of Information Sources

cs.GT econ.TH ·2026-09-27 ·Nicole Immorlica, Brendan Lucier, Yaroslav Mukhin, Clayton Thomas, Ruqing Xu
similarity 0.58
Abstract · Extended abstract to appear in WINE 2026 (The Conference on Web and Internet Economics)

We often learn from multiple sources that convey information in different ways. How informative is it to know the source of a signal, and how is this informativeness shaped by the distribution of sources? We extend the standard (binary-state, binary-signal) Blackwell experiment model by introducing a commonly known distribution over signaling schemes, representing the distribution of information sources. We compare learning under two information models: source-aware, where decision makers observe a signaling scheme and its realization (e.g., raw reviews, search results), and source-blind, where only the signal realization is observed (e.g., aggregate ratings, LLM-generated summaries). We show that a mean-preserving spread in the distribution of signaling schemes translates into Blackwell dominance for source-aware decision makers, implying they are "risk-loving" in information sources. In contrast, it has no impact on source-blind decision makers. When learning from repeated draws of signaling schemes, source-blind decision makers learn more slowly. However, as long as the average signaling scheme is $\varepsilon$ away from being completely uninformative, source-blind learning can match source-aware learning by using at most $O(1/\varepsilon)$ times more data.

0.28

Proportionality in Ranking Compression

cs.GT cs.LGecon.TH ·2026-10-16 ·Daniel Halpern, Xinyu Liu, Evi Micha, Yu Peng Ng, Warut Suksompong
top venuetheory similarity 0.58
Abstract · Appears in the 40th Annual Conference on Neural Information Processing Systems (NeurIPS), 2026

Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compressed into a smaller collection of rankings. This can also be seen as a combination of two fundamental social choice frameworks: ranking aggregation and multiwinner voting. We propose three proportionality notions that capture different types of representation in this setting: positional proportionality, pairwise proportionality, and proportionality for solid coalitions (PSC). On the one hand, we show that positional proportionality and PSC are always satisfiable for any input rankings and target compression size, and a desired output can be found in polynomial time. On the other hand, we prove that pairwise proportionality cannot be satisfied in general, but can nevertheless be attained when the input rankings are single-peaked or single-crossing.

0.33