semiorder

File:Semiorder.svg 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 {{harvs|first=Duncan|last=Luce|authorlink=R. Duncan Luce|year=1956|txt}} 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 $x$ , $y$ , and $z$ represent three quantities of the same material, and that $x$ is larger than $z$ by the smallest amount that is perceptible as a difference, while $y$ is halfway between the two of them. Then, a person who desires more of the material would prefer $x$ to $z$ , but would not have a preference between the other two pairs. In this example, $x$ and $y$ are incomparable in the preference ordering, as are $y$ and $z$ , but $x$ and $z$ are comparable, so incomparability does not obey the transitive law.{{sfnp|Luce|1956|p=179}}

To model this mathematically, suppose that objects are given numerical utility values, by letting $u$ be any utility function that maps the objects to be compared (a set $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 $<$ on the objects, by setting $x whenever u(x)\le u(y)-1 . Then (X,<) forms a semiorder. {{harvtxt|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.$

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.{{sfnp|Luce|1956|p=179}}

Axiomatics

{{multiple image | total_width=300

|image1 = Suborder 2.svg

|caption1=Forbidden: two mutually incomparable two-point linear orders

|alt1= Two mutually incomparable two-point linear orders

|image2=Suborder 1.svg

|caption2=Forbidden: three linearly ordered points and a fourth incomparable point

|alt2= A three-point linear order, with a fourth incomparable point

}}

A semiorder, defined from a utility function as above, is a partially ordered set with the following two properties:{{sfnp|Brightwell|1989}}

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

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.

This result is typically credited to {{harvtxt|Scott|Suppes|1958}}; see, e.g., {{harvtxt|Rabinovitch|1977}}. 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.{{harvtxt|Luce|1956|page=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. If a semiorder on $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 $O(n^2)$ , where the $O$ is an instance of big O notation.{{sfnp|Avery|1992}}

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 $(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. {{harvtxt|Fishburn|1973}} supplies a precise characterization of the semiorders that may be defined numerically.{{sfnp|Fishburn|1973}}

Relation to other kinds of order

=Partial orders=

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

Conversely, suppose that $(X,\le)$ is a partial order that has been constructed in this way from a semiorder. Then the semiorder may be recovered by declaring that $x whenever x\le y and x\ne 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 (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 $u$ may equivalently be defined as the interval order defined by the intervals $[u(x),u(x)+1]$ ,{{sfnp|Fishburn|1970}} 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 $(\ell _{i},\ell _{i}+1)$ .

=Quasitransitive relations=

According to Amartya K. Sen,{{harvtxt|Sen|1971|loc=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. semi-orders were examined by Dean T. Jamison and Lawrence J. Lau{{sfnp|Jamison|Lau|1970}} and found to be a special case of quasitransitive relations. In fact, every semiorder is quasitransitive,since it is transitive and quasitransitivity is invariant to adding all pairs of incomparable items.more general, to adding any symmetric relation 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 $n$ unlabeled items is given by the Catalan numbers{{harvtxt|Dean|Keller|1968}}; {{harvtxt|Kim|Roush|1978}}

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

while the number of semiorders on $n$ labeled items is given by the sequence{{sfnp|Chandon|Lemaire|Pouget|1978}}

{{Block indent|left=1.6|1, 1, 3, 19, 183, 2371, 38703, 763099, 17648823, ... {{OEIS|A006531}}}}

Other results

Any finite semiorder has order dimension at most three.{{sfnp|Rabinovitch|1978}}

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.{{sfnp|Fishburn|Trotter|1992}}

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.{{sfnp|Brightwell|1989}}

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.{{sfnp|Doignon|Falmagne|1997}}

The incomparability graphs of semiorders are called indifference graphs, and are a special case of the interval graphs.{{sfnp|Roberts|1969}}

Notes

References

{{citation

| last = Avery | first = Peter

| doi = 10.1016/0196-6774(92)90010-A

| issue = 1

| journal = Journal of Algorithms

| mr = 1146337

| pages = 144–147

| title = An algorithmic proof that semiorders are representable

| volume = 13

| year = 1992}}.

{{citation

| last = Brightwell | first = Graham R. | authorlink = Graham Brightwell

| doi = 10.1007/BF00353656

| issue = 4

| journal = Order

| pages = 369–380

| title = Semiorders and the 1/3–2/3 conjecture

| volume = 5

| year = 1989| s2cid = 86860160 }}.

{{citation

| last1 = Chandon | first1 = J.-L.

| last2 = Lemaire | first2 = J.

| last3 = Pouget | first3 = J.

| mr = 517680

| issue = 62

| journal = Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines

| pages = 61–80, 83

| title = Dénombrement des quasi-ordres sur un ensemble fini

| year = 1978}}.

{{citation

| last1 = Dean | first1 = R. A.

| last2 = Keller | first2 = Gordon

| doi = 10.4153/CJM-1968-055-7

| journal = Canadian Journal of Mathematics

| mr = 225686

| pages = 535–554

| title = Natural partial orders

| volume = 20

| year = 1968| doi-access = free

}}.

{{citation

| last1 = Doignon | first1 = Jean-Paul

| last2 = Falmagne | first2 = Jean-Claude | author2-link = Jean-Claude Falmagne

| doi = 10.1016/S0012-365X(96)00095-7

| mr = 1468838

| issue = 1–3

| journal = Discrete Mathematics

| pages = 35–44

| title = Well-graded families of relations

| volume = 173

| year = 1997| doi-access = free

| hdl = 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/166805

| hdl-access = free

}}.

{{citation

| last = Fishburn | first = Peter C. | authorlink = Peter C. Fishburn

| mr = 0253942

| journal = Journal of Mathematical Psychology

| pages = 144–149

| title = Intransitive indifference with unequal indifference intervals

| volume = 7

| year = 1970

| doi=10.1016/0022-2496(70)90062-3}}.

{{citation

| last = Fishburn | first = Peter C. | authorlink = Peter C. Fishburn

| mr = 0316322

| journal = Journal of Mathematical Psychology

| pages = 91–105

| title = Interval representations for interval orders and semiorders

| volume = 10

| year = 1973

| doi=10.1016/0022-2496(73)90007-2}}.

{{citation

| last1 = Fishburn | first1 = Peter C. | author1-link = Peter C. Fishburn

| last2 = Trotter | first2 = W. T.

| doi = 10.1016/0012-365X(92)90036-F

| mr = 1171114

| issue = 1

| journal = Discrete Mathematics

| pages = 25–40

| title = Linear extensions of semiorders: a maximization problem

| volume = 103

| year = 1992| doi-access = free

}}.

{{citation

| jstor=1913813

| doi=10.2307/1913813

| last1=Jamison | first1=Dean T. | author1-link=Dean Jamison

| last2=Lau | first2=Lawrence J. | author2-link=Lawrence J. Lau

| title=Semiorders and the Theory of Choice

| journal=Econometrica

| volume=41

| number=5

| pages=901–912

| date=Sep 1973 }}.

{{citation

| jstor=1911339

| doi=10.2307/1911339

| last1=Jamison | first1=Dean T.

| last2=Lau | first2=Lawrence J.

| title=Semiorders and the Theory of Choice: A Correction

| journal=Econometrica

| volume=43

| number=5–6

| pages=979–980

| date=Sep–Nov 1975 }}.

{{citation

| last1 = Jamison | first1 = Dean T.

| last2 = Lau | first2 = Lawrence J.

| date = July 1970

| publisher = Stanford University, Institute for Mathematical Studies in the Social Sciences

| title = Semiorders, Revealed Preference, and the Theory of the Consumer Demand}}. Presented at the World Economics Congress, Cambridge, Sep 1970.

{{citation

| last1 = Jamison | first1 = Dean T.

| last2 = Lau | first2 = Lawrence J.

| date = October 1977

| doi = 10.2307/1913952

| issue = 7

| journal = Econometrica

| jstor = 1913952

| pages = 1595–1605

| title = The nature of equilibrium with semiordered preferences

| volume = 45}}.

{{citation

| last1 = Kim | first1 = K. H.

| last2 = Roush | first2 = F. W.

| mr = 538212

| issue = 2

| journal = Journal of Combinatorics, Information &System Sciences

| pages = 58–61

| title = Enumeration of isomorphism classes of semiorders

| volume = 3

| year = 1978}}.

{{citation

| last = Luce | first = R. Duncan | authorlink = R. Duncan Luce

| mr = 0078632

| journal = Econometrica

| pages = 178–191

| title = Semiorders and a theory of utility discrimination

| jstor = 1905751

| volume = 24

| year = 1956

| issue = 2 | url = https://www.imbs.uci.edu/files/personnel/luce/pre1990/1956/Luce_Econometrica_1956.pdf

| doi=10.2307/1905751}}.

{{citation

| last = Rabinovitch | first = Issie

| mr = 0437404

| issue = 2

| journal = Journal of Mathematical Psychology

| pages = 209–212

| title = The Scott-Suppes theorem on semiorders

| volume = 15

| year = 1977

| doi=10.1016/0022-2496(77)90030-x}}.

{{citation

| last = Rabinovitch | first = Issie

| mr = 0498294

| issue = 1

| journal = Journal of Combinatorial Theory, Series A

| pages = 50–61

| title = The dimension of semiorders

| volume = 25

| year = 1978

| doi=10.1016/0097-3165(78)90030-4| doi-access = free

}}.

{{citation

| last = Roberts | first = Fred S. | authorlink = Fred S. Roberts

| contribution = Indifference graphs

| mr = 0252267

| pages = 139–146

| publisher = Academic Press, New York

| title = Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)

| year = 1969}}.

{{citation

| last1 = Scott | first1 = Dana | author1-link = Dana Scott

| last2 = Suppes | first2 = Patrick | author2-link = Patrick Suppes

| mr = 0115919

| journal = The Journal of Symbolic Logic

| pages = 113–128

| title = Foundational aspects of theories of measurement

| volume = 23

| year = 1958 | issue = 2 | doi=10.2307/2964389| jstor = 2964389 }}.

{{citation

| last = Sen | first = Amartya K.

| date = July 1971

| issue = 3

| journal = The Review of Economic Studies

| pages = 307–317

| title = Choice Functions and Revealed Preference

| url = https://www.ihs.ac.at/publications/eco/visit_profs/blume/sen.pdf

| volume = 38| doi = 10.2307/2296384

| jstor = 2296384

}}.

semiorder

Utility theory

Axiomatics

Relation to other kinds of order

=Partial orders=

=Weak orders=

=Interval orders=

=Quasitransitive relations=

Combinatorial enumeration

Other results

Notes

References

Further reading