Ordinal Hegselmann-Krause Systems

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.24449
Primary Topic
Opinion Dynamics and Social Influence
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Ordinal Hegselmann-Krause Systems

Tim Koglin, Martin Hoefer, Jannis Schramek, Jakob Lindner
arXiv (Cornell University)
Opinion Dynamics and Social Influence
preprint

Ordinal Hegselmann-Krause Systems

Tim Koglin, Martin Hoefer, Jannis Schramek, Jakob Lindner
preprint en

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.

arXiv (Cornell University)
Opinion Dynamics and Social Influence
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon