On the emptiness of the stability set of order \(d\) (Q1863933)

This paper starts with a nice overview of the main results concerning non-emptyness of the stability set of order \(d\) with respect to a given profile \(\succeq\) = \((\succeq_{1}, \ldots , \succeq_{n})\) of complete and transitive individual preference relations over the set \(A\) of alternatives. For \(C\) a winning coalition in a voting game \(G\) and \(\succeq\) a given profile, \(y \succ_{C} x\) iff for every \(i \in C\), \(y \succ_{i} x\). And \(y \succ x\) (\(y\) dominates \(x\)) iff there is a winning coalition \(C\) such that \(y \succ_{C} x\). \(\text{Core} (G, \succeq)\) := \(\{x \in A \mid \neg \exists y \in A [ y \succ x ]\}\) may also be called the stability set of order 0. \textit{A. Rubinstein} [J. Econ. Theory 23, 250--159 (1980; Zbl 0457.90007)] introduced the notion of stability set of order 1 and next \textit{Shuhe Li} [Soc. Choice Welfare 10, 51--56 (1993; Zbl 0781.90102)] introduced the notion of stability set of order \(d\), \(d \geq 1\), denoted by \(S^{d}(G, \succeq)\). It is well known that \(\text{Core} (G, \succeq) \neq \emptyset\) iff \(k < \frac{n}{n-q}\) where \(k\) is the number of alternatives, \(n\) is the number of individuals and \(q\) is the quota. It is also known that the stability set of order 1 is always non-empty if the individual preferences are linear orders. In 1993 Li (loc. cit.) showed that \(S^{d}(G, \succeq) \neq \emptyset\) iff \(k < (\lceil \frac{n}{n-q} \rceil - 1)(d + 1) + 1\), where \(\lceil x \rceil\) is the smallest integer greater than or equal to \(x\). This paper considers the case where \(k\) is the smallest number compatible with an empty stability set and provides an upper bound on the probability for having an empty stability set of order \(d\) for the majority game under the Impartial Weak Order Culture assumption. This upper bound turns out to be already extremely low for small populations and tends to zero as the number of individuals goes to infinity.