We study the complexity of constructive bribery in the context of structured multiwinner approval elections. Given such an election, we ask whether a certain candidate can join the winning committee by adding, deleting, or swapping approvals, where each such action comes at a cost and we are limited by a budget. We assume our elections to either have the candidate interval or the voter interval property, and we require the property to hold also after the bribery. While structured elections usually make manipulative attacks significantly easier, our work also shows examples of the opposite behavior. We conclude by presenting preliminary insights regarding the destructive variant of our problem.

For the problem of aggregating several rankings into one ranking, Kemeny (1959) proposed two methods: the median rule which selects the ranking with the smallest total swap distance to the input rankings, and the mean rule which minimizes the squared swap distances to the input rankings. The median rule has been extensively studied since and is now known simply as Kemeny’s rule. It exhibits majoritarian properties, so for example if more than half of the input rankings are the same, then the output of the rule is the same ranking.

We observe that this behavior is undesirable in many rank aggregation settings. For example, when we rank objects by different criteria (quality, price, etc.) and want to aggregate them with specified weights for the criteria, then a criterion with weight 51% should have 51% influence on the output instead of 100%. We show that the Squared Kemeny rule (i.e., the mean rule) behaves this way, by establishing a bound on the distance of the output ranking to any input rankings, as a function of their weights. Furthermore, we give an axiomatic characterization of the Squared Kemeny rule, which mirrors the existing characterization of the Kemeny rule but replaces the majoritarian Condorcet axiom by a proportionality axiom. Finally, we discuss the computation of the rule and show its behavior in a simulation study.

We study the independent approval model (IAM) for approval elections, where each candidate has its own approval probability and is approved independently of the other ones. This model generalizes, e.g., the impartial culture, the Hamming noise model, and the resampling model. We propose algorithms for learning IAMs and their mixtures from data, using either maximum likelihood estimation or Bayesian learning. We then apply these algorithms to a large set of elections from the Pabulib database. In particular, we find that single-component models are rarely sufficient to capture the complexity of real-life data, whereas their mixtures perform well.

This is a joint work with Łukasz Janeczko, Andrzej Kaczmarczyk, Marcin Kurdziel, Grzegorz Pierczyński and Stanisław Szufa.

We provide an axiomatic characterization of preference relations on indivisible goods that can be represented by additive utility functions. Specifically, we demonstrate that an ordinal preference relation can be represented by some additive utility function if and only if it satisfies an axiom called trade robustness. This axiom asserts that it is impossible to rearrange elements in a list of subsets in such a way that each subset becomes (weakly) worse than its original counterpart and at least one becomes worse. Our axiom generalizes a property proposed in cooperative game theory literature and a classic characterization of weighted voting games.

In the Submodular Facility Location problem (SFL) we are given a collection of n clients and m facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility f to which we assign the subset of clients S^f, one has to pay the opening cost g(S^f), where g() is a monotone submodular function with g(emptyset)=0. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA’06] gave the current-best O(log n) approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an O(loglog n) approximation.

Based on the following paper: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.5

In recent years, the study of various models and questions related to Liquid Democracy has been of growing interest among the community of Computational Social Choice. A concern that has been raised is that the current academic literature focuses solely on static inputs, concealing a key characteristic of Liquid Democracy: the right for a voter to change her mind as time goes by, regarding her options of whether to vote herself or delegate her vote to other participants, until the final voting deadline. In real life, a period of extended deliberation preceding the election day motivates voters to adapt their behavior over time, either based on observations of the remaining electorate or on information acquired for the topic at hand. By adding a temporal dimension to Liquid Democracy, such adaptations can increase the number of possible delegation paths and reduce the loss of votes due to delegation cycles or delegating paths towards abstaining agents, ultimately enhancing participation. Our work takes a first step to integrate a time horizon into decision-making problems in Liquid Democracy systems. Our approach, via a computational complexity analysis, exploits concepts and tools from temporal graph theory which turn out to be convenient for our framework.

Based on the following paper: https://arxiv.org/abs/2307.12898

Plan of presentations:
15:00: Oskar Skibski, Michał Lange, Piotr Kępczyński, Łukasz Janeczko.
16:00: Stach Kaźmierowski, Piotr Faliszewski, Marcin Dziubiński, Krzysztof Sornat.
17:00: Georgios Papasotiropoulos, Grzegorz Lisowski, Dorota Celińska-Kopczyńska, Piotr Skowron.

We show how hidden interesting subelections can be discovered in ordinal elections. An interesting subelection consists of a reasonably large set of voters and a reasonably large set of candidates such that the former have a consistent opinion about the latter. Consistency may take various forms but we focus on three: Identity (all selected voters rank all selected candidates the same way), antagonism (half of the selected voters rank candidates in some order and the other half in the reverse order), and clones (all selected voters rank all selected candidates contiguously in the original election). We first study the computation of such hidden subelections. Second, we analyze synthetic and real-life data, and find that identifying hidden consistent subelections allows us to uncover some relevant concepts.

We study the setting of single-winner elections with ordinal preferences where candidates might be members of alliances (which may correspond to e.g., political parties, factions, or coalitions). However, we do not assume that candidates from the same alliance are necessarily adjacent in voters’ rankings. In such a case, every classical voting rule is vulnerable to the spoiler effect, i.e., the presence of a candidate may harm his or her alliance. We therefore introduce a new idea of alliance-aware voting rules which extend the classical ones. We show that our approach is superior both to using classical cloneproof voting rules and to running primaries within alliances before the election. We introduce several alliance-aware voting rules and show that they satisfy the most desirable standard properties of their classical counterparts as well as newly introduced axioms for the model with alliances which, e.g., exclude the possibility of the spoiler effect. Our rules have natural definitions and are simple enough to explain to be used in practice.

Many interactions result in a socially suboptimal equilibrium, or in a non-equilibrium state, from which arriving at the desired equilibrium through simple dynamics can be impossible or take too long. Aiming at the theoretically and practically key problem of guaranteeing a certain equilibrium without altering the game, we persuade, bribe, or coerce a group of participants to make them act in a way that will motivate the rest of the players to act accordingly to the desired equilibrium. Formally, we ask which subset of the players can adopt the goal equilibrium strategies that will make acting according to the desired equilibrium a best response for the other players. We call such a subset a direct control set.

We first show when the desired equilibrium having certain direct control sets implies the strength of that equilibrium, and study the hardness of finding lightest direct control sets, even approximately. We then solve important subcases and provide approximation algorithms. Next, we concentrate on potential games and prove that, while finding such a set is \NP-hard, even for a constant-factor approximation, we can still solve the problem approximately or even precisely in relevant special cases. We approximately solve this problem for singleton potential games and treat more closely specific potential games, such as symmetric games and coordination games on graphs.

[slides] [example of breaking monotonicity]

We study preference aggregation from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per the preferences. By proposing basic axioms to capture this objective, we observe that none of the prominent multiwinner voting rules meet them. Consequently, we design selection mechanisms compliant with our desiderata, introducing conflictual voting rules. A subsequent deepened analysis sheds more light on how they operate. Our investigation identifies various aspects of conflict, for which we come up with relevant axioms and quantitative measures, which may be of independent interest. We support our theoretical study with experiments on both real-life and synthetic data.

[slides]

We consider a voting 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 decisions needs to be taken on a number of independent issues), and the model of collective scheduling. A critical property of voting is that it should be fair—not only to individuals but also to groups of voters with similar opinions on the subject of the vote; in other words, the outcome of an election should proportionally reflect the voters’ preferences. We formulate axioms of proportionality in this general model. Our axioms do not require predefining groups of voters; to the contrary, we ensure that the opinion of every subset of voters whose preferences are cohesive-enough are taken into account to the extent that is proportional to the size of the subset. Our axioms generalise the strongest known satisfiable axioms for the more specific models. We explain how to adapt two prominent committee election rules, Proportional Approval Voting (PAV) and Phragmén Sequential Rule, as well as the concept of stable-priceability to our general model. The two rules satisfy our proportionality axioms if and only if the feasibility constraints are matroids.

[slides]

In this talk I will discuss how numerical experiments on elections were typically performed in computational social choice and what we can learn from it. In particular, we will see what election sizes were considered and what statistical cultures were used etc. Further, we will analyze which choices were reasonable and under what conditions. The talk is based on the “Guide to Experiments” project, which collects experimental election papers from AAAI/IJCAI/AAMAS conferences held since 2010.

[slides]

We study the fair allocation of mixtures of indivisible goods and chores under lexicographic preferences—a subdomain of additive preferences. A prominent fairness notion for allocating indivisible items is envy-freeness up to any item (EFX). Yet, its existence and computation has remained a notable open problem. By identifying a class of instances with “terrible chores”, we show that determining the existence of an EFX allocation is NP-complete. This result immediately implies the intractability of EFX under additive preferences. Nonetheless, we propose a natural subclass of lexicographic preferences for which an EFX and Pareto optimal (PO) allocation is guaranteed to exist and can be computed efficiently for any mixed instance. Focusing on two weaker fairness notions, we investigate finding EF1 and PO allocations for special instances with terrible chores, and show that MMS and PO allocations can be computed efficiently for any mixed instance with lexicographic preferences.

[slides]

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.