3 impossibility results for achieving vNM consistency with discrete options
Let f be a function that takes as input an inconsistent preference i (any directed graph) and produces a set C of consistent preferences (acyclic tournaments). 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 (preservation of all maximal consistent subpreferences) 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 kis 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).
PCS and all c∈C have the same minimal graph edit distance to 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).
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 quite difficult unless more specific conditions for the inconsistent preferences are met.
Perhaps PCS is too strong a condition to meet, and instead we only want weaker conditions (such as dominating acyclic tournaments to be preserved).
3 impossibility results for achieving vNM consistency with discrete options
Let f be a function that takes as input an inconsistent preference i (any directed graph) and produces a set C of consistent preferences (acyclic tournaments). 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 (preservation of all maximal consistent subpreferences) 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).
PCS and all c∈C have the same minimal graph edit distance to 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).
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 quite difficult unless more specific conditions for the inconsistent preferences are met.
Perhaps PCS is too strong a condition to meet, and instead we only want weaker conditions (such as dominating acyclic tournaments to be preserved).