# complexity_of_deliberative_coalition_formation__d498e0de.pdf

Complexity of Deliberative Coalition Formation*

Edith Elkind, Abheek Ghosh , Paul Goldberg

Department of Computer Science, University of Oxford, UK {edith.elkind,abheek.ghosh,paul.goldberg}@cs.ox.ac.uk

Elkind et al. (2021) introduced a model for deliberative coalition formation, where a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. In their model, agents and proposals are points in a metric space, agents preferences are determined by distances, and agents deliberate by dynamically forming coalitions around proposals that they prefer over the status quo. The deliberation process operates via kcompromise transitions, where agents from k (current) coalitions come together to form a larger coalition in order to support a (perhaps new) proposal, possibly leaving behind some of the dissenting agents from their old coalitions. A deliberation succeeds if it terminates by identifying a proposal with the largest possible support. For deliberation in d dimensions, Elkind et al. consider two variants of their model: in the Euclidean model, proposals and agent locations are points in Rd

and the distance is measured according to || ||2; and in the hypercube model, proposals and agent locations are vertices of the d-dimensional hypercube and the metric is the Hamming distance. They show that in the Euclidean model 2compromises are guaranteed to succeed, but in the hypercube model for deliberation to succeed it may be necessary to use k-compromises with k d. We complement their analysis by (1) proving that in both models it is hard to find a proposal with a high degree of support, and even a 2-compromise transition may be hard to compute; (2) showing that a sequence of 2-compromise transitions may be exponentially long; (3) strengthening the lower bound on the size of the compromise for the d-hypercube model from d to 2Ω(d).

1 Introduction Imagine a nominally democratic country where the current ruling party has been in power for many years, through a combination of clever political strategizing and a range of more or less non-democratic means (e.g., gerrymandering, vote suppression, media control, etc.). Even if, initially, political parties and alliances other than the ruling party may differ in positions they take on various issues facing the society, after many years of being out of power, they may choose

*Extended version of the paper is available at https://arxiv.org/ abs/2202.12594 Supported by Clarendon Fund and SKP Scholarship. Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

to focus on what unites them rather than on what differentiates them, and seek to identify a common platform that would enjoy broad popular support and enable them to overturn the status quo. In doing so, they may pursue a variety of goals: to increase their chances of winning seats in an election, to place themselves in a better position in post-electoral bargaining, or in the most extreme cases to initiate a revolt against the current regime. This common platform may be quite different from the party s true position what matters is that it attracts a large number of supporters and that it offers an improvement over the status quo, i.e., is preferable to the policies of the current governing party. In a recent paper, Elkind et al. (2021, 2020) propose a simple model that aims to capture essential features of such scenarios1. In this model, both voters and proposals are associated with points in a metric space, with voters preference being driven by distances: voters prefer proposals that are close to them to ones that are further away. The number of voters is finite, but the set of feasible proposals may be any (potentially infinite) subset of the metric space. There is also a distinguished point, referred to as the status quo and denoted by r. A voter v approves a proposal p if her distance to p is strictly less than her distance to r. Voters deliberate in order to identify a proposal that is supported by as many voters as possible. At each point, each voter selects some approved proposal to support, with voters who support a given proposal forming a deliberative coalition around it. This collection of deliberative coalitions a deliberative coalition structure evolves based on transition rules: for instance, one transition rule allows two coalitions to identify a new proposal supported by all members of both coalitions and to form a new joint coalition around it. The transition rules aim to capture the behavior of agents who are consensus-driven i.e., they desire to form a large coalition to overturn the status quo and myopic, in the sense that they make a decision whether to participate in a transition based on the outcome of that transition only and not the entire deliberative process.

1The conference version of their paper (Elkind et al. 2021) was published in AAAI 21, and an extended version was presented at COMSOC 21 and is available from ar Xiv (Elkind et al. 2020). One of the models we consider, namely, the hypercube model, is only described in the ar Xiv version, so in what follows we refer to the ar Xiv version only.

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

In their work, Elkind et al. (2020) primarily focus on the power of various transition rules to enable the identification of popular proposals, in a range of metric spaces. They do not investigate the complexity of the associated algorithmic challenges, and only offer very crude bounds on the number of steps it may take the deliberation process to converge.

1.1 Our Contribution Our goal is to complement the analysis of Elkind et al. (2020), by exploring the complexity of the deliberation process in their model. We focus on two deliberation spaces: in the hypercube model, voters and proposals are vertices of the d-dimensional hypercube, with distances measured according to the Hamming distance, and in the Euclidean model voters and proposals are elements of the d-dimensional Euclidean space, with || ||2 being the underlying distance measure. In both models, each point of the underlying metric space is considered to be a feasible proposal. We consider three types of questions:

What is the computational complexity of identifying a proposal approved by as many voters as possible, both from a centralized perspective (i.e., how can we compute a popular proposal given the positions of all voters), and from a decentralized perspective (i.e., how can a group of voters identify the next step in the deliberative process)? We consider both the worst-case complexity of this problem and its parameterized complexity, with two natural parameters being the number of voters and the dimension of the space. How many transitions may be necessary for a deliberation to converge? Elkind et al. (2020) show that deliberation always converges after at most nn steps, where n is the number of voters; we improve this upper bound to 2n and derive exponential lower bounds for both of the models we consider. How many coalitions need to be involved in each deliberation step to ensure that a most approved proposal is identified? Elkind et al. (2020) prove that in Euclidean deliberation spaces 2-coalition deals are sufficient irrespective of dimension, and in a d-dimensional hypercube we may need transitions involving at least d coalitions; we improve this lower bound from d to 2Θ(d).

The work of Elkind et al. (2020) is an important step towards modeling coalition formation in the presence of a status quo option. Such a theory provides formal foundations for the design and development of practical systems that can support successful deliberation, for instance, by helping agents to identify mutually beneficial compromise positions (cf. di Fenizio and Velikanov; 2016). Our paper supplements the analysis of Elkind et al. (2020) by resolving several challenging open questions posed by their work.

1.2 Related Work Our work builds directly on the work of Elkind et al. (2020). In turn, their paper belongs to a rich tradition in political science that studies spatial coalition formation (Coombs 1964; Enelow and Hinich 1984; Merrill III and Grofman 1999;

Vries 1999). An important feature of their model that sets it somewhat apart from prior work is the presence of a special reference point, i.e., the status quo. The agenda of social choice in the presence of status quo has recently been pursued by Shapiro, Talmon, and co-authors in a series of papers (Shapiro and Talmon 2018; Shahaf, Shapiro, and Talmon 2019; Bulteau et al. 2021; Abramowitz, Shapiro, and Talmon 2021). The study of group deliberation is a broad and interdisciplinary area, see, e.g., (Austen-Smith and Feddersen 2005; Hafer and Landa 2007; Patty 2008; List 2011; List et al. 2013; Rad and Roy 2021; Perote-Pe na and Piggins 2015; Karanikolas, Bisquert, and Kaklamanis 2019); we refer the reader to the work of Elkind et al. (2020) for further discussion. In particular, an important consideration is whether simple deliberation protocols that only involve a small number of participants can achieve a desirable outcome (Goel and Lee 2016; Fain et al. 2017); this question is similar to the one considered in Section 5 of our paper. The process of deliberation that we consider can be viewed as one of dynamic coalition formation (Konishi and Ray 2003; Arnold and Schwalbe 2002; Chalkiadakis and Boutilier 2012). Indeed, the transitions from one deliberative coalition structure to the next one can be interpreted as a form of better response dynamics, where agents prefer deliberative coalitions whose proposal they approve to those whose proposal they do not approve, and, among coalitions whose proposal they approve, they favor larger coalitions. Potential functions are commonly used in the literature to establish upper bounds on convergence time of better response dynamics (see, e.g., Tardos and Wexler; 2007); however, our use of a potential function to establish a lower bound (Section 4) is somewhat unconventional.

2 Preliminaries Following Elkind et al. (2020), we define a deliberation space as a 4-tuple (X, V, r, ρ), where X is a (possibly infinite) set of proposals, V = {v1, . . . , vn} is a set of n agents, r X is a special element of X, which we will refer to as the status quo, and ρ is a metric on X V. An agent vi is said to approve a proposal x X \{r} if ρ(vi, x) < ρ(vi, r): intuitively, vi approves x if x is more representative of her position than r is. It will be convenient to require that each agent approves at least one proposal, i.e., to exclude agents that are happy with the status quo. We will consider two families of d-dimensional deliberation spaces, where d is a positive integer: Euclidean deliberation spaces and hypercube deliberation spaces. We refer to Elkind et al. (2020) for a discussion of some other deliberation spaces.

d-Euclidean The space of proposals X is Rd, r = (0, 0, . . . , 0), and vi Rd for each i [n]. The metric ρ is the usual Euclidean norm: ρ(x, y) = ||x y||2. d-Hypercube The space of proposals X is {0, 1}d, r = (0, 0, . . . , 0), and vi {0, 1}d for each i [n]. The metric ρ is the Hamming distance: ρ(x, y) = ||x y||1. At any point in the deliberation process, the set of agents is split into deliberative coalitions. A deliberative coalition

is a pair d = (C, x), where C is a non-empty subset of V, x X \{r}, and each agent in C approves x. When convenient, we identify a deliberative coalition d = (C, x) with its set of agents C, and say that agents in C support x. A deliberative coalition structure is a set D = {d1, . . . , dm}, m 1, such that: dj = (Cj, xj) is a deliberative coalition for each j [m]; j [m]Cj = V and Cj Cℓ= for all j, ℓ [m] such that j = ℓ. The agents start out in some deliberative coalition structure, and then this structure evolves according to transition rules. Elkind et al. (2020) define several such rules; in this paper, we focus on k-compromise transitions. The intuition behind all these rules is that agents seek to form large coalitions and act myopically, i.e., an agent in a deliberative coalition (C, x) is willing to deviate so as to end up in a coalition (C , x ) if (i) she approves x and (ii) |C | > |C|. Specifically, under a k-compromise transition, agents from ℓ k existing deliberative coalitions d1, . . . , dℓ, where dj = (Cj, xj) for j [ℓ], get together and identify a proposal x such that t of them approve x and t > |Cj| for each j [ℓ]. Then all agents who approve x form a deliberative coalition that supports proposal x. The agents in Cj who do not approve x stay put, i.e., they end up in deliberative coalition (C j, xj) with C j = Cj\C (note that C j may be empty). This notion is formalized as follows. Definition 2.1 (k-Compromise Transitions). A pair of coalition structures (D, D ) forms a k-compromise transition if there exist an ℓ [k] and ℓcoalitions d1, . . . , dℓ D, where dj = (Cj, xj) for j [ℓ], such that D is obtained from D by (1) removing d1, . . . , dℓ, (2) adding a deliberative coalition (C, x) such that C j [ℓ]Cj, for each j [ℓ] it holds that |C| > |Cj| and C Cj consists of all agents in Cj that approve x; (3) for each j [ℓ] such that Cj C adding a deliberative coalition (Cj \ C, xj). We say that a deliberative coalition structure D is kterminal if there does not exist a k-compromise transition of the form (D, D ). A k-deliberation is a sequence of k-compromise transitions such that for the last transition (D, D ) in this sequence it holds that D is terminal. We will refer to D as the outcome of the respective k-deliberation. We define the score of a proposal x X \{r} as the number of agents in V who approve x. We say that a proposal x X \{r} is popular if its score is at least as high as that of any other proposal in X \{r}. A deliberative coalition structure D is successful if it contains a deliberative coalition (C, x) such that x is a popular proposal and C consists of all agents who approve x. A k-deliberation is successful if its outcome is successful. Note that if there is a majority-approved proposal, a successful k-deliberation identifies some such proposal, enabling a majority-supported change to the status quo. An important result of Elkind et al. (2020) is that a deliberation process with k-compromise transitions always terminates. Theorem 1. (Elkind et al. 2020) For each integer k with 2 k n a k-deliberation can have at most nn transitions.

This result holds for any deliberation space, so in particular both for the d-Euclidean space and the d-hypercube for any d 1.

3 Complexity of Finding Popular Proposals In this section, we focus on the complexity-theoretic challenges presented by the deliberation process. We first consider two computational problems: SCORE and PERFECT SCORE. For SCORE, the input is a deliberation space and a positive integer η, and we ask if there is a proposal that is approved by at least η agents in V; in PERFECT SCORE, we are given a deliberation space and ask if there is a proposal that is approved by all agents in V. These problems model the challenge of finding a good proposal in a centralized way. As PERFECT SCORE is a special case of SCORE, an NPhardness result for PERFECT SCORE implies that SCORE, too, is NP-hard, whereas a polynomial-time algorithm for SCORE can be used to solve PERFECT SCORE in polynomial time. We will also consider another computational problem, which captures the complexity of the decentralized deliberation process: in k-COMPROMISE, we are given a deliberative space and a deliberative coalition structure, and the goal is to find a k-compromise transition from this coalition structure if one exists; note that k-COMPROMISE is a function problem and not a decision problem. For all three problems, we use prefixes Euc and Hyp to indicate whether we consider the variant of the problem for the Euclidean space or for the hypercube. Given a deliberation space I = (S, V, r, ρ), we denote by |I| the number of bits in the description of I. For dhypercube deliberation spaces, this is simply O(nd) (we need to specify d bits per agent). For Euclidean deliberation spaces, we assume that the locations of all agents are vectors of rational numbers given in binary; similarly, when we consider k-COMPROMISE, we assume that the proposals supported by the coalitions in the initial deliberative coalition structure are vectors of rational numbers given in binary. We will first consider hypercubes, and then Euclidean spaces.

3.1 Hypercube Deliberation Spaces In hypercube deliberation spaces, even deciding whether there is a unanimously approved proposal is computationally difficult. Theorem 2. Hyp-PERFECT SCORE is NP-complete. We prove Theorem 2 by a reduction from INDEPENDENT SET (Garey and Johnson 1979); the proof is provided in the full version of the paper. Since SCORE is at least as hard as PERFECT SCORE, and it is clearly in NP, we obtain the following corollary. Corollary 3. Hyp-SCORE is NP-complete. Moreover, for hypercube deliberation spaces, we can show that computing a k-compromise is at least as hard as finding a proposal with a perfect score. Corollary 4. For each k 2, there does not exist a polynomial-time algorithm for Hyp-k-COMPROMISE unless P = NP.

Proof. Suppose we have a polynomial-time algorithm for Hyp-k-COMPROMISE for some k 2. We will explain how it can be used to solve Hyp-PERFECT SCORE in polynomial time. Given an instance I of Hyp-PERFECT SCORE, we proceed inductively as follows. For each i [n], let Ii be our instance of Hyp-PERFECT SCORE restricted to the first i agents. We will explain how to find a proposal xi approved by each of the agents v1 . . . , vi if it exists (and output no if it does not). For I1, we can set x1 = v1. To solve Ii, we first solve Ii 1. If the answer for Ii 1 is no , then we output no as well. Otherwise, we form an instance of Hyp-k-COMPROMISE that contains the first i agents; the initial deliberative coalition structure consists of ({v1, . . . , vi 1}, xi 1) and the singleton deliberative coalition ({vi}, vi). We can then run the algorithm for Hyp-k COMPROMISE, k 2, on this instance; it returns a proposal if and only if Ii is a yes-instance of PERFECT SCORE.

On the positive side, the problem of finding a popular proposal becomes easy if the number of agents or the number of dimensions is small: indeed, we can obtain an FPT algorithm with respect to each of these parameters.

Proposition 5. Given a d-hypercube deliberation space, we can compute a popular proposal in time O(2ddn).

Proof. We can go through the proposals one by one; it takes O(d) time to decide whether a given agent prefers a given proposal to the status quo, so we can determine the score of each proposal in time O(dn). As there are 2d 1 proposals other than the status quo, the bound on the running time follows.

Proposition 6. Given a d-hypercube deliberation space, we can compute a popular proposal in time poly(2n2n, log d).

Proof. Given an n-bit vector b = (b1, . . . , bn) {0, 1}n, we say that a dimension j [d] is of type b if for each i [n] the j-th coordinate of vi is equal to bi. Thus, each dimension belongs to one of the 2n possible types. For a type b, let nb denote the number of dimensions of type b. We can then represent a proposal x by a sequence of numbers (xb)b {0,1}n, where 0 xb nb: the value xb indicates the number of dimensions of type b that are set to 1 in x. Now, for each subset of agents S V, we formulate a set of constraints on the values (xb)b {0,1}n which ensure that x is approved exactly by the agents in S.

1. For each agent i in S, X

b:bi=0 xb + X

b:bi=1 (nb xb) < X

b:bi=0 xb X

b:bi=1 xb 1.

In the constraint above, P b:bi=0 xb counts the number of dimensions where the agent has value 0, but the proposal has value 1, while P b:bi=1(nb xb) counts the number of dimensions where the agent has value 1 but the proposal has value 0; overall, it measures the distance

of the agent from the proposal. P b:bi=1 nb measures the distance of the agent from the status quo. 2. For each agent i not in S, X

b:bi=0 xb + X

b:bi=1 (nb xb) X

b:bi=0 xb X

b:bi=1 xb 0.

3. Feasibility constraints: for each b {0, 1}n, 0 xb nb.

The constraints above form an ILP with 2n variables and n + 2n constraints. Lenstra s algorithm (and subsequent improvements of it) can solve an ILP in time exponential in the number of variables, but linear in the number of bits required to represent the problem (constraints). As nb d and can be represented in O(log d) bits for each b {0, 1}n, we obtain a time complexity of poly(2n2n, log d). We can find the optimal proposal by searching over all 2n subsets of agents S V. The overall running time is then 2n poly(2n2n, log d) = poly(2n2n, log d).

3.2 Euclidean Deliberation Spaces Recall that, in a Euclidean space, an agent v approves a proposal x if and only if

ρ(v, x) < ρ(v, 0) ||x||2 < 2 v, x . (1)

That is, a given proposal x splits Rd into two half-spaces; these half-spaces are divided by the hyperplane orthogonal to and bisecting the line segment joining x to the origin. We will use this correspondence between proposals and halfspaces throughout this section. We first observe that, in contrast to hypercube spaces, for Euclidean deliberation spaces the PERFECT SCORE problem is easy.

Proposition 7. Euc-PERFECT SCORE is polynomial-time solvable.

Proof. It suffices to check whether there exists a hyperplane H passing through r such that the entire set V lies on the same side of this hyperplane. This is equivalent to checking whether there exists an x Rd that satisfies the following set of linear constraints: v, x > 0, v V. Once we find such an x, we can choose the proposal to be p = ϵx/||x|| for sufficiently small ϵ > 0.

However, finding a proposal that enjoys a specific degree of support turns out to be computationally challenging,

Theorem 8. Euc-SCORE is NP-complete.

We prove Theorem 8 by a reduction from 3-SAT; the proof is provided in the full version of the paper. Just like for hypercubes, Euc-SCORE is fixed-parameter tractable with respect to the number of agents.

Proposition 9. Euc-SCORE can be solved in time 2n poly(|I|).

Proof. We reuse the argument in the proof of Proposition 7, but apply it to every subset of agents. That is, for every subset S V of agents, we check whether there exists a hyperplane passing through the origin that has all the agents in S strictly on one side of the hyperplane, by solving a linear program. Altogether, we have to solve 2n linear programs, so the bound on the running time holds.

However, for the Euclidean case, we were unable to obtain an FPT algorithm with respect to the number of dimensions. On the positive side, we can place our problem in the complexity class XP with respect to this parameter, i.e., show that it can be solved in polynomial time for the practically important case where the dimension of the underlying Euclidean space is small.

Proposition 10. Euc-SCORE can be solved in time polynomial in nd+1 and |I|.

Proof. As we observed earlier, a proposal divides Rd into two half-spaces. The set of half-spaces in Rd has a VCdimension of d + 1 (Kearns and Vazirani 1994), and therefore, the set of proposals also has a VC-dimension of at most d + 1. Given a set V of n agents, let S be the following set of subsets of agents:

S = {S V | x X s.t. ||x||2 < 2 v, x , v S,

and ||x||2 2 v, x , v / S}.

In other words, for every set S S, there exists a proposal that is approved by all the agents in S and none of the agents not in S. As the set of proposals has a VC-dimension of d+1, the set S is of size O(nd+1) and the elements of S can be enumerated in time polynomial in n when d is fixed.2. The elements of S can be computed inductively, see the proof of Lemma 3.1 of Kearns and Vazirani (1994). We are also using the fact that given an arbitrary set of agents S, we can efficiently compute a proposal that is supported by exactly the agents in S by solving a linear program, as shown in Proposition 7. So, we can find the largest S in S and the corresponding proposal efficiently.

To conclude this section, we consider the complexity of 2-COMPROMISE in d-Euclidean deliberation spaces. Recall that Elkind et al. (2020) prove (Theorem 3) that a sequence of 2-compromises is guaranteed to converge to a successful deliberative coalition structure. Their argument proceeds by showing that whenever a deliberative coalition structure is not successful, then one of the following conditions holds: (i) two existing coalitions can merge; (ii) there exists an agent that can join a maximum-size coalition (the new coalition may need to choose a proposal that differs from the proposal originally supported by the maximum-size coalition), or (iii) the deliberative coalition structure consists of two coalitions (and hence there is a 2-compromise transition). Note that the transitions in (ii) and (iii) increase the size of the largest coalition and (i) does not decrease it, whereas (i) decreases the number of coalitions. Consequently, one

2See Lemma 3.1 and 3.2 of Chapter 3 of the book by Kearns and Vazirani (1994)

can reach a successful outcome in O(n2) steps by verifying conditions (i) (iii) and performing the respective transition when one of them holds. Now, one can efficiently verify whether condition (i) or (ii) holds, and compute the outcome of the respective transition; if this was also true for (iii), we would be able to solve Euc-SCORE in polynomial time, in contradiction to Theorem 8 (assuming P = NP). We obtain the following corollary. Corollary 11. For each k 2, there is no polynomial-time algorithm for Euc-k-COMPROMISE unless P = NP.

4 Number of Transitions In this section, we go back to viewing deliberation as a decentralized process, and ask whether all sequences of kcompromise transitions terminate after a number of steps that is polynomial in n. Recall that, in Euclidean spaces, if the agents are told to perform 2-compromise transitions in a specific easy-to-compute order, then deliberation terminates in n2+1 steps (Elkind et al. 2020) (see also the exposition at the end of Section 3). However, if the agents can choose the order of transitions arbitrarily, the only known upper bound (which applies to all deliberation spaces) is nn, proved using a lexicographic potential function. In the next theorem, we put forward a different potential function, which enables us to improve the upper bound to 2n. Theorem 12. The number of transitions in a 2-deliberation is at most 2n. This can be shown using the following potential function:

φ(D) = | D | + X

(C,x) D 2|C|. (2)

Proof. Consider a deliberative coalition structure D. Note that S (C,x) D C = V. From now on, to simplify notation, we will identify a deliberative coalition (C, x) with its set of agents C, i.e., we will speak of a coalition C in D. Suppose a 2-compromise transition occurs, where two coalitions A and B of sizes a and b in D compromise to form coalitions C, D, and E of sizes c, d and e in D , where D A, E B. We can assume without loss of generality that a b < c. Note that D and E may be empty, in which case they do not appear in the new coalition structure D . We have a + b = c + d + e, and the value of | D | | D | may be either 1, 0, or 1, depending upon whether D and/or E are empty. The change in potential is

φ(D ) φ(D) = 2c 2a 2b + 1 + (2d 1) + (2e 1).

Indeed, if D is non-empty then it contributes 2d to P C D 2|C| and 1 to the | D | portion of φ(D ). On the other hand, if D is empty, then it makes neither of these contributions to φ(D ), but also 2d 1 = 0. The same argument applies to E. As 2d 1 and 2e 1 are always non-negative, we obtain

φ(D ) φ(D) 2c 2a 2b +1 2 2b 2b 2b +1 = 1,

as c > b a. Hence, any 2-compromise transition increases the potential by at least 1. On the other hand, we have n φ(D) 2n 1 for any D.

Observe that Theorem 12 is independent of the deliberation space and is a property of 2-compromise transitions. A similar result can be proven for k-compromise transitions: they converge in at most kn steps. We now focus on proving a lower bound on the convergence of 2-compromise transitions. We first prove a lemma that applies to any deliberation space that satisfies a certain property. We then use this lemma to construct a family of examples for hypercube deliberation spaces, and for Euclidean deliberation spaces. Lemma 13. Suppose a deliberation space with the set of proposals X and the set of agents V satisfies the following property: for every C V there exists a proposal x X such that all agents in C approve x and none of the agents not in C approve x. Then, a deliberation may take Ω(2 n/2) 2-compromise transitions.

Proof. Fix a coalition structure D. The property of the deliberation space formulated in the statement of the lemma implies that for every pair of deliberative coalitions (A, x), (B, y) D and every C A B we can find a proposal z approved by agents in C (and no other agents). Thus, in what follows, we can reason in terms of sets of agents rather than deliberative coalitions. Consequently, to simplify notation, we will write C D instead of (C, x) D. We now prove that if the agents end up executing the following types of 2-compromise transitions, then they will take an exponential time to converge, starting from the coalition structure where all the agents are in singleton coalitions.

1. Type 1. If there is a pair C, C D such that |C| = |C |, then make the following transition (expressed in terms of coalition sizes):

(a) + (a) (a + 1) + a 1

where a = |C| = |C |. The change in the potential function (as defined in (2)) for such a transition is

φ 2a+1 + 2 a 1

2 2a/2. (3)

(Note that a 1

2 may be zero, which implies that the number of coalitions decreases, and therefore, may contribute 1 to φ due to change in | D |. However, in that case the term 2 a 1

2 would not appear in φ.) 2. Type 2. If there are no Type 1 transitions available, then select two smallest coalitions C, C D and make the following transition:

(a) + (b) (b + 1) + a 1

where a = |C|, b = |C | and a b.

Now, if max C D |C| n, then there must be at least one pair of coalitions of the same size. If not, then n X

i=1 i = n( n + 1)/2 = n/2 + n/2 < n,

so for large enough n, we get a contradiction. Hence, only Type 1 transitions are made until max C D |C| exceeds n. From (3), until max C D |C| n holds, we know that the change in potential for Type 1 transitions is bounded by

We also know that if max C D |C| goes above n then the value of φ must exceed 2 n n, and the initial value of φ is n. Hence, the number of transitions must be at least

3 2 n/2 2n 2 n/2

4.1 Hypercube Deliberation Spaces In the next theorem, we apply Lemma 13 to hypercube deliberation spaces by constructing a family of deliberation spaces that satisfies the required conditions for the lemma. Theorem 14. There exists a family of hypercube deliberation spaces where a 2-deliberation may take Ω(2 n/2) 2compromise transitions.

Proof. For every even d 2, we will construct an instance with n = d/2 agents. All these agents have 0s in their first d/2 dimensions and 1s in all but one (which is different for each agent) of the last d/2 dimensions. In particular, the i-th agent vi = (vi,j)j [d] has

vi,j = 0, if j d/2 or j 1 d/2 = i 1, otherwise .

Consider a set S of m < d/2 agents. They agree on d/2 m 1s. Now consider a proposal that has d/2 m 1 1s somewhere in the first d/2 dimensions and d/2 m 1s in the dimensions where the agents in S agree on, and 0s everywhere else. Each agent in S is at a distance of (d/2 m 1)+((d/2 1) (d/2 m)) = d/2 2 from this proposal, and at a distance of d/2 1 from the origin, so they approve the proposal. However, an agent not in S is at a distance of at least (d/2 m 1)+((d/2 1) (d/2 m 2)) = d/2 from the proposal, so they do not approve the proposal. Hence, for any subset of agents S, there is a proposal that is approved exactly by the agents in S. Applying Lemma 13, we obtain the desired result.

4.2 Euclidean Deliberation Spaces As we did for hypercube deliberation spaces, we construct a family of Euclidean deliberation spaces that satisfies the required conditions for Lemma 13. Theorem 15. There exists a family of Euclidean deliberation spaces where a 2-deliberation may take Ω(2 n/2) 2compromise transitions.

Proof. For each d 2, we will construct an instance with d agents. Let the agent vi V be positioned on the i-th axis at a distance of 1 from the origin, i.e., agent v1 is located at (1, 0, . . . , 0), agent v2 at (0, 1, 0, . . . , 0), and so on.

For every S V, let the point x S be defined as

x S i = 1/|S|, if vi S 0, otherwise .

Observe that the distance of agent vi S from x S is ρ(vi, x S) = (1 1/|S|)2+(1/|S|)2(|S| 1) = 1 1/|S| < 1, so agent vi prefers x S to the status quo. But, for an agent vi / S, the distance of vi from x S is 1 + |S|(1/|S|)2 = 1 + 1/|S| > 1. So, for any subset of agents S, there is a proposal x S that is supported exactly by the agents in S. Applying Lemma 13, we obtain the desired result.

5 Beyond Two-Way Compromises Elkind et al. (2020) showed that, while in Euclidean deliberation spaces 2-compromise transitions guarantee successful deliberation, in hypercube deliberation spaces this is not the case. Specifically, they proved the following result: Theorem 16. (Elkind et al. 2020) There are d-hypercube deliberation spaces where d-compromise transitions are necessary for a successful deliberation; on the other hand, in every d-hypercube deliberation space, (2d 1 + (d + 1)/2)- compromise transitions are sufficient for a successful deliberation. Theorem 16 leaves a big gap between the lower bound of d and the upper bound of 2d 1 + (d + 1)/2. We tighten this bound by proving a lower bound of 2Θ(d). Theorem 17. There are d-hypercube deliberation spaces where 2Θ(d)-compromise transitions are necessary for a successful deliberation. The proof of Theorem 17 is given in the full version of the paper. To prove that k-compromise transitions are necessary for a successful deliberation, we need to describe a deliberation space and a coalition structure, where: 1. The coalition structure is sub-optimal, i.e., there exists a coalition structure with a larger coalition. One way to prove this is to show that an ℓ-compromise transition, ℓ k, from this coalition structure leads to a strictly larger coalition. That is, we need to describe a particular proposal and a particular set of agents, and argue that these agents support the new proposal, and the new coalition is larger than the current coalitions of all these agents. 2. Any ℓ-compromise, for ℓ< k, does not lead to a strictly larger coalition. First, there must be at least k coalitions in the current coalition structure. Second, we need to prove that for any proposal in the deliberation space, any set of agents that supports this proposal and is contained in fewer than k current coalitions is at most as large as the current coalition of one of the members of this set. If we focus on single-agent transitions, the second point above says that, in the current coalition structure, any agent in a (weakly) smaller coalition should not support the proposal of a (weakly) larger coalition. So, the proposals of all the coalitions should be different and should not be supported by any agent from an equal or smaller coalition. kcompromise transitions include single-agent transitions and

other more complex transitions, and the construction should address all of them. Elkind et al. (2020) constructed such an example for k = d, we do this for

k = (d 1)/9 (d 1)/27

1 3(d 1)/27 1 = 2Θ(d).

6 Conclusions and Future Work

We have provided an in-depth investigation of the complexity of deliberation in two models proposed by Elkind et al. (2020), answering several open questions formulated in that paper. Our results are mostly negative: in both models we have considered, identifying a successful proposal is hard even for a centralized algorithm, and agents will find it computationally challenging to discover feasible transitions from the status quo. Moreover, a completely decentralized deliberation procedure, in which groups of agents are free to execute compromise transitions in any order, may take a very long time to converge. Finally, while the Euclidean deliberation spaces have the attractive feature that a successful deliberation is possible even if each transition only involves agents from two coalitions, in hypercube spaces we may need transitions that involve exponentially many coalitions, negating the benefits of a decentralized process. Nevertheless, we do not feel that these negative results mean that we should give up on this model of deliberation. Rather, it would be interesting to identify islands of tractability , i.e., additional conditions that make this model tractable, both in terms of computational complexity and in terms of the length of the deliberation process and the number of coalitions involved in each transition; our FPT and XP results are a step in that direction. It would also be interesting to complement our theoretical findings with empirical work, checking if natural heuristics enable the agents to quickly converge to good (even if not necessarily optimal) outcomes. There are several questions concerning the complexity of deliberative coalition formation that are left open by our work. For instance, while Theorem 15 shows that convergence may be slow if the number of dimensions scales with the number of agents, it is not clear if this remains true if the number of dimensions is a fixed constant. Further, throughout the paper, we assume that the space of feasible proposals is the entire metric space. A more general approach is to assume that it is a proper subset of the metric space: this subset can be described implicitly by constraints or, in case it is finite, listed explicitly as part of the input. Of course, the computational complexity questions become trivial if the feasible proposals are listed explicitly, but it is not clear if we can bound the length of deliberation as a polynomial function of the number of proposals; on the other hand, the lower bound arguments of Theorems 14 and 15 no longer apply. Finally, k-compromise transitions, as defined by Elkind et al. (2020) can be viewed as better responses in the respective game; it would also be interesting to explore the speed of convergence of best response dynamics, where a negotiation among k coalitions always results in the largest possible coalition that can be formed by their members.

Acknowledgements We would like to thank the reviewers for their valuable feedback and in particular for pointing out an error in the statement of Proposition 6.

References Abramowitz, B.; Shapiro, E.; and Talmon, N. 2021. How to Amend a Constitution? Model, Axioms, and Supermajority Rules. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 21), 1443 1445. Arnold, T.; and Schwalbe, U. 2002. Dynamic coalition formation and the core. Journal of Economic Behavior & Organization, 49(3): 363 380. Austen-Smith, D.; and Feddersen, T. 2005. Deliberation and voting rules. In Social Choice and Strategic Decisions, 269 316. Springer. Bulteau, L.; Shahaf, G.; Shapiro, E.; and Talmon, N. 2021. Aggregation over metric spaces: Proposing and voting in elections, budgeting, and legislation. Journal of Artificial Intelligence Research, 70: 1413 1439. Chalkiadakis, G.; and Boutilier, C. 2012. Sequentially optimal repeated coalition formation under uncertainty. Autonomous Agents and Multi-Agent Systems, 24(3): 441 484. Coombs, C. H. 1964. A theory of data. Wiley. di Fenizio, P. S.; and Velikanov, C. 2016. System Generated Requests for Rewriting Proposals. ar Xiv e-prints, abs/1611.10095. Elkind, E.; Grossi, D.; Shapiro, E.; and Talmon, N. 2020. United for Change: Deliberative Coalition Formation to Change the Status Quo. ar Xiv e-prints, abs/2001.08031. Elkind, E.; Grossi, D.; Shapiro, E.; and Talmon, N. 2021. United for Change: Deliberative Coalition Formation to Change the Status Quo. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 21), 5339 5346. Enelow, J. M.; and Hinich, M. J. 1984. The spatial theory of voting: An introduction. Cambridge University Press. Fain, B.; Goel, A.; Munagala, K.; and Sakshuwong, S. 2017. Sequential deliberation for social choice. In Proceedings of the 13th International Conference on Web and Internet Economics (WINE 17), 177 190. Springer. Garey, M. R.; and Johnson, D. S. 1979. Computers and intractability. Freeman San Francisco. Goel, A.; and Lee, D. T. 2016. Towards large-scale deliberative decision-making: Small groups and the importance of triads. In Proceedings of the 17th ACM Conference on Economics and Computation (ACM EC 16), 287 303. Hafer, C.; and Landa, D. 2007. Deliberation as selfdiscovery and institutions for political speech. Journal of Theoretical Politics, 19(3): 329 360. Karanikolas, N.; Bisquert, P.; and Kaklamanis, C. 2019. A Voting Argumentation Framework: Considering the Reasoning behind Preferences. In Proceedings of the 19th International Conference on Agents and Artificial Intelligence (ICAART 19), 42 53.

Kearns, M. J.; and Vazirani, U. 1994. An introduction to computational learning theory. MIT press. Konishi, H.; and Ray, D. 2003. Coalition formation as a dynamic process. Journal of Economic Theory, 110(1): 1 41. List, C. 2011. Group communication and the transformation of judgments: an impossibility result. Journal of Political Philosophy, 19(1): 1 27. List, C.; Luskin, R. C.; Fishkin, J. S.; and Mc Lean, I. 2013. Deliberation, single-peakedness, and the possibility of meaningful democracy: evidence from deliberative polls. The Journal of Politics, 75(1): 80 95. Merrill III, S.; and Grofman, B. 1999. A unified theory of voting: Directional and proximity spatial models. Cambridge University Press. Patty, J. W. 2008. Arguments-based collective choice. Journal of Theoretical Politics, 20(4): 379 414. Perote-Pe na, J.; and Piggins, A. 2015. A model of deliberative and aggregative democracy. Economics and Philosophy, 31(1): 93 121. Rad, S. R.; and Roy, O. 2021. Deliberation, Single Peakedness, and Coherent Aggregation. American Political Science Review, 115(2): 629 648. Shahaf, G.; Shapiro, E.; and Talmon, N. 2019. Sybil Resilient Reality-Aware Social Choice. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 19), 572 579. Shapiro, E.; and Talmon, N. 2018. Incorporating reality into social choice. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 18), 1188 1192. Tardos, E.; and Wexler, T. 2007. Algorithmic Game Theory, chapter Network Formation Games and the Potential Function Method, 487 516. Cambridge University Press. Vries, M. W. M. d. 1999. Governing with your closest neighbour: an assessment of spatial coalition formation theories. Ph.D. thesis, Radboud University Nijmegen.