Winner Determination and Strategic Control in Conditional Approval Voting

1 Introduction

This work focuses on a voting rule for multi-issue elections that couples approval voting with the possibility of expressing dependencies among issues. As a first example, imagine a group of friends who have to decide on the menu of a buffet for the party they are hosting. It is expected that their preferences on certain dishes are conditioned on whether some other (e.g., complementary) dishes will be selected or not. We can consider another example with conditional preferences, taken from recommendation systems for online advertising. Suppose an ad management service needs to make a personalized selection of ads, to be shown on Alice's favorite news website. For each slot (or area) in the advertising region of the site, there is a set of possible ads to choose from and the overall goal is to maximize Alice's satisfaction (the probability of an ad to be clicked by her). If we think of the slots as corresponding to issues, a recommendation could be made by looking at the data from users "similar" to Alice (voters), and their clicking behavior (approvals). The voters have conditional preferences, as the clicking probability is affected when an ad appears in a nearby slot with a related one (e.g. it is increased for frequently bought together products).

It seems obvious in the examples above, that deciding independently for each issue would not be a wise choice. Motivated by these considerations, the work of [Barrot and Lang, 2016] introduced an expressive framework that handles conditional ballots within the approval voting format, and defined, among others, the Conditional Minisum (CMS) voting rule. CMS can be thought of as a natural, intuitive generalization of the well known Minisum rule in approval-based elections, under preferential dependencies.

At the moment however, the power and limitations of CMS are still under-explored, and further studies are needed to arrive at a better evaluation of this relatively new rule. First, it has been shown that the higher level of expressiveness comes at the price of increased computational complexity; although the Minisum rule is easy to implement in the standard (unconditional) setting, CMS was proved to be intractable already by [Barrot and Lang, 2016]. Given this negative result, it becomes important to understand which properties can play a crucial role on obtaining efficient algorithms. The subsequent work of [Markakis and Papasotiropoulos, 2020] made some progress along this front, providing a sufficient condition for fast algorithms, but this has been far from a complete understanding. Second, we still know very little about the complexity of controlling and/or manipulating a CMS election. This is a very prominent research agenda within computational social choice, and further results would provide more insights on the benefits or drawbacks of conditional voting.

Contribution. Our main goal is to investigate algorithmic and complexity aspects of solving and controlling elections under CMS. More precisely, our results in Section 3, provide characterizations for the families of CMS instances that can be placed in P and FPT. The main insight gained out of this, is that the condition of bounded treewidth (of an appropriate graph, aggregating all the provided dependencies) serves as the lynchpin between expressiveness of preferences and efficiency of computation. These results also establish a connection between winner determination under CMS and a well studied class of Constraint Satisfaction Problems, which can be of independent interest. Moving on, in Section 4, we initiate for CMS the study of some standard notions of election control. These problems concern the attempt by an external agent to enforce a certain outcome by adding or deleting either voters or alternatives in the election. Our findings reveal that CMS is sufficiently resistant against such moves.

Related Work

The works most related to ours are [Barrot and Lang, 2016] and [Markakis and Papasotiropoulos, 2020]. The former introduced the rule we study, and provided computational hardness results, along with other interesting properties, whereas the latter focused on algorithms for special cases of the problem. For surveys on approval voting, we refer to [Brams and Fishburn, 2010] and [Kilgour, 2010]. Beyond approval voting, we point to the work of [Chevaleyre et al., 2008] for the relation of similar solution concepts within AI and to the enlightening survey of [Lang and Xia, 2016], for an exposition of solution concepts, proposed as attempts for a tradeoff between expressiveness and computational cost over combinatorial domains.

Regarding election control, the versions that we consider fall within the standard approaches that have been used for studying the complexity of affecting election outcomes. For an extensive study on this topic, we refer to [Faliszewski and Rothe, 2016]. Indicatively, the study of such problems with adding or deleting voters or alternatives began with the seminal paper of [Bartholdi III et al., 1992] and some of the subsequent works are, among others, [Hemaspaandra et al., 2007; Faliszewski et al., 2011; Liu et al., 2009].

2 Formal Background

For the relevant definitions of our setting, we closely follow the framework of [Barrot and Lang, 2016]. Let I = {I1, . . . , Im} be a set of m issues, where each issue Ij is associated with a finite domain Dj of different alternatives. Let D = D1×D2×· · ·×Dm be the set of all feasible outcomes.

We consider a set V = {1, . . . , n} of n voters who have to reach a common decision for every issue in I. The voters can express dependencies among issues in the following manner: we assume each voter i provides a directed graph Gi = (I, Ei), referred to as her dependency graph. For an issue Ij , we denote by Ni(Ij ) the set of in-neighbors of the vertex corresponding to Ij in the dependency graph Gi. For an issue Ij where the set of in-neighbors is non-empty, the opinion of voter i on Ij is dependent on the outcome of the issues in Ni(Ij). A useful quantity in the sequel is the maximum in-degree for a voter i, which is ∆i = maxj∈[m]{|Ni(Ij)|}.

Definition 1. A conditional approval ballot of a voter i over the issues of I = {I1, . . . , Im} is a pair Bi = 〈Gi, {Aj, j ∈ [m]}〉, where Gi is the dependency graph of voter i, and for each issue Ij, Aj is a set of conditional approval statements {t : dj}, for some t ∈ ∏k∈Ni(Ij) Dk and some dj ∈ Dj.

The rationale in Definition 1 is that the set Aj expresses the combinations of values that make the voter satisfied with respect to issue Ij. We note that when Ni(Ij) = ∅, voter i can express a simple unconditional ballot for approving an alternative d of issue Ij , which for simplicity, will be denoted as {d}. We also stress that our setting is incomparable with the semantics of the CP-nets framework, as already pointed out by [Barrot and Lang, 2016].

Definition 2. The global dependency graph of a set of voters is the undirected 1 simple graph that emerges from ignoring the orientation of edges in the graph (I, ⋃i∈[n] Ei).

1 Defined as a directed graph in [Markakis and Papasotiropoulos,

Let B = (B1, . . . , Bn) denote the voters' conditional ballots. An instance of a conditional approval election is called a profile, given by a tuple (I,D, V,B). An outcome of the election is a vector (s1, s2, . . . , sm) ∈ D (with sj ∈ Dj).

Definition 3. Given an outcome s = (s1, s2, . . . , sm), we say that voter i is dissatisfied (or disagrees) with issue Ij, if either Ni(Ij) = ∅ and {sj} /∈ Bj i , or if the projection of s on Ni(Ij), say t, satisfies {t : sj} /∈ Bj i , where Bj i is the restriction of the ballot Bi on the issue Ij . We denote as δi(s) the total number of issues from s that dissatisfy voter i.

For illustrative examples concerning the definitions, we refer to [Barrot and Lang, 2016] and [Markakis and Papasotiropoulos, 2020]. We focus on the following voting rule within the framework of conditional approval elections.

Problem: CONDITIONAL MINISUM (CMS)

Instance: A profile of a CMS election (I, D, V, B).

Output: An outcome that achieves mins∈D ∑i∈[n] δi(s).

If the global dependency graph of an instance is empty, i.e., ∆i = 0, ∀i ∈ [n], then the election degenerates to Unconditional Minisum which is simply the classic Minisum rule in approval voting over multiple independent issues. In the sequel, we will make extensive use of the treewidth parameter of a graph G, denoted as tw(G). For the relevant definition, we refer to [Robertson and Seymour, 1986] or to any textbook of parameterized complexity such as [Cygan et al., 2015]. Finally, we note that all missing proofs can be found in the full version of this work.

3 Winner Determination of CMS Elections

The price we pay for the higher expressiveness of CMS is its increased complexity, as already established by the work that introduced the rule [Barrot and Lang, 2016]. Here, we focus on understanding the properties that allow CMS to be implemented in polynomial time. For this, we stick to the nontrivial case where ∆i ≤ 1 for every voter i, which is already NP-hard, and investigate what further restrictions can make the problem tractable. More specifically, we utilize the global dependency graph of an instance, defined in Section 2, aggregating all the dependencies of the voters into a single graph. The role of the global dependency graph was highlighted in [Markakis and Papasotiropoulos, 2020], where an optimal algorithm was described when the treewidth is at most 2. In this section, we first provide a generalization of this result for any constant treewidth (Theorem 1), resolving one of the open questions by [Markakis and Papasotiropoulos, 2020]. But more importantly, we also show that this is tight, and we cannot hope to go beyond constant treewdith (Theorem 2 and Corollary 1), under standard complexity assumptions.

In our results, we make extensive use of Constraint Satisfaction Problems (CSPs), a prominent class of problems as they can model numerous applications in AI. A CSP instance is described by a tuple (V,D,C), where V is the set of variables, D is the Cartesian product of the domains of the variables, and C is a set of constraints. Each constraint involves a subset of the variables, and is represented by all the combinations of variables that make it satisfiable. We will pay particular attention to the so-called binary CSPs, where each constraint involves at most two variables. The decision problem for a CSP asks whether we can find an assignment to the variables of V so that all constraints of C are satisfied, whereas a natural optimization version [Freuder and Wallace, 1992] is to minimize the number of unsatisfied constraints. When analyzing CSPs, a useful concept in the literature is the primal or Gaifman graph of an instance, defined below.

2020], but their results utilized its undirected version.

Definition 4. The primal (or Gaifman) graph of a CSP instance is an undirected graph, whose vertices are the variables of the instance and there is an edge between two vertices, if and only if they co-appear in at least one constraint.

The proof of the following theorem is based on formulating our problem as minimizing the number of unsatisfied constraints in an appropriate binary CSP instance, whose primal graph has constant treewidth. For these classes of CSPs, one can then use known results from [Freuder, 1990] 2 or [Koster et al., 2002] for solving them efficiently.

Theorem 1. If the global dependency graph of a CMS instance with ∆i ≤ 1 for every voter i, has constant treewidth, then the problem is optimally solvable in polynomial time, even for arbitrary domain cardinality for each issue.

Remark 1. Theorem 1 does not seem to have any direct generalization to instances where ∆i ≥ 2 for some voter i, since in that case the global dependency graph will not necessarily coincide with the primal graph of the corresponding CSP (which is an essential part of the proof). Tackling higher degrees is left as an open problem. On the other hand, Theorem 1 can be generalized when there is a weight for each voter so as to optimize the weighted sum of the dissatisfaction scores.

Theorem 1 shows that ∆i ≤ 1 for each i, along with constant treewidth on the global dependency graph form a sufficient condition for polynomial time solvability. We argue that such conditions are not overly restrictive for election rules. Instances with ∆i ≤ 1 can be thought of as a natural first-step generalization of the unconditional approval voting case, by adding at most one dependence per issue. Constant treewidth also provides an adequate degree of expressiveness and can be encountered when the aggregate dependencies are not too dense. Graphs with low treewidth can arise when there is a commonly accepted hierarchy between issues or when voters have a high level of agreement on the type of dependencies in combination with the fact that ∆i ≤ 1 for each voter i.

A natural question is whether we can solve other classes of instances, containing graphs of non-constant treewidth, under the assumption of ∆i ≤ 1 for each i, by focusing on other parameters of the problem. Quite surprisingly, it turns out that the constant treewidth is essentially the only property that can yield efficiency guarantees. To establish this claim, we first show a "reverse" direction to Theorem 1, that binary CSPs can be reduced to CMS. Hence, together with Theorem 1, this means that CMS is computationally equivalent to binary CSPs, and thus to any other problem that is already known to have this property, such as the PARTITIONED SUBGRAPH ISOMORPHISM problem [Marx, 2010]. This reveals further connections between CMS and other combinatorial problems.

2 The original results in [Freuder, 1990] do not deal with the optimization version, but as demonstrated in later works (e.g., Proposition 4.3 from [Knop et al., 2019]), can be extended for this version.

Theorem 2. Every binary CSP with primal graph G, can be reduced in polynomial time to a CMS instance with ∆i ≤ 1 for every voter i, and with G as the global dependency graph.

Proof. For convenience, we will work with the decision version of CSP asking for a solution that satisfies every constraint. Let P be a binary CSP instance, and without loss of generality, assume that every constraint involves exactly two variables. We construct a CMS instance P ′ , where the issues correspond to the variables and the voters correspond to the constraints of P. In particular, for every variable xj of the CSP instance, we add an issue Ij and for every constraint we add a voter, with the following preferences: let xj, xk be the two variables involved in the constraint. We pick one of the two variables (arbitrarily), say xk, and we set Ik as the issue that the voter cares about, conditioned on Ij. We also set her conditional ballot for issue Ik in such a way, so that the voter becomes satisfied precisely for all combinations of values for xj and xk that make the constraint satisfied. The voter is also satisfied unconditionally with every outcome for every other issue of the produced instance. Obviously, the dependency graph of every voter has maximum in-degree equal to one.

As an example, suppose that a constraint is of the form x1∨x2 and the variables x1, x2 have binary domain. Then we introduce a voter, and two issues I1, I2 (if they have not been introduced already by other constraints), and we can select I2 as being dependent on I1. The conditional ballot regarding the satisfaction of the voter for I2 is {x1 : x2}, {x1 : x2}, {x1 : x2}. In addition, the voter approves unconditionally every outcome of any issue other than I2.

To complete the reduction, we consider the decision version of CMS where we ask for an assignment with no dissatisfactions, i.e., the instance P ′ has an affirmative solution only when all voters are satisfied with all the issues. Observe that this is a polynomial time reduction (the conditional ballot of each voter for her single issue of interest can be described in O(d2 ) time, where d is the maximum domain cardinality of the CSP variables). The following is quite obvious.

Claim 1. The primal graph of CSP instance P is identical to the global dependency graph of the CMS instance P ′ .

It remains to see that there exists a solution to P that satisfies every constraint if and only if there exists a solution to P ′ that satisfies every voter, which can be easily verified.

Theorem 2 allows us to apply some known hardness results on binary CSPs with large domain size, namely [Grohe, 2007; Grohe et al., 2001], which imply that one cannot hope to have an efficient algorithm for a class of CMS instances, if the class contains instances with non-constant treewidth. Hence, Theorem 1 is essentially tight, and this resolves the problem of finding a characterization for instances that admit polynomial time solutions for CMS, subject to a standard computational complexity assumption.

Corollary 1. Let G be a recursively enumerable (e.g., decidable) class of graphs, and let CMS(G) be the class of instances with a global dependency graph that belongs to G, and with ∆i ≤ 1 for every voter i. Assuming FPT̸= W[1], there is a polynomial algorithm for CMS(G) if and only if every graph in G has constant treewidth.

Remark 2. If we strengthen the complexity assumption used, from FPT̸=W[1] to the Exponential Time Hypothesis (ETH), we can obtain an even stronger impossibility result. In particular, by exploiting the result of [Marx, 2010], and the reduction in the proof of Theorem 2, we can show that under ETH, one cannot even hope for an algorithm on CMS(G) that runs in time f(G)||P||o(tw(G))/log(tw(G)) , where ||P|| is the size of the CMS instance and G ∈ G. This implies that the O(ntw(G) ) algorithm from Theorem 1 is best possible up to an O(log (tw(G))) factor in the exponent.

Parameterized complexity of CMS. The algorithm used in the proof of Theorem 1, runs in time exponential in tw(G), where G is the global dependency graph and thus it places CMS in XP w.r.t the treewidth parameter. One can wonder if anything more can be said concerning the fixed parameter tractability of the problem. Given the equivalence of our problem with binary CSPs, we can use known results [Samer and Szeider, 2010; Gottlob and Szeider, 2008], to extract some further characterizations and obtain an almost complete picture with respect to the most relevant parameters. On the positive side, we can show that our problem is in FPT w.r.t. the parameter "treewidth + domain size". On the negative side, we cannot hope to prove FPT only w.r.t the treewidth parameter, independent of the domain size, as stated below.

Corollary 2. When ∆i ≤ 1 for every voter i, CMS is in FPT w.r.t the parameter tw + d, where tw is the treewidth of the global dependency graph and d is the maximum domain size. Moreover, it is W[1]-hard w.r.t. tw and w.r.t. d.

4 Strategic Control of CMS Elections

In this section, we consider strategic aspects of CMS and study questions related to controlling an election of interdependent issues, which falls under the broad and well studied umbrella of influencing election outcomes in computational social choice. Suppose that there is an external agent (called controller) who has a strong preference for a specific value of some (or every) issue in a CMS election. One of the instruments for enforcing a desirable value for the issue(s) the controller cares about, is by enabling new voters to participate or respectively, by disabling some existing voters, which can be done for example by changing the criteria for eligibility of voters (e.g., age, permanent residence, or even more specialized criteria in committee elections). Furthermore, a different instrument for the controller is to add more choices for the issues under consideration or delete existing ones, towards enforcing her will. We refer to [Chen et al., 2017] for related examples. It is reasonable to assume that the controller does not have unlimited power, and therefore, she is capable of adding/deleting only a certain number of voters/alternatives.

Each combination of control features gives rise to a different control type. In this manner, we obtain 8 distinct algorithmic problems that we study in this work, the formal definitions of which are presented in the following subsections. These are adaptations to CMS elections, of the original definitions provided in [Bartholdi III et al., 1992]. Following the terminology of [Hemaspaandra et al., 2007], we say that a voting rule is vulnerable to a certain control type, if the corresponding problem is always solvable in polynomial time. If the problem is C-hard for a complexity class C, we consider the rule to be resistant to the specific control type (typically C is the class NP). In the cases where it is not possible for a controller to affect the election towards fulfilling her will, we say that the rule is immune to the corresponding control type. As noted in [Hemaspaandra et al., 2009], the "dream case" would be an efficiently computable voting rule which would be either resistant or immune to all control types. Hence, given the results of Section 3, we are mainly interested in elections that satisfy the conditions identified there. For an overview of the results of this section, we refer to Table 1.

4.1 Controlling Voters

We start with the problems of adding or deleting voters for enforcing a specific outcome either for a single issue or for every issue of the election.

Instance: A CMS election (I,D, V,B), where V is the set of registered voters, a set V ′ of yet unregistered voters with V ∩ V ′ = ∅ (for use only by CAV), an integer quota q, a distinguished alternative pj ∈ Dj for a specific issue Ij or an outcome p ∈ D specifying an alternative for every issue. Problem CAV-1 (resp. CDV-1): Does there exist a set V ′′ ⊆ V ′ (resp. V ′′ ⊆ V ), with |V ′′ | ≤ q, such that pj is the value of issue Ij in every optimal CMS solution of the profile (I,D, V ∪ V ′′ ,B) (resp. of the profile (I,D, V \ V ′′ ,B))? Problem CAV-ALL (resp. CDV-ALL): Does there exist a set V ′′ ⊆ V ′ , (resp. V ′′ ⊆ V ) with |V ′′ | ≤ q, such that p is the unique optimal CMS solution of the profile (I, D, V \V ′′ , B) (resp. of the profile (I,D, V \ V ′′ ,B))?

Remark 3. One has the option of either breaking ties in favor of the controller, if there are multiple optimal solutions in CMS (as in [Davies et al., 2011]), or demand that the controller's will is fulfilled in every optimal outcome. We focus on the second case, as is also done in the seminal paper of [Bartholdi III et al., 1992]. Additionally, it is possible that the controller has a strong opinion not just for a single or all issues, but for a subset of issues. As a starting point, we have chosen to consider the two (intuitively simpler) extremes.

We now present our results for these 4 problems, exhibiting that it is not generally easy for a controller to enforce her will in such elections. In fact, resistance to control by adding or deleting voters can be established even for very simple forms of elections, without even the presence of conditional ballots.

Theorem 3. CAV-ALL and CDV-ALL are NP-hard even for Unconditional Minisum and for binary domain in each issue.

Theorem 3 may not be very surprising, since controlling all issues appears to be a quite strict requirement. The next step is to see whether such hardness results go through when the controller wishes to control just a single issue. For Unconditional Minisum this is not the case, if we insist on a constant domain size for the designated issue. The reason is that this can be reduced to an FPT version of the SET MULTI-COVER.

Proposition 1 (implied by [Bredereck et al., 2020]). CAV-1 and CDV-1 can be solved in polynomial time for Unconditional Minisum if the domain size of each issue is constant.

As a consequence, any potential hardness result for CAV-1 and CDV-1 would have to consider either non-constant domain or conditional ballots. Indeed, it suffices to move to non-constant domain size, to establish NP-hardness.

Theorem 4. CAV-1 and CDV-1 are NP-hard, even for Unconditional Minisum, but with non-constant domain size in at least one issue.

We now have a complete picture for the unconditional setting, the results of which, transfer to the conditional case too. The status of CDV-1 and CAV-1 for constant domain size in the presence of conditional ballots, remains unresolved.

4.2 Controlling Alternatives

We now consider the analogous control problems, regarding the addition or deletion of alternatives, instead of voters.

Instance: A CMS election (I, D, V, B), where D = D1 × · · ·×Dm, and Dk is the set of qualified alternatives of each issue Ik, a set D′k of spoiler alternatives for each Ik (for use only by CAA), an integer quota q, a distinguished alternative pj ∈ Dj for a specific issue Ij or an outcome p ∈ D specifying an alternative for every issue.

Problem CAA-1 (resp. CDA-1): Does there exist a set D′′ ⊆ ⊔k∈[m]D′k (resp. D′′ ⊂ ⊔k∈[m]Dk), with |D′′ | ≤ q, such that pj is the value of the issue Ij in every optimal CMS solution of the profile where the domain of each issue Ik is enlarged by the alternatives in D′′ ∩D′k (resp. reduced by the alternatives in D′′ ∩D′k )?

Problem CDA-ALL: Does there exist a set D′′ ⊂ ⊔k∈[m]Dk, with |D′′ | ≤ q, such that p is the unique optimal CMS solution of the profile where the domain of each issue Ik is reduced by the alternatives in D′′ ∩D′k ?

Note: For CDA-1 and CDA-ALL, we also require that for every k, |Dk \ D′′ | ≥ 1.

In the definitions above, we use ⊔ to denote the disjoint union of sets, having in mind that we could consider alternatives of different domains as distinct, even if they correspond to the same values (e.g. in boolean domains).

Remark 4. We first note that we have not included CAAALL in the definitions as CMS is trivially immune to adding alternatives in order to enforce a qualified alternative in every issue. Concerning CAA-1, we assume that the voters may express an opinion about any outcome of every issue, whether it concerns a qualified or a spoiler alternative. Additionally, another way to define such problems would be to allow the controller to completely delete or add issues, however, given the existence of dependency graphs, erasing an issue can make the preferences of a voter ill-defined. Lastly, the constraint |Dk \D′′ | ≥ 1, for CDA-1 and CDA-ALL, is to ensure that the controller cannot eliminate all the alternatives of an issue.

It turns out that the picture differs significantly from the problem of adding or removing voters.

Proposition 2. CDA-1 and CDA-ALL can be solved in polynomial time whereas CAA-1 is immune, for Unconditional Minisum, with arbitrary domain size.

As soon as we move however to instances with conditional ballots, the problems do become hard (with the exception of Proposition 3). We start with the hardness of CDA-ALL.

Theorem 5. CDA-ALL is NP-hard, when ∆i ≤ 1 for every voter i, and even when the treewidth of the global dependency graph is at most one, but with non-constant domain size in at least one issue.

Next, we move to CDA-1 and CAA-1. When we allow a large domain size, we show that they have a similar behavior, and they are both resistant. The proof of Theorem 6 below, shows a connection with some natural problems on directed graphs, that have been linked to election control in the past for different voting rules [Betzler and Uhlmann, 2009].

Theorem 6. CAA-1 and CDA-1 are NP-hard, when ∆i ≤ 1 for every voter i, and even when the treewidth of the global dependency graph is at most one, but with non-constant domain in at least one issue.

Proof. We will prove hardness for CDA-1 (the proof for CAA1 is similar) using a reduction from the NP-hard MAX OUTDEGREE DELETION (MOD) [Betzler and Uhlmann, 2009].

Instance: A directed graph G = (V,E), a distinguished vertex p ∈ V and an integer k ≥ 1.

Problem: Does there exist V ′ ⊆ V with |V ′ | ≤ k such that p is the only vertex of maximum out-degree in G[V \ V ′ ]?

For S ⊆ V , we denote by degS(u) the out-degree of vertex u in a graph G = (V, E), when we count only outgoing edges towards the vertices of S. Let P = (G = (V, E), p, k) be an instance of MOD in a directed graph with n vertices and m edges. We create a CDA-1 instance, where we have one issue Ij for every vertex vj, j ∈ [n] and an extra issue I0, hence I = {I0, I1, I2, . . . , In}. For j ∈ [n], the domain of issue Ij is binary in the form Dj = {dj, dj}. The domain of I0, say D0, contains (k +1)(n-1)+1 alternatives. In particular, it contains an alternative bp that corresponds to the designated vertex p ∈ V , and for every vertex v ∈ V \ {p}, there are k + 1 alternatives bℓv , for ℓ ∈ [k + 1]. Essentially, these are identical k +1 'copies' encoding the selection of v in I0, and play a significant role in the reverse direction of the reduction. As for the voters, there are two types of voters, edge voters and vertex voters. There is one edge voter for every edge (i, j) ∈ E, with a dependency graph having one edge from Ij to I0, and voting as follows:

• For the issue I0, she votes conditioned on Ij for {dj : bi} if i = p or otherwise for {dj : bℓi }, ∀ℓ ∈ [k + 1].
• For all other issues she is satisfied with any outcome.

For every vertex other than p, we also have a block of L identical voters, where it suffices to take L = m+ 1. Each voter in the j-th block, with j ∈ V \ {p} has a dependency graph with 1 edge, from I0 to Ij and votes as follows:

• For the issue Ij, she is satisfied with the combinations {bℓj : dj} for any ℓ. Also, if the value of I0 differs from bℓj , for any ℓ, she is satisfied with any value on Ij . Hence, the only restriction is that when the value of I0 comes from an alternative corresponding to vertex j, the voter can be satisfied w.r.t. Ij only by dj .
• For all other issues, she is satisfied with any outcome.

In total, we have m + (n - 1)L voters. We also use k as the quota parameter, and we suppose the controller wants to enforce the outcome bp at issue I0. Clearly, for every voter i, ∆i ≤ 1, and the global dependency graph is a star centered on I0. The maximum domain cardinality is O(kn) = O(n2 ).

Suppose there exists a set S of vertices in G of size at most k, say WLOG that S = {1, . . . , k} ⊆ V , whose deletion leaves p as the only vertex of maximum out-degree. We now choose to delete the corresponding alternatives {d1, . . . , dk} from the issues {I1, . . . , Ik}. If we select bp for the issue I0, then the total dissatisfaction score can be brought down to m- degV \S(p), by choosing dj for every issue Ij where dj has not been deleted. On the other hand, if we select for I0 some bℓj for any ℓ ∈ [k + 1], we need to consider two cases, depending on j. If j ∈ V \ S, then by the same reasoning as before, the best we could achieve is a dissatisfaction score equal to m-degV \S(j). But since p has the maximum out-degree, this would yield a worse solution. For the second case, suppose j ∈ S, then dj has been deleted from Ij. Hence, the j-th block of vertex voters will be dissatisfied w.r.t. Ij, and since L > m, this cannot yield an optimal solution. To conclude, after the deletion of the selected alternatives, bp has to be selected for I0 in any optimal solution.

For the reverse direction, suppose that there is a set D′′ of at most k alternatives, the deletion of which, forces bp to be selected for I0 in every optimal solution. We claim that the deleted alternatives must come from distinct issues among I1, . . . , In, and they all correspond to some dj for j ∈ [n]. It is now easy to observe that deleting from V the set S formed by the vertices corresponding to these alternatives in D′′ , makes p the unique vertex of maximum out-degree in the induced subgraph of G. If not, there is a vertex, say v ∈ V \ S, with greater or equal out-degree. In that case, if we select bℓ′ v for I0 for some arbitrary ℓ′ , and dj for all issues Ij, for which dj has not been deleted, we will obtain a solution with at most the same dissatisfaction score as the one that used bp. Indeed, we will have fewer or equal dissatisfactions from the edge voters w.r.t. I0, and also all the blocks of the vertex voters will be satisfied which contradicts the fact that bp was elected for I0 in every optimal solution.

Let us now move to a constant domain size for CDA-1 and CAA-1. Here, the problems seem to behave differently.

Proposition 3. CDA-1 can be solved in polynomial time, when ∆i ≤ 1 for every voter i, the treewidth of the global dependency graph is constant, and the domain size is also constant for every issue.

Hence, constant domain size makes a difference for CDA-1 when we stick to the assumptions from Section 3 on each ∆i and on the treewidth. For CAA-1, we are not yet aware if the same result holds (but the proof arguments certainly do not go through). However, we have established intractability, as soon as we move to slightly richer instances with ∆i ≤ 2.

Theorem 7. CAA-1 is NP-hard, when ∆i ≤ 2 for every voter i, even when the treewidth of the global dependency graph is at most one and even for binary domain size in every issue.

Overall, we end the current section, concluding that CMS is computationally resistant in most of the variants of the control problem considered.

5 Conclusions

Our work has mostly focused on the natural, first-step generalization of the classic Minisum rule into conditional voting, i.e., with ∆i ≤ 1 for every voter i. For this case, we conclude that CMS provides a satisfactory tradeoff between expressiveness and efficiency under the assumption of bounded treewidth, and at the same time exhibits sufficient resistance to control in the considered settings.

There are still several interesting problems for future research. Algorithmic results for instances with even higher expressiveness, e.g., with ∆i ≤ 2, seem more challenging (the problem remains NP-hard and we are not aware of any properties that could lead to optimal algorithms for special cases). From a strategic point of view, some questions have been left open for the models we considered, including also parameterized complexity aspects. More interestingly, one can go further and study other strategic moves such as destructive versions of control or bribery aspects in a CMS election. Along this spirit, CMS was proven to be non-strategyproof by [Barrot and Lang, 2016], but the complexity of finding a manipulation has not been examined. Lastly, an experimental evaluation of the CMS election rule would also be an interesting pursuit, complementary to our theoretical analysis.

Acknowledgements

This work has been supported by the Hellenic Foundation for Research and Innovation (H.F.R.I.) under the "First Call for H.F.R.I. Research Projects to support faculty members and researchers and the procurement of high-cost research equipment" grant (Project Number: HFRI-FM17-3512).