betaFeedback

WorksComputer Science

Ordinal Hegselmann-Krause Systems

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

Paper details

vlnc:W_fryvj24c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare)

View statement
Looking for related papers…