Semiorder

The Hasse diagram of a semiorder. Two items are comparable when their vertical coordinates differ by at least one unit (the spacing between solid blue lines).

In order theory, a branch of mathematics, a semiorder is a type of ordering for items with numerical scores, where items with widely differing scores are compared by their scores and where scores within a given margin of error are deemed incomparable. Semiorders were introduced and applied in mathematical psychology by DuncanLuce  ( 1956 ) as a model of human preference. They generalize strict weak orderings, in which items with equal scores may be tied but there is no margin of error. They are a special case of partial orders and of interval orders, and can be characterized among the partial orders by additional axioms, or by two forbidden four-item suborders.

Utility theory

The original motivation for introducing semiorders was to model human preferences without assuming that incomparability is a transitive relation. For instance, suppose that ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ represent three quantities of the same material, and that ${\displaystyle x}$ is larger than ${\displaystyle z}$ by the smallest amount that is perceptible as a difference, while ${\displaystyle y}$ is halfway between the two of them. Then, a person who desires more of the material would prefer ${\displaystyle x}$ to ${\displaystyle z}$, but would not have a preference between the other two pairs. In this example, ${\displaystyle x}$ and ${\displaystyle y}$ are incomparable in the preference ordering, as are ${\displaystyle y}$ and ${\displaystyle z}$, but ${\displaystyle x}$ and ${\displaystyle z}$ are comparable, so incomparability does not obey the transitive law. ^[1]

To model this mathematically, suppose that objects are given numerical utility values, by letting ${\displaystyle u}$ be any utility function that maps the objects to be compared (a set ${\displaystyle X}$) to real numbers. Set a numerical threshold (which may be normalized to 1) such that utilities within that threshold of each other are declared incomparable, and define a binary relation ${\displaystyle <}$ on the objects, by setting ${\displaystyle x<y}$ whenever ${\displaystyle u(x)\leq u(y)-1}$. Then ${\displaystyle (X,<)}$ forms a semiorder. ^[2] If, instead, objects are declared comparable whenever their utilities differ, the result would be a strict weak ordering, for which incomparability of objects (based on equality of numbers) would be transitive. ^[1]

Axiomatics

Forbidden: two mutually incomparable two-point linear orders

Forbidden: three linearly ordered points and a fourth incomparable point

A semiorder, defined from a utility function as above, is a partially ordered set with the following two properties: ^[3]

• Whenever two disjoint pairs of elements are comparable, for instance as ${\displaystyle w<x}$ and ${\displaystyle y<z}$, there must be an additional comparison among these elements, because ${\displaystyle u(w)\leq u(y)}$ would imply ${\displaystyle w<z}$ while ${\displaystyle u(w)\geq u(y)}$ would imply ${\displaystyle y<x}$. Therefore, it is impossible to have two mutually incomparable two-point linear orders. ^[3]
• If three elements form a linear ordering ${\displaystyle w<x<y}$, then every fourth point ${\displaystyle z}$ must be comparable to at least one of them, because ${\displaystyle u(z)\leq u(x)}$ would imply ${\displaystyle z<y}$ while ${\displaystyle u(z)\geq u(x)}$ would imply ${\displaystyle w<z}$, in either case showing that ${\displaystyle z}$ is comparable to ${\displaystyle w}$ or to ${\displaystyle y}$. So it is impossible to have a three-point linear order with a fourth incomparable point. ^[3]

Conversely, every finite partial order that avoids the two forbidden four-point orderings described above can be given utility values making it into a semiorder. ^[4] Therefore, rather than being a consequence of a definition in terms of utility, these forbidden orderings, or equivalent systems of axioms, can be taken as a combinatorial definition of semiorders. ^[5] If a semiorder on ${\displaystyle n}$ elements is given only in terms of the order relation between its pairs of elements, obeying these axioms, then it is possible to construct a utility function that represents the order in time ${\displaystyle O(n^{2})}$, where the ${\displaystyle O}$ is an instance of big O notation. ^[6]

For orderings on infinite sets of elements, the orderings that can be defined by utility functions and the orderings that can be defined by forbidden four-point orders differ from each other. For instance, if a semiorder ${\displaystyle (X,<)}$ (as defined by forbidden orders) includes an uncountable totally ordered subset then there do not exist sufficiently many sufficiently well-spaced real-numbers for it to be representable by a utility function. Fishburn (1973) supplies a precise characterization of the semiorders that may be defined numerically. ^[7]

Relation to other kinds of order

Partial orders

One may define a partial order ${\displaystyle (X,\leq )}$ from a semiorder ${\displaystyle (X,<)}$ by declaring that ${\displaystyle x\leq y}$ whenever either ${\displaystyle x<y}$ or ${\displaystyle x=y}$. Of the axioms that a partial order is required to obey, reflexivity (${\displaystyle x\leq x}$) follows automatically from this definition. Antisymmetry (if ${\displaystyle x\leq y}$ and ${\displaystyle y\leq x}$ then ${\displaystyle x=y}$) follows from the first semiorder axiom. Transitivity (if ${\displaystyle x\leq y}$ and ${\displaystyle y\leq z}$ then ${\displaystyle x\leq z}$) follows from the second semiorder axiom. Therefore, the binary relation ${\displaystyle (X,\leq )}$ defined in this way meets the three requirements of a partial order that it be reflexive, antisymmetric, and transitive.

Conversely, suppose that ${\displaystyle (X,\leq )}$ is a partial order that has been constructed in this way from a semiorder. Then the semiorder may be recovered by declaring that ${\displaystyle x<y}$ whenever ${\displaystyle x\leq y}$ and ${\displaystyle x\neq y}$. Not every partial order leads to a semiorder in this way, however: The first of the semiorder axioms listed above follows automatically from the axioms defining a partial order, but the others do not. A partial order that includes four elements forming two two-element chains would lead to a relation ${\displaystyle (X,<)}$ that violates the second semiorder axiom, and a partial order that includes four elements forming a three-element chain and an unrelated item would violate the third semiorder axiom (cf. pictures in section #Axiomatics).

Weak orders

Every strict weak ordering < is also a semi-order. More particularly, transitivity of < and transitivity of incomparability with respect to < together imply the above axiom 2, while transitivity of incomparability alone implies axiom 3. The semiorder shown in the top image is not a strict weak ordering, since the rightmost vertex is incomparable to its two closest left neighbors, but they are comparable.

Interval orders

The semiorder defined from a utility function ${\displaystyle u}$ may equivalently be defined as the interval order defined by the intervals ${\displaystyle [u(x),u(x)+1]}$, ^[8] so every semiorder is an example of an interval order. A relation is a semiorder if, and only if, it can be obtained as an interval order of unit length intervals ${\displaystyle (\ell _{i},\ell _{i}+1)}$.

Quasitransitive relations

According to Amartya K. Sen, ^[9] semi-orders were examined by Dean T. Jamison and Lawrence J. Lau ^[10] and found to be a special case of quasitransitive relations. In fact, every semiorder is quasitransitive, ^[11] and quasitransitivity is invariant to adding all pairs of incomparable items. ^[12] Removing all non-vertical red lines from the topmost image results in a Hasse diagram for a relation that is still quasitransitive, but violates both axiom 2 and 3; this relation might no longer be useful as a preference ordering.

Combinatorial enumeration

The number of distinct semiorders on ${\displaystyle n}$ unlabeled items is given by the Catalan numbers ^[13]

$${\displaystyle {\frac {1}{n+1}}{\binom {2n}{n}},}$$

while the number of semiorders on ${\displaystyle n}$ labeled items is given by the sequence ^[14]

1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... (sequence A006531 in the OEIS)

Other results

Any finite semiorder has order dimension at most three. ^[15]

Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are semiorders. ^[16]

Semiorders are known to obey the 1/3–2/3 conjecture: in any finite semiorder that is not a total order, there exists a pair of elements ${\displaystyle x}$ and ${\displaystyle y}$ such that ${\displaystyle x}$ appears earlier than ${\displaystyle y}$ in between 1/3 and 2/3 of the linear extensions of the semiorder. ^[3]

The set of semiorders on an ${\displaystyle n}$-element set is well-graded: if two semiorders on the same set differ from each other by the addition or removal of ${\displaystyle k}$ order relations, then it is possible to find a path of ${\displaystyle k}$ steps from the first semiorder to the second one, in such a way that each step of the path adds or removes a single order relation and each intermediate state in the path is itself a semiorder. ^[17]

The incomparability graphs of semiorders are called indifference graphs, and are a special case of the interval graphs. ^[18]

Notes

1. Luce (1956), p. 179.
2. Luce (1956), Theorem 3 describes a more general situation in which the threshold for comparability between two utilities is a function of the utility rather than being identically 1; however, this does not lead to a different class of orderings.
3. Brightwell (1989).
4. This result is typically credited to Scott & Suppes (1958); see, e.g., Rabinovitch (1977).
5. Luce (1956 , p. 181) used four axioms, the first two of which combine asymmetry and the definition of incomparability, while each of the remaining two is equivalent to one of the above prohibition properties.
6. Avery (1992).
7. Fishburn (1973).
8. Fishburn (1970).
9. Sen (1971 , Section 10, p. 314) Since Luce modelled indifference between x and y as "neither xRy nor yRx", while Sen modelled it as "both xRy and yRx", Sen's remark on p.314 is likely to mean the latter property.
10. Jamison & Lau (1970).
11. since it is transitive
12. more general, to adding any symmetric relation
13. Dean & Keller (1968); Kim & Roush (1978)
14. Chandon, Lemaire & Pouget (1978).
15. Rabinovitch (1978).
16. Fishburn & Trotter (1992).
17. Doignon & Falmagne (1997).
18. Roberts (1969).

References

• Avery, Peter (1992), "An algorithmic proof that semiorders are representable", Journal of Algorithms, 13 (1): 144–147, doi:10.1016/0196-6774(92)90010-A, MR   1146337 .
• Brightwell, Graham R. (1989), "Semiorders and the 1/3–2/3 conjecture", Order , 5 (4): 369–380, doi:10.1007/BF00353656, S2CID   86860160 .
• Chandon, J.-L.; Lemaire, J.; Pouget, J. (1978), "Dénombrement des quasi-ordres sur un ensemble fini", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (62): 61–80, 83, MR   0517680 .
• Dean, R. A.; Keller, Gordon (1968), "Natural partial orders", Canadian Journal of Mathematics, 20: 535–554, doi: 10.4153/CJM-1968-055-7 , MR   0225686 .
• Doignon, Jean-Paul; Falmagne, Jean-Claude (1997), "Well-graded families of relations", Discrete Mathematics, 173 (1–3): 35–44, doi: 10.1016/S0012-365X(96)00095-7 , MR   1468838 .
• Fishburn, Peter C. (1970), "Intransitive indifference with unequal indifference intervals", Journal of Mathematical Psychology, 7: 144–149, doi:10.1016/0022-2496(70)90062-3, MR   0253942 .
• Fishburn, Peter C. (1973), "Interval representations for interval orders and semiorders", Journal of Mathematical Psychology, 10: 91–105, doi:10.1016/0022-2496(73)90007-2, MR   0316322 .
• Fishburn, Peter C.; Trotter, W. T. (1992), "Linear extensions of semiorders: a maximization problem", Discrete Mathematics, 103 (1): 25–40, doi: 10.1016/0012-365X(92)90036-F , MR   1171114 .
• Jamison, Dean T.; Lau, Lawrence J. (Sep 1973), "Semiorders and the Theory of Choice", Econometrica, 41 (5): 901–912, doi:10.2307/1913813, JSTOR   1913813 .
• Jamison, Dean T.; Lau, Lawrence J. (Sep–Nov 1975), "Semiorders and the Theory of Choice: A Correction", Econometrica, 43 (5–6): 979–980, doi:10.2307/1911339, JSTOR   1911339 .
• Jamison, Dean T.; Lau, Lawrence J. (July 1970), Semiorders, Revealed Preference, and the Theory of the Consumer Demand, Stanford University, Institute for Mathematical Studies in the Social Sciences. Presented at the World Economics Congress, Cambridge, Sep 1970.
• Jamison, Dean T.; Lau, Lawrence J. (October 1977), "The nature of equilibrium with semiordered preferences", Econometrica, 45 (7): 1595–1605, doi:10.2307/1913952, JSTOR   1913952 .
• Kim, K. H.; Roush, F. W. (1978), "Enumeration of isomorphism classes of semiorders", Journal of Combinatorics, Information &System Sciences, 3 (2): 58–61, MR   0538212 .
• Luce, R. Duncan (1956), "Semiorders and a theory of utility discrimination" (PDF), Econometrica, 24 (2): 178–191, doi:10.2307/1905751, JSTOR   1905751, MR   0078632 .
• Rabinovitch, Issie (1977), "The Scott-Suppes theorem on semiorders", Journal of Mathematical Psychology, 15 (2): 209–212, doi:10.1016/0022-2496(77)90030-x, MR   0437404 .
• Rabinovitch, Issie (1978), "The dimension of semiorders", Journal of Combinatorial Theory, Series A, 25 (1): 50–61, doi: 10.1016/0097-3165(78)90030-4 , MR   0498294 .
• Roberts, Fred S. (1969), "Indifference graphs", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 139–146, MR   0252267 .
• Scott, Dana; Suppes, Patrick (1958), "Foundational aspects of theories of measurement", The Journal of Symbolic Logic, 23 (2): 113–128, doi:10.2307/2964389, JSTOR   2964389, MR   0115919 .
• Sen, Amartya K. (July 1971), "Choice Functions and Revealed Preference" (PDF), The Review of Economic Studies , 38 (3): 307–317, doi:10.2307/2296384, JSTOR   2296384 .

Further reading

• Pirlot, M.; Vincke, Ph. (1997), Semiorders: Properties, representations, applications, Theory and Decision Library. Series B: Mathematical and Statistical Methods, vol. 36, Dordrecht: Kluwer Academic Publishers Group, ISBN   0-7923-4617-3, MR   1472236 .