Date: Thu, 9 May 2024 | Total: 3
In many real-world applications of committee elections, the candidates are associated with certain attributes and the chosen committee is required to satisfy some constraints posed on the candidate attributes. For instance, when dress collocation, it is generally acknowledged that when wearing a tie, you'd better wear a shirt, and wearing a suit, you'd better wear leather shoes. Here, dresses are categorized by upper garment, lower garment, shoes et.al, and upper garment is with the attribute tie and shirt, lower garment is with the attribute suit, and shoes is with the attribute leather. And two constraints "tie infers shirt" and "suit infers leather shoes" are proposed. We study this variant of committee elections from the computational complexity viewpoint. Given a set of candidates, each with some attributes and a profit, and a set of constraints, given as propositional logical expressions of the attributes, the task is to compute a set of k candidates, whose attributes satisfy all constraints and whose total profit achieves a given bound. We achieve a dichotomy concerning classical complexity with no length limit on constraints: the problem is polynomial-time solvable, if the following two conditions are fulfilled: 1) each candidate has only one attribute and 2) each attribute occurs at most once in the constraints. It becomes NP-hard if one of the two conditions is violated. Moreover, we examine its parameterized complexity. The parameterization with the number of constraints, the size of the committee, or the total profit bound as parameter leads to para-NP-hardness or W[1]-hardness, while with the number of attributes or the number of candidates as parameter, the problem turns out to be fixed-parameter tractable.
An election is defined as a pair of a set of candidates C=\{c_1,\cdots,c_m\} and a multiset of votes V=\{v_1,\cdots,v_n\}, where each vote is a linear order of the candidates. The Borda election rule is characterized by a vector \langle m-1,m-2,\cdots,0\rangle, which means that the candidate ranked at the i-th position of a vote v receives a score m-i from v, and the candidate receiving the most score from all votes wins the election. Here, we consider the control problems of a Borda election, where the chair of the election attempts to influence the election outcome by adding or deleting either votes or candidates with the intention to make a special candidate win (constructive control) or lose (destructive control) the election. Control problems have been extensively studied for Borda elections from both classical and parameterized complexity viewpoints. We complete the parameterized complexity picture for Borda control problems by showing W[2]-hardness with the number of additions/deletions as parameter for constructive control by deleting votes, adding candidates, or deleting candidates. The hardness result for deleting votes settles an open problem posed by Liu and Zhu. Following the suggestion by Menon and Larson, we also investigate the impact of introducing top-truncated votes, where each voter ranks only t out of the given m candidates, on the classical and parameterized complexity of Borda control problems. Constructive Borda control problems remain NP-hard even with t being a small constant. Moreover, we prove that in the top-truncated case, constructive control by adding/deleting votes problems are FPT with the number \ell of additions/deletions and t as parameters, while for every constant t\geq 2, constructive control by adding/deleting candidates problems are W[2]-hard with respect to \ell.
To characterize the computational complexity of satisfiability problems for probabilistic and causal reasoning within the Pearl's Causal Hierarchy, arXiv:2305.09508 [cs.AI] introduce a new natural class, named succ-$\exists$R. This class can be viewed as a succinct variant of the well-studied class $\exists$R based on the Existential Theory of the Reals (ETR). Analogously to $\exists$R, succ-$\exists$R is an intermediate class between NEXP and EXPSPACE, the exponential versions of NP and PSPACE. The main contributions of this work are threefold. Firstly, we characterize the class succ-$\exists$R in terms of nondeterministic real RAM machines and develop structural complexity theoretic results for real RAMs, including translation and hierarchy theorems. Notably, we demonstrate the separation of $\exists$R and succ-$\exists$R. Secondly, we examine the complexity of model checking and satisfiability of fragments of existential second-order logic and probabilistic independence logic. We show succ-$\exists$R- completeness of several of these problems, for which the best-known complexity lower and upper bounds were previously NEXP-hardness and EXPSPACE, respectively. Thirdly, while succ-$\exists$R is characterized in terms of ordinary (non-succinct) ETR instances enriched by exponential sums and a mechanism to index exponentially many variables, in this paper, we prove that when only exponential sums are added, the corresponding class $\exists$R^{\Sigma} is contained in PSPACE. We conjecture that this inclusion is strict, as this class is equivalent to adding a VNP-oracle to a polynomial time nondeterministic real RAM. Conversely, the addition of exponential products to ETR, yields PSPACE. Additionally, we study the satisfiability problem for probabilistic reasoning, with the additional requirement of a small model and prove that this problem is complete for $\exists$R^{\Sigma}.