Better Collective Decisions via Uncertainty Reduction

1 Introduction

A rural community needs to decide whether to install wind turbines on a nearby hill. Some 40% of the residents are certain that this is a good idea, because they are committed to renewable energy. About 30% of the residents are firmly against the proposal, because of the construction noise or the impact on the views from their homes. However, the remaining 30% of the residents struggle to make up their minds: they are generally in favor of wind power, but worry that the location chosen for the project may be on the migration route of a rare bird species. A local environmental charity wants to help this community to make a decision that is consistent with the majority's preferences. By consulting with scientists, the charity concludes that the selected location is unlikely to present a danger for the birds, so building the turbines is the 'correct' decision. As the decision will be made by a majority vote at a community meeting, the charity needs to reach out to (some of) the undecided voters and explain that it is in their best interest to vote in favor of the wind turbines. Another approach would be to discourage the confused residents from participating in the meeting, or to suggest to them that they may want to delegate their votes to more competent voters; these strategies may result in decisions that are better for the entire community, including the confused voters themselves.

Inspired by this scenario, in this work we study the problem faced by a benevolent party that wants to help a group of agents to make majority-preferred decisions on a number of binary issues. For each agent and each issue, one of the two options is 'correct', in the sense that this is the option the agent would have selected if they could invest time and effort into studying it. However, just as in our example, some of the agents may be uncertain about some of the issues, in which case they may vote against their best interest. Examples of such confusion abound in the real world and are welldocumented, e.g., in the context of Brexit or nuclear power.

In our setting, there are multiple issues and the benevolent party does not have its own preferences over the outcomes. Rather, it wants to maximize the number of issues on which the group is guaranteed to make the decision that matches the true preferences of the majority. This party, which may be a charity, an impartial governmental organization, or an ad-hoc working group, may have several tools at its disposal. For instance, it may be able to reach out to a subset of the agents and offer them an opportunity to learn more about the issues (e.g., by presenting information in an accessible manner, or holding a Q&A session with an expert). Alternatively, it may discourage some of the agents from participating in the vote.

The benevolent party may also help the agents with delegation decisions. Specifically, we assume that the voting mechanism used by the community supports delegation: an agent may delegate her vote to another agent, who will vote on her behalf on all issues. The agents are assumed to be willing to delegate to other agents who have similar preferences (i.e., i would not delegate to j if they disagree on an issue they are both certain about), but are more knowledgeable. The benevolent party can suggest delegation options to some of the agents, in a way that respects these constraints and maximizes the number of good decisions.

1.1 Our Contribution

We develop a formal model that enables us to reason about voters' confusion and ways to mitigate it. In this paper, we focus on independent binary issues, but our ideas can be extended to more complex decision-making scenarios. Our approach is worst-case: we want to maximize the number of issues that are 'safe', in the sense that the majority-supported outcome is guaranteed no matter how the uncertain voters cast their ballots. We consider both a general discrete issue space and a one-dimensional setting, where the issues are ordered in such a way that, for each agent, the set of issues on which she would benefit from a positive decision forms an interval of this ordering, and she is only uncertain about issues that are close to the endpoints of her 'positive interval'. For instance, consider a vote over tax rates, and a voter whose policy preferences are consistent with a tax rate in the [25%, 35%] range: this voter may confidently reject a proposal to set the tax rate to 15% or 45% and support a proposal to set it to 30%, but may struggle to make up her mind about the proposals in the [23%, 27%] range or the [34%, 38%] range.

We formulate three computational problems that model, respectively, educating the agents, preventing some agents from participating, and helping with delegation decisions. We establish that these problems are NP-hard even in the onedimensional setting, but show that they are fixed-parameter tractable-even in the general setting-both with respect to the number of voters and the number of issues. Moreover, we consider a natural special case of the one-dimensional setting in which all three problems are polynomial-time solvable. We omit some proofs due to space constraints.

1.2 RelatedWork

The analysis of voting outcomes under uncertainty is a prominent topic in computational social choice (see, e.g., [Walsh, 2007; Hazon et al., 2008; Bachrach et al., 2010; Wojtas and Faliszewski, 2012; Kenig and Kimelfeld, 2019]; however, it is usually assumed that it is an external party, rather than the voters themselves, who is uncertain about the votes. There is a large body of work in political science that considers voter education (see, e.g., [Lupia and McCubbins, 1998; Bullock, 2011; Boudreau et al., 2019] and the references therein); however, it does not engage with the associated algorithmic issues. The computational problem associated with removing voters is closely related to election control by deleting voters (see, e.g., the survey of Faliszewski and Rothe [2016]); however, in the control literature, it is assumed that the party engaging in voter deletion pursues its own goals rather than tries to implement the popular opinion. Finally, in the context of vote delegation, we mention works on liquid democracy from the perspective of discovering a good outcome [Brill and Talmon, 2018; Bloembergen et al., 2019; Kahng et al., 2021; G¨olz et al., 2021] in particular, Cohensius et al. [2017] and Green-Armytage [2015] consider vote delegation in the one-dimensional Euclidean domain.

2 Preliminaries

We will now define our model and formulate the computational problems that we are going to study.

Voting instances There is a proposal space P and a set of n agents N. For each agent i ∈ N, the space P is split as P = P +(i) ∪ P -(i) with P +(i) ∩ P -(i) = ∅; the proposals in P +(i) are beneficial for i, so i would want to approve them, while proposals in P -(i) are not beneficial for i. Also, for each agent i ∈ N, the space P is split as P = P ! (i)∪P ? (i) with P ! (i)∩P ? (i) = ∅; agent i is certain about the proposals in P ! (i) and uncertain about the proposals in P ? (i). Thus, an agent i can be described by a tuple π(i) = (P +(i), P ! (i)) ∈ P × P, which we will call agent i's belief; we write Π = (π(1), . . . , π(n)) and refer to the triple I = (P,N,Π) as a voting instance. For i ∈ N and ∗ ∈ {+,-}, † ∈ {!, ?}, let P ∗† (i) = P ∗ (i) ∩ P † (i). When casting an approval ballot, agent i will vote for all proposals in P +! (i) and against all proposals in P -! (i). Her vote over proposals in P ? (i), however, may be arbitrary; in particular, she may disapprove proposals in P +? (i) and approve proposals in P -? (i).

Correct and possible outcomes For each p ∈ P and ⋆ ∈ {+,-, ?, !}, let N ⋆ (p) = {i ∈ N : p ∈ P ⋆ (i)}. We say that a proposal p is good if |N +(p)| ≥ |N|/2 and bad if |N -(p)| ≥ |N|/2. Note that a proposal can be both good and bad: this happens if it is beneficial for exactly |N|/2 agents. An outcome z ∈ {0, 1} is correct for p if p is good and z = 1 ('approve'), or if p is bad and z = 0 ('disapprove'). We denote the set of correct outcomes for p by corr(p, I). Because of agent uncertainty, the outcome of an approval vote is not always correct: we say that 1 (respectively, 0) is a possible outcome for p if |N +(p) ∪ N ? (p)| ≥ |N|/2 (respectively, if |N -(p) ∪ N ? (p)| ≥ |N|/2). Note that corr(p, I) ⊆ poss(p, I) for each p ∈ P, but for some p ∈ P we may have poss(p, I) \ corr (p, I) ̸= ∅.

Safe proposals and safe zones Given a voting instance I = (P,N,Π), we say that a proposal p ∈ P is safe if poss(p, I) = corr(p, I) and unsafe otherwise. The set of safe proposals is called the safe zone for I.

Example 1. Consider an instance I with N = {1, 2, 3}, P = {p1, p2, p3, p4, p5}, and Π given by P +(1) = {p2, p3, p4}, P ? (1) = {p2, p4}, P +(2) = {p2, p3}, P ? (2) = {p1}, P +(3) = {p1, p2, p3}, and p? (3) = ∅.

The first agent benefits from p3 and knows this, so she is going to approve p3. She also benefits from p2, but is uncertain about this proposal, so she may disapprove it. We have corr(p1, I) = {0}, since agents 1 and 2 do not benefit from p1 (so N -(p1) = {1, 2}, N +(p1) = {3}). However, poss(p1, I) = {0, 1}, because agent 2 is uncertain about p2 (i.e., p2 ∈ P ? (2)) and may vote either way on it (i.e., |N +(p1) ∪N ? (p1)| = 2, |N -(p1) ∪N ? (p1)| = 2). Hence, p1 is not safe. The other four proposals, however, are safe.

Proposal Spaces

In general, our framework allows for infinite proposal spaces. However, in this work we will focus on settings where the proposal space is finite, i.e., P = {p1, . . . , pm}. A natural restricted case of our model is a one-dimensional setting, where P is ordered as p1 ≺ · · · ≺ pm, and agent preferences respect this order, as described below. We say that a set of proposals P ′ ⊆ P forms an interval of ≺ if P ′ = ∅ or P ′ = {pℓ : j ≤ ℓ ≤ k} for some 1 ≤ j ≤ k ≤ m. In the onedimensional setting we assume that, for each agent i ∈ N, the set P +(i) forms an interval of ≺. This approach takes inspiration from the notion of interval approval domains [Elkind and Lackner, 2015].

Furthermore, in the one-dimensional case we expect an agent to be certain that she dislikes extreme proposals and likes proposals in the center of her interval; however, she may be uncertain about proposals that are close to the endpoints of her interval. Hence, we assume that, for each i ∈ N with P +(i) = {pj , . . . , pk}, we have P ? (i) = P ?L(i)∪P ?R(i), where both P ?L(i) and P ?R(i) are intervals of ≺ that satisfy the following conditions: (1) P ?L(i) = ∅ or P ?L(i)∩{pj-1, pj} ̸= ∅; (2) P ?R(i) = ∅ or P ?R(i) ∩ {pk, pk+1} ̸= ∅.

Example 2. Note that the instance I from Example 1 is onedimensional. However, if we were to add either of the two agents 4, 5 with P +(4) = {p1, p5}, P ? (4) = ∅, P +(5) = {p2, p3, p4}, P ? (5) = {p3}, this would no longer be the case: P +(4) is not an interval, and P ? (5) fails conditions (1) and (2).

As the one-dimensional setting is essentially a domain restriction, algorithms for general finite proposal spaces apply in the one-dimensional setting, while NP-hardness results for the one-dimensional setting imply hardness for general spaces. Therefore, in what follows, for all problems we consider, we prove hardness results for the one-dimensional case (Section 3) and develop FPT algorithms for the general case (Section 4). Additionally, in Section 5 we present polynomial-time algorithms for a special, more restricted case of the one-dimensional model.

Algorithmic Challenges

We consider three approaches to eliminating uncertainty: (1) educating agents, (2) removing agents, and (3) delegating votes (known as liquid democracy). In each case, the goal is to maximize the size of the safe zone; an important special case of this task is to ensure that all projects are safe.

Educating agents In the first approach we consider, at a unit cost, we can educate one agent so as to entirely remove her uncertainty: if i has been educated, then the set P ? (i) becomes empty, so, when voting, agent i will approve proposals in P +(i) and disapprove proposals in P -(i).

EDUCATING AGENTS PROBLEM (EAP):

Input: A voting instance I = (P, N, Π), a budget κ, and a parameter λ ∈ N.

Question: Can we educate at most κ agents in N so that in the resulting instance I ′ the number of safe proposals is at least λ?

Note that the input to EAP contains the list Π; that is, we assume that, when deciding which agents to educate, we know which proposals are beneficial for them, i.e., we know the sets P +(i), P -(i) for all i ∈ N. Of course, this is not always the case; in particular, the agents themselves can be assumed to know the sets P +! (i), P -! (i) and P ? (i), but not P +(i) and P -(i). However, we expect that in practice we can usually make good predictions based on, e.g., demographic criteria.

Denying access The next approach we consider is to prevent up to κ agents from participating in the vote (equivalently, this approach can be viewed as selecting a committee). However, we still want to make decisions in a way that is beneficial to the majority of all agents, including those who are not invited to vote. That is, we consider the set of correct outcomes for each proposal with respect to the original voting instance I and the set of possible outcomes with respect to the modified instance I ′ , with up to κ agents removed. Note that it may be the case that corr(p, I) = {0, 1}, but poss(p, I ′ ) is a singleton; we consider such outcomes as acceptable.

DENYING ACCESS PROBLEM (DAP):

Input: A voting instance I = (P, N, Π), a budget κ, and a parameter λ ∈ N.

Question: Can we remove at most κ agents from N to obtain an instance I ′ such that the number of proposals p ∈ P with corr(p, I) ⊃ poss(p, I ′ ) is at least λ?

Note that, to solve DAP, we do not need full access to the 'hidden' sets P +(i), P +(i); it suffices to have access to the 'known' sets P +! (i), P -! (i) and P ? (i) for each i ∈ N as well as the correct outcome for each proposal (which we expect to be easier to estimate than individual preferences).

Allowing delegations The last approach we consider is to allow the agents to delegate their votes to other agents, transitively. An agent that accumulates t votes participates in the election with voting weight t. This framework is known as liquid democracy [Green-Armytage, 2015]. We assume that our agents are rather conservative in their delegation decisions: we say that agent i is willing to delegate her vote to agent j if (1) P +! (i)∩P -! (j) = ∅ and P -! (i)∩P +! (j) = ∅, and (2) |P ! (i)| < |P ! (j)|. Condition (1) indicates that agent i cannot observe any disagreement between herself and agent j, and condition (2) indicates that agent j is more knowledgeable than agent i. A delegation graph consistent with an instance I is a directed acyclic graph D over the vertex set N such that the outdegree of each vertex is at most 1; it may contain an arc (i, j) only if agent i is willing to delegate to agent j. Given a graph D, for each i ∈ N we denote the unique sink reachable from i by s(i); the agent s(i) is the 'guru' of agent i, so that i will adopt the beliefs of s(i). The graph D corresponds to a modified instance I ′ (D) = (N, P,Π′ ) such that π′ (i) = π(s(i)) for each agent i ∈ N; intuitively, in I ′ (D) agent i copies the ballot of her guru s(i). We want to construct a delegation graph that results in decisions that benefit the majority of the agents for as many proposals as possible.

CONSTRAINED LIQUID DEMOCRACY (CLD):

Input: A voting instance I = (P,N,Π), and a parameter λ ∈ N.

Question: Is there a delegation graph D consistent with I such that the number of proposals p ∈ P with corr(p, I) ⊃ poss(p, I ′ (D)) is at least λ?

Importantly, in a way, our model implicitly assumes that the delegation decisions are made in a centralized manner; however, no agent can be asked to delegate their vote in a way that is unacceptable to them.

Example 3. Consider again the instance I of Example 1.

Note that, in I, we can make all proposals safe by educating agent 2. If we can only remove agents, then the only way to ensure the correct outcome on p1 is to remove agents 2 and 3; however, if we do so, we may get an incorrect outcome on p2 and p4, so no removal strategy can ensure the correct outcome on all proposals.

Finally, observe that agent 1 can delegate to agent 2 (they agree on the two proposals on which they are both certain, i.e., p3 and p5, and |P ! (2)| > |P ! (1)|), and agent 2 can delegate to agent 3, but agent 1 cannot directly delegate to agent 3. However, if 1 delegates to 2 and 2 delegates to 3, then agent 3 becomes the guru for agent 1. No delegation strategy ensures a correct outcome on all proposals.

3 Intractability Results

It follows from our definitions that checking whether a given proposal is safe or determining the number of safe proposals can be done in polynomial time. Next we show that EAP, DAP, and CLD are NP-complete. Containment in NP follows immediately; thus, in what follows, we focus on showing that these problems are NP-hard. Perhaps surprisingly, our hardness results hold even for the one-dimensional setting.

Theorem 1. EAP, DAP and CLD are NP-complete, even in the one-dimensional proposal space.

Proof. We provide a proof for CLD; the proofs for EAP and DAP are omitted due to space constraints. We reduce from the NP-hard problem VERTEX COVER ON CUBIC GRAPHS (VC-CG) [Garey et al., 1976]. An instance of this problem consists of an undirected cubic graph G = (V,E) (i.e., the degree of each vertex v ∈ V is exactly 3) and an integer κ; it is a yes-instance if G admits a vertex cover of size κ (i.e., a subset V ′ ⊆ V that contains at least one endpoint of each edge), and a no-instance otherwise.

Consider an instance of VC-CG given by a graph G = (V,E) and an integer κ. Fix an arbitrary order ◁E on E. For each edge e ∈ E with endpoints u and v, we introduce proposals se, re,u, pe, re,v (jointly denoted as the edge gadget for e). For each vertex u, we introduce proposals su, pu, and qu (jointly denoted as the vertex gadget for u). Additionally, we introduce two proposals, denoted by s$, p$ (the sink gadget). The proposals are ordered so that (1) all edge gadgets precede all vertex gadgets, and all vertex gadgets precede the sink gadget; (2) the edge gadgets appear in the order induced by ◁E; (3) the vertex gadgets appear in an arbitrary order; (4) within an edge gadget for e = {u, v}, the proposals are ordered as se ≺ re,u ≺ pe ≺ re,v; (5) within a vertex gadget for u, the proposals are ordered as su ≺ pu ≺ qu; (6) within the sink gadget, the proposals are ordered as s$ ≺ p$.

For each vertex u ∈ V , we consider the edges a, b, c incident on u (assume a ◁E b ◁E c), and introduce eight agents, denoted vu a,1 , vu a,2 , vu b,1 , vu b,2 , vu c,1 , vu c,2 , vu 1 , vu 2 (they are said to be related to u) with the following beliefs:

• the sets P +(vu a,1 ) and P +(vu a,2 ) consist of all proposals in the shortest interval containing pa, ra,u and rb,u, and P ? (vu a,1 ) = {pa, ra,u}, whereas P ? (vu a,2 ) = {rb,u}.
• the beliefs of vu b,1 and vu b,2 (resp., vu c,1 and vu c,2 ) are defined similarly, replacing pa by pb (resp., pc), ra,u by rb,u (resp., rc,u) and rb,u by rc,u (resp., pu).
• the sets P +(vu 1 ) and P +(vu 2 ) consist of all proposals in the interval from pu to p$, and P ? (vu 1 ) = {pu, qu}, P ? (vu 2 ) = {p$}.

We then add polynomially many balancing agents so that we have 2K + 1 agents in total for some K ∈ N and:

• |N +(pe)| =K +2, |N +? (pe)| = 2 for each e ∈ E;
• |N +(re,u)| =K+2, |N +? (re,u)| = 1 or |N +(re,u)| = K + 3, |N +? (re,u)| = 2 for each e ∈ E, u ∈ e;
• |N +(pu)| = |N +(qu)| = K + 3, |N +? (pu)| = 2, |N +? (qu)| = 1;
• |N +(se)| = |N +(su)| = |N +(s$)| =K+1, N ? (se) = N ? (su) = N ? (s$) = ∅, for each e ∈ E, u ∈ V ; and
• |N +(p$)| =K + |V | +κ+1, |N +? (p$)| = |V |.

To this end, we add agents that benefit from a single proposal only (and are certain about it), until the desired differences in support for each proposal are accomplished, and then add sufficiently many agents who benefit from all proposals, to get the target numbers. Let NV denote the set of all vertexrelated agents and let NB be the set of balancing agents.

We now consider the delegation graph. Note first that for each u ∈ V agent vu 1 may delegate to vu 2 , and for each edge e incident on u agent vu e,1 may delegate to vu e,2 . We claim that the delegation graph cannot contain any other arcs.

To see this, observe first that for each i ∈ NB we have P ? (i) = ∅, |P +(i)| = 1. Moreover, for each agent j ∈ NV we have |P +! (j)| ≥ 2. Hence, no agent in NB can delegate her vote to another agent, and no agent in NV can delegate her vote to an agent in NB.

Further, let S = {sξ : ξ ∈ V ∪ E ∪ {$}} be the set of separators, and note that N ? (s) = ∅ for all s ∈ S. Hence, for the arc (i, j) to be in the delegation graph, i and j must agree on all separators. This can only happen if the positive intervals for i and j start in the same gadget as well as end in the same gadget, which establishes our claim.

It follows that all paths in the delegation graph consist of at most one arc. Hence, any delegation scenario may only change the number of uncertain agents for each proposal, e.g., for each p ∈ P, no agent in N +! (p) can delegate (either directly or indirectly) to an agent in N -! (p) or vice versa.

Hence, we can make all proposals safe if and only if the following conditions are satisfied:

• For each e ∈ E, |N ? (pe)| decreases by at least 1.
• For each e ∈ E and u ∈ e, |N ? (re,u)| does not increase.
• For each u ∈ V , |N ? (pu)| does not increase.
• |N ? (p$)| increases by at most κ.

We will now prove that there exists a delegation graph D that guarantees correct decisions on all proposals if and only if G has a vertex cover of size κ.

For the 'if' direction, let X be a size-κ vertex cover of G. Then, for each x ∈ X, consider the following delegations: vx e,1 → vx e,2 for each e incident on x, and vx 1 → vx 2 . As each edge e is incident on some x ∈ X, these delegations reduce by 1 the size of each set N ? (pe), e ∈ E, and increase by κ the size of the set N ? (p$). The only other proposals affected by these delegations are proposals of the form re,x and px, qx, where x ∈ X. But then it can be checked that the sizes of the sets N ? (re,x), N ? (px) and N ? (qx) either decrease by one or do not change. Specifically, if a◁E b◁E c are the three edges incident on x then (1) vx a,1 → vx a,2 decreases |N ? (ra,x)| by 1 and increases |N ? (rb,x)| by 1; (2) vx b,1 → vx b,2 decreases |N ? (rb,x)| by 1 and increases |N ? (rc,x)| by 1; (3) vx c,1 → vx c,2 decreases |N ? (rc,x)| by 1 and increases |N ? (px)| by 1; (4) vx 1 → vx 2 decreases |N ? (px)| and |N ? (qx)| by 1. Overall, the number of uncertain agents for each proposal falls within the desired bounds, and all proposals are safe.

For the 'only if' direction, consider a delegation graph D that guarantees correct decisions on all proposals. Fix a node u ∈ V , and let a ◁E b ◁E c be the edges of G incident on u. If D contains the arc vu c,1 → vu c,2 , then it must also contain the arc vu 1 → vu 2 (or else |N ? (pu)| would increase by 1). Similarly, if D contains the arc vu b,1 → vu b,2 , it must also contain vu c,1 → vu c,2 (or else |N ? (rc,u)| would increase by 1) and hence vu 1 → vu 2 . Finally, if D contains the arc vu a,1 → vu a,2 , it must also contain vu b,1 → vu b,2 (or else |N ? (rb,u)| would increase by 1) and hence vu c,1 → vu c,2 and, in turn, vu 1 → vu 2 . That is, if D contains a delegation between two agents related to u, it must contain the arc vu 1 → vu 2 .

Let X be the set of vertices x with vx 1 → vx 2 . Each such delegation increases |N ? (p$)| by 1, so |X| ≤ κ. Now, consider an edge e = {u,w}. Since |N ? (pe)| must decrease by at least one, at least one of the delegations vu e,1 → vu e,2 or vw e,1 → vw e,2 must take place; assume without loss of generality that D contains the arc vu e,1 → vu e,2 . As argued above, this means that D also contains the arc vu 1 → vu 2 , i.e., u ∈ X. Hence, X is a vertex cover for G of size at most κ.

4 Fixed-Parameter Tractability in n andm

In this section, we show that all three of our problems-EAP, DAP, and CLD-are fixed-parameter tractable (FPT) with respect to the number of voters (n), and independently, with respect to the number of proposals (m). These results hold even for the maximization version of these problems, where the goal is to maximize the number of proposals on which the correct outcome is obtained, and also do not require the assumption that the proposal space is one-dimensional.

For the number of agents n, we can use brute-force algorithms, as there are 2n possible subsets of agents to educate or delete, and at most nn different delegation graphs. For the number of proposals m, our approach is based on integer linear programming.

Proposition 1. EAP, DAP, and CLD are FPT for n as well as FPT for m.

Proof. We show the proof for DAP and m. First, note that we can remove all proposals p with |N +(p)| = |N -(p)| from the description of our voting instance (as we are satisfied with either outcome on any such proposal). Thus, from now on we will assume that, for each p ∈ P , we have |N +(p)| > n/2 or |N -(p)| > n/2.

Given an agent i, construct a string t = (t1, . . . , tm) over {+,-, ?}, where, for each j ∈ [m], we set tj = + if pj ∈ P +! (i), tj = - if pj ∈ P -! (i), and tj =? if pj ∈ P ? (i). We will refer to t as the type of i. Let T = {+,-, ?}m. By construction, there are at most 3m distinct agent types.

For each t ∈ T , let yt denote the number of agents of type t in I, and let xt denote the number of agents of type t in the instance I ′ obtained after some agents have been deleted. The constraint that we can remove at most κ agents is encoded as

For each proposal pj ∈ P , let T +! (j) = {t ∈ T : tj = +}, T -! (j) = {t ∈ T : tj = -}, T ? (j) = {t ∈ T : tj =?}. Given a proposal pj, let

Note that aj, bj ≤ n. If pj is good, then we would like aj to be positive, and if pj is bad, then we would like bj to be positive. Thus, for each j ∈ [m] we introduce a variable zj that takes values in {0, 1}, and add the constraint

if pj is good and the constraint

if pj is bad. The reader can verify that condition (j-good) ensures that zj = 1 if and only if aj > 0, whereas condition (j-bad) ensures that zj = 1 if and only if bj > 0.

To summarize, the set of variables of our ILP is {xt : t ∈ T} ∪ {aj, bj, zj : j ∈ [m]}, and its objective function is max ∑j∈[m] zj. The set of constraints consists of (1), (2), and, for each j ∈ [m], one of the constraints (j-good) or (jbad), depending on whether pj is good or bad, together with the constraint 0 ≤ zj ≤ 1. Following Lenstra's result [Jr., 1983], this ILP can be solved in time poly ((3m)O(3m) , n).

5 The Radical One-Dimensional Domain

Here we consider a more restricted variant of the onedimensional model in which, for each agent i ∈ N, the set P +(i) is a suffix of ≺, i.e., either P +(i) = ∅ or pm ∈ P +(i). Intuitively, this model reflects settings where the proposals can be naturally ordered from radical proposals to mild proposals, so that a typical agent disapproves the most radical proposal, but approves the mildest proposal, and switches from disapproval to approval at a certain point in which the proposals become less extreme. Consequently, in this model, referred to as the radical 1D domain, P ? (i) is an interval of ≺, for each i ∈ N. For convenience, in what follows we assume that the number of agents n is odd and hence corr(p, I)

is a singleton for each p ∈ P (but our results hold also for even number of agents); slightly abusing notation, we write corr(p, I) = z instead of corr(p, I) = {z}.

First, we make the following two observations.

Observation 1. For the radical 1D domain, the list (corr(pi, I))i∈[m] is of the form (0, . . . , 0, 1, . . . , 1).

Proof. Suppose that corr(pj, I) = 1 for some j < m. Then |N +(pj)| > n/2. Consider a proposal pk with k > j. For each agent i ∈ N with pj ∈ P +(i) we have pk ∈ P +(i) and hence N +(pj) ⊆ N +(pk). It follows that |N +(pk)| > n/2, i.e., corr(pk, I) = 1.

Observation 2. For the radical 1D domain, if a proposal pj is safe and corr (pj , I) = 0, then each proposal pk with k ≤ j is safe. Similarly, if pj is safe and corr(pj, I) = 1, then each proposal pk with k ≥ j is safe.

Proof. Fix a safe proposal pj. Suppose corr(pj, I) = 0; the case corr(pj, I) = 1 is symmetric. As pj is safe, we have |N -! (pj)| > n/2. Consider a proposal pk with k < j. Note that pj ∈ P -! (i) implies pk ∈ P -! (i). Hence N -! (pj) ⊆ N -! (pk) and |N -! (pk)| ≥ |N -! (pj)| > n/2, so pk is safe.

We will now show that for the radical 1D domain the problems EAP, DAP and CLD admit polynomial-time algorithms.

Proposition 2. In the radical 1D domain, EAP, DAP, and CLD are all solvable in polynomial time.

Proof. By Observation 2, unsafe proposals form an interval of the form {pj+1, . . . , pk-1} for some pj, pk ∈ P with corr(pj, I) = 0, corr(pk, I) = 1. We consider all O(m2 ) possible choices for j and k such that k+1-j ≤ λ, and aim to modify the instance so as to guarantee correct outcomes on pj and pk; this ensures that we obtain correct outcomes on all proposals, except possibly for the proposals in the set {pj+1, . . . , pk-1}.

For EAP and DAP, we can decide if a suitable modification exists by running our FPT algorithm (Proposition 1) on the set of proposals {pj, pk}; note that this algorithm runs in polynomial time when there are just two proposals.

Unfortunately, this strategy fails for CLD, because proposals other than pj and pk influence which edges can appear in a delegation graph. Hence, we use a different approach. We say that an agent i is I-correct on proposal pℓ if corr(pℓ, I) = 0 and pℓ ∈ P -! (i), or corr(pℓ, I) = 1 and pℓ ∈ P +! (i). Also, we say that a delegation graph D is (j, k)-good if in the instance I ′ (D) more than n/2 agents are I-correct on pj and more than n/2 agents are I-correct on pk.

To check if there is a (j, k)-good delegation graph, we partition the set N as N = NA ∪ NB ∪ NC ∪ ND so that

• agents in NA are I-correct on both pj and pk;
• agents in NB are I-correct on pj, but not on on pk;
• agents in NC are I-correct on pk, but not on pj; and
• agents in ND are I-correct on both pj and pk.

Suppose there exists a (j, k)-good delegation graph D. Then, in I ′ (D), more than n/2 agents are I-correct on pj and more than n/2 agents are I-correct on pk. As these two sets of agents must overlap, there is an agent in I ′ (D) that is Icorrect on both pj and pk. Since delegation amounts to agents copying the preferences of their gurus, this means that there is some such agent in I, i.e., NA must be non-empty.

Thus, if NA = ∅, there is no (j, k)-good delegation graph. Assume, then, that NA is non-empty. Note that all agents in ND must be uncertain about pj and pk (and hence about all proposals in between) and are therefore willing to delegate to agents in NA, who are certain about both. Further, if there is a (j, k)-good delegation graph, then there is one in which all agents who can delegate to an agent in NA do so (and thereby copy the preferences of their guru). Hence, as our next step, we repeatedly check whether NB ∪ NC ∪ ND contains an agent who is willing to delegate to an agent in NA; if so, then we move this agent to NA. This process stops when no such agent remains. Observe that at this point ND = ∅.

Now, if |NB| + |NA| > n/2, then there is a majority of agents who are I-correct on pj, and if |NC| + |NA| > n/2, then there is a majority of agents who are I-correct on pk; so, if both of these conditions are satisfied, then we are done. Assume without loss of generality that |NC| ≥ |NB|. As we have |NB| + |NA| + |NC| + |NA| = n + |NA| > n, the condition |NC| + |NA| > n/2 is satisfied in this case.

Suppose, however, that |NB| + |NA| ≤ n/2. Then, the only way to obtain the correct outcome on both pj and pk is to find t = ⌈ n2 ⌉-|NA|-|NB| agents in NC who can delegate to agents in NB; indeed, in this case, after the delegation we will have ⌈ n2 ⌉ agents who are I-correct on pj and |NC| - t + |NA| = n + |nA| - ⌈ n2 ⌉ ≥ ⌈ n2 ⌉ agents who are I-correct on pk (where the last inequality holds because |NA| ≥ 1).

To determine whether these t delegating agents could be found, we construct a graph G on NB ∪ NC with an edge from agent i to agent i′ if and only if i is willing to delegate to i′ , and mark each agent in NC that has a path to an agent in NB; the answer is positive if and only if at least t agents are marked. This completes the proof.

6 Outlook

We have considered three algorithmic approaches to coping with confused communities that wish to reach good joint decisions, and showed that, even though our problems are generally NP-complete, there are special cases for which efficient algorithms exist.

Avenues for future research include the following: (1) a study of other proposal spaces, including, in particular, continuous proposal spaces; (2) extending our analysis to settings where proposals may have different importance and/or issues are non-binary; (3) an exploration of different approaches to coping with voter uncertainty, including models in which the effect of education efforts is probabilistic and may propagate through an underlying social network; (4) the development of computer-based simulations for the practical evaluation of the effectiveness of our algorithmic approaches.