Computational complexity to verify the unstability of effectivity function (Q687989)

An \(n\)-person game with a preference order of each player over a set \(A\) of \(m\) alternatives is considered. The preferences are assumed to be aggregated to a rule of social choice which can be represented as an effectivity function \(E\), in the sense that a coalition \(S\) is effective of a subset \(B\) of \(A\) if the final result will belong to \(B\) specified by \(S\). The effectivity function is called stable if for any combination of preference orders there exists a so-called core of \(A\) such that no alternative in the core can be dominated. Scarf balancedness is sufficient for this kind of stability, as well as a necessary and sufficient condition is the non-existence of cycles in \(E\). This paper is concerned with the computational complexity of this stability problem. In section 2, the basic notations and the formal definition of an effectivity function is given. In section 3, the necessary and sufficient conditions of \textit{H. Keiding} [Int. J. Game Theory 14, 93-101 (1985; Zbl 0567.90101)] is discussed, with special emphasis on the concepts of a `Strong Cycle' (SC) and a `Cycle' (CYCLE). A first theorem concerns the relation between SC and CYCLE in \(E\), a second one characterizes the stability of \(E\) by acyclicity. In section 4, known results on computational complexity are summarized. Besides \(\mathcal P\) and \({\mathcal N}{\mathcal P}\), a subset \({\mathcal N}{\mathcal P}{\mathcal C}\) of \({\mathcal N}{\mathcal P}\) consisting of the most intractable problems in \({\mathcal N}{\mathcal P}\) is considered. If any problem in \({\mathcal N}{\mathcal P}\) can be polynomially transformed to a problem \(\mathcal P\), it is shown that \(\mathcal P\) has the same computational complexity as \({\mathcal N}{\mathcal P}{\mathcal C}\). Furthermore, it is shown that a familiar problem SATISFIABILITY (SAT) is in \({\mathcal N}{\mathcal P}{\mathcal C}\). i. e. SAT can be transformed into CYCLE through a polynomial time procedure. By showing the \({\mathcal N}{\mathcal P}\)- completeness of CYCLE, a previously unanswered conjecture is proved. Section 5 contains the main result of the paper. The CYCLE problem is checked with respect to the existence of a cycle in \(E\). For problem SC the transformation of SAT into SC is proved. Detailed proofs are given for the assertions \(\text{SC}\in{\mathcal N}{\mathcal P}{\mathcal C}\) (Theorem 5.1) and \(\text{CYCLE}\in{\mathcal N}{\mathcal P}{\mathcal C}\) (Theorem 5.4), illustrated by examples. In section 6, the problem CORE of verifying the existence of the core of \(A\) is shown to belong to \(\mathcal P\) (Theorem 6.1). Thus, CYCLE is much more intractable than CORE, and as a general conclusion of this paper it can be pointed out that the stability problem cannot be solved by a polynomial time algorithm.