Resolving von Neumann-Morgenstern Inconsistent Preferences

[niplav]

I consider the problem of resolving preferences that are inconsistent under the von Neumann-Morgenstern axioms into consistent preferences. For preferences over deterministic options, I model inconsistent preferences as directed graphs, and the resolution as selecting acyclic tournaments with the same vertices and minimal graph-edit distance, or Hodge decomposition. For preferences over lotteries, I offer two different methods for modeling inconsistence and one method for resolving them: as edge-weighted weakly connected directed graphs (resolution via Hodge decomposition) and as arbitrary relations over lotteries. None of those two representations prove to be satisfactory. I apply the findings to propose an algorithm for changing a utility function as the underlying set of objects changes.

In economics, decision theory, game theory and parts of artificial intelligence the standard approach to modeling actors is to assume those actors have a fixed utility function they optimise Peterson 2017, ch. 6, Tadelis 2013, ch. 2, Russel & Norvig 2010, ch. 16, following the foundations laid by von Neumann and Morgenstern von Neumann & Morgenstern 1947, ch. 3. This model is quite appealing: It assigns a real-numbered value to each possible outcome, several theorems establish that an agent with a utility function can’t be money-pumped Gustaffson 2022, and it is compatible with taking Pareto improvements Wald 1947.

However, this model has come under criticism as being non-descriptive of human preferences, which can be experimentally shown to violate one or more of the von Neumann-Morgenstern axioms Allais 1953, El Gamal 2013. Furthermore, the AI systems humanity has constructed so far usually have no in-built utility functions and appear inconsistent, as they are often programs selected by gradient descent to perform well on a loss or reward function, and it is doubtful that they have internal goal representations that correspond to the their loss or reward function Hubinger 2019.

This tension between the normative theory of rational agency and the observations I can make about intelligent systems in the real world provides a stark contrast and brings up the question of how one could modify the preferences of intelligent systems to be more consistent.

Motivation

The intuitive case for focusing on resolving inconsistent preferences is that given we find a normative ideal for rationality, real-life systems will probably not perfectly conform to that ideal. So we’ll have an ideal and we have the real-life situation—it is natural to ask how to get from here to there.

I claim the project of finding procedures for modifying preferences to make them consistent is interesting and important for several different reasons:

• Learning the preferences of weaker incoherent systems Dewey 2010: Assuming that one system $S_1$ wants to learn the preferences of a less coherent system $S_2$, $S_1$ might want to “correct” inconsistent preferences learned from $S_2$ to avoid being exploitable via Dutch books. For example, an AI assistant trying to learn and then fulfill the preferences of a gambling-addicted human could notice that the human has a cyclic preference which results in them being predictably losing money at the casino, even though they otherwise care about money.

• Managing ontological crises: If a system defines its preferences using a world model, but this world model changes, those preferences might now be inconsistent. Such situations would benefit from a method for resolving inconsistent preferences de Blanc 2011.

• Creating AI systems with consistent preferences: Assuming that humans will build capable agentic AI systems, we might want to both describe how those agents might achieve coherence, and prescribe ways for them to reach coherence. There are three reasons why we might expect more capable agents to be more coherent:

  • Deliberate design: If e.g. humans create AI systems, they might construct such AI systems to have or develop consistent preferences as to avoid unpredictable behavior.

  • Competitive pressure: An agent could modify their preferences in response to competitive pressures that exploit any incoherencies it displays, for example through other agents that are attempting to money-pump it Gustaffson 2022.

  • Self-modification: Agents might modify their own inconsistent preferences to adhere to the von Neumann-Morgenstern axioms, to avoid wasting resources and making it easier to reason about their own future behavior.

Why vNM?

The von Neumann-Morgenstern axiom has been critized and defended as being the true theory of rationality. I don’t have a very strong position on this, and use vNM because it’s the current “state of the art” in decision theory—it seems plausible to me that vNM will be superseded by some theory that is “better” along the relevant dimensions<sub>57%</​sub>. I hope that in that case the lessons learned from resolving vNM-inconsistent preferences transfer over somewhat.

Structure of the Text

This text starts by explaining the von Neumann-Morgenstern axioms and various theorems relating the axioms to concepts such as Dutch books and Pareto improvements. There is a well-developed literature discussing the relevance of these axioms, and I tentatively conclude that these axioms are worth taking as a standard for rational agency. I also observe that humans do not satisfy those axioms.

I then examine the literature on inconsistent preferences, finding investigations from economics on time-inconsistent preferences and some scattered attempts in the non-academic literature, but no satisfactory investigations into the topic that cover all possible violations of the von Neumann-Morgenstern axioms.

I then proceed to analyse the problem of resolving inconsistent preferences in two cases:

• Deterministic case: I propose the set of all directed graphs as a mathematical structure that can represent inconsistent preferences over non-lottery options. I propose three algorithms for resolving inconsistent preferences of this type, prove two of the algorithms as being functionally equivalent, and analyse the algorithms in terms of computational complexity and five other criteria.

• Lottery case: I propose two different mathematical structures for representing potentially inconsistent preferences over lotteries: Edge-weighted weakly connected directed graphs and arbitrary relations over lotteries. I propose Hodge decomposition as an efficient method for resolving inconsistencies in the first case, but find that edge-weighted weakly connected directed graphs are insufficient for representing common inconsistencies found in reported human preferences. I then note that arbitrary relations over lotteries are able to represent those inconsistencies, but I’m unable to find an algorithm for resolving inconsistencies in that format.

I finally speculate about one application of the methods for resolving incoherence: Incorporating changes in the world model into preferences defined over that world model.

Related Work

As far as our literature review has revealed, the academic literature has no investigation into the specific question I’m attempting to answer.

Modeling Inconsistent Preferences

In the economic literature, preferences are usually more restricted than in the von Neumann-Morgenstern setting: It is usually assumed that there is a set of goods $B$ and a utility function $U:B\times R\to R$ that takes as argument a good and the amount of that good that has been consumed. Consumption can take place at different time steps: Let $c:B\times N$ be a function that returns the consumption of a good at a specific timestep. With a single good $b$ and different quantities $c(b,1),c(b,2),\dots ,c(b,n)$ consumed at $n$ timesteps, the time-discounted utility (discount factor $\delta$) of this consumption is ${\sum }_{i=1}^n{\delta }^{i}U(b,c(b,i\left)\right)$ (which is equivalent to the use of discount rates in reinforcement learning Sutton 2020, ch. 3.

A common form of modeling human preferences that are not exponentially time-discounted in this way is hyperbolic discounting, in which the discounting factor is a hyperbolic function with a parameter $k$ instead of an exponential. Let $U_h(b,i,k)=\frac{1}{1+ki}U(b,c(b,i\left)\right)$ be the hyperbolically discounted utility of consuming $b$ at time step $i$.

This kind of discounting leads to disproportionately preferring small rewards soon over large rewards later, and might lead to preference reversals: For two goods $b$ and $b^{\prime }$, an agent can have the preference $U_h(b,c(b,i\left)\right)>U_h(b^{\prime },c(b,i+c\left)\right)$ at a time step $i$ and a time step $i+c$, but reverse that preference if it lies at another timestep $j$: $U_h(b,c(b,j\left)\right)<U_h(b^{\prime },c(b,j+c\left)\right)$. Such hyperbolic discounting has been observed in humans Myerson & Green 1994 and pigeons Ainslie & Herrnstein 1981. This kind of preference reversal does not occur with exponential discounting.

Hyperbolic preferences can be modeled in a game-theoretic setup, in which subagents in aggregation execute a Pareto-dominated strategy, and via a single agent which follows an unchangeable plan Caillaud & Jullien 2000. Caillaud and Jullien do not attempt to resolve these time-inconsistencies to make them time-consistent. Backus and Zin explore further alternatives to the time-discounted utility setup, though they still work with utility functions that are invariant under positive affine transformation Backus et al. 2004.

Resolving Inconsistent Preferences

In the context of taxonomical data, Sun et al. 2017 investigate the problem of recovering hierarchies from noisy data. They represent inconsistent taxonomies with directed acyclic graphs and consistent hierarchical taxonomies using directed graphs. They find that, when measuring the number of edges being removed, a voting ensemble of several different techniques such as TrueSkill does well on removing as few edges as possible, and usually outperforms removing greedy approximations of the feedback arc set Sun et al. 2017.

Outside of the academic literature, Aird & Shovelain 2020 represent inconsistent preferences as vector fields on a state space (for example states with more/​less security and more/​less wealth), where a vector $v$ at a specific point $p$ in the vector field indicates a preference for a change in the direction of $v$ at $p$.

However, as they note, such a vector field can have inconsistencies in the form of curl. They then discuss the restrictions on the vector field so that it conforms to the von Neumann-Morgenstern axioms, which they conclude to be potential vector fields, and outline how to use Helmholtz decomposition to decompose inconsistent preference vector fields with three dimensions. Their approach bears a strong resemblance to the Hodge decomposition we use with edge-weighted graphs.

Taking a very different approach, Kirchner 2022 investigates how to infer utility functions from non-transitive preferences using a neural network. Kirchner relates inferring such preferences to sorting data in which comparisons sometimes are random, resulting in cycles during comparison. He finds that this approach is able to reconstruct orderings even when 10% of the results of comparisons are noise.

• Value Formation: An Overarching Model (Thane Ruthenis, 2022)

• A logic to deal with inconsistent preferences (Bob Jacobs, 2023)

• Value systematization: how values become coherent (and misaligned) (Richard Ngo, 2023)

• The Value Change Problem (Nora Amann, 2023)

Learning Inconsistent Preferences

The problem of inferring the preferences of irrational agents has been formally posed Mindermann & Armstrong 2018: It is in general impossible learn such preferences, as any action is equally compatible both with a preference for that action and a systematic bias causing the action. Nevertheless Evans et al. 2016 find a framework that is experimentally successful at inferring the preferences of an agent with time-inconsistent hyperbolic discounting and incorrect beliefs using Bayesian inference. Their method for inferring preferences of inconsistent software agents gives similar results to estimates made by humans. Their framework does not cover all possible variants of inconsistent preferences, and makes no statement about how to resolve the time-inconsistencies. Evans et al. also give no theoretical guarantee about the performance of their method.

The von Neumann-Morgenstern Axioms

The von Neumann-Morgenstern (vNM) axioms and the framework of utility functions are widely regarded as the standard method of modeling preferences over world-states.

There is an extensive philosophical debate about the reasonableness of the vNM axioms, and a number of proposed alternatives. We have explicitly decided not to contribute to this debate (though some of our findings on the difficulty of establishing vNM-coherence might be interesting to philosophers), and instead assume that preferences conforming to the vNM axioms are a goal to be achieved.

Let $\Omega$ be a set of $n$ distinct outcomes, and let $\Delta \left(\Omega \right)$ be the set of all probability distributions on $\Omega$, which in von Neumann and Morgenstern call “lotteries” von Neumann & Morgenstern 1947.

For given ${\omega }_1,{\omega }_2\in \Omega$, a lottery in which ${\omega }_1$ has a probability $p_1$ and ${\omega }_2$ has a probability $p_2$ is written as $[p_1:{\omega }_1,p_2:{\omega }_2]$^[1].

Definition 1. Let $l_1,l_2,l_3\in \Delta \left(\Omega \right)$. Let $⪯$ be a relation on all lotteries on $\Omega$, that is $⪯\subseteq \Delta \left(\Omega \right)\times \Delta \left(\Omega \right)$.

If $l_1⪯l_2$ and $l_2⪯l_1$, then we write $l_1\sim l_2$.

Then the relation $⪯$ is a preference relation if and only if it fulfills the four von Neumann-Morgenstern axioms

1. Completeness: For any lotteries $l_1,l_2$, it holds that $l_1⪯l_2$ or $l_2⪯l_1$.

2. Transitivity: For any lotteries $l_1,l_2,l_3$, if $l_1⪯l_2$ and $l_2⪯l_3$, then it must also hold that $l_1⪯l_3$.

3. Continuity: Given $l_1,l_2,l_3$, if it holds that $l_1⪯l_2⪯l_3$, then there must be a probability $p\in [0,1]$ so that $l_2\sim [p:l_1,(1-p):l_3]$.

4. Independence: Given $l_1,l_2,l_3$ it holds that $l_1⪯l_2$ if and only if for any $p\in [0;1]$ it holds that $[p:l_1,(1-p):l_3]⪯[p:l_2,(1-p):l_3]$.

The axiom of completeness implies reflexivity: For all lotteries $l$ it holds that $l⪯l$.

We denote the probability a lottery $l$ assigns to $\omega \in \Omega$ as $p_l\left(\omega \right)$.

Given a preference relation $⪯$, one can create a function $U:\Delta \left(\Omega \right)\to [0;1]$ for which it holds that $U\left(l_1\right)\ge U\left(l_2\right)$ if and only if $l_1⪯l_2$ von Neumann & Morgenstern 1947, ch. 3.6.

Definition 2. This function is called a utility function for the preference relation $⪯$.

Let us as a shorthand write $\omega$ for the lottery that assigns probability 1 to $\omega$, and probability 0 to all other options (we call such a lottery a “deterministic option”).

$U$ has the property that for any lottery $l$ from $\Delta \left(\Omega \right)$, the value $U\left(l\right)$ is simply the expected value of $l$, that is the mean of the utilities weighted by the probabilities:

$$U\left(l\right)=\sum _{\omega \in \Omega }U\left(\omega \right)\cdot p_l\left(\omega \right)$$

Assuming Asymmetry

Definition 3. A relation $\prec \subseteq \Delta \left(\Omega \right)\times \Delta \left(\Omega \right)$ is a strict preference relation if and only if it fulfills the four von Neumann-Morgenstern axioms and also the additional criterion of antisymmetry: $l_1\prec l_2$ and $l_2\prec l_1$ if and only if $l_1=l_2$.

The reason for this assumption is that one of the algorithms we investigate (namely EGEDmin) produces a total order over $\Omega$.

This restriction does not change the fundamental structure of the vNM axioms; specifically, it does not affect the continuity axiom (as even with strict preferences over deterministic options, there can still be non-strict preferences over lotteries).

Inconsistent Preferences over Deterministic Options

A consistent preference over $\Omega$ that fulfills completeness, transitivity and antisymmetry can be represented by an acyclic tournament $G$^[2], with $E\subseteq \Omega \times \Omega$. That is, $G$ itself is complete, transitive and antisymmetric. We call such $G$ a consistent graph (or consistent directed graph, or acyclic tournament).

The set of possible preferences over $\Omega$ (including inconsistent preferences), $P_{\Omega }$, may be represented as the set of all directed graphs with vertices $\Omega$. We will use $P_n$ to denote the set of all directed graphs with $n$ vertices ($n=|\Omega |$), allowing for reflexive edges (that is edges of the form $({\omega }_1,{\omega }_1)$). The set $P_{\Omega }$ can be constructed by enumerating the set of adjacency matrices (elements of $\{0,1{\}}^{n\times n}$) and then, for each adjacency matrix, constructing the corresponding graph. There are $2^{n^2}$ possible preferences in $P_{\Omega }$.

For a directed graph $G\in P_{\Omega }$, one can interpret the presence of an edge $({\omega }_1,{\omega }_2)\in E_G$, with ${\omega }_1,{\omega }_2\in \Omega$, as ”${\omega }_1$ is preferred over ${\omega }_2$”, written ${\omega }_1\succ {\omega }_2$ or ${\omega }_1\to {\omega }_2$.

Let $C_{\Omega }$ be the set of consistent graphs over $\Omega$, with $C_{\Omega }\subset P_{\Omega }$, can be constructed by enumerating the set of permutations of $\Omega$, constructing a strict total order out of each permutation, and taking the transitive closure of that strict total order. There are $n!$ elements in $C_{\Omega }$.

We take the set of inconsistent graphs $I_{\Omega }\subset P_{\Omega }$ to be all graphs that are not consistent, that is $I_{\Omega }=P_{\Omega }\setminus C_{\Omega }$.

Let $W_{\Omega }$ be the set of weakly consistent graphs over $\Omega$, which may be represented as the set of all directed graphs that are equivalent to some weak ordering. It can be constructed by taking all weak orderings on $\Omega$, for each weak ordering $⪯$ creating an edge from ${\omega }_1$ to ${\omega }_2$ if and only if ${\omega }_1⪯{\omega }_2$, and then taking the transitive closure of that graph. The weak orderings are counted by the ordered Bell numbers.

Violating the von Neumann-Morgenstern Axioms

In the deterministic case there are only two vNM axioms that can be violated: completeness and transitivity, since continuity and independence rely on the underlying objects of the preference relation being lotteries.

Directed graphs are well able to represent all violations of these vNM axioms.

Incompleteness.

Incompleteness is distinct from indifference: indifference between ${\omega }_1$ and ${\omega }_2$ exists if both ${\omega }_1⪯{\omega }_2$ and ${\omega }_2⪯{\omega }_1$, incompleteness (or incomparability) is the case if neither ${\omega }_2⪯{\omega }_1$ nor ${\omega }_1⪯{\omega }_2$.

The presence of an incomplete preference in an agent is difficult to operationalize, Gustaffson 2022 treats incomparable options as interchangeable, but setups in which an agent takes a default choice or randomizes when presented with incomparable options are also possible (however, as Gustaffson notes, the randomization offers an adversary the option to (in expectation) perform money-pumps).

In a graph-theoretic setting, incomparability between options ${\omega }_1,{\omega }_2$ is represented by the absence of any edge between ${\omega }_1$ and ${\omega }_2$ in the graph $G$ representing the preference.

Intransitivity.

Intransitivity is quite easy to represent in a graph $G$: If there is an edge ${\omega }_1\to {\omega }_2\in E$ and an edge ${\omega }_2\to {\omega }_3\in E$, but no edge ${\omega }_1\to {\omega }_3\in E$, then one has represented an intransitive preference ${\omega }_1\prec {\omega }_2,{\omega }_2\prec {\omega }_3,{\omega }_1\nprec {\omega }_3$.

Symmetry.

A symmetric (or indifferent) preference between ${\omega }_1,{\omega }_2$ (written as ${\omega }_1\sim {\omega }_2$) can also easily be represented by a directed graph by having the edges ${\omega }_1\to {\omega }_2,{\omega }_2\to {\omega }_1\in E$.

Algorithms for Resolving Inconsistencies

Any method for resolving inconsistent graphs is a function $f:P_{\Omega }\to P\left(C_{\Omega }\right)$ that maps any inconsistent graph to a set of consistent graphs which might contain more than one element since the inconsistent graph might not fully determine its consistent counterpart.

Finding Consistent Graphs with the Smallest Graph-Edit Distance

One potential class of such functions would be ones that minimize a “distance” $d:G_{\Omega }\times C_{\Omega }\to R$ between the (possibly inconsistent) graph and its consistent counterparts.

The function $f_m$ would then return

$$f_d\left(G\right)=\underset{C\in C_{\Omega }}{\text{argmin}}d(C,G)$$

We propose a candidate for $f_d$, which minimizes the edge-graph-edit distance between any $G\in P_{\Omega }$ and the set of consistent versions $C\subseteq C_{\Omega }$ of $G$.

Formally:

$$f_{\text{EGED}}\left(G\right)=\underset{C\in C_{\Omega }}{\text{argmin}}\text{EGED}(C,G)$$

where $\text{EGED}(X,Y)$ is the smallest number of edges that need to be added or removed from $X$ to create $Y$. The addition or removal of vertices is not allowed, since the elements of $\Omega$ can be distinguished from one another.

This function is intuitively appealing: Let $G\in P_{\Omega }$ be a (possibly inconsistent) preference over $\Omega$. Then let ${\omega }_1,{\omega }_2\in \Omega$ be two possible outcomes. the existence of an edge $({\omega }_1,{\omega }_2)\in V_P$ represents that ${\omega }_1$ is preferred over ${\omega }_2$.

Then, given $G$, if one desired a consistent version of $G$, one would want to give up as few as possible of such rankings of two options. One must sometimes give up some of those rankings to achieve von Neumann-Morgenstern consistent preferences (for example to break cycles), but a high number of deletions or additions of rankings is undesirable.

Proposition 1. For two directed graphs on the same set of vertices, $G_1=(\Omega ,E_1),G_2=(\Omega ,E_2)$ the edge-graph-edit distance is the same as the size of the symmetrical difference of the sets of edges, that is $\text{EGED}(G_1,G_2)=|E_1\Delta E_2|$.

Proof.

1. $\text{EGED}(G_1,G_2)\le |E_1\Delta E_2|$: To generate $G_2$ from $G_1$ it is necessary to remove edges from $G_1$ not in $G_2$, and then add edges from $G_2$ not in $G_1$. These comprise the set $\left(E_1\setminus E_2\right)\cup \left(E_2\setminus E_1\right)$. So the graph-edit distance is upper-bounded by the size of the symmetric difference.

2. $\text{EGED}(G_1,G_2)\ge |E_1\Delta E_2|$: Assume that $|E_1\Delta E_2|<\text{EGED}(G_1,G_2)$. Removing $E^{-}=E_1\setminus E_2$ from $G_1$ and adding the edges $E^{+}=E_2\setminus E_1$ results in $G_2$. But then $E^{-}\uplus E^{+}$ is already a graph edit that creates $G_2$ from $G_1$, so $\text{EGED}(G_1,G_2)$ can’t be a minimal edge-graph-edit distance between $G_1$ and $G_2$. ◻

Algorithm 1: A naive algorithm for computing EGEDmin

function EGEDmin(G)
m=∞,R=∅
for L∈ℭ_Ω: # L is a consistent graph with vertices Ω and edges E_L
    d=|EΔE_L|
    if d<m:
        R={L}, m=d
    else if d==m:
        R=R∪{L}
return R

Establishing Consistency Stepwise

An alternative approach to resolve a graph $G$ to a set $C$ of consistent graphs is to proceed by establishing the desired properties stepwise. Our proposed algorithm (which we call “$stepwise$”) is to execute the following steps:

• Remove minimum feedback arc sets. Sun et al. 2017 use a greedy approximation algorithm to find and remove the minimum feedback arc set from a “noisy hierarchy” and create a directed acyclic graph.stepwise takes a similar approach by computing all minimum feedback arc sets for $G$ and then removing them to ensure the graph is acyclic (so that later establishing transitivity does not violate asymmetry). The result is a set of directed acyclic graphs $A$, one for each minimum feedback arc set removed from $G$. For this, one can use an algorithm for finding the minimum feedback arc set from Baharev 2021, called mfas in stepwise.

• Generate all compatible topological sortings. The elements of $A$ are now to be converted into acyclic tournaments. We achieve this by computing all topological sortings for each element $A\in A$ with a recursive algorithm based on Kahn’s algorithm that appends nodes with in-degree 0 in front of a strict order $C$. The result is a set of acyclic tournaments $C$ on $\Omega$.

Algorithm 2: Computing stepwise

function stepwise(G)
if G is consistent
    return {G}
Remove reflexive edges from G
A=∅, R=∅
for fas∈mfas(G):
    A=A∪{G\fas}
for a∈A
    R=R∪topological_sorts(a)
return R

function topological_sorts(G)
if |Ω|==0:
    return G
R=∅
for ω∈Ω so that ω has in-degree 0 in G:
    M=G with ω removed
    T=topological_sorts(M)
    for t∈T:
        R=R∪{t*} # t* is the transitive closure of t
return R

We can now prove that stepwise has the same output as EGEDmin. First we prove that all outputs of stepwise have the same edge-graph-edit distance from $G$.

Lemma 1. For a given $G=(\Omega ,E_G)$, all graphs returned by $stepwise$ have the same edge-graph-edit distance from $G$.

Proof. Let $S=stepwise\left(G\right)$, and $S=(\Omega ,E_S)\in S$. Since all $S$ are transitive, complete and reflexive, all $S$ have the same number of edges, namely the triangular number $|E_S|=\frac{|\Omega |(|\Omega |+1)}{2}$. We also know that $\text{EGED}(G,S)=|E_G\Delta E_S|$, and $E_G\Delta E_S=E_G\setminus E_S\cup E_S\setminus E_G$ (the edges we remove from $E_G$ and the edges we add to $E_S$). The edges removed from $E_G$ are the minimal feedback arc sets, so they all have the same size $m=|E_G\setminus E_S|$. It now suffices to show that $i=E_S\setminus E_G$, the size of the edges added, is constant. It holds that $|E_G|-m+i=|E_S|$, and then $i=|E_S|-|E_G|+m$, which must be constant. So $\text{EGED}(S,G)=m+i$ is also constant for a given $G,S\in S$. ◻

We then show that the edges removed by EGEDmin are always a minimum feedback arc set.

Lemma 2. Given a directed graph $G$, let $T=(\Omega ,E_T)\in EGEDmin\left(G\right)$. Let $E_T^{-}=E\setminus E_T$ (the edges removed from $G$ to achieve $T$) and $E_T^{+}=E_T\setminus E$ (the edges added to $G$ to create $T$). Then $E_T^{-}$ is a minimum feedback arc set of $G$.

Proof.$E_T^{-}$ is a feedback arc set: Assume for contradiction that $E_T^{-}$ was not a feedback arc set. Then $G$ would need to contain a cycle of directed edges $E_c={\omega }_1\to {\omega }_2\to \cdots \to {\omega }_{k-1}\to {\omega }_k\to {\omega }_1$ so that the cycle was still present after removing $E_T^{-}$, that is $E_c\subseteq E\setminus E_T^{-}$. We know that then $E_T=\left(E\setminus E_T^{-}\right)\cup E_T^{+}$, but adding edges can’t remove a subset, so $E_c\subseteq E\setminus E_T^{-}\Rightarrow E_c\subseteq \left(E\setminus E_T^{-}\right)\cup E_T^{+}$.

But then $T$ can’t be transitive, asymmetric and complete: If it was transitive and complete, then there would need to be an edge ${\omega }_1\to {\omega }_3$ (created through ${\omega }_1\to {\omega }_2\to {\omega }_3$), an edge ${\omega }_1\to {\omega }_4$ (created through ${\omega }_1\to {\omega }_3\to {\omega }_4$), and so on. Then $E_T$ would also contain the edge ${\omega }_1\to {\omega }_{k-1}$, and thereby also the edge ${\omega }_k\to {\omega }_{k-1}$ (through the transitivity of ${\omega }_k\to {\omega }_1\to {\omega }_{k-1}$). But since both ${\omega }_k\to {\omega }_{k-1}\in E_T$ and ${\omega }_{k-1}\to {\omega }_k\in E_T$, it can’t be asymmetric.

$E_T^{-}$ is minimal: Assume $E_T^{-}$ was a feedback arc set, but not minimal. Then there would need to be another feedback arc set $E_T^{{-}^{\prime }}$ so that $|E_T^{{-}^{\prime }}|<|E_T^{-}|$. Then one can create $T^{\prime }=(\Omega ,E_T^{\prime })$ from $G$ by removing $E_T^{{-}^{\prime }}$ from $E$ and then completing the resulting directed acyclic graph to a consistent graph.

We know that $|E_T|=|E_T^{\prime }|=\frac{|\Omega |(|\Omega |+1)}{2}$, since both $T$ and $T^{\prime }$ are acyclic tournaments.

Then it is the case that $\text{EGED}(G,T)>\text{EGED}(G,T^{\prime })$:

$$\begin{array}{cc}& \text{EGED}(G,T)>\text{EGED}(G,T^{\prime })\\ & \iff |E\Delta E_T|>|E\Delta E_T^{\prime }|\\ & \iff |E_T^{-}\uplus E_T^{+}|>|E_T^{{-}^{\prime }}\uplus E_T^{{+}^{\prime }}|\\ & \iff |E_T^{-}|+|E_T|-(|E|-|E_T^{-}|)>|E_T^{{-}^{\prime }}|+|E_T^{\prime }|-(|E|-|E_T^{{-}^{\prime }}|)\\ & \iff |E_T^{-}|-|E|+|E_T^{-}|>|E_T^{{-}^{\prime }}|-|E|+|E_T^{{-}^{\prime }}|\\ & \iff 2\cdot |E_T^{-}|>2\cdot |E_T^{{-}^{\prime }}|\end{array}$$

So $E_T^{-}$ must be minimal, since otherwise it is not a set of edges removed by EGEDmin. ◻

Using the fact that $E_T^{-}$ is a minimum feedback arc set, and that all outputs of stepwise have the same edge-edit distance from the input, we can prove that all outputs of stepwise are contained in EGEDmin.

Lemma 3. $\forall G\in P:stepwise\left(G\right)\subseteq EGEDmin\left(G\right)$.

Proof. Let $S=(\Omega ,E_S)\in stepwise\left(G\right)$ for any $G$, and let $T=(\Omega ,E_T)\in EGEDmin\left(G\right)$. Let $E_S^{-}=E\setminus E_S$ be the minimum feedback arc set we remove from $S$ to create $G$, and $E_S^{+}=E_S\setminus E$ the edges we add to make $G$ complete. We similarly define $E_T^{-}=E\setminus E_T$ and $E_T^{+}=E_T\setminus E_T$.

We can now show that $\text{EGED}(S,G)\le \text{EGED}(T,G)$: Assume that $\text{EGED}(S,G)>\text{EGED}(T,G)$. By Lemma 2 $E_T^{-}$ is a minimum feedback arc set, and so $|E_T^{-}|=|E_S^{-}|$. Furthermore, $|E_S|=|E_T|$, since they are both acyclic tournaments on $\Omega$.

Then

$$\begin{array}{cc}& \text{EGED}(G,S)=|E\Delta E_S|\\ & =|\left(E\setminus E_S^{-}\right)\uplus E_S^{+}|\\ & =(|E|-|E_S^{-}|)+|E_S^{+}|\\ & =(|E|-|E_S^{-}|)+|E_S|-(|E|-|E_S^{-}|)\\ & =(|E|-|E_T^{-}|)+|E_T|-(|E|-|E_T^{-}|)\\ & =(|E|-|E_T^{-}|)+|E_T^{+}|\\ & =|\left(E\setminus E_T^{-}\right)\uplus E_T^{+}|\\ & =|E\Delta E_T|=\text{EGED}(G,T)\end{array}$$

So it can’t be the case that $\text{EGED}(S,G)>\text{EGED}(T,G)$.

We can also show that $\text{EGED}(S,G)\ge \text{EGED}(T,G)$: Assume that $\text{EGED}(S,G)<\text{EGED}(T,G)$. Since both $S,T\in C_{\Omega }$, this contradicts the assumption that the output of EGEDmin has minimal distance. ◻

We now show that all outputs of EGEDmin are also outputs of stepwise.

Lemma 4. $\forall G\in P:EGEDmin\left(G\right)\subseteq stepwise\left(G\right)$.

Proof. Assume there exists a $G\in P_{\Omega }$ so that there exists a $T=(\Omega ,E_T)\in EGEDmin\left(G\right)$ so that $T\notin stepwise\left(G\right)$.

Then, by Lemma 2, $E_T^{-}=E\setminus E_T$ is a minimum feedback arc set. Therefore, removing $E_T^{-}$ from $E$ results in a directed acyclic graph $G_A$ which is an element of the intermediate set $A$ of directed acyclic graphs in stepwise.

Let $E_T^{+}=E_T\setminus E$. Assume $E_T^{+}$ was not a set of edges added to $G_A$ in a topological sort.

Then let $\omega \in \Omega$ be the node in $T$ that has no incoming edges.$\omega$ must also have had no incoming edges in $G_A$, since we only add edges to $G_A$ to achieve $T$, and therefore has in-degree 0 in $G_A$, which means that $\omega$ must have been added first to some topological sort in T by topological_sorts.

One can now create $T^{\prime }$ and $G_A^{\prime }$ by removing $\omega$ and all edges from $\omega$ from $T$ and $G_A$. Let the node in $T^{\prime }$ with no incoming edges be called ${\omega }^{\prime }$. Then in $G_A$ the node ${\omega }^{\prime }$ either had no incoming edges or one incoming edge from $\omega$, since one can create $T^{\prime }$ from $G_A$ by adding $E_T^{+}$ and then (potentially) removing the edge $\omega \to {\omega }^{\prime }$. So in the graph $G_A^{\prime }$ with $\omega$ and all its outgoing edges removed from $G_A$, the node ${\omega }^{\prime }$ has in-degree zero, and is therefore also selected as the first element in some topological sort of $G_A^{\prime }$, to which $\omega$ is prepended after recursion. In the base case of a $T^{\star }$ with one element ${\omega }^{\star }$, this element ${\omega }^{\star }$ is the only element of $G_A^{\star }$ and also the only element of the topological sort of $G_A^{\star }$.

Therefore, by induction, given an acyclic tournament $T$ and a set of edges $E_T^{+}=E_T\setminus E$, this set $E_T^{+}$ must be the edges added by some topological sort of $G_A=(\Omega ,E\setminus E_T^{-})$. ◻

This concludes the proof that both algorithms always have the same output.

Theorem 5. $\forall G\in P:stepwise\left(G\right)=EGEDmin\left(G\right)$.

Proof. By Lemma 3 it holds that $stepwise\left(G\right)\subseteq EGEDmin\left(G\right)$ and by Lemma 4 it holds that $stepwise\left(G\right)\supseteq EGEDmin\left(G\right)$, so the sets must be equal. ◻

Applying HodgeRank

Another option to resolve inconsistent preferences over deterministic options into consistent preferences is to apply the HodgeRank algorithm by Jiang et al. to an unweighted graph $G$ Jiang et al. 2009.

HodgeRank is described in further detail in this section.

To apply HodgeRank to unweighted graphs one simply sets both weights of each edge to 1 (for $e\in E$ it is then the case that $w\left(e\right)=1$, $l\left(e\right)=1$).

Then, for a directed graph $G$, we can define an algorithm HodgeResolve that applies HodgeRank to $G$, and then converts the potential function $p$ on $\Omega$ into an acyclic tournament. Here ${\omega }_1\to {\omega }_2$ if and only if $p_{{\omega }_1}>p_{{\omega }_2}$.

One issue with HodgeRank is that the potentials of two options are sometimes equal to each other, which violates the criterion of asymmetry. There are two ways of dealing with this symmetry:

1. Keep the symmetric edges and accept that the output is a weak ordering, and modify the criteria to be applicable.

2. Resolve ties in the ordering by returning all topological sorts as a result. This has the disadvantage of potentially returning a set of results that is factorial in the size of $\Omega$.

We decide to take the first option, to preserve the polynomial runtime of HodgeRank.

function HodgeResolve(G)
    for all e∈E:
        w(e)=1, l(e)=1
    Gh=(Ω, E, w, l)
    p=HodgeRank(Gh) # pω is the potential that HodgeRank assigns to ω
    Er=∅
    for ω1, ω2∈Ω×Ω:
        if pω1≥pω2:
            Er=Er ∪ {(ω1, ω2)}
    Gr=(Ω, Er)
    return Gr

Criteria

Given the algorithms outlined above, one might want to compare them according to different criteria, similar to the method of evaluating voting methods in social choice theory by some criteria Austen-Smith & Banks 2000, ch. 2, such as the Condorcet criterion or manipulability. For this purpose, we examine the algorithms with regards to the computational complexity, size of output, and two additional criteria.

Surjectivity and Identity

A fairly intuitive criterion is that for a given method of resolution $f$, and for every $C\in C_{\Omega }$, there should be a $G\in P_{\Omega }$ so that $C\in f\left(G\right)$ (Surjectivity). This condition is implied by the stronger condition of $f$ being the identity function for already consistent graphs: $\forall C\in C_{\Omega }:f\left(C\right)=\left\{C\right\}$ (Identity).

Minimizing Graph-Edit Distance

EGEDmin fulfills both conditions: $C$ trivially has the smallest graph-edit distance to itself (namely zero), and is unique in that regard.

Applying HodgeRank

Jiang et al. 2011 state that for complete graphs, computing the potential function of a graph $G$ via HodgeRank on the nodes is equivalent to minimizing the squared distance between the edge-weights of $G$ and the edge-weights induced by the potential function. If $G$ already is consistent, the resulting potential function simply re-creates $G$, since their distance is 0. So HodgeResolve maps every consistent graph to itself, and therefore fulfills Identity and therefore also Surjectivity.

Polynomial Time Complexity

Ideally, a method for resolving inconsistent graphs into consistent graphs would be efficiently computable.

Minimizing Graph-Edit Distance

However, the method that attempts to find consistent graphs by minimizing edge-graph-edit distance fails this criterion.

Finding all acyclic tournaments with the smallest edit-distance to a given directed graph is NP-hard. This can be shown by a reduction to Slater’s problem. Slater’s problem is the problem of, given any tournament $T$, finding a linear order $T_L$ (an acyclic tournament, also called a Slater order) that has the smallest distance to $T$, where the distance between two tournaments $T_1,T_2$ is the number of edges that have to be flipped in $T_1$ to create $T_2$. Slater’s problem (and a number of related problems, such as finding all acyclic tournaments with the smallest distance to a given tournament) is known to be NP-hard Hudry 2010.

Theorem 6. Finding the set of acyclic tournaments with smallest edge-graph-edit distance to a given graph $G$ is NP-hard.

Proof. Reduction from finding all Slater orders with the smallest distance to a given tournament $T$.

Assume we know an algorithm A to compute $f_{\text{EGED}}\left(G\right)$ efficiently, that is, to compute the set of all acyclic tournaments with the minimal graph-edit distance to a given directed graph $G$ in polynomial time.

Then one could solve Slater’s problem in polynomial time: For any given tournament $T$, A would compute a set $C_T$ of acyclic tournaments which have the same minimal graph-edit distance $2k$ to $T$, the distance is divisible by two because by editing a tournament $T$ into a tournament $T^{\prime }$. Edges can only be flipped, which engenders two edge operations (removing an edge and then adding a new one). Then that set would also be the set of Slater orders of $T$ (with distance $k$), a solution to ($P_3$) from Hudry 2010, which is known to be NP-hard. ◻

Similarly, finding only one element from $f_{\text{EGED}}\left(G\right)$ is also NP-hard, by reducing it to $P_2$ (“PROBLEM $P_2$. Given a tournament $T$, compute a Slater order $O^{\ast }\left(T\right)$ of $T$”) Hudry 2010.

Applying HodgeRank

Jiang et al. 2011 state that computing the potential function of a graph $G$ is equivalent to solving a $n\times n$ least-squares problem ($n=|\Omega |$), which requires $O\left(n^3\right)$ time.HodgeResolve executes HodgeRank and then iterates through all possible edges of $G$, which takes at most $O\left(n^2\right)$ time, so the time complexity of HodgeResolve is also $O\left(n^3\right)$.

Uniqueness

It would be desirable if one could guarantee that the function $f$ that resolves inconsistent graphs returns a single consistent graph for each inconsistent graph, that is $\forall G\in P_{\Omega }:|f\left(G\right)|=1$.

Minimizing Graph-Edit Distance

EGEDmin does not fulfill this criterion.

Theorem 7. For a graph $G_e$ with no edges and $n$ vertices $\Omega$, every acyclic tournament with the same set of vertices has the same graph-edit distance to $G_e$. Therefore, $|EGEDmin\left(G_e\right)|=n!$, which is not unique.

Proof. Let $T$ be any acyclic tournament with vertices $\Omega$. Then $T$ has $(\frac{n}{2})$ edges. Since $G_e$ has no edges, one can edit $G_e$ to be $T$ simply by adding all edges of $T$ to $G_e$. This is sufficient and necessary for turning $G_e$ into $T$. Since this holds for any tournament $T$, the graph-edit distance from $G_e$ to any acyclic tournament is the same, namely $(\frac{n}{2})$. So $|EGEDmin\left(G_e\right)|=|C_{\Omega }|=n!$. ◻

Applying HodgeRank

If one allows for the output of HodgeResolve to be a weak ordering, then HodgeResolve has a unique output, since assigning each vertex a real-valued potential $p:\Omega \to R$ and then ordering vertices by that potential creates a weak ordering $W$.

However, if one demands that the output of HodgeResolve be a total order then the output is dependent on the method of achieving that total order. If one generates the total orders by generating all acyclic tournaments with vertices $\Omega$ that are subgraphs of $W$, the output is no longer unique: In the worst case $G=(\Omega ,\varnothing )$, which results in HodgeRank assigning a potential of 0 to every node, and HodgeResolve putting every vertex in the same equivalence class in the weak ordering. As a graph this is the complete directed graph on $\Omega$, which contains all acyclic tournaments on $\Omega$ as subgraphs. Then there are $|\Omega |!$ acyclic tournaments generated from this weak ordering, since all acyclic tournaments are equally compatible with the weak ordering.

Further Considerations

Violating Uniqueness appears to have consequences for decision-making: If we want to use the output of $f$ for prioritising which actions to take to achieve high-ranking options, having more than one result leaves it unclear which options to prioritize (since there will be two ${\omega }_1,{\omega }_2\in \Omega$ that are ranked differently by different elements of the set of results).

However, results from two different fields apply to this case.

• Social Choice Theory: Since all elements of $C_G=f\left(G\right)$ are complete, transitive, and asymmetric, one can apply the large toolbox of methods and results from social choice theory to elements from $C_G$ by treating them as individual preferences in a preference profile by applying a social welfare function in sense of Arrow to it Gaertner 2009, ch.2. Some impossibility results such as Arrow’s impossibility theorem still apply, but at least results about tactical voting (such as the Gibbard-Satterthwaite theorem) are irrelevant in this case, since the inconsistent preference does not “control” outputs of $f$, and there are no reasons for manipulation.

• Moral Uncertainty: MacAskill et al. 2020, ch. 2 outline how to make decisions given multiple ethical theories and credences on those ethical theories, using the so-called Maximum Expected Choiceworthiness rule. In the case of ordinal preferences, they use the Borda count for establishing cardinal values for options.

Resolution to Polynomially Many Preferences

If uniqueness can’t be fulfilled (perhaps because the given graph $G$ is under-determined), a weaker criterion is that the number of consistent graphs corresponding to $G$ is polynomial in the size of $\Omega$ ($\forall G\in P_{\Omega }:|f\left(G\right)|\le p\left(|\Omega |\right)$, where $p\left(n\right)$ is some polynomial in $n$).

Minimizing Graph-Edit Distance

However, as proven in Theorem 7{reference-type=”ref” reference=”omgedworstcase”} above, this criterion is not fulfilled for EGEDmin, instead in the worst case the number is factorial in the size of $\Omega$.

We decided to also investigate the number of results for EGEDmin for small graphs. For this purpose, we generated all directed graphs with five nodes or less and computed $EGEDmin\left(G\right)$.

Definition 4. Let $G$ be any directed graph. Then the confusion of $G$ is the number of acyclic tournaments with the smallest edge-graph-edit distance to $G$, that is the confusion $c:P\to N^{+}$ of $G$ is $c\left(G\right)=|EGEDmin\left(G\right)|$. The set of graphs with $n$ vertices and confusion $c$ shall be denoted $G_{n,c}$.

The term “confusion” was chosen to emphasize that graphs with a lower such number have fewer consistent versions. An acyclic tournament has minimal confusion (namely 1, where the output of EGEDmin is simply itself). $G_e$ from Theorem 7 has maximal confusion, namely $n!$.

A natural question to ask is whether, with bigger graphs, the average confusion converges to a certain value or diverges, or shows no clear behavior. We generated all directed graphs with up to 5 vertices and computed their confusion.

$|G_{n,1}|$ is the number of all graphs with $n$ vertices and confusion 1, and $|G_{n,1}|/n!$ is the same number but up to isomorphism of the graphs.$|G_{n,n!}|$ is the number of graphs with $n$ vertices and maximal confusion.

For some given set of directed graphs $P_n$, not all numbers between $1$ and $n!$ can be confusions. There are, for example, no graphs of size 3 with confusion 4 (or 5).

$n$	Samples	Average confusion	$|G_{n,1}|$	$|G_{n,1}|/n!$	$|G_{n,n!}|$
0	1	1	100% (1)	1	$2^0$
1	2	1	100% (2)	2	$2^1$
2	16	1.5	50% (8)	4	$2^3$
3	512	2.625	28.125% (144)	24	$2^6$
4	65536	$\approx$ 4.91	$\approx$ 16.4% (10752)	448	$2^{10}$
5	33554432	$\approx$ 9.43	$\approx$ 9.853% (3306240)	27552	$2^{15}$
6	90927	$\approx$ 18.138	$\approx$ 6.225% (5660)	?[3]	?
7	1580	$\approx$ 36.412	$\approx$ 3.608% (57)	?	?

Interestingly, neither $|G_{n,1}|$ nor $|G_{n,1}|/n!$ are known integer sequences: a search on the OEIS and via SuperSeeker Sloane 2003 yield no matching results.

Conjecture 1. The average confusion of all directed graphs with size $n$ diverges to infinity:

$$\underset{n\to \infty }{lim}\frac{1}{2^{n^2}}\sum _{i=1}^{n!}|G_{n,i}|\cdot i=\infty$$

We attempted to prove this conjecture, but were unable to do so.

Proposition 2.$|G_{n,1}|$ is always divisible by $2^n$.

Proof. This is an artifact of including graphs with reflexive edges in the set of graphs tested. Let $G$ be a graph with confusion $k$ and no reflexive edges.

Let now $G^{\circ }$ be the set of all graphs that are variants of $G$ with reflexive edges added. This set include $G$ itself, and $G$ with all reflexive edges, as well as each version of $G$ with only one reflexive edge. Every element in $G^{\circ }$ also has confusion $k$: all reflexive edges must be removed to create a consistent preference, yielding $G$, and there are $k$ unique acyclic tournaments that has the smallest edge-graph-edit distance to $G$.

Then it is the case $|G^{\circ }|=2^n$: for each node, the presence of a reflexive edge on that node can be described by one bit of information, and since there are $n$ nodes, the size of $|G^{\circ }|$ is the same as the length of an $n$ bit bitstring. ◻

Dividing $G_{n,1}$ by both $n!$ and $2^n$ yields the sequence $1,1,1,3,28,861$, which also doesn’t occur in the OEIS, and also can’t be found using SuperSeeker.

Applying HodgeRank

As seen in the case of Uniqueness, this depends on whether one demands the output of HodgeResolve to be a total order: If a weak ordering is allowed, the output of HodgeResolve is always a single graph, so the output size is polynomial, but if we demand a total order as an output the output size can be factorial in the number of nodes.

Preservation of Consistent Subgraphs

Definition 5. For a given $G=(\Omega ,E_P)$, with $G\in P_{\Omega }$, a subgraph $S_G=(\Xi ,E)$ of $G$ (with $\Xi \subseteq \Omega$, and the set of edges $E$ of $S_G$ being a subset of $E_P$) is an inclusion-maximal consistent subgraph of $G$ if and only if:

• $S_G$ is a consistent graph (equivalently an acyclic tournament)^[4].

• $S_G$ inherits all available edges from $G$, that is if there are two ${\xi }_1,{\xi }_2\in \Xi$ and $({\xi }_1,{\xi }_2)\in E_P$ then $({\xi }_1,{\xi }_2)\in E$ as well.

• $S_G$ is inclusion-maximal, that is, there exists no $\omega \in \Omega \setminus \Xi$ so that adding $\omega$ and its edges adjacent to all $\xi \in \Xi$ to $S_G$ is still a consistent graph.

Definition 6. Let $S_G$ be the set of all inclusion-maximal consistent subgraphs of $G$ and let $f:P\to P\left(C\right)$ be a function that turns any $G$ into a set $C_G=f\left(G\right)$ of consistent graphs. Then $f$ fulfills Preservation of Consistent Subgraphs if and only if every element of $S_G$ is a subgraph of at least one $C_G$, that is

$$\forall S\in S_G:\exists C\in C_G:V_S\subseteq V_C\wedge E_S\subseteq E_C$$

This criterion is quite strong, as we will show. Its intuitive appeal can be explained as follows: Assume one has overall inconsistent preferences, but there is some subset of objects one has consistent preferences over, e.g. an agent has consistent preferences over all fruit and consistent preferences over dairy products, but inconsistent preferences over food in general. Then a method for resolving those inconsistent preferences into consistent ones should “preserve” those consistent preferences over subsets of options a non-zero amount — after becoming consistent the agent still has the same preferences over fruit and dairy product as before.

Furthermore, one can show that there are graphs with an exponential number of inclusion-maximal consistent subgraphs in the number of nodes.

Lemma 8. Let $G\in P_n$ be an arbitrary directed graph with $n$ nodes, and let $S_G$ be the set of inclusion-maximal consistent subgraphs of $G$. Then there exists no polynomial $p$ so that $\forall G\in P_n:|S_G|\le p\left(n\right)$.

Proof. Moon & Moser 1965 describe how to construct an undirected graph $G_n=(V_G,E_G)$ with $n$ vertices and $3^{\frac{n}{3}}$ inclusion-maximal cliques. Then one can construct a directed graph $P_n=(V_P,E_P)$ with $3^{\frac{n}{3}}\approx {1.4422}^n$ inclusion-maximal consistent subgraphs from $G_n$, which grows faster than any polynomial. First, $P_n$ receives the same vertices as $G_n$. Then, every $v\in V$ is assigned a unique number $j\left(v\right):V\to N$, and for each $\{u,v\}\in E_G$, the set of edges $E_P$ contains $(u,v)$ if and only if $j\left(u\right)>j\left(v\right)$, and $(v,u)$ if and only if $j\left(v\right)>j\left(u\right)$. Now, if a subgraph $S_G$ of $G_n$ with vertices $V_S$ is a maximal clique, then a subgraph $S_P$ of $P_n$ with vertices $V_S$ is an inclusion-maximal consistent subgraph in $P_n$:

1. $S_P$ is complete, because for every $\{u,v\}$ in $S_G$, either $(u,v)$ or $(v,u)$ exists in $S_P$.

2. $S_P$ is transitive. For any three vertices $\{u,v,w\}$ in $S_G$, $S_G$ contains the edges $\left\{\right\{u,v\},\{v,w\},\{u,w\left\}\right\}$ (since it is a clique). Then, without loss of generality, assume that $j\left(u\right)>j\left(v\right)>j\left(w\right)$. Then $(u,w)\in E_P$. Therefore $S_P$ contains the edges $\left\{\right(u,v),(v,w),(u,w\left)\right\}$.

3. $S_P$ is asymmetric, because for any edge $\{u,v\}$ in $S_G$ it is the case that $j\left(u\right)>j\left(v\right)$ and $j\left(v\right)>j\left(u\right)$ can’t be true at the same time (since $j$ assigns each vertex a unique natural number). So $S_P$ can only contain either $(u,v)$ or $(v,u)$.

4. $S_P$ is inclusion-maximal. If $S_P$ were not inclusion-maximal, there’d exist a vertex $u$ so that every vertex $v$ of $S_P$ had an edge with $u$. But since the procedure of constructing $P_n$ above did not add any edges, that would mean that $S_G$ was not a maximal clique.

◻

Minimizing Graph-Edit Distance

EGEDmin violates this criterion, which can be easily demonstrated:

Example 1.

Counterexample

Counterexample resolved versions

$G_c$ above is resolved into two acyclic tournaments, none of which contain the edge $d\to c$.

The graph $G_c$ above contains a subgraph $S_{cd}=\left(\right\{c,d\},\{(c,d)\left\}\right)$ that is also an inclusion-maximal acyclic tournament in $G_c$. The two acyclic tournaments with the lowest graph-edit distance (namely 3: reversing the edge $d\to c$ (2 operations) and adding an edge between $a$ and $b$) to $G_c$ are shown in the resolved graph. Note that none of them contain $S_{cd}$ as a subgraph.

This counter-example can be generalized so that inclusion-maximal consistent subgraphs with an arbitrary number of nodes $n$ get reversed: Each edge ${\omega }_1\to {\omega }_2$ of $G_c$ gets replaced by an acyclic tournament $T_i=({\Xi }_i,E_i)$ with $n-2$ vertices, so that there is an edge from ${\omega }_1$ to every ${\xi }_i\in {\Xi }_i$ and an edge from every ${\xi }_i\in {\Xi }_i$ to ${\omega }_2$. The graph on the left has confusion 40, and the subgraph emphasized in red is preserved in none of the outputs of EGEDmin.

We also investigated the number of inclusion-maximal consistent subgraphs preserved by EGEDmin. We again did this by analyzing the outputs of EGEDmin for all graphs with five nodes or less, and some graphs with six or seven nodes.

Definition 7. Let $\text{IMCS}:P_n\to P_{\mathrm{1..}n}$ be a function that returns the inclusion-maximal consistent subgraphs for a given graph.

Given a directed graph $G$, let $S$ be the set of inclusion-maximal consistent subgraphs of $G$. One can now ask: For a given inclusion-maximal consistent subgraph, how often did that subgraph occur in the set of outputs $EGEDmin\left(G\right)$?

Definition 8. Let $\text{RSP}(S,G)$ (with $S\in S$) be the ratio of subgraph preservation:

$${\text{RSP}}_{EGEDmin}(S,G)=\frac{|\{R\in EGEDmin(G\left)|S\text{subgraph of}R\right\}|}{|EGEDmin\left(G\right)|}$$

(No relation to responsible scaling policies.)

As we saw above, there are graphs with inclusion-maximal consistent subgraphs $S$ so that $\text{RSP}\left(S\right)=0$.

One can then use $\text{RSP}$ to define a metric that tells us, for a given graph, how often inclusion-maximal consistent subgraphs were preserved on average.

Definition 9. Let ${\text{AMSP}}_{EGEDmin}\left(G\right)$ be the average, for every inclusion-maximal consistent subgraph $S$, of the number of times $S$ appears in the output of EGEDmin (average maximal subgraph preservation):

$${\text{AMSP}}_{EGEDmin}\left(G\right)=\frac{1}{|\text{IMCS}\left(G\right)|}\sum _{S\in \text{IMCS}\left(G\right)}{\text{RSP}}_{EGEDmin}\left(S\right)$$

Both ${\text{RSP}}_{EGEDmin}$ and ${\text{AMSP}}_{EGEDmin}$ can be adapted to different methods for resolution, simply by swapping out the instances of EGEDmin for something else (e.g. HodgeRank). By default, I will use $\text{RSP}$ and $\text{AMSP}$ for ${\text{RSP}}_{EGEDmin}$ and ${\text{AMSP}}_{EGEDmin}$.

A higher number for AMSP is better: It means that more inclusion-maximal consistent subgraphs get preserved more often by the method for resolving inconsistent preferences.

$n$	Samples	Avg $\#\left(\text{IMCS}\right(G\left)\right)$	Avg $\text{AMSP}\left(G\right)$	Min $\text{AMSP}\left(G\right)$	Graphs with $\text{AMSP}\left(G\right)=1$
0	1	1	1	1	1 (100%)
1	2	1	1	1	2 (100%)
2	16	1.125	1	1	16 (100%)
3	512	$\approx$ 1.32	$\approx$ 0.995	2⁄3	496 ($\approx$ 98.4%)
4	65536	$\approx$ 1.568	$\approx$ 0.984	0	57728 ($\approx$ 94.4%)
5	33554432	$\approx$ 1.864	$\approx$ 0.969	0	7803263 ($\approx$ 80.1%)
6	90927	$\approx$ 2.207	$\approx$ 0.95	0	72209 ($\approx$ 79.4%)
7	1580	$\approx$ 2.618	$\approx$ 0.932	0	1095 ($\approx$ 69.3%)

One can see that the average number of inclusion-maximal consistent subgraphs increases, albeit initially slowly. The number of times that maximal consistent subgraphs are preserved (Avg $\text{AMSP}\left(G\right)$) starts dropping, though the shrinking behavior isn’t clear from the limited amount of data. The number of graphs in which all inclusion-maximal consistent subgraphs are preserved by EGEDmin shrinks even more quickly, indicating that preserving all consistent subgraphs is a property that is difficult to fulfill.

Only for small graphs (up to 3 vertices) it is guaranteed that at least one inclusion-maximal consistent subgraph occurs in the output of EGEDmin.

So we can pose some conjectures indicated by the datapoints observed above:

Conjecture 2. In the limit of graph size, on average EGEDmin preserves almost none of the inclusion-maximal consistent subgraphs:

$$\underset{n\to \infty }{lim}\frac{1}{|P_n|}\sum _{G\in P_n}\text{AMSP}\left(G\right)=0$$

Conjecture 3. For graphs with $>7$ nodes it remains the case that there are graphs for which the smallest number of inclusion-maximal consistent subgraphs preserved by EGEDmin is zero:

$$\underset{n\to \infty }{lim}\underset{G\in P_n}{min}\text{AMSP}\left(G\right)=0$$

Conjecture 4. In the limit of number of nodes in a graph, for almost no graphs does EGEDmin preserve all inclusion-maximal consistent subgraphs.

$$\underset{n\to \infty }{lim}\frac{1}{|P_n|}|\{G\in P_n|\text{AMSP}(G)=1\}|=0$$

Applying HodgeRank

If the output of HodgeResolve is allowed to be a weak ordering, then the original definition of Preservation of Consistent Subgraphs does not apply, as it presumes a mapping $f$ from $P$ to $C$. However, the definition can easily be transferred by defining $f$ as a function from directed graphs to weakly consistent graphs, that is $f:P_{\Omega }\to W_{\Omega }$. The definition of Preservation of Consistent Subgraphs stays otherwise unchanged^[5].

HodgeResolve does not fulfill Preservation of Consistent Subgraphs. The following figure shows two graphs (both on the left in their respective subfigures). For the graph in the left subfigure no inclusion-maximal consistent subgraphs are preserved, for the right one all but one inclusion-maximal consistent subgraphs are preserved.

$1\to 2$ is the only consistent subgraph, but it gets reversed.

Each edge is an inclusion-maximal consistent subgraph, and only the edge $3\to 4$ gets reversed. 1 and 2 in the result have the same potential.

In the first image, a graph with 1 inclusion-maximal consistent subgraph and its resolution through HodgeResolve, and in the second image a graph with several inclusion-maximal consistent subgraphs and its resolution through HodgeResolve. The labels at the edges are the gradients that HodgeRank has computed.

In the following table, $\text{AMSP}$ refers to ${\text{AMSP}}_{HodgeResolve}$, and $\text{IMCS}$ refers to ${\text{IMCS}}_{HodgeResolve}$.

$n$	Samplesize	Avg $\#\left(\text{IMCS}\right(G\left)\right)$	Avg $\text{AMSP}\left(G\right)$	Min $\text{AMSP}\left(G\right)$	Graphs with $\text{AMSP}\left(G\right)=1$
0	1	1	1	1	1 (100%)
1	2	1	1	1	2 (100%)
2	16	1.125	1	1	16 (100%)
3	512	$\approx$ 1.32	$\approx$ 1	1	512 (100%)
4	65536	$\approx$ 1.568	$\approx$ 0.978	0	63232 ($\approx$ 96.5%)
5	33554432	$\approx$ 1.864	$\approx$ 0.932	0	29373632 ($\approx$ 87.5%)
6	65536	$\approx$ 2.209	$\approx$ 0.879	0	49680 ($\approx$ 75.8%)
7	65536	$\approx$ 2.612	$\approx$ 0.831	0	41926 ($\approx$ 63.9%)
8	65536	$\approx$ 3.064	$\approx$ 0.783	0	34227 ($\approx$ 52.2%)
9	65536	$\approx$ 3.567	$\approx$ 0.738	0	27138 ($\approx$ 41.4%)
10	65536	$\approx$ 4.13	$\approx$ 0.701	0	21349 ($\approx$ 32.6%)

With this data, the next plot shows how well EGEDmin and HodgeResolve perform at preserving inclusion-maximal consistent subgraphs.

Comparing EGEDmin and HodgeResolve at how well they perform on various metrics of preserving inclusion-maximal consistent subgraphs.

One can see that on average, EGEDmin preserves inclusion-maximal consistent subgraphs more often, and may also retain all inclusion-maximal consistent subgraphs more often (although the low sample sizes for graphs with six and seven nodes makes this difficult to conclude without doubt).

Preservation of Completely Dominating and Dominated Set

Inclusion-maximal consistent subgraphs are a way of formalizing what it means for a preference to be locally consistent: there is some subset of $\Omega$ so that the preferences are not “confused” about this subset. One can also try to find a corresponding condition that would make a statement about global consistency. Voting theory offers some inspiration here: the minimal undominated set (also Condorcet set) Miller 1977 is defined for every tournament $T=(V_T,E_T)$ as a set of vertices $V^{\ast }\subseteq V_T$ so that (1) there is no edge from $V_T\setminus V^{\ast }$ to $V^{\ast }$ and (2) there is no proper subset of $V^{\ast }$ that meets (1).

One can create a related (but weaker) definition for directed graphs:

For a given $G$, let ${\Sigma }_1,{\Sigma }_2$ be non-empty sets of vertices of $G$ such that ${\Sigma }_1\uplus {\Sigma }_2=\Omega$. Then ${\Sigma }_1$ is a completely dominating set and ${\Sigma }_2$ is a completely dominated set if and only if $\forall {\sigma }_1\in {\Sigma }_1,{\sigma }_2\in {\Sigma }_2:({\sigma }_1,{\sigma }_2)\in E\wedge ({\sigma }_2,{\sigma }_1)\notin E$.

This means that all elements in a completely dominating set are strictly preferred to all elements in a completely dominated set—there is a subset of options that are clearly better than all other options.

A change from the Condorcet set is that we don’t demand the completely dominating set to be minimal (which would always make the empty set the completely dominating set). Additionally, the completely dominating set is not unique: In an acyclic tournament, for $1\le i\le |\Omega |$ the $i$ greatest elements form a dominating set.

A completely dominating set then represents a global consistency in the preference: within ${\Sigma }_1$ and ${\Sigma }_2$ we are unsure about our preference, but we know that any element of ${\Sigma }_1$ is better than any element of ${\Sigma }_2$.

Definition 10. A function $f:P\to P\left(C\right)$ fulfills Preservation of Complete Domination if and only if for any directed graph $G$ with a completely dominating set ${\Sigma }_1$ and a completely dominated set ${\Sigma }_2$ it holds that $\forall C\in f\left(G\right)$ the set of nodes ${\Sigma }_1$ is a completely dominating set of ${\Sigma }_2$ in $C$.

Proposition 3. Let $f$ be a function that fulfills Preservation of Complete Domination. If for a graph $G$ there are $n$ sets of vertices ${\Sigma }_1,\dots ,{\Sigma }_n$ so that ${⨄}_{i=1}^n{\Sigma }_i=\Omega$ and

$$\forall c\in \{1,\dots ,n\}:\bigcup _{i=1}^c{\Sigma }_i\text{completely dominates}\bigcup _{j=c+1}^n{\Sigma }_j$$,

then for any $C\in f\left(G\right)$ with $C=(\Omega ,E_C)$ it holds that $\forall 1<j<k<n:\forall {\sigma }_j\in {\Sigma }_j,{\sigma }_k\in {\Sigma }_k:({\sigma }_j,{\sigma }_k)\in E_C\wedge ({\sigma }_k,{\sigma }_j)\notin E_C$ (or, less formally, every element from a subset of a completely dominating set is strictly preferred over any element from a subset of a completely dominated set in the output of the resolution function $f$).

Proof. Fix $1<j<k<n$. Let ${\Sigma }_l={⨄}_{i=1}^{k-1}{\Sigma }_i$ and ${\Sigma }_r={⨄}_{i=k}^n{\Sigma }_i$. Then ${\Sigma }_l$ dominates ${\Sigma }_r$ in $G$, and by assumption also in $C\in f\left(G\right)$. Since ${\Sigma }_j⊊{\Sigma }_l$ and ${\Sigma }_k⊊{\Sigma }_r$, it holds that $\forall {\sigma }_j\in {\Sigma }_j,{\sigma }_k\in {\Sigma }_k:{\sigma }_j\to {\sigma }_k\in E_C\wedge {\sigma }_k\to {\sigma }_j\notin E_C$. So ${\Sigma }_j$ now completely dominates ${\Sigma }_k$ in $C$. ◻

Remark 1. Sets of such ${\Sigma }_1,\dots ,{\Sigma }_n$ such that there is a relationship of complete domination between any two of them are quite similar to graph quotients, but is somewhat stricter (demanding that each ${\sigma }_i\in {\Sigma }_i$ be preferred to each other ${\sigma }_j\in {\Sigma }_j$).

Remark 2. Preservation of complete domination implies some other criteria: If there is a consistent subgraph which is a completely dominating set, then it will comprise the “greatest” subgraph in the resolved preference, with the greatest element in $G$ also being the greatest element in $f\left(G\right)$. The same holds for the a completely dominated consistent subgraph, which stays at the bottom.

Minimizing Graph-Edit Distance

Theorem 9.EGEDmin fulfills Preservation of Complete Domination.

Proof. Let $C=(\Omega ,E_C)$, with $C\in EGEDmin\left(G\right)$ be a consistent graph for a directed graph $G$, where $G$ has a completely dominating set ${\Sigma }_1$ and a completely dominated set ${\Sigma }_2$. Assume $C$ does not have the completely dominating set ${\Sigma }_1$, and let $n=EGED(G,C)$. Then there must be a “highest” or “largest” ${\sigma }_2\in {\Sigma }_2$ in $C$ (one for which there is no other ${\sigma }_2^{\prime }\in {\Sigma }_2$ so that ${\sigma }_2^{\prime }\to {\sigma }_2$ is an edge in $C$). There must also be a “highest” or “largest” ${\sigma }_1^{\ast }\in {\Sigma }_1$ so that ${\sigma }_2\to {\sigma }_1^{\ast }$ is an edge in $C$.

Let there be $m\ge 0$ elements of ${\Sigma }_1$ “between” ${\sigma }_2$ and ${\sigma }_1^{\ast }$, that is for ${\Sigma }_2^{\ast }=\{{\sigma }_2^{\ast }|{\sigma }_2\to {\sigma }_2^{\ast }\in E_C\wedge {\sigma }_2^{\ast }\to {\sigma }_1^{\ast }\in E_C\}$ it holds that ${\Sigma }_2^{\ast }=m$.

One can now create a $C^{\prime }$ from $C$ so that $EGED(G,C^{\prime })=n-2(m+1)$ by moving ${\sigma }_1^{\ast }$ into the position directly above ${\sigma }_2$ by reversing the edges ${\sigma }_2\to {\sigma }_1^{\ast }$ and ${\sigma }_2^{\ast }\to {\sigma }_1^{\ast }$ for all ${\sigma }_2^{\ast }\in {\Sigma }_2^{\ast }$. The modified $C^{\prime }$ now contains some edges from $G$ that need to be reversed to create $C$: ${\sigma }_1^{\ast }\to {\sigma }_2$ and $\{{\sigma }_1^{\ast }\to {\sigma }_2^{\ast }|{\sigma }_2^{\ast }\in {\Sigma }_2^{\ast }\}$ are already edges in $G$, and because edge reversals have weight 2 (deleting and then adding one edge), this saves $2(m+1)$ edge operations.

Furthermore all other edge operations to minimally achieve $C$ from $G$ can be held constant to create $C^{\prime }$, so that the graph-edit distance is not changed otherwise.$C^{\prime }$ is now an acyclic tournament with a smaller edge-graph-edit distance from $G$ than $C$. Thus all other outputs $C=EGEDmin\left(G\right)$ must also have a smaller edge-graph-edit distance than $C$ has to $G$.

If $C^{\prime }$ does not have the same completely dominating set ${\Sigma }_1$ that $G$ has, one can create a new graph $C^{\prime \prime }$ by finding a new “highest” ${\sigma }_2$ and corresponding ${\sigma }_1^{\ast }$ and switching them. This $C^{\prime \prime }$ again has shorter edge-graph-edit distance.

This process can be repeated as long as ${\Sigma }_1$ is not a completely dominating set in the consistent graph, monotonically decreasing the edge-graph-edit distance, until no further such modifications can be found.

The final consistent graph resulting from this process contains ${\Sigma }_1$ as a completely dominating set: Every ${\sigma }_1\in {\Sigma }_1$ has a one-directional edge to every ${\sigma }_2\in {\Sigma }_2$. ◻

Applying HodgeRank

Conjecture 5.$HodgeResolve\left(G\right)$ fulfills Preservation of Complete Domination for every $G\in P$.

This conjecture holds for all directed graphs with 5 nodes or less, by computational experiment, and for random samples of graphs ($2^{16}$ graphs generated for each number of nodes, using the Erdős-Rényi model with the probability $\frac{1}{2}$ of edge creation) with up to 13 nodes.

Summary

We can now summarize how well the two algorithms fulfill the different criteria:

Criterion	EGEDmin	HodgeResolve
Surjectivity	✓	✓
Identity	✓	✓
Worst-case computational complexity	$NP$-hard	$O\left(n^3\right)$
Uniqueness	✗	~[6]
Polynomial output size	✗	~
Preservation of consistent subgraphs	✗	✗
Preservation of complete domination	✓	?

Impossibilities

Some of the criteria listed in Section 3.3 are incompatible with each other.

Resolution to Polynomially Many Preferences and Preservation of Consistent Subgraphs are Incompatible

It is not possible to have an algorithm that retains every maximal consistent subgraph at least once in the set of outputs and has only polynomially many outputs.

Theorem 10. Let $f:P\to P\left(C\right)$ be a function for resolving inconsistent graphs that fulfills Preservation of Consistent Subgraphs for all graphs $P$. Then there exists no polynomial $p$ so that for all directed graphs $P_n$ of size $n$ it holds that $\forall P_n\in P_n:|f\left(P_n\right)|\le p\left(n\right)$.

We show this with a graph that is a counterexample, i.e. for which such a polynomial can not exist.

Definition 11. Let $V$ denote a directed graph with three vertices $\alpha ,\beta ,\gamma$ and three edges $\alpha \to \beta ,\beta \to \gamma ,\gamma \to \alpha$. Let now denote $E_n$ be a graph that is constructed out of $n$ copies of $V$, “stacked” on top of each other. More formally, let the vertices of $E_n$ be the set $\{{\alpha }_1,\dots ,{\alpha }_n,{\beta }_1,\dots ,{\beta }_n,{\gamma }_1,\dots ,{\gamma }_n\}$ so that ${\alpha }_i,{\beta }_i,{\gamma }_i$ are the vertices of the graph $V_i$, and the edges of $E_n$ are the edges of each $V_i$ and the edges $\left\{\right(u_i,v_j)|i>j\wedge u,v\in \{\alpha ,\beta ,\gamma \left\}\right\}$.

We first prove that each inclusion-maximal consistent subgraph of $E_n$ only contains one edge from each $V_i$.

Lemma 11. Every inclusion-maximal consistent subgraph $V$ of $E_n$ contains exactly one edge from each $V_i\in \{V_1,\dots ,V_n\}$.

Proof. Assume $S$ is a subgraph of $E_n$, and there exists (without loss of generality) a $V_i$ so that $S\cap V_i$ has two edges ${\alpha }_i\to {\beta }_i$ and ${\beta }_i\to {\gamma }_i$. Since $S$ is stipulated to be consistent, due to the transitivity requirement it must also contain the edge ${\alpha }_i\to {\gamma }_i$. But then $S$ would no longer be a subgraph of $E_n$, since ${\alpha }_i\to {\gamma }_i$ is not an edge in $V_i$. If $S\cap V_i$ has three edges, $S$ must be inconsistent, since transivity or asymmetry are violated. Assume now there is a subgraph $V_i$ of $E_n$ so that $S\cap V_i$ has no edges. Then one can add any one edge from $V_i$ to $S$ while retaining consistency: If one adds (without loss of generality) ${\alpha }_i\to {\beta }_i$, this preserves consistency, since

• Completeness is preserved (${\alpha }_i,{\beta }_i$ are connected to all ${\omega }_h,{\omega }_j$ ($h<i<j$)).

• Transitivity is preserved (${\omega }_h\to {\alpha }_i,{\alpha }_i\to {\beta }_i$ also means that ${\omega }_h\to {\beta }_i$ since $h<i$, and similar for ${\alpha }_i\to {\beta }_i,{\beta }_i\to {\omega }_j$).

• Asymmetry is preserved because we add no reversed edges where there were edges in $S$ before.

◻

We then show that any consistent graph on the vertices of $E_n$ can not contain $2^n+1$ inclusion-maximal consistent subgraphs of $E_n$.

Lemma 12. Let $S$ be a set of inclusion-maximal consistent subgraphs of $E_n$, and $|S|=2^n+1$. Then there exists no consistent graph $C$ on the vertices of $E_n$ so that $\forall S\in S:S\text{is a subgraph of}C$.

Proof. We showed that each $S\in S$ contains exactly one edge from each $V_i$. If two $S_1,S_2$ for a given $V_i$ share the same edge (i.e. $S_1\cap V_i=S_2\cap V_i$), $S_1$ and $S_2$ can be subgraphs of the same consistent graph $C$. If two $S_1,S_2\in S$, for a given $V_i$, don’t share the same edge (that is $S_1\cap V_i\ne S_2\cap V_i$), they can be nevertheless still be subgraphs of the same consistent $C$:

If (without loss of generality) $(S_1\cap V_i)={\alpha }_i\to {\beta }_i$ and $(S_2\cap V_i)={\beta }_i\to {\gamma }_i$, $C$ can contain those edges as well as ${\alpha }_i\to {\gamma }_i$.

If, though, there are three $S_1,S_2,S_3\in S$ that each don’t share an edge on a given $V_i$, they can’t be subgraphs of any consistent $C$: Such a $C$ would need to contain $\{{\alpha }_i\to {\beta }_i,{\beta }_i\to {\gamma }_i,{\gamma }_i\to {\alpha }_i\}$, but this would violate either asymmetry (if one added ${\alpha }_i\to {\gamma }_i$ as well) or transitivity (through the absence of ${\alpha }_i\to {\gamma }_i$).

Therefore, for each $V_i$, only two edges from $V_i$ can occur in any element of $S$. Then an $S\in S$ can be uniquely identified by which edge from each $V_i$ it contains, since there are two edges for each $V_i$ and there are $n$ such “levels” $V_i$, and no two edges from different $V_i,V_j$ are mutually exclusive.

Therefore, $|S|\le 2^n$ if all elements of $S$ are to be subgraphs of an acyclic tournament. But introducing an additional distinct $S_{2^n+1}$ to $S$ must add a third edge from at least one $V_i$, thus $2^n$ is the maximal size of $S$. ◻

We can now show that the set of consistent graphs that contain all inclusion-maximal consistent subgraphs of $E_n$ grows exponentially in $n$ (albeit with a small exponent).

Lemma 13. The set of consistent graphs $C$ on the vertices of $E_n$ that includes all inclusion-maximal consistent subgraphs of $E_n$ has size at least $(\frac{3}{2}{)}^n$.

Proof. Assume that one can partition the set $C$ of inclusion-maximal consistent subgraphs of $E_n$ into a set $P$ of disjoint sets of size $\le 2^n$ (that is $\forall C_i\in P:|C_i|=2^n|$) such that there exists a consistent graph $C$ that contains all $C_i$. Then the number of such partitions would be the number of consistent graphs required to “cover” all elements in $C$, since by Lemma 12 the sets of compatible graphs have at most size $2^n$. Then the size of $P$ would be at least $\frac{3^n}{2^n}={1.5}^n$, which is exponential in $n$. ◻

Therefore, Theorem 10 is true.

Corollary 1. There is no polynomial $p$ and function $f:P\to P\left(C\right)$ such that $|f\left(E_n\right)|\le p\left(n\right)$ and $f$ fulfills Preservation of Consistent Subgraphs, so Theorem 10 is true (with $E_n$ as a counterexample).

Remark 3. This bound is $(\frac{3}{2}{)}^{\frac{v}{3}}={\sqrt[3]{3\frac{3}{2}}}^v\approx {1.145}^v$ for the number of vertices $v$ in $E_v$, which is exponential but can probably be improved upon.

Polynomial Time Complexity and Preservation of Consistent Subgraphs are Incompatible

Given that in the worst case, only a small proportion of consistent subgraphs can be preserved, it also is not possible to have an algorithm that returns, for each inclusion-maximal consistent subgraph $S$, at least one consistent graph that contains $S$, and computes its output in polynomial time.

Theorem 14. Let $A$ be an algorithm for resolving inconsistent graphs that implements an $f$ which fulfills Preservation of Consistent Subgraphs for all graphs $G\in P$. Then there exists no polynomial $p$ so that for all directed graphs $P_n\in P_n$ of size $n$ it holds that $A\left(P_n\right)$ computes its output in less than $p\left(n\right)$ steps.

Proof. Let $C=A\left(E_n\right)$. Lemma 13 shows that $C$ is exponential in the number of vertices (by remark 3. Any $A$ would at least need to enumerate all $C\in C$, which would take exponential time. ◻

Remark 4. The set of inclusion-maximal consistent subgraphs on $E_n$ can be compactly represented as the Cartesian product of the inclusion-maximal consistent subgraphs of the “levels” $V_i$:

$$\underset{i=1}{\overset{n}{\times }}\{{\alpha }_i\to {\beta }_i,{\beta }_i\to {\gamma }_i,{\gamma }_i\to {\alpha }_i\}$$

This might also allow for a compact representation of the result of $f$ which includes all inclusion-maximal consistent subgraphs. We suspect there are counter-examples that don’t allow for this, but haven’t been able to find any.

Inconsistent Preferences over Lotteries

Von Neumann and Morgenstern formulate their famous theorem by defining some restriction on relations over lotteries von Neumann & Morgenstern 1947, as explained in this section.

Finding a mathematical structure which can encode all inconsistent preferences over lotteries and is still computationally tractable remains an open problem, but we propose two structures which can either tractably encode some subset of inconsistent preferences or are rich enough to encode all inconsistent preferences, but too complex to be compactly represented.

Violating the Axioms

Introducing lotteries allows for a large variety of violations of the von Neumann-Morgenstern axioms.

Discontinuity

Discontinuity in relations over lotteries can occur if we know that $l_1⪯l_2⪯l_3$, but there is no $p$ so that $l_2\sim [p:l_1,(1-p):l_3]$. A discontinuous preference that fulfills $l_1⪯l_2⪯l_3$ could then state that for every $p\in (0;1]$ it holds that $l_2\succ [p:l_1,(1-p):l_3]$ but $l_2\prec l_3$: the lottery $l_2$ is strictly preferred over any mixture of $l_1,l_3$, but $l_3$ is still strictly preferred to $l_2$. The equivalent can occur if $l_2$ is strictly dispreferred to any mixture of $l_1,l_3$, but strictly preferred over $l_1$.

In humans, this can sometimes be observed as the certainty effect from prospect theory, in which subjects systematically overrate the value of certain (deterministic) option, which leads to the Allais paradox.

A view under which discontinuities of this type make sense is if an agent has a specific aversion to lotteries, irrespective of the options they are comprised of (Von Neumann and Morgenstern call the continuity axiom “excluding a “utility of gambling”″ von Neumann & Morgenstern 1947, 3.7.1, and state that “concepts like a “specific utility of gambling” cannot be formulated free of contradiction on this level.” [ibid.]).

Dependence

Violations of the independence axiom (“dependence”) occur if for two lotteries $l_1,l_2$ (with $l_1⪯l_2$) there is an option $l_3$ and a $p\in [0;1]$ so that $[p:l_1,(1-p):l_3]\succ [p:l_2,(1-p):l_3]$: Mixing in $l_3$ in equal proportion to both $l_1,l_2$ causes the preference to switch.

Together with a strong preference for certainty it is observed in the Allais paradox: In experiments with humans, the lottery [A_1=[1: $1 \text{mio.}]] is strictly preferred over the lottery $B_1=[0.89: $1 \text{mio.}, 0.01: $0, 0.1: $5 \text{mio.}]$, but the lottery $B_2=[0.9: $0, 0.1: $5 \text{mio.}]$ is strictly preferred over $A_2=[0.89: $0, 0.11: $1 \text{mio.}]$.

By using the independence axiom, these two preferences can be shown to be contradictory. This can be done by first “mixing out” 0.89 of $1mio. from $A_1$ and $B_1$, that is representing $[1: $1 \text{mio.}]$ as $[0.89: $1 \text{mio.}, 0.11: $1 \text{mio.}]$ and then (by independence) dropping $0.89: $1 \text{mio.}$ from $A_1$ and $B_1$, and then re-normalizing the probabilities so that they sum to 1. One can then “mix in” 0.89 of $0 into the two resulting distributions to create $A_2$ and $B_2$, so under the von Neumann-Morgenstern axioms $A_1\prec B_1$ and $B_2\prec A_2$ contradict each other.

$$\begin{array}{cc}& A_1\prec B_1\\ \iff & [1:\$1\text{mio.}]\prec [0.89:\$1\text{mio.},0.01:\$0,0.1:\$5\text{mio.}]\\ \iff & [0.89:\$1\text{mio.},0.11:\$1\text{mio.}]\prec [0.89:\$1\text{mio.},0.01:\$0,0.1:\$5\text{mio.}]\\ \iff & [1:\$1\text{mio.}]\prec [1/11:\$0,10/11:\$5\text{mio.}]\\ \iff & [0.89:\$0,0.11:\$1\text{mio.}]\prec [0.9:\$0,0.1:\$5\text{mio.}]\\ \iff & A_2\prec B_2\end{array}$$

Representing Inconsistencies

It is more difficult to find a mathematical structure to represent arbitrary inconsistent preferences over lotteries over some set of options $\Omega$.

Edge-Weighted Graphs

Given $\Omega$, some inconsistent preferences on lotteries on $\Omega$ can be represented by the set $G_{\Omega }$ of edge-weighted directed graphs on $\Omega$, where edge weights of a graph $G$ can be expressed as the values of a function $w_G:\Omega \times \Omega \to R$.

Definition 12. The subset $S_{\Omega }\subset G_{\Omega }$ of consistent preferences on $\Omega$ is the set of all edge-weighted directed graphs that is complete, transitive, irreflexive and weight-transitive, where a graph is weight-transitive if for all edges $e\in E$ it holds that $w_G(\alpha \to \beta )=c_1\wedge w_G(\beta \to {\omega }_3)=c_2\Rightarrow w_G(\alpha \to {\omega }_3)=c_1+c_2$.

An element from $S_{\Omega }$ assigns each element from $\Omega$ a cardinal value, equivalent to a utility function on $\Omega$.

Edge-weighted directed graphs on $\Omega$ are not expressive enough to represent all relevant inconsistent preferences, though. As a trivial example, let $l_1=[0.25:\alpha ,0.75:\beta ]$ and $l_2=[0.75:\alpha ,0.25:\beta ]$ with $l_1\prec l_2$, but $l_3=[0.3:\alpha ,0.7:\beta ],l_4=[0.7:\alpha ,0.3:\beta ]$ with $l_3\succ l_4$. The first preference implies a positive weight for the edge $\alpha \to \beta$, but the second preference implies a negative weight for $\alpha \to \beta$.

Introducing two positively weighted edges between $\alpha ,\beta$ (creating a two-cycle) is able to represent that such a preference between lotteries is present, but it doesn’t allow reconstruction of which lotteries are preferred over which others: Given a preference of $\alpha$ over $\beta$ by $w_l$, and of $\beta$ over $\alpha$ by $w_r$ doesn’t enable reconstruction of whether $l_1\prec l_2$ or $l_1\succ l_2$.

Arbitrary Relations over the Lotteries

As von Neumann & Morgenstern 1947 uses lotteries on $\Omega$ as the set of options over which agents can have preferences, a natural instinct is to use arbitrary relations over lotteries on $\Omega$ as the mathematical object to represent preferences.

However, if $\Omega$ has at least one element, such a relation can be uncountably large and without compact representation, making it impossible to be handled computationally.

Example 2. A pathological example would be a relation $R\in \Delta \left(\Omega \right)\times \Delta \left(\Omega \right)$ on probability distributions of $\Omega =\{\alpha ,\beta \}$ in which $[p:\alpha ,(1-p):\beta ]\prec [q:\alpha ,(1-q):\beta ]$ if and only if $p\in [0;1]$ is an uncomputable real number and $q\in [0;1]$ is a computable real number.

We were also unable to find a method for resolving such inconsistent preferences into their consistent versions.

Algorithms

After some search, we were able to identify HodgeRank from Jiang et al. 2011 as a candidate algorithm for resolving an edge-weighted inconsistent graph into an edge-weighted consistent graph.

Some other possible candidates for methods for resolving inconsistent preferences over edge-weighted graphs were considered, and finally rejected.

One option was the PageRank algorithm, also mentioned in Sun et al. 2017. We rejected PageRank for the same reason as Sun et al. 2017 did: In a directed acyclic graph, a unique greatest element does not necessarily receive the highest ranking. This problem extends to using other centrality measures for graphs such as degree centrality and betweenness centrality: In graphs that are already consistent, the greatest element usually receives a low centrality score, and elements closer to the center receive larger scores, which is counter to our criteria.

HodgeRank

HodgeRank, introduced in Jiang et al. 2011, is an algorithm based on Hodge theory from algebraic geometry for decomposing a doubly edge-weighted, potentially not fully connected graph $G=(\Omega ,E,w:E\to R\cup \{nan\},l:E\to N\})$ into the sum of three different edge weighted graphs:

• A gradient graph $G_g=(\Omega ,E,w_g:E\to R)$, in which $w_g$ is derived from a potential function that assigns consistent values to vertices $\omega \in \Omega$: the potential $p:\Omega \to R$ of a node has a value so that $g(e=({\omega }_i,{\omega }_j\left)\right)=p\left({\omega }_j\right)-p\left({\omega }_i\right)$.

• A curl graph $G_c=(\Omega ,E,w_c:E\to R)$, where a function $c$ assigns every 3-cycle in the graph a specific value, and the value $w_c\left(e\right)$ for an edge is the sum of the values $c$ assigns to all the 3-cycles $e$ is in.

• A harmonic graph $G_h=(\Omega ,E,w_h:E\to R)$.

Then $w\left(e\right)=w_g\left(e\right)+R\left(e\right)=w_g\left(e\right)+w_c\left(e\right)+w_h\left(e\right)$, where $R$ is a residual.

Jiang et al. 2011 develop HodgeRank from a social-choice theoretic perspective: Given a set of incomplete cardinal ratings $C$ of the type $(R\cup \{nan\}{)}^{n\times m}$ by a set $V=\{1,\dots ,m\}$ of voters on $A=\{1,\dots ,n\}$ alternatives, one can construct an edge-weighted graph $G_C=(\Omega ,E,w,l)$ where the nodes are the options $A$ and each edge weight is some combination of the cardinal votes on the options ${\omega }_1,{\omega }_2$ that comprise the edge.

An edge weight can be for example the arithmetic mean

$$w_C({\omega }_1\to {\omega }_2)=\frac{{\sum }_{i=1}^n{C}_{i,{\omega }_2}-C_{i,{\omega }_1}}{|\{n|C_{n,{\omega }_1},C_{n,{\omega }_2}\text{both}\ne nan\}|}$$

though Jiang et al 2015 also discuss using other methods such as the geometric mean or the ratio of preference to dispreference.

If every voter assigns nan to both ${\omega }_1$ and ${\omega }_2$, there is no edge between the two options.

The function $l:E\to R$ denotes the number of voters which have a non-nan rating for both nodes in the edge. In the case where we do not take the social choice view, we can assume that $\forall e\in E:l\left(e\right)=1$, which does not change the process of computing the output of HodgeRank.

function HodgeRank(G) # G is a tuple (Ω, E, w, l) Revert all e∈E with w(e)<0 so thay they now have positive weight. f=(w(e₁, …, w(eₖ)) L=diag(l(e₁), …, l(eₖ)) O=zeros(|E|, |Ω|) for (u,v) in E O_eu=-1, O_ev=1 s=-(O.T×L×O)⁺×O.T×L×f # A⁺ is the Moore-Penrose pseudo-inverse of A return s

Computing HodgeRank from an edge-weighted directed graph

This pseudocode is implemented in Python here.

Remark 5. One might ask, under the social choice view, whether it makes sense for some voter $v\in V$ to lie about their preferences over $A$ in order to change the output of HodgeRank to correspond to their own ranking ordinally. In fact this is the case and therefore HodgeRank is not strategy-free.

It is easy to find an example for this: Assume there are three options $A=\{a,b,c\}$, and three voters $V=\{1,2,3\}$, and let the cardinal values assigned to the options be $u_1\left(a\right)=4,u_1\left(b\right)=3,u_2\left(b\right)=4,u_2\left(c\right)=3,u_3\left(c\right)=4,u_3\left(a\right)=3$, with the rest of the values assigned to the options being nan. Then the values HodgeRank assigns to the options are $h\left(a\right)=h\left(b\right)=h\left(c\right)=0$. But voter 1 can change their reported assignments to be $u_1^{\prime }\left(a\right)=5,u_1^{\prime }\left(b\right)=3,u_1^{\prime }\left(c\right)=1$, changing the outputs of HodgeRank to $h^{\prime }\left(a\right)=1,h^{\prime }\left(b\right)=0$ and $h^{\prime }\left(c\right)=-1$, which is more compatible with their preferences.

It would be interesting to investigate the computational complexity of finding manipulations of existing preference of one voter to ordinally change the output of HodgeRank to more strongly conform to that voters’ preferences.

Besides the disadvantage of allowing for strategic manipulation, the decomposition returned by HodgeRank appears to display many desirable properties as a method for resolving inconsistent preferences over edge-weighted graphs:

• Existence: It always exists.

• Uniqueness: This decomposition is unique up to an additive constant.

• Polynomial time computability: Finding $w_g$ is equivalent to solving an $|V|\times |V|$ least-squares problem, which can be solved in $O\left(n^3\right)$ time, for example by computing the Moore-Penrose pseudo-inverse of a specific matrix. Finding $w_h$ and $w_c$ from $R$ is more computationally intensive, but still polynomial: they are equivalent to solving a least-squares problem of size $\frac{|V|}{3}\approx O\left(n^3\right)$, and can therefore be found in $O\left(n^9\right)$.

• Robustness to incomplete and cyclic data: HodgeRank still returns a result, even if edges are missing or there are positive-valued cycles in the data.

• Relation to known solution concepts from social choice theory: If $G$ has no missing edges and $w$ is defined for every edge, HodgeRank returns an affine transformation of the result that the Borda count would return.

In the context of inconsistent preferences, HodgeRank can be interpreted as taking the observed preferences of an agent as an edge-weighted directed graph, and decomposing it so that the potential function $p$ determines how much the agent values different elements in $V$. Here $p$ can act as a utility function. The social-choice theoretic perspective offers an intriguing possibility of modeling agents as being comprised of subagents Demski & Garrabrant 2019, Minsky 1988, which we will not pursue further here.

Applications

Equipped with a notion of how to represent inconsistent preferences and how to resolve them, one can examine problems that have come up in other contexts and apply the knowledge gained to them. I will examine one of those: The problem of changing a preference as the underlying set of options changes.

Ontology Identification, Ontological Shifts and Ontological Crises

The term “ontological crisis” was introduced in de Blanc and intuitively refers to a scenario in which an agent has preferences, defined over some world model, and then the world model changes without corresponding changes in the values de Blanc 2011.

An example of this can be observed in human values before and after exposure to philosophy: A human might have a value they would formulate as “I value the continuation of my life”. However, after reading Reasons and Persons, the view of personal identity that justifies a notion of “continuation” might seem much less defensible, as thought experiments around teleportation, the fusion and fission of persons, gradual replacement of the body or atom-by-atom recreation of the body all undermine the concept of a single fixed personal identity.

However, this person would likely not just give up their value of their continued existence, but instead attempt to “port it” to the new world model.

Soares and Fallenstein motivate the problem of ontological crises in the context of a problem they call Ontology Identification: Given a Turing machine using the atomic model of physics, they ask how one can identify which parts of the program and the tape represent atoms or macroscopic objects, and repeat the question for a Turing machine using a quantum-mechanical model of the world Soares & Fallenstein 2017. The problem is further elaborated on outside of the academic literature early in Dai 2012 and Dai 2019, in Yudkowsky et al. 2016 and Andreev & Yudkowsky 2016, and under the term “model splintering” in Armstrong 2020, Armstrong & Gorman 2022.

The word “ontology” here is a place-holder for a more rigorously defined model, such as Markov Decision Processes (MDPs) or Partially Observable Markov Decision Processes (POMDPs).

It seems useful to disambiguate some terms that appear in the literature, to create clarity about what they mean:

• Ontology Identification: “Given goals specified in some ontology and a world model, how can the ontology of the goals be identified in the world model? What types of world models are amenable to ontology identification?” Soares & Fallenstein 2017.

• Ontological Shift: Given some goals specified in some ontology and a world model in which those goals have already been identified, an ontological shift occurs if the world model changes but the ontology of the goals does not.

• Ontological Crisis: An ontological crisis is the result of an ontological shift, and the behavior of an agent after an ontological crisis could be undefined.

Existing Approaches

De Blanc approaches the problem of ontological crises formally in the context of what they call “finite state models” (they neglect to give a full definition) de Blanc 2011, and one can refine their problem statement and their approach to a solution by stating it in terms of Markov decision processes Russell & Norvig 2010, ch. 17.1.

Definition 13. A finite Markov decision process (MDP) $M=(S,A,P,R,I)$ is a tuple of five elements, where $S$ is a set of states (in this case finite, with $n=|S|$), the set $A$ is a set of actions (also finite, with $m=|A|$) and $P(s,a,s^{\prime }):S\times A\times S\to [0,1]$ is a function that returns the probability of transitioning from $s$ to $s^{\prime }$ via the action $a$, that is $P(s,a,s^{\prime })=Pr(s_{t+1}=s^{\prime }|s_t=s,a_t=a)$. The function $R:S\to R$ is a reward function that returns a real-numbered value for reaching a certain state^[7], and $I:S\to [0,1]$ is a probability distribution for the states that the agent is initially in.

Given some ordering of the states $s_1,\dots ,s_n$, the transition function $P$ from $M$ can also be represented as a family of right-stochastic matrices $T\left(a\right)$ (the transition matrices), $R$ can be encoded as a real-numbered vector with size $n$, and $I$ can be described as real-numbered vector of size $n$ in which the elements sum to 1.

$$T\left(a\right)=\left(\begin{array}{ccc}P(s_0|a,s_0)& \cdots & P(s_0|a,s_n)\\ ⋮& \ddots & ⋮\\ P(s_n|a,s_0)& \cdots & P(s_n|a,s_n)\end{array}\right)\in [0,1{]}^{n\times n}$$

$$R=\left(\begin{array}{c}R\left(s_0\right)\\ ⋮\\ R\left(s_n\right)\end{array}\right)\in R^n$$

$$I=\left(\begin{array}{c}I\left(s_0\right)\\ ⋮\\ I\left(s_n\right)\end{array}\right)\in R^n$$

Consider two MDPs $M_1=(S_1,A,P_1,R_1,I_1)$ and $M_2=(S_2,A,P_2,R_2,I_2)$, but with $R_2$ being unknown. An agent who starts with $M_1$, but who discovers that a better model $M_2$ of the environment has a different set of states and transition probabilities (however, the set of actions stays the same) and thereby now wants to operate in $M_2$ has the problem of defining $R_2$.

Definition 14. The method de Blanc uses to find $R_2$ is to find two linear maps $\varphi \in R^{n_1\times n_2}$ and $\psi \in R^{n_2\times n_1}$ (with sizes $n_1=|S_1|,n_2=|S_2$) such that $\varphi$ and $\psi$ can be used to “translate” between $M_1$ and $M_2$ de Blanc 2011. Then, for any $a\in A$, $\varphi$ and $\psi$ should be selected so that for any $a\in A$, it holds that $\psi T_1\left(a\right)\varphi$ is approximately equal to $T_2\left(a\right)$ (from here on out written as $\psi T_1\left(a\right)\varphi \approx T_2\left(a\right)$). It should also hold that $\varphi T_2\left(a\right)\psi \approx T_1\left(a\right)$.

De Blanc doesn’t name $\varphi ,\psi$, but we will call such $\varphi ,\psi$ for MDPs a de Blanc bisimulation.

Definition 15. Let $\text{BisimulationDifference}(M_1,M_2,\varphi ,\psi )$ for two MDPs $M_1,M_2$ and a de Blanc bisimulation $\varphi ,\psi$ be

$$\begin{array}{cc}\text{BisimulationDifference}(M_1,M_2,\varphi ,\psi )=& \sum _{a\in A}\sum _{i=1}^{n_1}{D}_{KL}\left(\right(T\left(a{)}_2{)}_{i,\ast }||\right(\psi T\left(a{)}_1\varphi {)}_{i,\ast }\right)+\\ & \sum _{a\in A}\sum _{j=1}^{n_2}{D}_{KL}\left(\right(T\left(a{)}_1{)}_{j,\ast }||\right(\varphi T\left(a{)}_2\psi {)}_{j,\ast }\right)+\\ & D_{KL}\left(I_2||I_1^{\top }\varphi \right)+D_{KL}\left(I_1||I_2^{\top }\psi \right)\end{array}$$

$D_{KL}\left(\right(T\left(a{)}_2{)}_{i,\ast }||\right(\psi T\left(a{)}_1\varphi {)}_{i,\ast }\right)$ is difference between the $i$th row of the state transition matrix of $M_2$ for action $a$ and the $i$th row of the state transition matrix of $M_1$ transformed to $M_1$ via $\varphi$ and $\psi$ into $M_1$. We compute the Kullback-Leibler divergence row-wise because each row is a probability distribution. These differences are summed up across all rows and actions.

We also add the sums over all actions and rows for $D_{KL}\left(\right(T\left(a{)}_1{)}_{j,\ast }||\right(\varphi T\left(a{)}_2\psi {)}_{j,\ast }\right)$, because the Kullback-Leibler divergence is asymmetric.

Finally, we add the Kullback-Leibler divergences between the initial state distributions, again symmetrically.

Definition 16. We call a function that returns a de Blanc bisimulation for two MDPs by minimizing the Kullback-Leibler divergence between the MDPs BisimulateShift.

$$\begin{array}{c}\text{BisimulateShift}(M_1,M_2)=\underset{\varphi ,\psi }{\text{argmin}}\text{BisimulationDifference}(M_1,M_2)\end{array}$$

The matrices $\varphi$ and $\psi$ can be found by minimising $\text{BisimulationDifference}(M_1,M_2,\varphi ,\psi )$ with a hill-climbing algorithm from random initial values, or by gradient descent with $\text{BisimulationDifference}$ as a loss function.

De Blanc notes that both products of the matrices $\varphi ,\psi$ are be close to equal to the identity matrix after computing $\text{BisimulateShift}(M_1,M_2)$, that is $\varphi \psi \approx 1_{n_1}$ and $\psi \varphi \approx 1_{n_2}$, which implies that mapping from $M_1$ to $M_2$ and back loses little information and the state transition probabilities can be mapped to each other.

Given $\varphi$ and $\psi$, it is possible to infer $R_2$ using $\varphi$: It is $R_2=R_1^{\top }\varphi$.

Advantages

There are some advantages to taking this approach for resolving ontological crises. One is that it does not presuppose a known mapping between $S_1$ and $S_2$, and can infer the mapping solely from the transition behavior of $M_1$ and $M_2$.

Another advantage is that for an exact solution found by BisumlateShift, the expected reward of repeating any action in $M_2$ only depends on the expected reward of executing the same action in $M_2$ with a linear transformation of the initial state distribution.

Proposition 4. Let $M_1,M_2$ be two MDPs, and let $\varphi ,\psi$ be two matrices found by BisimulateShift, so that $\varphi \psi =1_{n_1},\psi \varphi =1_{n_2}$ and $\psi T_1\left(a\right)\varphi =T_2\left(a\right)$. For an action $a\in A$, let $r_2(a,k,i_2)$ be the expected average reward of executing an action $a$ for $k\in N$ times in the MDP $M_2$ with an initial state distribution $i_2\in R^{n_2}$, and $r_1(a,k,i_1)$ the equivalent for $M_1$ (where $i_1\in R^{n_1}$. In matrix notation the expected average reward of executing $a$ for $k$ times in the two MDPs is

$$r_1(a,k,i_1)=\frac{1}{k}\sum _{i=1}^k{R}_1^{\top }\times \left(T_1\right(a){)}^i\times i_1$$

and

$$r_2(a,k,i_2)=\frac{1}{k}\sum _{i=1}^k\left(R_1^{\top }\varphi \right)\times T_2(a{)}^i\times i_2$$

Then $r_2(a,k,i_2)=r_1(a,k,M{i}_2)$, where $M\in R^{n_1\times n_1}$ and therefore $M{i}_1$ is a linear transformation of the distribution over initial states.

Proof.$r_2(a,k,i_2)$ can be expanded and simplified to

$$\begin{array}{cc}& r_2(a,k,i_2)=\\ & \frac{1}{k}\sum _{i=1}^k\left(R_1^{\top }\varphi \right)\times T_2(a{)}^i\times i_2=\\ & \frac{1}{k}\sum _{i=1}^k\left(R_1^{\top }\varphi \right)\times \left(\psi T_1\right(a)\varphi {)}^i\times (i_2^{\top }\varphi {)}^{\top }=\\ & \frac{1}{k}\sum _{i=1}^k{R}_1^{\top }\times T_1(a{)}^i\varphi \times {\varphi }^{\top }{i}_1=\\ & \frac{1}{k}\sum _{i=1}^k{R}_1^{\top }\times T_1(a{)}^i\times \varphi {\varphi }^{\top }\times i_2=\\ & r_1(a,k,\varphi {\varphi }^{\top }{i}_2)\end{array}$$

◻

Conjecture 6. There exists a linear function $f\left(x\right)=ax+b$ so that for any $a\in A$, $k\in N$, it holds that $r_2(a,k,i_2)=f\left(r_1\right(a,k,i_1\left)\right)$.

Disadvantages

The approach de Blanc outlines has some limitations. As they remark, their setting of what they call “finite state models” is a fairly restrictive class of computational models of the environment. Similarly, MDPs are also not able to represent some environments, especially ones in which observations of states carry uncertainty.

They also remark that BisimulateShift “is not computationally tractable for large ontologies”, and their lack of clarity on the exact algorithm used (as well as the absence of any formal analysis of their method) makes it difficult to judge the computational complexity of the problem. It might be fruitful to study the convergence behavior of using different optimization procedures for finding $\varphi$ and $\psi$ to make further statements about the computational complexity of BisimulateShift.

Finally, the setting of a “finite state model” or an MDP can’t encode certain types of consistent preferences. Let $M=(S=\{s,s^{\prime }\},A=\{a_1,a_2\},I,P,R)$, where $P(s,a_1,s^{\prime })=P(s^{\prime },a_1,s)=P(s,a_2,s)=P(s^{\prime },a_2,s^{\prime })=1$ (that is $a_1$ causes the agent to switch states, and $a_2$ is the action where the agent stays in the same state).

Let now $t_1,t_2\in (S\times A{)}^k\times S$ be two trajectories in $M$, namely $t_1=(s,a_1,s^{\prime },a_1,s,a_2,s)$ and $t_2=(s,a_2,s,a_1,s^{\prime },a_1,s)$. Then the cumulative reward of both trajectories is the same, no matter the reward function: $R\left(t_1\right)=R(s,a_1,s^{\prime })+R(s^{\prime },a_1,s)+R(s,a_2,s)=R(s,a_2,s)+R(s,a_1,s^{\prime })+R(s^{\prime },a_1,s)=R\left(t_2\right)$. However, intuitively there should way a way to differently value these two trajectories: It should be possible to value be in $s^{\prime }$ earlier rather than later.

Using Inconsistent Preferences to Represent Ontological Crises

The framework of representing preferences as edge-weighted directed graphs on a set $\Omega$ of vertices, and consistent preferences as the set of edge-weighted acyclic tournaments on a set of deterministic options $\Omega$, can be used to represent ontological shifts.

Definition 17. Given a consistent edge-weighted graph $G=(\Omega ,E_G,w)$, a graph-based ontological shift is a function from $\Omega$ to subsets of a new set of options $\Xi$, together with coefficients: $s:\Omega \to P(\Xi \times [0,1\left]\right)$, where $(\xi ,c)\in s\left(\omega \right)$ means that $\omega \in \Omega$ in the old set of options turned out to be $\xi \in \Xi$ to the degree $c$. The larger $c$, the more $\omega$ is $\xi$.

In this text, I will assume that $\forall \omega \in \Omega :0\le {\sum }_{(\xi ,c)\in s\left(\omega \right)}c\le 1$.

If the coefficients of the image of $\omega$ sum to 1, that means that $\omega$ has been completely “ported over” to $\Xi$. If they sum to less than 1, that means that $\omega$ was a (partially) confused concept, if the coefficients in the image sum to 0 (or $s\left(\omega \right)=\varnothing$), that means that $\omega$ was a wholly confused concept and does not actually exist. If the sum of the coefficients are $>1$, that means that $\omega$ turned out to be “more real” than in the old set of options (which we exclude as an option here).

Definition 18. Given $G$, the result $G^{\star }=(\Xi ,E^{\star },w^{\star }:\Xi \times \Xi \to R)$ after a graph-based ontological shift $s$ is an edge-weighted graph.

The output of the function $t$ is a combination of the weights $w$ of $G$ and the coefficients of $s$ (for all ${\omega }_1,{\omega }_2$):

$$t({\xi }_1,{\xi }_2,G,s)=\sum _{({\omega }_1,{\omega }_2)\in E}\sum _{({\xi }_1,c_1)\in s\left({\omega }_1\right),({\xi }_2,c_2)\in s\left({\omega }_2\right)}{c}_1\cdot c_2\cdot w({\omega }_1,{\omega }_2)$$

Then for all ${\xi }_1,{\xi }_2$ the value of $w^{\star }({\xi }_1,{\xi }_2)=t({\xi }_1,{\xi }_2,G,s)$.

Example 3. Let $\Omega =\{L\text{(Land animals)},A\text{(Air animals)},W\text{(Water animals)}\}$, and the current preference prefer land animals over air animals over water animals, that is $E_G=\{L\stackrel{1}{\to }A,L\stackrel{1}{\to }W,A\stackrel{2}{\to }W\}$.

Let now $\Xi =\{M\text{(Mammals)},B\text{(Birds)},F\text{(Fish)},I\text{(Insects)}\}$ be a set that better represents the available options, and let $s$ be

$$\begin{array}{cc}& s\left(L\right)=\left\{\right(M,0.5),(I,0.5\left)\right\}\\ & s\left(A\right)=\left\{\right(B,0.45),(I,0.45),(M,0.1\left)\right\})\\ & s\left(W\right)=\left\{\right(F,0.9),(M,0.1\left)\right\}\end{array}$$

That is, land animals turn out to be half mammals, half insects, air animals are mostly birds and insects, and few mammals, and water animals are mostly fishes, and few mammals.

(Ignoring, for the sake of simplicity of the example, exocoetidae^[8] and aquatic insects).

The initial preference $G$, as an edge-weighted graph.	$G^{\ast }$, after applying the ontological shift $s$ and determining the edge weights using $t$. Positive 3-cycle in red.	$G^{\prime }$ after applying a procedure for resolving the inconsistent preference $G^{\ast }$, in this case using HodgeRank.

Undergoing an ontological shift $s$ and then resolving the ontological crisis using HodgeRank. In the right image transitive correctly weighted edges are ommitted for readability.

The procedure for resolving ontological crises by representing them as inconsistent preferences is in pseudocode below as ResolveShift. The algorithm takes a consistent edge-weighted graph $G$, a graph-based ontological shift $s$ mapping elements from $\Omega$ to a new set $\Xi$, together with coefficients, and a method for resolving inconsistent preferences on edge-weighted graphs.

It then creates a new graph $G^{\star }$, mapping all nodes using $s$ and creating new edges using the existing weights and coefficients with the function $t$ explained above. Finally, $G^{\star }$ is resolved into a consistent preference with the method Resolve (which may be specified externally, e.g. by using HodgeRank or dropping the weights and using EGEDmin).

function ResolveShift(G, s, Resolve)
    E*=∅, w*=0
    for (ω₁, ω₂)∈E
        for (ξ₁, c₁)∈s(ω₁), (ξ₂, c₂)∈s(ω₂)
            w*(ξ₁, ξ₂)=w*(ξ₁, ξ₂)+c₁·c₂·w(ω₁, ω₂)
            E*=E*∪{(ξ₁, ξ₂)}
    G'=Resolve(G*)
    return G'

Resolving an ontological shift $s$ on an edge-weighted directed graph.$G$ is a tuple $(\Omega ,E,w)$, and $s$ is of type $\Omega \to P(\Xi \times [0,1\left]\right)$.

Advantages

An advantage of ResolveShift over BisimulateShift is the set of preferences that can be represented by $G$ and $G^{\prime }$. If $\Omega$ is the set of all finite sequences of state-action pairs $\left(\right(S\times A{)}^k\times S{)}_{k\ge 0}$ then $t_1=(s,a_1,s^{\prime },a_1,s,a_2,s)$ and $t_2=(s,a_2,s,a_1,s^{\prime },a_1,s)$ are two different elements in $\Omega$, and a preference of $t_1$ over $t_2$ can be represented e.g. with an edge $t_1\to t_2$ in $E$.

A further advantage of ResolveShift is that it has a polynomial runtime complexity of $O(|E|\cdot m^2)$, which is a subset of the functions in $O(n^2\cdot m^2)$ (with $n=|\Omega |$, and $m=|\Xi |$), unlike BisimulateShift, which offers no such guarantees.

Disadvantages

If the dynamics (e.g. the transition function) of the elements of $\Xi$ are known, then BisimulateShift is able to use this information to construct $R_2$. Additionally, if no mapping $s$ from $\Omega$ to $\Xi$ exists (that is, only $\Omega$ and $\Xi$ are known, but their relations are not), then ResolveShift is not applicable.

Definition 19. Let $f:G\to S$ be a method for resolving inconsistent preferences represented by edge-weighted graphs, and let $s_1,s_2,\dots ,s_n$ (with $s_i:{\Omega }_i\to P\left({\Omega }_{i+1}\right)\times [0,1]$) be a family of functions describing ontological shifts.

Let $g_1,g_2,\dots ,g_n$ be a family of functions that return the result of ResolveShift using the shift function $s_i$ for $g_i$, but without executing a resolution procedure: $g_i\left(G_i\right)=ResolveShift(G_i,s_i,\text{id})$, where $\text{id}:P_{{\Omega }_{i+1}}\to P_{{\Omega }_{i+1}}$ is the identity function.

Let $G_1=({\Omega }_1,E_1,w_1)$ be any arbitrary consistent preference on ${\Omega }_1$.

Then $f$ is distributive over ontological shifts if and only if

$$(f\circ g_n\circ \cdots \circ g_2\circ g_1)\left(G_1\right)=(f\circ g_n\circ f\circ \cdots \circ f\circ g_2\circ f\circ g_1)\left(G_1\right)$$

Intuitively, this condition says that it shouldn’t matter whether an agent changes their mind on which things exist to have preferences over multiple times, and then resolves the resulting preferences into consistent ones, or resolve their preferences after each time they undergo an ontological shift $s_i$.

Proposition 5.HodgeRank is not distributive over ontological shifts.

Proof. It is easy to find examples where HodgeRank is not distributive over ontological shifts.

Let $G_1=(\Omega =\{a,b\},E=\{\left(a\stackrel{1}{\to }b\right)\left\}\right)$. Let $s_1\left(a\right)=\left\{\right(d,0.28\left)\right\}$, $s_1\left(b\right)=\left\{\right(c,0.57),(e,0.43\left)\right\}$. And let $s_2\left(c\right)=\left\{\right(f,0.014\left)\right\}$, $s_2\left(d\right)=\left\{\right\}$, and $s_2\left(e\right)=\left\{\right(f,0.34),(g,0.66\left)\right\}$.

Then Figure 17 shows applying the two ontological shifts $s_1,s_2$, and resolving in the end using HodgeRank, and Figure 21 shows applying HodgeRank after $s_1$ and then again after $s_2$. The final graphs have different weights.

The initial preference $G_1$, as an edge-weighted graph.	The unresolved preference $g_1\left(G_1\right)$.	$g_2\left(g_1\right(G_1\left)\right)$, which has no edges.	Resolving $g_2\left(g_1\right(G_1\left)\right)$ using HodgeRank results in a graph in which there is indifference between the vertices $f$ and $g$.

---

The initial preference $G_1$.	$HodgeRank\left(g_1\right(G_1\left)\right)$, which has an edge between $e$ and $c$, unlike the result of just $g_1\left(G_1\right)$.	The final preference, $(HodgeRank\circ g_2\circ HodgeRank\circ g_1)\left(G_1\right)$ is not indifferent between $f$ and $g$, and slightly prefers $f$.

◻

This example works because $d$ gets “deleted” from the set of options, so having all preferences depend on $d$ without resolving the incomparability between $c$ and $e$ results in there being no preference, while resolving retains a slight preference of $e$ over $c$, which remains with $f$ and $g$.

Conjecture 7. There is a resolution function $f$ for edge-weighted graphs that is distributive over ontological shifts in this framework.

Conclusion

In this investigation, we have identified the problem of resolving preferences that are inconsistent under the von Neumann-Morgenstern framework.

We first examined the restricted case of preferences over deterministic options, using directed graphs as an underlying mathematical structure to represent inconsistent preferences. We proposed two algorithms: EGEDmin and HodgeResolve (based on the HodgeRank algorithm). We analyzed both algorithms on several different criteria, with no clear winner.

We also proved that the criteria Resolution to Polynomially Many Preferences and Preservation of Consistent Subgraphs are incompatible, as well as Resolution to Polynomially Many Preferences and Polynomial Time Complexity.

For inconsistent preferences over lotteries, we examined a representation using edge-weighted directed graphs. This representation is inadequate, as it can not encode all possible inconsistent preferences, most notably the violation of independence observed in the Allais paradox.

We nevertheless reviewed the HodgeRank algorithm that allows for resolving inconsistent edge-weighted directed graphs into utility functions, and observe that HodgeRank has several desirable properties, and that it also fails to conform to the (hard to fulfill) criterion of strategy-freeness from social choice theory.

We then connected inconsistent preferences to the little-explored issue of ontological crises, and offered a new perspective on what to do after a change with a set of objects that a preference was defined over, opening up many questions we didn’t have the time to solve.

Further Research

We believe that the topics discussed in this text offer some fruitful lines of inquiry into the mathematical structure of wanting.

On a concrete level we stated several conjectures and questions we were not able to prove, but might be relatively easy to answer. Of these, conjecture 5{reference-type=”ref” reference=”conj:hodgedom”} on whether HodgeResolve fulfills Preservation of Complete Domination is most relevant, but conjecture 1{reference-type=”ref” reference=”conj:avgconftoinf”} and conjecture 2{reference-type=”ref” reference=”conj:egednosubpres”} might also be interesting from graph-theoretic perspective.

Additionally, we only analysed two methods of mapping from directed graphs to acyclic tournaments, but are convinced that there are many other methods that could be investigated, specifically methods that use different methods of evaluating graph similarity or ones that result in weak orderings, or methods that are selected to preserve as many inclusion-maximal consistent subgraphs as possible.

Resolving inconsistent graphs could also be approached from a different perspective using random walks on the graph, breaking cycles and completing edges as they are encountered. An extension of this setup could involve two agents: One trying to resolve its preferences through a process of breaking cycles as it traverses the graph representing its preferences, and an adversary attempting to money-pump the agent. This setup also is amenable for an analysis of money-pumping under the light of computational complexity: which violations of the von Neumann-Morgenstern axioms are computationally easy or hard to find, and what is the attack/​defense balance between finding and exploiting such violations?

In the context of preferences over lotteries, we are left with no satisfactory mathematical structure that we can use: edge-weighted graphs are not expressive enough, and arbitrary relations over all lotteries too unwieldy. Finding such a structure or finding a method for resolving arbitrary relations over lotteries would be helpful for further progress. Inspiration could be found in models of human decision making from mathematical psychology, such as the Priority Heuristic and the Random Utility Model from Gamal 2013 and the BEAST model Erev et al. 2017, as well as alternatives to the utility framework from decision theory, such as risk-weighted utility maximization or the Jeffrey-Bolker axioms Buchak 2013, Jeffrey 2004.

The problem of ontological crises appears under-researched. As a first step, BisimulateShift could be extended to POMDPs, but finding out how real-world systems change their internal representations during learning could be valuable, with Nanda et al. being a fascinating analysis of the toy case of modular addition in neural networks Nanda et al. 2023. This question could also be interesting for social scientists (discovering how humans manage ontological crises in practice) and philosophers.

We would also like to see further exploration of value-learning Dewey 2011 of inconsistent preferences, perhaps extending Evans et al. to allow for a larger diversity of inconsistent preferences Evans et al. 2016.

Acknowledgements

This text has been long in the making, and has benefitted from much advice and input. I thank Holger Dell for his help and suggestions. I’d also like to thank the Crystal Healing Group for their inputs, especially Kaarel Hänni for the gentle introduction to Hodge decomposition, and Alexander Gietelink-Oldenziel for the hours of talking about decomposing irrational preferences into rational ones. I also want to thank Felix Harder for help with the impossibility result, and Filip Sondej for his surprising ideas in the lottery case.

Appendix A: Hints in Prior Texts

Starting from a state of arbitrary incoherence and moving iteratively in one of many pro-coherence directions produced by whatever whacky mind you currently have isn’t obviously guaranteed to increasingly approximate maximization of some sensical utility function. For instance, take an entity with a cycle of preferences, apples > bananas = oranges > pears > apples. The entity notices that it sometimes treats oranges as better than pears and sometimes worse. It tries to correct by adjusting the value of oranges to be the same as pears. The new utility function is exactly as incoherent as the old one.

—Katja Grace, “Counterarguments to the basic AI x-risk case”, 2022

---

1. ↩︎

   The notation for lotteries is common in social choice theory Gaertner 2009, ch. 8.2. Some sources would instead write this as $p_1\cdot {\omega }_1+p_2\cdot {\omega }_2$ von Neumann & Morgenstern, 1947, but I have decided against it, since no addition is actually taking place.

2. ↩︎

   Unless further specified, in this text it will always be the case that the nodes of $G$ are called $\Omega$ and its edges are called $E$.

3. ↩︎

   Sample size too small.

4. ↩︎

   Without reflexive edges $(\xi ,\xi )\in E$.

5. ↩︎

   This definition allows for there to be graph $G$, a consistent subgraph $S_G$ of $G$ and resolved weakly consistent graph $W=(\Omega ,E_W)\in f\left(G\right)$ such that there exist nodes ${\omega }_1,{\omega }_2\in \Omega$ in $S_G$ which are not strictly ordered in $W$, that is both ${\omega }_1\to {\omega }_2\in E_W$ and ${\omega }_2\to {\omega }_1\in E_W$. It is possible to define a stronger criterion, Strict Preservation of Consistent Subgraphs, which requires that for such ${\omega }_1,{\omega }_2$ only the edge ${\omega }_1\to {\omega }_2$ being present in $E_W$, but we will not work with that definition here.

6. ↩︎

   Only if the output is allowed to be a weak ordering.

7. ↩︎

   Russell and Norvig note that sometimes $R$ takes actions into account as well: $R:S\times A\times S\to R$ (with different rewards for transitioning to a state with different actions), but also notes that this merely simplifies the description of some environments, but doesn’t change which environments can be described Russell & Norvig 2010, ch. 17.

8. ↩︎

   Also known as flying fish.

[niplav]

Submission statement: I mostly finished this a year ago, but held off on posting because I was planning on improving it and writing a corresponding “here’s the concepts without the math” post. Might still happen, but now I’m not aiming at a specific timeline.

Things I now want to change:

• Soften the confidence in the vNM axioms, since there’s been some good criticisms

• Revamp the whole ontological crisis section to be more general

• Rewrite from academese to easier

• Move proofs to an appendix

• Create some manim videos to illustrate

• Merge with this post

• Many other things

Still, I hope this is kinda useful for some people.

Edit: Also, there’s some issues with the MathJax and dollar signs, I will fix this later.

[Charlie Steiner]

Nice, especially the second half.

To me, this post makes it seem like the natural place to push forward is to try and restrict incoherent policies over lotteries until they’re just barely well-behaved—either on the behavior end (continuity etc) or the algorithmic end (compte budgets etc).

[Alexander Gietelink Oldenziel]

Great work niplav !

Happy to see you’ve pushed through and finished this monumental piece of work =)

[rain8dome9]

Is this a paper? Has it been published anywhere?

[niplav]

Not published anywhere except here and on my site.