Complexity of Deliberative Coalition Formation

Authors

  • Edith Elkind University of Oxford
  • Abheek Ghosh University of Oxford
  • Paul Goldberg University of Oxford

DOI:

https://doi.org/10.1609/aaai.v36i5.20428

Keywords:

Game Theory And Economic Paradigms (GTEP), Multiagent Systems (MAS)

Abstract

Elkind et al. (AAAI'21) 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 Euclidean model 2-compromises 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).

Downloads

Published

2022-06-28

How to Cite

Elkind, E., Ghosh, A., & Goldberg, P. (2022). Complexity of Deliberative Coalition Formation. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4975-4982. https://doi.org/10.1609/aaai.v36i5.20428

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms