Heuristic Algorithms for the Approximation of Mutual Coherence
Gregor Betz Vera Chekan Tamara Mchedlidze
Mutual coherence is a measure of similarity between two opinions. Although
the notion comes from philosophy, it is essential for a wide range of
technologies, e.g., the Wahl-O-Mat system. In Germany, this system helps voters
to find candidates that are the closest to their political preferences. The
exact computation of mutual coherence is highly time-consuming due to the
iteration over all subsets of an opinion. Moreover, for every subset, an
instance of the SAT model counting problem has to be solved which is known to
be a hard problem in computer science. This work is the first study to
accelerate this computation. We model the distribution of the so-called
confirmation values as a mixture of three Gaussians and present efficient
heuristics to estimate its model parameters. The mutual coherence is then
approximated with the expected value of the distribution. Some of the presented
algorithms are fully polynomial-time, others only require solving a small
number of instances of the SAT model counting problem. The average squared
error of our best algorithm lies below 0.0035 which is insignificant if the
efficiency is taken into account. Furthermore, the accuracy is precise enough
to be used in Wahl-O-Mat-like systems.