On the distribution of the number of optimal elements for various generalized weak orders
type: Item
instance of: scholarly article
title: On the distribution of the number of optimal elements for various generalized weak orders
zbMATH Open document ID: 0649.06002
DOI: 10.1007/BF01194877
author: John J. jun. Long
author: Carl G. Wagner
published in: Archiv der Mathematik
publication date: 1989-01-01T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 60E99
Mathematics Subject Classification ID: 62E20
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 4059464
zbMATH Keywords: limiting distribution
zbMATH Keywords: optimal alternative
zbMATH Keywords: ordered partition
zbMATH Keywords: moment
zbMATH Keywords: binary relation
zbMATH Keywords: generalized weak order
zbMATH Keywords: asymmetric weak orders
zbMATH Keywords: asymmetric, nevatively transitive relations
zbMATH Keywords: complete weak orders
zbMATH Keywords: complete, reflexive, transitive relations
zbMATH Keywords: strict preference
zbMATH Keywords: preference- or-indifference
MaRDI profile type: Publication
cites work: Asymptotic Methods in Enumeration
cites work: Principles of combinatorics
cites work: Transitivity
cites work: Q3264494
cites work: Enumeration of generalized weak orders
full work available at URL: https://doi.org/10.1007/bf01194877
OpenAlex ID: W1969928097
description: scientific article; zbMATH DE number 4059464