Semiorders

Semiorder is probably one of the most frequently used ordered structure in all areas of Science. Scientists build models, representations of what they observe. The iterative process of model building and checking relies upon endless comparisons: between several observations, between results of different models, or between observations and results. These comparisons can be realized via human perceptions or via very sophisticated and precise instruments. In any case, there always exists a threshold under which differences are not perceptible any more. Thus, observations or results which are very slightly different will be declared “equal”. This will inevitably lead to situations where a is “equal” to 6, b is “equal” to c but a is not “equal” to c. This fact has been acknowledged in the past by scientists like G. Fechner as early as in 1860, by H. Poincaré in 1905 and by others (excerpts from their texts have been reproduced in chapter 2). In the area of decision-analysis and preference modelling, which is the field of activity of the authors of this book, it is R. D. Luce who pointed out, in 1956, the phenomenon of intransitivity of “equality”. It must be noted that this intransitivity is in contradiction with the traditional model used by the scientists who build decision-aid tools, in fields like operations research, statistics, economy, finance or insurance. In that traditional model, preferences are represented by a real-valued function g, defined on the set of possible decisions (feasible solutions), such that decision a is preferred to b if the value g(a) is greater (for example) than g(b).

The purpose of this chapter is not to give the formal definitions of the concepts which will be used in this book (these formal definitions will be given in chapter 3). We just want to introduce here the vocabulary needed to understand chapter 2, in which we expose the motivations for studying semiorders. We have avoided, as much as possible, the mathematical developments, so that the reader who is mainly interested in the applications can understand chapters 1 and 2 without too much effort.

Let t _i be a cup of tea containing i milligrams of sugar. Any ordinary human being, comparing cups of tea, will generally consider that there is no difference between t _i and t _i+1 (few people are able to perceive a difference of 1 milligram of sugar), and this, for every i. We say that a person is indifferent between t _i and t _i+1. However, she may have a preference for t _N over t _o (or the contrary) when N is large enough. This example, which shows that the indifference relation of an individual is not necessarily transitive, was introduced by Luce (Luce 1956). Before him, Armstrong 1939 and Georgescu-Roegen 1936, had already mentioned this phenomenon.

We give in this chapter the rigorous definitions of the concepts we will use in the sequel of the book. Some definitions were already presented in chapter 1 but we have repeated them here in order to have all the basic definitions gathered in a same chapter and, also, because the purpose of chapter 1 was to give an intuitive introduction to the concepts while this chapter is the mathematical introduction of the book. The reader can also refer to Fishburn 1985, Monjardet 1978 or Roubens and Vincke 1985.

In this chapter, we study in detail some particular numerical representations of a semiorder which are in some sense minimal or parsimonious. Such representations generalize to semiorders the rank of the elements in a strict complete order which means that they have similar rights to pretend at being a “default” numerical representation. The notion of minimal representation of a semiorder was first introduced and proven to exist by Pirlot. The exposition below is essentially based on Doignon 1988, Doignon and Falmagne 1994, Pirlot 1990, Pirlot 1991 and Mitas 1994. Related results have recently and independently be obtained in Troxell 1995 for the symmetric part of a semiorder, i.e. a unit interval graph or indifference graph.

Valued relations arise in fields like psychological studies on preference or discrirri-ination, classification and decision-aid. Given a set A of elements a, b,..., a value v(a,b) may be associated to each oriented pair (a, b), representing either the proportion of times a given individual judges stimulus a to be “greater” than stimulus b or the proportion of individuals who prefer a to b, or else the “similarity” between a and b or the credibility or intensity of preference of a over b.

In this chapter, we have tried to gather some results about the aggregation of a family of semiorders into some “global synthetic structure”. Since the subject seems not to have been intensively studied as such, we have tried to formulate a general framework which encompasses a number of well-known methods of preference aggregation. By “aggregation” we generally mean a “mechanism” which associates some structure to any family of structures of a given type (semiorders, for instance) in a “sensible” manner. Of course, what is “sensible” takes different forms according to the context; here we focalize on preference modelling and decision situations. Note that the results we state below can very often be extended to interval orders; this will be eventually mentioned.

In this chapter, we mention briefly some other subjects in relation with semiorders, which were treated in the literature but will not be developed in this book.

In writing this book we wanted to put together a number of concepts and results which could be useful for supporting the development of practical methods and tools in view of applications. What are the main ideas on which we put a stress in this book, that is what we briefly want to summarize as a conclusion.