Acyclic Domains of Linear Orders: A Survey
A = {1,2…i, j,k…n} is a finite set of n elements that I will generally call alternatives (but which could also be called issues, decisions, outcomes, candidates, objects, etc.). The elements of A will be also denoted by letters like x,y, z etc. A subset o
- PDF / 556,792 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 203 Views
1 Notations and Preliminaries A = {1, 2. . .i, j, k. . .n} is a finite set of n elements that I will generally call alternatives (but which could also be called issues, decisions, outcomes, candidates, objects, etc.). The elements of A will be also denoted by letters like x, y, z etc. A subset of cardinality p of A will be called a p-set. A2 (respectively, A3 ) denotes the set of all ordered pairs (x, y) (respectively, ordered triples (x, y, z) written for convenience as xyz) of A. When the elements of A are denoted by the n first integers, P2 (n) denotes the set of the n(n − 1)/2 ordered pairs (i < j). A binary relation on A is a subset R of A2 and we write xRy or (x, y) ∈ R when x is in the relation R with y. For integer ≥ 2, a cycle of length of R, called also a -cycle, is a subset {x1 , x2 , . . ..x } of A such that x1 Rx2 . . .. . ..x Rx1 . For B ⊆ A, the restriction of a relation R to B is denoted by R/B . A strict linear order on A is an irreflexive, transitive and complete (x = y implies xRy or yRx) binary relation on A. Henceforth, we will omit the qualifier strict and sometimes, when there is no ambiguity, the qualifier linear. Linear orders on A are in a one-to-one correspondence with permutations of A. So if L is a linear order on A one can write it as a permutation x1 . . .xk xk+1 . . .xn . Then one says that xk has rank k and is covered by xk+1 and that xk and xk+1 are consecutive in L. I denote by τk the transposition which exchange xk and xk+1 in L: τk (L) = x1 . . .xk+1 xk . . .xn . The set of all linear orders on A is denoted by L or Ln if |A| = n. D denotes any subset of L. In all of this paper the preferences of what I will call a voter (but what could also be called agent, person, individual, criterion, etc.) on a set A of alternatives is
B. Monjardet ´ CES, Universit´e Paris I Panth´eon Sorbonne, Maison des Sciences Economiques, 106–112 bd de l’Hopital 75647 Paris C´edex 13, France, and CAMS, EHESS e-mail: [email protected] S.J. Brams et al. (eds.), The Mathematics of Preference, Choice and Order: Essays in Honor 139 of Peter C. Fishburn, Studies in Choice and Welfare, c Springer-Verlag Berlin Heidelberg 2009
140
B. Monjardet
represented by a linear order L = x1 x2 . . .xn where x1 is assumed to be the last preferred alternative, x2 the next-to-last, etc. So, yLx or (y, x) ∈ L means that alternative x is preferred to alternative y in the linear order L. Remark 1. One could consider that the notation yLx should mean that y is preferred to x. But we are working in this paper with posets and, unfortunately, this choice would be not in accordance with the usual convention of poset theory. Indeed in this theory the symbol used for a (strict) order is generally < what means that yLx is interpreted as y < x, and so as y is less than x. The reader must keep in mind a consequence of our choice: in a linear order of preference L = x1 x2 . . .xn , the worst alternative x1 (respectively, the best alternative xn ) has rank 1 (respectively, n). The problem of getting a collectiv
Data Loading...
