Complexity of deliberative coalition formation

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' preference...

Full description

Bibliographic Details
Main Authors: Elkind, E, Ghosh, A, Goldberg, P
Format: Conference item
Language:English
Published: Association for the Advancement of Artificial Intelligence 2022
_version_ 1817931380137394176
author Elkind, E
Ghosh, A
Goldberg, P
author_facet Elkind, E
Ghosh, A
Goldberg, P
author_sort Elkind, E
collection OXFORD
description 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 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 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 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).
first_indexed 2024-12-09T03:21:06Z
format Conference item
id oxford-uuid:3534285d-9d9a-4d15-9e76-be1a7889b29c
institution University of Oxford
language English
last_indexed 2024-12-09T03:21:06Z
publishDate 2022
publisher Association for the Advancement of Artificial Intelligence
record_format dspace
spelling oxford-uuid:3534285d-9d9a-4d15-9e76-be1a7889b29c2024-11-12T11:30:39ZComplexity of deliberative coalition formation Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:3534285d-9d9a-4d15-9e76-be1a7889b29cEnglishSymplectic ElementsAssociation for the Advancement of Artificial Intelligence2022Elkind, EGhosh, AGoldberg, PElkind 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 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 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 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).
spellingShingle Elkind, E
Ghosh, A
Goldberg, P
Complexity of deliberative coalition formation
title Complexity of deliberative coalition formation
title_full Complexity of deliberative coalition formation
title_fullStr Complexity of deliberative coalition formation
title_full_unstemmed Complexity of deliberative coalition formation
title_short Complexity of deliberative coalition formation
title_sort complexity of deliberative coalition formation
work_keys_str_mv AT elkinde complexityofdeliberativecoalitionformation
AT ghosha complexityofdeliberativecoalitionformation
AT goldbergp complexityofdeliberativecoalitionformation