We study strategic behaviour of project proposers in the  context of approval-based participatory budgeting, assuming that the votes are fixed and known and the proposers want to set as high project prices as possible, provided that their projects get selected and the prices are not below the minimum costs of their delivery. We study the existence of pure Nash equilibria in such games, for a number of voting rules. While such equilibria might not exist, we provide several positive results for intuitive restrictions of voters’ preferences. Furthermore, we report an experimental study of strategic cost selection on real-life election data.

Vitality indices form a natural class of centrality measures that assess the importance of a node based on the impact its removal has on the network. In this talk, we will discuss the connection between vitality indices and game-theoretic centrality measures, which are centrality measures defined based on coalitional game theory. We will also discuss group centrality measures and define a group version of the Shapley value.

Opracowanie to przedstawia oryginalny projekt ordynacji proporcjonalno-lokalnej (dalej „ordynacji PL”), będący odpowiedzią na postulat wprowadzenia w Polsce ordynacji mieszanej. Proponowany system jest możliwie zbliżony do obecnego, choć jednocześnie wprowadza starannie przemyślane nowe elementy. Nawiązuje zarówno do najlepszych rozwiązań stosowanych w innych krajach, jak też opiera się do dogłębnych studiach nad realiami polskiego życia politycznego. Bierze pod uwagę obecne i możliwe strategie partii, kandydatów oraz wyborców. Wiele jego elementów jest odpowiedzią na obawy, które były podnoszone we wcześniejszych dyskusjach wokół takiej zmiany. Także takie obawy, które wynikają z doświadczeń państw, które dokonywały zmian ordynacji bez głębszych analiz i nie ustrzegły się poważnych błędów. Projekt ten był efektem prac specjalnego zespołu sejmowego, spotykającego się w latach 2021-2022.

We consider approval-based committee elections, in which a size-k subset of available candidates must be selected given approval sets for each voter, indicating the candidates approved by the voter. A number of axioms capturing ideas of fairness and proportionality have been proposed for this framework. We argue that even the strongest of them, such as priceability and the core, only rule out certain undesirable committees, but fail to ensure that the selected committee is fair in all cases. We propose two new solution concepts, stable priceability and balanced stable priceability, and show that they select arguably fair committees. Our solution concepts come with a non-trivial-to-construct but easy-to-understand market-based explanation for why the chosen committee is fair. We show that stable priceability is closely related to the notion of Lindahl equilibrium from economics.

The Mallows model is a popular distribution for ranked data. We empirically and theoretically analyze how the properties of rankings sampled from the Mallows model change when increasing the number of alternatives. We find that real-world data behaves differently than the Mallows model, yet is in line with its recent variant proposed by Boehmer et al. [IJCAI ’21]. As part of our study, we issue several warnings about using the model.

We provide a characterization of closeness centrality in the class of distance-based centralities. To this end, we introduce a natural property, called majority comparison, that states that out of two adjacent nodes the one closer to more nodes is more central. We prove that any distance-based centrality that satisfy this property gives the same ranking in every graph as closeness centrality. The axiom is inspired by the interpretation of the graph as an election in which nodes are both voters and candidates and their preferences are determined by the distances to the other nodes. Given this, majority comparison states that out of two adjacent nodes the one preferred by more nodes should have higher centrality.

In this talk I will present the idea of the map of (ordinal) elections and argue what it is good for. First, we will spend considerable amount of time on understanding diversity, polarization, and agreement within elections on the map. Then, we will look at other applications, such as using the map to visualize performance of various algorithms.

We consider a model where a number of candidates need to be selected subject to certain feasibility constraints. The model generalises committee elections (where there is a single constraint on the number of candidates that need to be selected), various elections with diversity constraints, the model of public decisions (where there is a set of independent issues, and the constraints say that we need to pick a single decision for each issue) and the model of collective scheduling. The voters express their preferences over the candidates through voting, and the goal is to select the outcome that would be arguable fair. We mainly focus on group fairness understood as proportionality. We formulate axioms of proportionality in this general model. Our axioms are always satisfiable, and generalise the strongest known satisfiable axioms for the more specific models. This is a working paper.

We investigate ties in multiwinner approval voting both theoretically and experimentally. Specifically, we analyze the computational complexity of 1) determining if there is a tie in a given election for a given rule, and 2) the complexity of counting the number of winning committees. We mainly concentrate on Thiele rules as well as their greedy variants, and Phragmen-like rules (Phragmen and MES). We also conduct some experiments to see a) how often ties occur for different models, and b) how vulnerable to ties are different rules.

We consider a problem of mechanism design without money, where a planner selects a winner among a set of agents with binary types and receives outside signals (like the report of impartial referees). We show that there is a gap between the optimal Dominant Strategy Incentive Compatible (DSIC) mechanism and the optimal Bayesian Incentive Compatible (BIC) mechanism. In the optimal BIC mechanism, the planner can leverage the outside signal to elicit information about agents’ types. BIC mechanisms are lexicographic mechanisms, where the planner first shortlists agents who receive high reports from the referees and then uses agents’ reports to break ties among agents in the shortlist. We compare the “self-evaluation” mechanism with a “peer evaluation” mechanism where agents evaluate other agents, and show that for the same signal precision, the self-evaluation mechanism outperforms the peer evaluation mechanism.

While many papers in computational social choice are theoretical, the number of experimental works is rapidly growing. During the tutorial, we will focus on experiments related to voting and participatory budgeting. We will discuss most popular statistical culture models (that serve for generating synthetic elections), and real-life elections from several datasources such as, for example, Preflib or Pabulib. Moreover, we will describe Python libraries such as abcvoting (implementations of approval-based multiwinner voting rules) and mapel (tools for generating maps of elections).

Influencing (and being influenced by) others through social networks is fundamental to all human societies. Whether this happens through the diffusion of rumors, opinions, or viruses, identifying the diffusion source (i.e., the person that initiated it) is a problem that has attracted much research interest. Nevertheless, existing literature has ignored the possibility that the source might strategically modify the network structure (by rewiring links or introducing fake nodes) to escape detection. Here, without restricting our analysis to any particular diffusion scenario, we close this gap by evaluating two mechanisms that hide the source—one stemming from the source’s actions, the other from the network structure itself. This reveals that sources can easily escape detection, and that removing links is far more effective than introducing fake nodes. Thus, efforts should focus on exposing concealed ties rather than planted.