What majority decisions are possible (Q1025491)

\textit{D. C. McGarvey} [Econometrica 21, 608--610 (1953)] showed that every asymmetric relation on a finite set of candidates \(M\) reflects the pairwise preferences of some finite profile of voters, where each voter's contribution to the profile is a strictly linear preference order on \(M\). McGarvey's theorem has since been refined by \textit{R. Stearns} [Am. Math. Mon. 66, 761--763 (1959; Zbl 0090.25101)], \textit{P. Erdős} and \textit{L. Moser} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 9, 125--132 (1964; Zbl 0136.44901)], and \textit{N. Alon} [Adv. Appl. Math. 29, No. 1, 126--135 (2002; Zbl 1020.91012)]. Consider McGarvey's theorem to be the assertion ``arbitrary asymmetric relations on \(M\) are generated from strict linear orders through the process of compiling pairwise preferences''. In the paper under review the author considers the following question: aside from the strict linear orders, what other kinds of choice functions generate arbitrary asymmetric relations? He proves the striking result that the strict linear orders may be replaced by any non-empty family \(\mathfrak{D}\) of functions \(c(x,y)\) such that \(c(x,y)=c(y,x)\in \{x,y\}\) for all \(c\in \mathfrak{D}\) and \(x\neq y\in M\); \(\mathfrak{D}\) is closed under permutations of \(M\); and there exist \(c\in \mathfrak{D}\) and \(x\in M\) such that \(\left| \{y\neq x\in M:c(x,y)=y\}\right| \neq \left| \{y\neq x\in M:c(x,y)=x\}\right| \).