  Elkind et al. (AAAI, 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 k-compromise 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 R^d
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
continuous model 2-compromises are guaranteed to succeed, but in the discrete
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^{\Omega(d)}.
