Title: Double Threshold Digraphs,
Abstract: A semiorder is a model of preference relations where each element $x$ is
associated with a utility value $\alpha(x)$, and there is a threshold $t$ such
that $y$ is preferred to $x$ iff $\alpha(y) > \alpha(x)+t$. These are motivated
by the notion that there is some uncertainty in the utility values we assign an
object or that a subject may be unable to distinguish a preference between
objects whose values are close. However, they fail to model the well-known
phenomenon that preferences are not always transitive. Also, if we are
uncertain of the utility values, it is not logical that preference is
determined absolutely by a comparison of them with an exact threshold. We
propose a new model in which there are two thresholds, $t_1$ and $t_2$; if the
difference $\alpha(y) - \alpha(x)$ less than $t_1$, then $y$ is not preferred
to $x$; if the difference is greater than $t_2$ then $y$ is preferred to $x$;
if it is between $t_1$ and $t_2$, then then $y$ may or may not be preferred to
$x$. We call such a relation a double-threshold semiorder, and the
corresponding directed graph $G = (V,E)$ a double threshold digraph. Every
directed acyclic graph is a double threshold graph; bounds on $t_2/t_1$ give a
nested hierarchy of subclasses of the directed acyclic graphs. In this paper we
characterize the subclasses in terms of forbidden subgraphs, and give
algorithms for finding an assignment of of utility values that explains the
relation in terms of a given $(t_1,t_2)$ or else produces a forbidden subgraph,
and finding the minimum value $\lambda$ of $t_2/t_1$ that is satisfiable for a
given directed acyclic graph. We show that $\lambda$ gives a measure of the
complexity of a directed acyclic graph with respect to several optimization
problems that are NP-hard on arbitrary directed acyclic graphs.