  Mechanistic and tractable mathematical models play a key role in
understanding how social influence shapes public opinions. Recently, a
weighted-median mechanism has been proposed as a new micro-foundation of
opinion dynamics and validated via experimental data. Numerical studies also
indicate that this new mechanism recreates some non-trivial real-world features
of opinion evolution. In this paper, we conduct a thorough theoretical analysis
of the weighted-median opinion dynamics. We fully characterize the set of all
equilibria, and we establish the almost-sure finite-time convergence for any
initial condition. Moreover, we prove a necessary and sufficient
graph-theoretic condition for the almost-sure convergence to consensus, as well
as a sufficient graph-theoretic condition for almost-sure persistent dissensus.
It turns out that the weighted-median opinion dynamics, despite its simplicity
in form, exhibit rich dynamical behavior that depends on some delicate network
structures. To complement our sufficient conditions for almost-sure dissensus,
we further prove that, given the influence network, determining whether the
system almost surely achieves persistent dissensus is NP-hard, which reflects
the complexity the network topology contributes to opinion evolution.
