United for Change: Deliberative Coalition Formation to Change the Status Quo

We study a setting in which a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. We describe a deliberation process in which agents dynamically form coalitions around proposals that they prefer over the status quo. We formulate conditions on the space of proposals and on the ways in which coalitions are formed that guarantee deliberation to succeed, that is, to terminate by identifying a proposal with the largest possible support. Our results provide theoretical foundations for the analysis of deliberative processes such as the ones that take place in online systems for democratic deliberation support. Earlier versions of this article have been accepted for presentation at the 35th AAAI Conference on Artificial Intelligence, AAAI-21 [Elkind et al., 2021] and at the 8th International Workshop on Computational Social Choice, COMSOC-21. We wish to thank Schloss Dagstuhl-Leibniz Center for Informatics. The paper develops ideas discussed by the authors and other participants during the Dagstuhl Seminar 19381 (Application-Oriented Computational Social Choice), summer 2019. We would also like to thank the participants of the University of Bayreuth Colaform workshop and the Lorentz Center workshop on Modelling of Social Complexity in Argumentation for useful feedback on earlier versions of this work. We thank the generous support of the Braginsky Center for the Interface between Science and the Humanities.