Abstract
This paper investigates the computational complexity of "deliberative coalition formation," a model where agents in a metric space form alliances to overturn a political status quo. While previous work established the dynamics of this process, the algorithmic feasibility remained unexplored. We analyze the complexity of finding optimal proposals and the convergence properties of the deliberation process. Our results show that finding the most popular proposal is generally NP-hard in both Hypercube and Euclidean models. Furthermore, we demonstrate that the deliberation process can take exponentially many steps to converge and may require massive coordination (a "grand bargain") to reach optimal outcomes, highlighting significant algorithmic challenges in reaching a democratic consensus.
Introduction
In group decision-making, the transition from a disliked "status quo" to a new, broadly supported proposal is a fundamental process. Elkind et al. (2021) introduced a formal model for this deliberation: agents and proposals are represented as points in a metric space, such as a multi-dimensional issue space. In this framework, agents form coalitions around proposals they prefer over the status quo. These coalitions can merge through k-compromise transitions, where multiple groups agree to support a new, larger compromise proposal that benefits all participants.
While the original model captured the qualitative dynamics of political maneuvering, it left the underlying computational complexity unexplored. This study addresses three critical questions: the difficulty for a central planner to identify the optimal proposal, the difficulty for agents to identify valid next steps in deliberation, and the time required for the process to reach a stable conclusion.
The Deliberative Model
The research focuses on two primary geometric settings that represent different types of decision-making environments:
- The Hypercube Model: Agents and proposals are vertices of a $d$-dimensional hypercube, representing binary "yes/no" stances on $d$ distinct issues. Distance is measured using Hamming distance.
- The Euclidean Model: Agents and proposals are points in $\mathbb{R}^d$, using standard straight-line (Euclidean) distance.
In these models, an agent approves a proposal if it is strictly closer to their ideal point than the status quo is. The authors define several key computational problems to probe these settings:
- SCORE: Identifying a proposal approved by at least $\eta$ agents.
- PERFECT SCORE: Identifying a proposal approved by the entire collective.
- k-COMPROMISE: Identifying a valid transition involving $k$ existing coalitions.
Computational Hardness
The study reveals a "double whammy" of computational hardness. First, finding the most popular proposal (the SCORE problem) is proven to be NP-complete in both the Hypercube and Euclidean models. This suggests that even a central authority with full information faces significant hurdles in identifying the "best" democratic outcome.
Second, the decentralized process is equally difficult. The authors prove that it is NP-hard for agents themselves to find even a single valid compromise step to take next. These results were obtained using reductions from classic problems such as Independent Set and 3-SAT.
In the Euclidean model, the geometry of approval provides some structure: an agent approves a proposal if it lies in a specific half-space defined by the status quo. By employing tools from computational geometry, specifically VC-dimension, the authors show that if the number of issues ($d$) is small, the problem becomes more manageable (falling into the complexity class XP).
Convergence and the "Grand Bargain"
A central concern in deliberative models is whether the process will settle and how long it will take. The authors provide the following insights into the dynamics of deliberation:
- Exponential Deliberation: Even when agents are restricted to simple 2-way compromises, the sequence of transitions can be remarkably long. The authors improved the known upper bound for convergence to $2^n$ (where $n$ is the number of agents) but established a lower bound showing that scenarios exist where deliberation requires $\Omega(2^{\sqrt{n}/2})$ steps.
- The Hypercube Bottleneck: In the hypercube model, the authors strengthened previous findings by proving that reaching the most popular proposal might require a "grand bargain"—a $k$-compromise involving an exponential number of coalitions ($2^{\Theta(d)}$). This suggests that decentralized deliberation in discrete issue spaces is particularly prone to stagnation unless massive coordination occurs.
Islands of Tractability
Despite the general hardness results, the paper identifies specific conditions under which the problems become tractable:
- Fixed-Parameter Tractability (FPT): The problem is FPT with respect to the number of agents ($n$). This implies that for small committees or boards, the optimal proposal can be found efficiently regardless of the complexity of the issue space.
- Low-Dimensionality: As noted, when the number of dimensions ($d$) is a small constant, the Euclidean model allows for more efficient proposal discovery.
Conclusion and Future Work
The findings present a largely negative outlook on the worst-case computational efficiency of deliberative coalition formation. The model is demanding both for central planners and for the agents involved. However, these results open several avenues for future research:
- Heuristics: Investigating whether natural heuristics allow for faster convergence in practice, despite theoretical worst-case bounds.
- Restricted Proposal Spaces: Examining how the complexity changes if proposals are limited to a "feasible set" defined by budgets or legal constraints.
- Fixed Dimensions: Determining if convergence remains slow when the number of dimensions is fixed but the number of agents grows significantly.
By mapping the complexity landscape of deliberation, this work provides a rigorous foundation for understanding the algorithmic limits of reaching consensus in multi-dimensional political spaces.
Summary updated