Let f be a function that takes as input an inconsistent preference i and produces a set C of consistent preferences. Let S be the set of subgraphs of i for which it holds that for every s∈S: s is an acyclic subgraph, s is a subgraph of i, and s is maximal in i for those properties.
S shall contain all s that fulfill the above conditions.
Let PCS be the property that for every s∈S, s is a subgraph of at least one c∈C (every consistent subpreference appears at least once in a consistent version)
Then you have the following impossibilities:
• PCS and f has polynomial runtime. (Proof sketch: finding an s of size k is in NP. Finding all of them is in NP as well.)
• PCS and C has polynomial size. (Proof sketch: You can construct a graph with exponentially many acyclic tournaments as subgraphs).
In the context of making inconsistent preferences consistent, these are fairly strong results.
Not sure about their approximation behavior, but I think this makes becoming a coherent agent very difficult.
• PCS and all c∈C have minimum graph edit distance of i. (Proof sketch: There is a graph for which all acyclic tournaments with the same (minimal) graph-edit distance don't contain a specific subgraph). Graph in picture, the minimal edit distance is 3, the non-preserved consistent subgraph is a2→a4. This extends to arbitrarily big consistent subgraphs (replace all edges with acyclic tournaments with n nodes).