Double Semiorders and Double Indifference Graphs

• Published in: SIAM journal on matrix analysis and applications 1982-12, Vol.3 (4), p.566
• Main Authors: Cozzens, Margaret B, Roberts, Fred S
• Format: Article
• Language: English
• Subjects: Assignment problem; Graph coloring; Mathematical functions; Preferences; Social sciences; Transmitters
• ISSN: 0895-4798; 1095-7162
• DOI: 10.1137/0603058

The notion of semiorder was introduced by Luce in 1956 as a model for preference in the situation where indifference judgments are nontransitive. The notion of indifference graph was introduced by Roberts in 1968 as a model for nontransitive indifference. Motivated by problems of measurement and serration in the social sciences and by frequency assignment problems in communications, we discuss generalizations called double semiorders and double indifference graphs. Semiorders are exactly the binary relations $(A,P)$ such that there is a real-valued function $f$ on $A$ satisfying $xPy$ iff $f ( x ) > f ( y ) + \delta $, where $\delta$ is a fixed positive number. Indifference graphs are exactly the graphs $( V,E )$ such that there is a real-valued function $f$ on $V$ satisfying $\{ x,y \} \in E$ iff $| f ( x ) > f ( y ) | \leqq \delta $. Suppose $\delta _1 > \delta _2 > 0$. We present conditions on a pair of binary relations $( A,P_1 )$ and $( A,P_2 )$ necessary and sufficient for the existence of a real-valued function $f$ on $A$ satisfying $xP_i y$ iff $f ( x ) > f ( y ) + \delta _i $, $i = 1,2$. These lead to conditions on $( V,E_1 )$ and $( V,E_2 )$ necessary and sufficient for the existence of a real-valued function $f$ on $V$ satisfying $\{ x,y \} \in E_i $ iff $| f ( x ) - f ( y ) |\leqq \delta _i,\, i = 1,2$.