Equilibria in Strategic Nominee Selection

1 Introduction

My PhD project is devoted to the problem of strategic voting (see [Meir, 2018] for an overview) and group behaviour. In particular, I investigate primaries, i.e. selection of candidates participating in the elections by political parties. This process constitutes one of the major aspects of democratic systems and has further gained interest from the multi-agent systems community (see, e.g., [Borodin et al., 2019]). I address this important topic by a study of strategic behaviour of parties selecting a representative which provides the best outcome of the elections from their party's perspective. Further, the importance of influence of agents on each other in social networks cannot be underestimated. Indeed, this problem has been studied in-depth in the context of social choice theory (see [Grandi, 2017] for an overview). It is thus of high interest to understand how the spread of opinions affects the decision-making process.

The goal of my PhD project is to provide a game-theoretic analysis of strategic nominee selection in the context of several social choice mechanisms. In particular, I consider tournament-based rules, including knockout tournaments. Further, I study the problem of checking the convergence of an opinion diffusion protocol for a social network, which is crucial while reasoning about the voters' preferences after their communication. Furthermore, I consider the related social network phenomenon of majority illusion.

2 Key Concepts

Let me introduce the key concepts used in my PhD project.

Tournaments. One of the well-studied methods of selecting a winner among conflicting options is by using tournaments. There, a graph over the set of candidates depicts their pairwise comparison. Notably, such a graph can be interpreted as the information on which of a pair of candidates is preferred by the majority of voters. However, it is not always clear how to select the set of winners from a tournament and a number of methods for such a selection has been defined (see [Brandt et al., 2016] for an overview). Among other methods, knockout tournaments are often considered. There, candidates are seeded at the leafs of a binary tree and progress to the next round if they beat their current opponent. The last remaining candidate is the winner of a tournament.

Hotelling-Downs Model. One of the crucial models in the theory of strategic selection of policies is the HotellingDowns model [1929]. As mentioned by [Downs, 1957], it has a potential of predicting how parties choose their political stance. In this framework a distribution of voters on a spectrum is considered. Further, players strategically choose a location on this spectrum in order to attract as many voters as possible. It assumed that a voter is attracted to the player which is the closest to them. One of the appealing properties of this game is that the existence of a pure Nash equilibrium (NE) is guaranteed if there are only two players competing.

Opinion Diffusion. The spread of opinions in networks has raised growing attention in the area of multi-agent systems. Among other models, the threshold-based protocols have been particularly well-studied (see, e.g., [Granovetter, 1978]). There, an agent changes their opinion if a specified fraction of the agents connected to them (such as the strict majority) disagrees with them.

Majority Illusion. One of the particularly interesting social networks phenomena studied in the latest multi-agent systems literature is the majority illusion, studied by [Lerman et al., 2016]. It occurs if a large number of agents in the network perceives the minority option as the one adopted by the majority of others in the network (then we say that they are under majority illusion). The occurrence of this phenomenon has a strong implication on the outcome of the opinion diffusion protocol. For instance, if all agents are under majority illusion, the minority opinion is adopted by all of the agents after a single round of communication under the described synchronous threshold-based opinion diffusion model.

3 Thesis Contribution

In this section I provide an overview of contributions to be included in my PhD project.

3.1 Published Papers

Let me describe the results provided so far.

Equilibrium Computation For Knockout Tournaments Played By Groups. In this paper, co-authored with M.S. Ramanujan, and Paolo Turrini [2022], we studied the problem of strategic nominee selection in the context of knockout tournaments. In our approach, the competitors in a tournament are coalitions of players choosing their nominee to compete in a given round. We studied game-theoretic aspects of such a scenario, focusing on the computational complexity of checking the existence of a NE. We distinguished between the case in which coalitions select one player for the entire tournament, and the one in which they can change their nominee at every round. In the first of them, we found that if coalitions are only interested in winning the tournament, the problem can be solved in quasi-polynomial time. Also, if they strive to advance far, we can check if a NE exists in polynomial time. Similar results hold for the scenario allowing coalitions to modify their choice during the competition.

A Hotelling-Downs Framework for Party Nominees. In this paper, developed with Paul Harrenstein, M.S. Ramanujan, and Paolo Turrini [2021], we consider a variation of the Hotelling-Downs model. Here, we formalise the problem of primaries by associating each of the players with a political party. In the considered model, a party has a finite number of politicians, with specific locations on the spectrum. A party's pure strategy is the selection of a representative to compete in elections. We show that, in contrast with the original Hotelling-Downs model, in the considered scenario a NE might not exist even if there are only two parties competing. Moreover, we establish that in the general case checking if a NE exists in this setting is NP-complete. However, this problem is tractable in elections limited to two parties.

Convergence of Opinion Diffusion is PSPACE-Complete. In this paper, co-authored with Dmitry Chistikov, Mike Paterson, and Paolo Turrini [2020], we studied the algorithmic properties of the threshold opinion diffusion model. Namely, we considered the problem of whether a given network with a binary labelling converges, when agents communicate synchronously and update their opinions if the strict majority of their influencers disagrees with them. We show that this problem is PSPACE-complete.

3.2 Further Directions

Let me describe my ongoing work.

Nominee Selection in Tournament Solutions. I am exploring the comparison of algorithmic results obtained in the context of nominee selection in coalitional knockout tournaments to similar problems in the context of other tournament solutions. So, I consider the scenario in which coalitions select a representative to compete in a tournament without the knockout structure. I am aiming at finding the complexity of checking whether a NE exists in this scenario, when a winner of the tournament is determined by the Uncovered Set rule.

Algorithmic Aspects of Majority Illusion. I am studying the problem of majority illusion from the computational complexity perspective. I investigate two problems. In the first of them I aim at establishing the complexity of checking if it is possible to label a given social network so that a specified fraction of agents is under majority illusion. In the second, I am considering the problem of checking, for a labelled network, whether it is possible to change a small number of connections between agents to ensure that at most a given fraction of them are under majority illusion. This study is aimed at providing an insight from the theoretical perspective into the well-studied problem of majority illusion.

4 Conclusion

In my PhD project I study the problem of strategic nominee selection from the perspective of a number of different social choice methods. I further explore topics in the theory of opinion diffusion related to this problem. My findings leave a large room for further study. In particular, many computational problems considered in my thesis were shown to be hard. Hence, finding non-trivial classes of inputs for which they are tractable would be of high interest.