Interaction and Expressivity in Collective Decision-Making

Grandi, Umberto

doi:10.24963/ijcai.2022/816

Interaction and Expressivity in Collective Decision-Making

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. Early Career. Pages 5813-5815.

https://doi.org/10.24963/ijcai.2022/816

Keywords

EC: Game Theory And Economic Paradigms
EC: Knowledge Representation And Reasoning
EC: Agent-based And Multi-agent Systems

Abstract

Collective decisions among human and artificial agents can be enhanced by allowing for more interaction among decision-makers and by letting them express more information about their preferences.

In this paper I present ongoing research on two settings: iterative voting, which repeatedly applies a voting rule until decision-makers converge to an outcome, and delegative voting on multiple issues.

[Airiau et al., 2017] Stéphane Airiau, Umberto Grandi, and Filipo Studzinski Perotto. Learning agents for iterative voting. In Proceedings of the 5th International Conference on Algorithmic Decision Theory (ADT), 2017.
[Botan et al., 2019] Sirin Botan, Umberto Grandi, and Lau- rent Perrussel. Multi-issue opinion diffusion under con- straints. In Proceedings of the 18th International Joint Conference on Autonomous Agents and Multiagent Sys- tems (AAMAS), 2019.
[Boudou et al., 2022] Joseph Boudou, Rachael Colley, and Umberto Grandi. Itero: An online iterative voting applica- tion. In Proceedings of the 31st International Joint Con- ference on Artificial Intelligence (IJCAI), 2022. IJCAI
[Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D Procaccia, and Jérôme Lang. Handbook of Computational Social Choice. Cambridge University Press, 2016.
[Brill and Talmon, 2018] Markus Brill and Nimrod Talmon. Pairwise liquid democracy. In Proceedings of the 27th In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), 2018.
[Brill et al., 2016] Markus Brill, Edith Elkind, Ulle Endriss, and Umberto Grandi. Pairwise diffusion of preference rankings in social networks. In Proceedings of the 25th In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), 2016. IJCAI
Markus Brill. Interactive democracy. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2018.
[Brill, 2021] Markus Brill. From computational social choice to digital democracy. In Proceedings of the 30th In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), 2021. IJCAI
[Castiglioni et al., 2020] Matteo Castiglioni, Diodato Fer- raioli, and Nicola Gatti. Election control in social net- works via edge addition or removal. In The 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.
[Colley and Grandi, 2022] Rachael Colley and Umberto Grandi. Preserving consistency in multi-issue liquid democracy. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022. IJCAI
[Colley et al., 2020] Rachael Colley, Umberto Grandi, and Arianna Novaro. Smart voting. In Proceedings of the 29th International Joint Conference on Artificial Intelli- gence (IJCAI), 2020.
[Colley et al., 2022] Rachael Colley, Umberto Grandi, and Arianna Novaro. Unravelling multi-agent ranked dele- gations. Autonomous Agents and Multi Agent Systems, 36(1):9, 2022.
John S. Dryzek and Christian List. Social choice theory and deliberative democracy: A recon- ciliation. British Journal of Political Science, 33(1):1-28, 2003.
[Endriss, 2016] Ulle Endriss. Judgment aggregation. In Fe- lix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computa- tional Social Choice. Cambridge University Press, 2016.
[Faliszewski et al., 2018] Piotr Faliszewski, Rica Gonen, Martin Koutecký, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. In Proceedings of the 27th International Joint Conference on Artificial Intelli- gence (IJCAI), 2018. IJCAI
[Grandi et al., 2013] Umberto Grandi, Andrea Loreggia, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Restricted manipulation in iterative voting: Condorcet ef- ficiency and borda score. In Proceeding of the 3rd Interna- tional Conference on Algorithmic Decision Theory (ADT), 2013.
[Grandi et al., 2015] Umberto Grandi, Emiliano Lorini, and Laurent Perrussel. Propositional opinion diffusion. In Pro- ceedings of the 14th International Joint Conference on Au- tonomous Agents and Multiagent Systems (AAMAS), 2015.
[Grandi et al., 2020] Umberto Grandi, Jérôme Lang, Ali Ozkes, and Stéphane Airiau. Voting behavior in one- shot and iterative multiple referenda. SSRN preprint SSRN:ssrn.3747713, 2020.
[Grandi et al., 2021] Umberto Grandi, Emiliano Lorini, Ar- ianna Novaro, and Laurent Perrussel. Games of influ- ence. Journal of Logic and Computation, 31(4):1129- 1157, 2021.
[Grandi, 2017] Umberto Grandi. Social choice and social networks. In Ulle Endriss, editor, Trends in Computa- tional Social Choice, chapter 9, pages 169-184. AI Ac- cess, 2017.
[Grandi, 2019] Umberto Grandi. Agent-mediated social choice. In Laslier JF., Moulin H., Sanver M., and Zwicker W., editors, The Future of Economic Design, Studies in Economic Design. Springer, 2019.
[Grossi, 2022] Davide Grossi. Social choice around the block: On the computational social choice of blockchain. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent (AAMAS), 2022.
[Hassanzadeh et al., 2013] Farzad Farnoud Hassanzadeh, Eitan Yaakobi, Behrouz Touri, Olgica Milenkovic, and Je- hoshua Bruck. Building consensus via iterative voting. In Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013.
[Jain et al., 2021] Pallavi Jain, Krzysztof Sornat, and Nim- rod Talmon. Preserving consistency for liquid knapsack voting. In 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021.
[Lang and Xia, 2016] Jérôme Lang and Lirong Xia. Vot- ing in combinatorial domains. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procac- cia, editors, Handbook of Computational Social Choice. Cambridge University Press, 2016.
[Lev and Rosenschein, 2012] Omer Lev and Jeffrey S. Rosenschein. Convergence of iterative voting. In Proceed- ings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012.
[List et al., 2013] Christian List, Robert C Luskin, James S Fishkin, and Iain McLean. Deliberation, single- peakedness, and the possibility of meaningful democracy: evidence from deliberative polls. The Journal of Politics, 75(1):80-95, 2013.
[Meir et al., 2010] Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R. Jennings. Convergence to equilibria in plurality voting. In Proceedings of the 24th conference on Artificial Intelligence (AAAI), 2010.
[Meir et al., 2020] Reshef Meir, Kobi Gal, and Maor Tal. Strategic voting in the lab: compromise and leader bias behavior. Autonomous Agents and Multi Agent Systems, 34(1):31, 2020.
[Meir, 2017] Reshef Meir. Iterative voting. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 4, pages 69-86. AI Access, 2017.
[Rad and Roy, 2021] Soroush Rafiee Rad and Olivier Roy. Deliberation, single-peakedness, and coherent aggrega- tion. American Political Science Review, 115(2):629-648, 2021.
[Shapiro, 2018] Ehud Shapiro. Point: foundations of e- democracy. Communications of the ACM, 61(8):31-34, 2018.
[Talmon and Shapiro, 2022] Nimrod Talmon and Ehud Shapiro. Foundations for grassroots democratic meta- verse. arXiv preprint arXiv:2203.04090, 2022.
[Wilder and Vorobeychik, 2018] Bryan Wilder and Yevgeniy Vorobeychik. Controlling elections through social influ- ence. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1 Introduction

There are many ways in which AI techniques and technologies can contribute to the improvement of collective decision-making processes among human or artificial agents. Many such research directions require that the classical social choice setting (independent voters expressing preferences over typically few independent alternatives) are generalised to more complex settings. In previous research I focused extensively on how to introduce a social network in the modelling of a collective decision problem (see Grandi [2017] for an overview, but many other papers appeared since then). In this paper I focus on two further improvements. First, study interactive mechanisms in which voters participate to an iterated election, each time receiving information about the current winner or the other voters' ballots. This setting is known as iterative voting (for a survey of initial work in this area see Meir [2017]). Second, give voters more expressivity by considering collective decisions on multiple issues, most notably in the setting of delegative voting. Both research directions aim at paving the way for some sort of agent-mediated social choice, an idea which I presented in a recent position paper [Grandi, 2019]. 1

Context. Current research in computational social choice 2 moved towards the design and the analysis of algorithms for digital democracy. Research directions have been outlined in a number of recent position papers [Brill, 2018; Shapiro, 2018; Brill, 2021; Talmon and Shapiro, 2022; Grossi, 2022].

1 A similar program was put forward by C´esar Hidalgo in a 2018 TED talk (see www.peopledemocracy.com).

2 For an overview of this research field see Brandt et al. [2016].

2 Social Influence and Iterative Voting

Consider a simple collective decision in which a set of voters have preferences over a set of candidates or alternatives, and express it in the form of a plurality vote, thus submitting the name of their preferred candidate. Assume now that some of this information is shared among the voters. For instance, an agent can discover for whom other agents close to them have voted for, or get information about the score of each candidate from a publicly accessible poll. There are two ways in which a voter can react to such information: either be influenced, or respond strategically.

The combination of voting and social influence is a wellstudied topic. For instance, settings where a group of voters is steered towards the majority vote [Hassanzadeh et al., 2013] or when an external player aims at controlling an election on a social network [Faliszewski et al., 2018; Wilder and Vorobeychik, 2018; Castiglioni et al., 2020]. In past work I designed and analysed social influence models that are adapted to voting situations such as preferences over alternatives or multi-issue voting [Grandi et al., 2015; Brill et al., 2016; Botan et al., 2019] and strategic models of social influence [Grandi et al., 2021].

When agents are instead assumed to respond to the information received dynamically from the other voters by changing their reported vote or their reported preference, we enter in the realm of iterative voting. This setting was first proposed as an equilibrium selection mechanism for voting games [Meir et al., 2010; Lev and Rosenschein, 2012], initiating a productive line of research. However, the repeated execution of a simple voting rule such as plurality can also be viewed as a novel voting procedure per se. This approach might solve a tension in the design of collective decisions, that are required to be easy to explain to voters while at the same time satisfy a number of good properties.

In previous work we assessed the quality of the result of a repeated election by measuring social welfare as the average position of the winner in the individual preferences as well as the frequency of election of Condorcet winners, showing the beneficial effects of iterative voting. We used both multiagent simulations in a standard voting-for-candidates situation [Grandi et al., 2013] and a behavioural experiment in the lab for multi-issue voting [Grandi et al., 2020]. 3 We also designed and implemented a platform for organising iterated plurality elections online called Itero, 4 with the aim to promote iterative voting in outreach events and test it in realistic situations [Boudou et al., 2022].

3 A similar experiment did not find any statistically significant

Iterative voting can be seen as a lightweight form of deliberation. Thus, this latter line of research supports the thesis that deliberation among voters can improve the quality of a collective decision and somehow escape the classical impossibilities in social choice (see, e.g., the work of Dryzek and List [2003], the analysis of List et al. [2013] on the data of deliberative polls, or the findings of Rad and Roy [2021]).

3 Delegations andMulti-issue Voting

A number of social choice problems can be modelled using multiple (binary) issues with the additional use of constraints. Elicitation of preferences, aggregation of partial ballots, and logical dependencies between issues are all problems that have been studied extensively (see, e.g., Lang and Xia [2016] and Endriss [2016] for overviews).

In recent work we focused on the setting of delegative voting and more particularly on a mechanism known as liquid democracy, in which voters have the possibility to express their opinion directly or to delegate their vote (and the delegations they received) to another voter. We first focused on the problem of solving delegation cycles, proposing a general language for agents to express ranked multi-agent delegations on multiple issues and proposing algorithms for their unravelling [Colley et al., 2020; Colley et al., 2022]. We then moved to study delegations in presence of constraints relating the multiple issues at stake. Generalising initial work by Brill and Talmon [2018] on pairwise preference delegations, and by Jain et al. [2021] on knapsack voting, we proposed polynomial algorithms for delegations under constraints that make use of a priority ordering over the issues that is elicited from the voters [Colley and Grandi, 2022].

4 Conclusions and Perspectives

In this paper I presented recent and ongoing research on enhancing collective decision-making with more interaction and more expressivity. Both topics are concerned with the design of algorithms and their analysis and are guided by philosophical considerations (deliberation can improve collective decisions) or practical applications (the rise of technologies supporting liquid democracy and electronic institutions). One step further is to assess the proposed mechanisms when used by artificial agents acting as proxies for human decisionmakers. Initial work has been done, e.g., on assessing how simple reinforcement learning agents can perform in an iterated voting election [Airiau et al., 2017].

Research on algorithms for digital democracy is experiencing a momentum, and the need for new applications in this domain is real. The rise of an interdisciplinary community around these subjects has the potential of unveiling new fascinating problems and research directions for the AI community studying collective decision-making. To give an example, in a recent experiment that we conducted online during the French presidential elections 5 we asked users to approve or disapprove more than one hundred political proposals, and to rank the approved ones, with the aim to construct a collective political program. The design of the platform showed us the need for novel social choice methods that are able to deal with large numbers of alternatives and heavily incomplete preference data, suggesting us a number of research directions for future work.

improvement in the social welfare of iterated elections [Meir et al., 2020]. The set of voting situations they analyse was however less prone to improvements than the ones considered in our experiment.

4 https://itero.irit.fr/

Acknowledgments

I acknowledge the support of the ANR JCJC project SCONE (ANR 18-CE23-0009-01). I am indebted to all my collaborators and co-authors without whom most of the work reported here would not have seen the light.

Umberto Grandi. 2022. Interaction and Expressivity in Collective Decision-Making. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22. IJCAI, 5813–5815. https://doi.org/10.24963/ijcai.2022/816

@inproceedings{ijcai2022p816,
  title     = {Interaction and Expressivity in Collective Decision-Making},
  author    = {Grandi, Umberto},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Luc De Raedt},
  pages     = {5813--5815},
  year      = {2022},
  month     = {7},
  note      = {Early Career},
  doi       = {10.24963/ijcai.2022/816},
  url       = {https://doi.org/10.24963/ijcai.2022/816},
}

TY  - CPAPER
TI  - Interaction and Expressivity in Collective Decision-Making
AU  - Grandi, Umberto
T2  - Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2022
SP  - 5813
EP  - 5815
DO  - 10.24963/ijcai.2022/816
UR  - https://doi.org/10.24963/ijcai.2022/816
ER  -

[1] [Airiau et al., 2017] Stéphane Airiau, Umberto Grandi, and Filipo Studzinski Perotto. Learning agents for iterative voting. In Proceedings of the 5th International Conference on Algorithmic Decision Theory (ADT), 2017.

[2] [Botan et al., 2019] Sirin Botan, Umberto Grandi, and Lau- rent Perrussel. Multi-issue opinion diffusion under con- straints. In Proceedings of the 18th International Joint Conference on Autonomous Agents and Multiagent Sys- tems (AAMAS), 2019.

[3] [Boudou et al., 2022] Joseph Boudou, Rachael Colley, and Umberto Grandi. Itero: An online iterative voting applica- tion. In Proceedings of the 31st International Joint Con- ference on Artificial Intelligence (IJCAI), 2022. IJCAI

[4] [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D Procaccia, and Jérôme Lang. Handbook of Computational Social Choice. Cambridge University Press, 2016.

[5] [Brill and Talmon, 2018] Markus Brill and Nimrod Talmon. Pairwise liquid democracy. In Proceedings of the 27th In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), 2018.

[6] [Brill et al., 2016] Markus Brill, Edith Elkind, Ulle Endriss, and Umberto Grandi. Pairwise diffusion of preference rankings in social networks. In Proceedings of the 25th In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), 2016. IJCAI

[7] Markus Brill. Interactive democracy. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2018.

[8] [Brill, 2021] Markus Brill. From computational social choice to digital democracy. In Proceedings of the 30th In- ternational Joint Conference on Artificial Intelligence (IJ- CAI), 2021. IJCAI

[9] [Castiglioni et al., 2020] Matteo Castiglioni, Diodato Fer- raioli, and Nicola Gatti. Election control in social net- works via edge addition or removal. In The 34th AAAI Conference on Artificial Intelligence (AAAI), 2020.

[10] [Colley and Grandi, 2022] Rachael Colley and Umberto Grandi. Preserving consistency in multi-issue liquid democracy. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022. IJCAI

[11] [Colley et al., 2020] Rachael Colley, Umberto Grandi, and Arianna Novaro. Smart voting. In Proceedings of the 29th International Joint Conference on Artificial Intelli- gence (IJCAI), 2020.

[12] [Colley et al., 2022] Rachael Colley, Umberto Grandi, and Arianna Novaro. Unravelling multi-agent ranked dele- gations. Autonomous Agents and Multi Agent Systems, 36(1):9, 2022.

[13] John S. Dryzek and Christian List. Social choice theory and deliberative democracy: A recon- ciliation. British Journal of Political Science, 33(1):1-28, 2003.

[14] [Endriss, 2016] Ulle Endriss. Judgment aggregation. In Fe- lix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computa- tional Social Choice. Cambridge University Press, 2016.

[15] [Faliszewski et al., 2018] Piotr Faliszewski, Rica Gonen, Martin Koutecký, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. In Proceedings of the 27th International Joint Conference on Artificial Intelli- gence (IJCAI), 2018. IJCAI

[16] [Grandi et al., 2013] Umberto Grandi, Andrea Loreggia, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Restricted manipulation in iterative voting: Condorcet ef- ficiency and borda score. In Proceeding of the 3rd Interna- tional Conference on Algorithmic Decision Theory (ADT), 2013.

[17] [Grandi et al., 2015] Umberto Grandi, Emiliano Lorini, and Laurent Perrussel. Propositional opinion diffusion. In Pro- ceedings of the 14th International Joint Conference on Au- tonomous Agents and Multiagent Systems (AAMAS), 2015.

[18] [Grandi et al., 2020] Umberto Grandi, Jérôme Lang, Ali Ozkes, and Stéphane Airiau. Voting behavior in one- shot and iterative multiple referenda. SSRN preprint SSRN:ssrn.3747713, 2020.

[19] [Grandi et al., 2021] Umberto Grandi, Emiliano Lorini, Ar- ianna Novaro, and Laurent Perrussel. Games of influ- ence. Journal of Logic and Computation, 31(4):1129- 1157, 2021.

[20] [Grandi, 2017] Umberto Grandi. Social choice and social networks. In Ulle Endriss, editor, Trends in Computa- tional Social Choice, chapter 9, pages 169-184. AI Ac- cess, 2017.

[21] [Grandi, 2019] Umberto Grandi. Agent-mediated social choice. In Laslier JF., Moulin H., Sanver M., and Zwicker W., editors, The Future of Economic Design, Studies in Economic Design. Springer, 2019.

[22] [Grossi, 2022] Davide Grossi. Social choice around the block: On the computational social choice of blockchain. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent (AAMAS), 2022.

[23] [Hassanzadeh et al., 2013] Farzad Farnoud Hassanzadeh, Eitan Yaakobi, Behrouz Touri, Olgica Milenkovic, and Je- hoshua Bruck. Building consensus via iterative voting. In Proceedings of the 2013 IEEE International Symposium on Information Theory, 2013.

[24] [Jain et al., 2021] Pallavi Jain, Krzysztof Sornat, and Nim- rod Talmon. Preserving consistency for liquid knapsack voting. In 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021.

[25] [Lang and Xia, 2016] Jérôme Lang and Lirong Xia. Vot- ing in combinatorial domains. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procac- cia, editors, Handbook of Computational Social Choice. Cambridge University Press, 2016.

[26] [Lev and Rosenschein, 2012] Omer Lev and Jeffrey S. Rosenschein. Convergence of iterative voting. In Proceed- ings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012.

[27] [List et al., 2013] Christian List, Robert C Luskin, James S Fishkin, and Iain McLean. Deliberation, single- peakedness, and the possibility of meaningful democracy: evidence from deliberative polls. The Journal of Politics, 75(1):80-95, 2013.

[28] [Meir et al., 2010] Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R. Jennings. Convergence to equilibria in plurality voting. In Proceedings of the 24th conference on Artificial Intelligence (AAAI), 2010.

[29] [Meir et al., 2020] Reshef Meir, Kobi Gal, and Maor Tal. Strategic voting in the lab: compromise and leader bias behavior. Autonomous Agents and Multi Agent Systems, 34(1):31, 2020.

[30] [Meir, 2017] Reshef Meir. Iterative voting. In Ulle Endriss, editor, Trends in Computational Social Choice, chapter 4, pages 69-86. AI Access, 2017.

[31] [Rad and Roy, 2021] Soroush Rafiee Rad and Olivier Roy. Deliberation, single-peakedness, and coherent aggrega- tion. American Political Science Review, 115(2):629-648, 2021.

[32] [Shapiro, 2018] Ehud Shapiro. Point: foundations of e- democracy. Communications of the ACM, 61(8):31-34, 2018.

[33] [Talmon and Shapiro, 2022] Nimrod Talmon and Ehud Shapiro. Foundations for grassroots democratic meta- verse. arXiv preprint arXiv:2203.04090, 2022.

[34] [Wilder and Vorobeychik, 2018] Bryan Wilder and Yevgeniy Vorobeychik. Controlling elections through social influ- ence. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.