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 -Lipschitz ordinal aggregation function converges in worst-case time . For the special case of median aggregation and for the family of aggregation functions, in which agents select the -th largest opinion in their neighborhood, we obtain sharper bounds of . For general ordinal aggregation, some sequence of 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 -Lipschitz condition are shown to guarantee convergence in linear time. This result applies to many natural examples such as minimum, maximum, median, and functions. When the Lipschitz condition is violated, there exist instances in which synchronous dynamics do not converge at all.