Lune

AAAI2022Top-tier venue

Complexity of Deliberative Coalition Formation

Edith Elkind, Abheek Ghosh, Paul Goldberg

Abstract

Elkind et al. (2021 Elkind et al. ( , 2020) ) 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 Ω(d) .

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. United for Change: Deliberative Coalition Formation to Change the Status QuoEdith Elkind, Davide Grossi, Ehud Shapiro, Nimrod TalmonAAAI 2021 · 15 citations

Builds on1

  1. United for Change: Deliberative Coalition Formation to Change the Status QuoEdith Elkind, Davide Grossi, Ehud Shapiro, Nimrod TalmonAAAI 2021 · 15 citations

Related papers

  1. Metric Distortion of Small-Group DeliberationAshish Goel, Mohak Goyal, Kamesh MunagalaSTOC 2025 · 1 citation
  2. An Analysis of Approval-Based Committee Rules for 2D-Euclidean ElectionsMichal Tomasz Godziszewski, Pawel Batko, Piotr Skowron, Piotr FaliszewskiAAAI 2021 · 25 citations
  3. Condorcet Relaxation In Spatial VotingArnold Filtser, Omrit FiltserAAAI 2021 · 2 citations
  4. Unravelling Expressive Delegations: Complexity and Normative AnalysisGiannis Tyrovolas, Andrei Constantinescu, Edith ElkindAAAI 2024 · 3 citations
  5. Causes of Stability in Dynamic Coalition FormationNiclas Boehmer, Martin Bullinger, Anna Maria KerkmannAAAI 2023 · 17 citations
Dusk over the sea between two cliffs drawn in fine vertical lines