Semiorder

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 Duncan Luce (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.

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).

Definition

Axiom 2

Axiom 3

Let X be a set of items, and let < be a binary relation on X. Items x and y are said to be incomparable, written here as x ~ y, if neither x < y nor y < x is true. Then the pair (X,<) is a semiorder if it satisfies the following three axioms:[1]

1. For all x and y, it is not possible for both x < y and y < x to be true. That is, < must be an asymmetric relation
2. For all x, y, z, and w, if x < y, y ~ z, and z < w, then x < w.
3. For all x, y, z, and w, if x < y and y < z, then either x < w or w < z. Equivalently, with the same assumptions on x, y, z, every other item w must be comparable to at least one of x, y, or z.

It follows from the first axiom that x ~ x, and therefore the second axiom (with y = z) implies that < is a transitive relation.

Relation to other kinds of order

Partial orders

One may define a partial order (X,≤) from a semiorder (X,<) by declaring that x ≤ y whenever either x < y or x = y. Of the axioms that a partial order is required to obey, reflexivity (x ≤ x) follows automatically from this definition, antisymmetry (if x ≤ y and y ≤ x then x = y) follows from the first semiorder axiom, and transitivity (if x ≤ y and y ≤ z then x ≤ z) follows from the second semiorder axiom. Conversely, from a partial order defined in this way, the semiorder may be recovered by declaring that x < y whenever x ≤ y and x ≠ y. The first of the semiorder axioms listed above follows automatically from the axioms defining a partial order, but the others do not. The second and third semiorder axioms forbid partial orders of four items forming two disjoint chains: the second axiom forbids two chains of two items each, while the third item forbids a three-item chain with one unrelated item.

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 vertice is incomparable to its two closest left neighbors, but they are comparable.

Interval orders

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,[2] semi-orders were examined by Dean T. Jamison and Lawrence J. Lau[3] and found to be a special case of quasitransitive relations. In fact, every semiorder is a quasitransitive relation, since it is a transitive one. Moreover, adding to a given semiorder all its pairs of incomparable items keeps the resulting relation a quasitransitive one.[4]

Utility theory

The original motivation for introducing semiorders was to model human preferences without assuming (as strict weak orderings do) that incomparability is a transitive relation. For instance, if x, y, and z represent three quantities of the same material, and x and z differ by the smallest amount that is perceptible as a difference, while y is halfway between the two of them, then it is reasonable for a preference to exist between x and z but not between the other two pairs, violating transitivity.[5]

Thus, suppose that X is a set of items, and u is a utility function that maps the members of X to real numbers. A strict weak ordering can be defined on x by declaring two items to be incomparable when they have equal utilities, and otherwise using the numerical comparison, but this necessarily leads to a transitive incomparability relation. Instead, if one sets a numerical threshold (which may be normalized to 1) such that utilities within that threshold of each other are declared incomparable, then a semiorder arises.

Specifically, define a binary relation < from X and u by setting x < y whenever u(x) ≤ u(y) − 1. Then (X,<) is a semiorder.[6] It may equivalently be defined as the interval order defined by the intervals [u(x),u(x) + 1].[7]

In the other direction, not every semiorder can be defined from numerical utilities in this way. For instance, if a semiorder (X,<) includes an uncountable totally ordered subset then there do not exist sufficiently many sufficiently well-spaced real-numbers to represent this subset numerically. However, every finite semiorder can be defined from a utility function.[8] Fishburn (1973) supplies a precise characterization of the semiorders that may be defined numerically.

If a semiorder is given only in terms of the order relation between its pairs of elements, then it is possible to construct a utility function that represents the order in time O(n²), where n is the number of elements in the semiorder.[9]

Combinatorial enumeration

The number of distinct semiorders on n unlabeled items is given by the Catalan numbers

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

while the number of semiorders on n labeled items is given by the sequence

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

Other results

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

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.[13]

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 x and y such that x appears earlier than y in between 1/3 and 2/3 of the linear extensions of the semiorder.[14]

The set of semiorders on an n-element set is well-graded: if two semiorders on the same set differ from each other by the addition or removal of k order relations, then it is possible to find a path of 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.[15]

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

Notes

1. Luce (1956) describes an equivalent set of four axioms, the first two of which combine the definition of incomparability and the first axiom listed here.
2. Amartya K. Sen (Jul 1971). "Choice Functions and Revealed Preference" (PDF). The Review of Economic Studies. 38 (3): 307–317. Here: Sect.10, p.314
3. Dean T. Jamison and Lawrence J. Lau (Jul 1970). Semiorders, Revealed Preference, and the Theory of the Consumer Demand (Technical Report No.31). Stanford University, Institute for Mathematical Studies in the Social Sciences. Presented at the World Economics Congress, Cambridge, Sep 1970.
4. Jochen Burghardt (Nov 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036v2. Here: Lemma 20, p.27. 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.
5. Luce (1956), p. 179.
6. 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.
7. Fishburn (1970).
8. This result is typically credited to Scott & Suppes (1958); see, e.g., Rabinovitch (1977). However, Luce (1956), Theorem 2 proves a more general statement, that a finite semiorder can be defined from a utility function and a threshold function whenever a certain underlying weak order can be defined numerically. For finite semiorders, it is trivial that the weak order can be defined numerically with a unit threshold function.
9. Avery (1992).
10. Kim & Roush (1978).
11. Chandon, Lemaire & Pouget (1978).
12. Rabinovitch (1978).
13. Fishburn & Trotter (1992).
14. Brightwell (1989).
15. Doignon & Falmagne (1997).
16. 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.
• 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.
• 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", J. 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", J. 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. (Oct 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: 178–191, doi:10.2307/1905751, JSTOR 1905751, MR 0078632.
• Rabinovitch, Issie (1977), "The Scott-Suppes theorem on semiorders", J. 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: 113–128, doi:10.2307/2964389, MR 0115919.

Further reading

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