CS Paper Radar

Ordinal Hegselmann-Krause Systems

Martin Hoefer, Tim Koglin, Jakob Lindner, Jannis Schramek

cs.DS cs.GTcs.SI ·submitted 2026-11-18 13:59 UTC · v1
published

Abstract

We study opinion formation in the popular Hegselmann-Krause model when agents replace the traditional averaging update by a median update or more general ordinal aggregation methods. We analyze the convergence properties of synchronous and asynchronous dynamics. For asynchronous dynamics, we show that every HKS with a $1$-Lipschitz ordinal aggregation function converges in worst-case time $\mathcal{O}(n^4)$. For the special case of median aggregation and for the family of $k\textsf{-large}$ aggregation functions, in which agents select the $k$-th largest opinion in their neighborhood, we obtain sharper bounds of $\mathcal{O}(n^3)$. For general ordinal aggregation, some sequence of $\mathcal{O}(n^2)$ updates reaches an equilibrium from every initial state. Nevertheless, other update sequences may cycle, and uniform random activation can require exponentially many updates with overwhelming probability. For synchronous dynamics, we obtain a tight characterization. Ordinal aggregation functions satisfying the $1$-Lipschitz condition are shown to guarantee convergence in linear time. This result applies to many natural examples such as minimum, maximum, median, and $k\textsf{-large}$ functions. When the Lipschitz condition is violated, there exist instances in which synchronous dynamics do not converge at all.

Comment
A preliminary version will appear in the proceedings of WINE 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Scaling Laws for Majority-based Opinion Dynamics in the Presence of Stubborn Agents

cs.MA math.PR ·2026-08-11 ·Luke Meredith, Arpan Mukhopadhyay
similarity 0.64
Abstract

In a multi-agent system, there are often stubborn followers of specific opinions or beliefs. Motivated by this observation, in this paper, we aim to understand how stubborn agents affect the distribution of opinions in a network where both stubborn and non-stubborn agents interact with each other. To do so, we assume that all agents have an opinion in the set $\{0,1\}$ and each non-stubborn agent updates its opinion according to the $2k$\textit{-choices rule}, where the agent samples $2k$ neighbours (including both stubborn and non-stubborn neighbours) uniformly at random and adopts the majority opinion among the sampled group of neighbours and itself. We assume that a proportion of agents, $γ_i$, are stubborn followers of opinion $i\in \{0,1\}$. It is natural to expect that the steady-state distribution of the opinions in the network will be dominated by the opinion with the larger proportion of stubborn followers. We show that while this is true, the time to reach steady-state depends heavily on the values of the parameters $γ_0$ and $γ_1$. When the individual values of these parameters, as well as their difference, are small, it can take an exponentially long time (in the network size) to reach the steady-state. In sharp contrast, when at least one of the parameters $γ_0$ and $γ_1$ is large, the network reaches the steady-state in a time that is only logarithmic in the network size. Hence, there exists a sharp phase transition in the network dynamics based on the proportions of stubborn agents. We also characterise the behaviour of the system when the parameters $γ_0$ and $γ_1$ lie on the boundary of the phase transition. In this boundary region, we show using Stein's method that the dynamics are driven by a diffusion process which takes polynomial time to mix.

0.04

Plurality Consensus for $h$-Majority via First-Repetition Rules

cs.DC cs.DS ·2026-11-11 ·Niccolò D'Archivio, George Giakkoupis, Frédéric Giroire, Emanuele Natale
similarity 0.61
Abstract · 16 pages

In the h-Majority dynamics, each of n agents holds one of k opinions and, in every synchronous round, observes the opinions of h agents chosen independently and uniformly at random and adopts a most frequent one among them, breaking ties uniformly at random. Let M_0 be the initial number of agents holding the most frequent opinion, and Delta_0 its bias, its lead over the second most frequent opinion. We show that, for every sample size h >= 3, if Delta_0 >= L sqrt(M_0 log n) max{1, n/(h^2 M_0)} for a sufficiently large constant L, then h-Majority reaches consensus on the initially most frequent opinion within O((1 + n/(h^2 M_0)) log n) rounds with high probability. This is the time bound proved for the DejaVu dynamics with h samples (arXiv:2604.03648); our bias condition is that of DejaVu when h >= sqrt(n/M_0), and larger by a factor sqrt(n/(h^2 M_0)) otherwise. Our main contribution, the analysis of one round, rests on a comparison principle: among all rules that read the same observations and treat opinions symmetrically, plurality maximizes the difference between the probability of outputting the most frequent opinion and that of outputting any fixed competitor. We apply it to the rule that adopts the first opinion repeated among h-1 observations, and otherwise the h-th observation: its output law is the law of the new opinion of a random agent after one round of DejaVu with h-1 samples. Hence, in expectation, one round of h-Majority widens the gap between the most frequent opinion and each competitor at least as much as that round of DejaVu, whose analysis we use as a black box. Independently and concurrently, d'Amore, Rybicki, Shimizu, Shiraga and Vacus (arXiv:2610.40562) obtained, among other results, the same time bound under the weaker bias condition of DejaVu, with a different analysis of one round and a martingale analysis over many rounds.

0.13

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

cs.DS ·2026-10-11 ·Shahrzad Haddadan, Jie Gao
hot direction similarity 0.59
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.

0.34

Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics

cs.DC cs.DSmath.PR ·2026-10-29 ·Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu, Takeharu Shiraga, Robin Vacus
theory similarity 0.59
Abstract

How does the number of sampled opinions affect the time required to reach consensus in distributed consensus dynamics? We study the synchronous $h$-Majority, in which every node independently samples $h$ nodes uniformly at random with replacement in each round and adopts a most frequent sampled opinion, breaking ties uniformly at random. We show that $h$-Majority achieves the nearly-optimal trade-off between the sample size and the consensus time, among a broad class of consensus dynamics. In particular, we prove the following results. For every sample size $h \ge 3$ and for every initial configuration, we prove that the process reaches consensus with high probability within $$\widetilde{O}\left(1+\min\left\{\frac{1}{\min\{h^2p_{\max},1\}},\frac{\sqrt{n}}{h}\right\}\right)$$ rounds, where $n$ is the number of nodes and $p_{\max}$ is the largest initial fraction of nodes supporting any single opinion. This is the first bound on the consensus time for $h$-Majority that holds for every $h\ge3$ and every initial configuration. When the initially most popular opinion has a sufficiently large lead over every other opinion, we show that all nodes adopt this opinion with high probability within $O(\log n/\min\{h^2p_{\max},1\})$ rounds. We establish a matching lower bound up to polylogarithmic factors for any fixed update rule that treats all opinions symmetrically and that selects either a sampled opinion or the node's current opinion.

0.49

Equilibria and Consensus in Mixed Weighted-Average and Weighted-Median Opinion Dynamics: The Consensus-Promoting Role of Weighted-Average Individuals

eess.SY math.OC ·2026-10-12 ·Junkai Cheng, Wenjun Mei
similarity 0.57
Abstract · 29 pages, 10 figures, including supplementary material

How individuals respond to their neighbors' opinions shapes whether a networked group reaches consensus. This paper analyzes synchronous discrete-time opinion dynamics on a fixed influence network, where individuals use either weighted-average (WA) or weighted-median (WM) opinion-aggregation mechanisms with individual-specific inertia coefficients. We characterize equilibria through graph-theoretic conditions on opinion level sets and WA balance equations, proving that every solution converges to a Lyapunov-stable equilibrium. We define type-dependent cohesive sets, whose WA members assign all their influence weight to the set and WM members assign at least half. The absence of two disjoint such sets gives a necessary and sufficient graph-theoretic criterion for consensus from any initial condition. Otherwise, an open set of initial conditions leads to persistent dissensus. Converting WM individuals to WA cannot create type-dependent cohesive sets and preserves existing guarantees of consensus from any initial condition. If the conversion eliminates every disjoint pair of these sets, the converted system also guarantees consensus from any initial condition. Four numerical studies examine the locations and proportion of weighted-average individuals, as well as the influence weights, while comparing the consensus criterion with finite-horizon simulation outcomes. In the four network ensembles with 100 individuals, the observed frequency of reaching a prescribed consensus tolerance is nondecreasing with WA proportion at each tested simulation horizon. This trend supports the consensus-promoting role of WA individuals, although individual realizations need not follow it.

0.23

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.56
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

The Voter Model with Opinion Graph

cs.GT cs.DC ·2026-10-12 ·Petra Berenbrink, Thorsten Götte, Martin Hoefer, Tim Koglin
similarity 0.56
Abstract · Abstract shortened to comply Arxiv requirements

We study the \emph{voter model with opinion graph}, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a finite set $A$ of $n$ agents. Each agent $u \in A$ has an opinion $x_u \in O$, where we model opinions as vertices in an undirected opinion graph $G = (O,E)$ with $|O|=q$. In each step, an agent $u$ interacts with another agent $v \in A$. In contrast to classical voting, $u$ adopts the opinion $x_v$ if and only if $x_v$ and $x_u$ are neighbors in $G$. The process is stable once all remaining opinions are an independent set in $G$. We analyze two variants of the process: the ordinary EdgeVOG process, which samples a pair of interacting agents uniformly at random from all possible pairs, and the productive EdgeVOG process, which samples only pairs with neighboring opinions in $G$. We show the following: - For every opinion graph and every initial configuration, ordinary EdgeVOG stabilizes within $O(n^2\log n)$ steps in expectation and with high probability. The expectation bound is asymptotically tight. For the productive EdgeVOG process, the expected stabilization time is exactly the initial number of compatible agent pairs, while $O(n^2\log n)$ steps suffice with high probability. - An opinion $i$ with initial support $s_i$ survives with probability at least $p_i:=s_i/(s_i+\sum_{j\in N(i)}s_j)$. Further, let $μ= \sum_{i \in O} p_i$, then we show the probability that less than $(1-δ)μ$ opinions survive is at most $\exp(-δ^2μ/(2(Δ^2+1)))$ for every $0\leqδ\leq1$. -If $G$ has maximum degree $Δ$ and every opinion initially has support at most $\hat{s}$, then no opinion ever acquires more than $\tilde{O}(\min\{n,Δ^6\hat{s}\})$ agents with high probability. This yields near-linear stabilization bounds for productive EdgeVOG for a large class of configurations.

0.21

Tight Lower Bounds for Distributional Paging

cs.DS ·2026-10-29 ·Ali Vakilian
similarity 0.54
Abstract

Distributional paging seeks a polynomial-time eviction rule that competes with the optimal \emph{online} policy $\mathrm{OPT}$ when requests come from a known stochastic source. Two algorithms by Lund, Phillips, and Reingold [FOCS, 1994] are canonical. Their randomized \emph{dominating distribution} algorithm, for Markov sources, evicts a page drawn from a distribution over the cache satisfying pairwise linear inequalities; their deterministic \emph{median} algorithm, for sources with independent inter-arrival times across pages, evicts the cached page with the largest lower median of its conditional next-request time. Their original guarantees of $4$ and $5$ were recently improved to $2$ and $4$ by Pabbaraju and Vakilian [ICALP 2025]. We show that neither improved constant can be reduced in its respective source model. For Markov paging, we give two complementary factor-$2$ lower-bound constructions, each with an explicit polynomial-time dominating selector. A directed-cycle family has ratio $2k/(k+1)$, while a recurrent four-page family with cache size three has ratio $2-4\varepsilon/3$. For the independent inter-arrival model, we show that the median algorithm is not $c$-competitive for any $c<4$. These are separate results for distinct stochastic models. Matching the known upper bounds, they establish tight competitive ratios of $2$ and $4$, respectively, improving on previous lower bounds of $1.5907$ and $1.511$.

0.10