跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24449 · v1

Ordinal Hegselmann-Krause Systems

首次提交 2026-11-18 21:59
版本更新 2026-11-18 21:59
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

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 11-Lipschitz ordinal aggregation function converges in worst-case time O(n4)\mathcal{O}(n^4). For the special case of median aggregation and for the family of k-largek\textsf{-large} aggregation functions, in which agents select the kk-th largest opinion in their neighborhood, we obtain sharper bounds of O(n3)\mathcal{O}(n^3). For general ordinal aggregation, some sequence of O(n2)\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 11-Lipschitz condition are shown to guarantee convergence in linear time. This result applies to many natural examples such as minimum, maximum, median, and k-largek\textsf{-large} functions. When the Lipschitz condition is violated, there exist instances in which synchronous dynamics do not converge at all.

作者备注:A preliminary version will appear in the proceedings of WINE 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-18 21:59 · 最新观测版本

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 11-Lipschitz ordinal aggregation function converges in worst-case time O(n4)\mathcal{O}(n^4). For the special case of median aggregation and for the family of k-largek\textsf{-large} aggregation functions, in which agents select the kk-th largest opinion in their neighborhood, we obtain sharper bounds of O(n3)\mathcal{O}(n^3). For general ordinal aggregation, some sequence of O(n2)\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 11-Lipschitz condition are shown to guarantee convergence in linear time. This result applies to many natural examples such as minimum, maximum, median, and k-largek\textsf{-large} functions. When the Lipschitz condition is violated, there exist instances in which synchronous dynamics do not converge at all.

查看此版本解读 →查看此版本原文 ↗