Opinion Diffusion on Society Graphs Based on Approval Ballots

A society graph, as considered by [Faliszewski et al., IJCAI 2018], is a graph corresponding to an election instance where every possible ranking is a node, and the weight of such a node is given by the number of voters whose vote correspond to the said ranking. A natural diffusion process on this graph is defined, and an immediate question that emerges is whether there is a diffusion path that leads to a particular candidate winning according to a certain voting rule-this turns out to be NP-complete. In this contribution, we consider the setting when votes are approval ballots, as opposed to rankings-and we consider both the possible and necessary winner problems. We demonstrate that it is possible to efficiently determine if a candidate is a possible winner (i.e, if there exists a diffusion path along which a given candidate wins the election) if the underlying society graph is a star (i.e, tree of diameter at most two), while the problem is NP-complete for trees of diameter d for d > 2. Analogously, we show that it is possible to efficiently determine if a candidate is a necessary winner (i.e, a winner for every possible diffusion path) if the underlying society graph is a star, while the problem is coNP-complete for trees of diameter d for d > 2. We also show the following results on structured graphs for the possible winner problem: the problem is strongly NP-complete on a disjoint union of paths, and on trees of constant diameter. We also report preliminary experiments from an ILP-based implementation.