To get to coherence, you need a method that accepts incoherence and spits out coherence. In the context of preferences, two datapoints:
You can compute the Hodge-decomposition of a weakly connected directed edge-weighted graph in polynomial time, and the algorithm is AFAIK feasible in practice, but directed edge-directed graphs can’t represent typical incoherent preferences such as the Allais paradox.
Computing the set of acyclic tournaments with the smallest graph-edit distance to a given directed graph seems like it is at least in NP, and the best algorithm I have for it is factorial on the number of nodes.
So it look like computing the coherent version of incoherent preferences is computationally difficult. Don’t know about approximations, or how this applies to Helmholtz decomposition (though vector fields also can’t represent all the known incoherence).
To get to coherence, you need a method that accepts incoherence and spits out coherence. In the context of preferences, two datapoints:
You can compute the Hodge-decomposition of a weakly connected directed edge-weighted graph in polynomial time, and the algorithm is AFAIK feasible in practice, but directed edge-directed graphs can’t represent typical incoherent preferences such as the Allais paradox.
Computing the set of acyclic tournaments with the smallest graph-edit distance to a given directed graph seems like it is at least in NP, and the best algorithm I have for it is factorial on the number of nodes.
So it look like computing the coherent version of incoherent preferences is computationally difficult. Don’t know about approximations, or how this applies to Helmholtz decomposition (though vector fields also can’t represent all the known incoherence).