On the distribution of the number of optimal elements for various generalized weak orders
Let R be a binary relation on a set X and let aR, cR and sR denote, respectively, the asymmetric part of R, the complement of R, and the symmetric part of R. R is called a generalized weak order (GWO) if caR is transitive. Generalized weak orders were introduced by \textit{P. Fishburn} [Rev. Econ. Stud. 46, 163-173 (1979; Zbl 0399.06002)] and include as special cases the symmetric weak orders (asymmetric, negatively transitive relations) and complete weak orders (complete, reflexive, transitive relations) familiar to economists as models, respectively, of strict preference and preference-or-indifference. An alternative \(x\in X\) is optimal for a GWO R if \(\forall y\in X\), yRx\(\Rightarrow xRy\). The authors study the distribution of the number of optimal elements for randomly selected GWOs of several types. Specifically, if X is a set with n elements, let \(G_ n=\{R:\) R is a GWO on \(X\}\), \(T_ n=\{R\in G_ n:\) R is transitive\(\}\), \(M_ n=\{R\in G_ n:\) R and cR are transitive\(\}\), and \(W_ n=\{R:\) R is a complete weak order on \(X\}\), and let the random variables \(g_ n\), \(t_ n\), \(m_ n\) and \(w_ n\) record the number of optimal elements for a GWO R selected at random from \(G_ n\), \(T_ n\), \(M_ n\), and \(W_ n\), respectively. Using earlier combinatorial results of the second author [Arch. Math. 39, 147-152 (1982; Zbl 0476.06003)] on the numbers \(| G_ n|\), \(| T_ n|\), \(| M_ n|\), \(| W_ n|\), the authors determine the limit density functions and moments of \(g_ n\), \(t_ n\), \(m_ n\), and \(w_ n\) as \(n\to \infty\). Among the results established are the fact that, as \(| X| \to \infty\), almost all GWOs on X are simply symmetric relations, and the fact that \(E(w_ n)\to 2 \log 2\) as \(n\to \infty\). Recent additional work by the authors, generalizing the above results will appear in Adv. Math. in a paper entitled ``Random variables related to a class of ordered structures''.
asymmetric, nevatively transitive relations
complete, reflexive, transitive relations
scientific article; zbMATH DE number 4059464