Nimrod Talmon

ECAI Conference 2025 Conference Paper

A Dynamic Approach to Collaborative Document Writing

• Avital Finanser
• Nimrod Talmon

We introduce a model for collaborative text aggregation in which an agent community coauthors a document (modeled as an unordered collection of paragraphs) using a dynamic mechanism: agents propose paragraphs and vote on those suggested by others. We formalize the setting and explore its realizations, concentrating on voting mechanisms that aggregate votes into a single, dynamic document. We focus on two desiderata: the eventual stability of the process and its expected social welfare. Following an impossibility result, we describe several aggregation methods and report on agent-based simulations that utilize natural language processing (NLP) and large-language models (LLMs) to model agents. Using these simulations, we demonstrate promising results regarding the possibility of rapid convergence to a high social welfare collaborative text.

TARK Conference 2025 Conference Paper

AI-Generated Compromises for Coalition Formation: Modeling, Simulation, and a Textual Case Study

• Eyal Briman
• Ehud Shapiro
• Nimrod Talmon

The challenge of finding compromises between agent proposals is fundamental to AI sub-fields such as argumentation, mediation, and negotiation. Building on this tradition, Elkind et al. (2021) introduced a process for coalition formation that seeks majority-supported proposals preferable to the status quo, using a metric space where each agent has an ideal point. The crucial step in this iterative process involves identifying compromise proposals around which agent coalitions can unite. How to effectively find such compromise proposals, however, remains an open question. We address this gap by formalizing a holistic model that encompasses agent bounded rationality and uncertainty and developing AI models to generate such compromise proposals. We focus on the domain of collaboratively writing text documents -- e. g. , to enable the democratic creation of a community constitution. We apply NLP (Natural Language Processing) techniques and utilize LLMs (Large Language Models) to create a semantic metric space for text and develop algorithms to suggest suitable compromise points. To evaluate the effectiveness of our algorithms, we simulate various coalition formation processes and demonstrate the potential of AI to facilitate large-scale democratic text editing, such as collaboratively drafting a constitution, an area where traditional tools are limited.

JAIR Journal 2025 Journal Article

Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games

• Joanna Kaczmarek
• Jörg Rothe
• Nimrod Talmon

Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only sufficiently connected coalitions are taken into consideration for calculating the players' power indices. Focusing on the probabilistic Penrose-Banzhaf index (which Dubey and Shapley proposed in 1979 as an alternative to the normalized Penrose-Banzhaf index) and the Shapley-Shubik index, we study control of these games by an agent who can add edges to or delete edges from the given graph. We determine upper and lower bounds on how much such control actions can change a distinguished player's power and we study the computational complexity of the related problems.

AIJ Journal 2025 Journal Article

Drawing a map of elections

• Stanisław Szufa
• Niclas Boehmer
• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

Our main contribution is the introduction of the map of elections framework. A map of elections consists of three main elements: (1) a dataset of elections (i. e. , collections of ordinal votes over given sets of candidates), (2) a way of measuring similarities between these elections, and (3) a representation of the elections in the 2D Euclidean space as points, so that the more similar two elections are, the closer are their points. In our maps, we mostly focus on datasets of synthetic elections, but we also show an example of a map over real-life ones. To measure similarities, we would have preferred to use, e. g. , the isomorphic swap distance, but this is infeasible due to its high computational complexity. Hence, we propose polynomial-time computable positionwise distance and use it instead. Regarding the representations in 2D Euclidean space, we mostly use the Kamada-Kawai algorithm, but we also show two alternatives. We develop the necessary theoretical results to form our maps and argue experimentally that they are accurate and credible. Further, we show how coloring the elections in a map according to various criteria helps in analyzing results of a number of experiments. In particular, we show colorings according to the scores of winning candidates or committees, running times of ILP-based winner determination algorithms, and approximation ratios achieved by particular algorithms.

AAAI Conference 2025 Conference Paper

Federated Assemblies

• Daniel Halpern
• Ariel D. Procaccia
• Ehud Shapiro
• Nimrod Talmon

A *citizens' assembly* is a group of people who are randomly selected to represent a larger population in a deliberation. While this approach has successfully strengthened democracy, it has certain limitations that suggest the need for assemblies to form and associate more organically. In response, we propose *federated assemblies*, where assemblies are interconnected, and each parent assembly is selected from members of its child assemblies. The main technical challenge is to develop random selection algorithms that meet new representation constraints inherent in this hierarchical structure. We design and analyze several algorithms that provide different representation guarantees under various assumptions on the structure of the underlying graph.

EUMAS Conference 2025 Conference Paper

Query-Based Committee Selection

• Nimrod Talmon
• Shiri Alouf-Heffetz
• Itay Asher Zimet

IJCAI Conference 2024 Conference Paper

Aggregation of Continuous Preferences in One Dimension

• Alberto Del Pia
• Dušan Knop
• Alexandra Lassota
• Krzysztof Sornat
• Nimrod Talmon

We develop a general, formal model of social choice in which voters have continuous preferences over a one-dimensional space. Our model is parameterized by different restrictions that we introduce regarding the way voter preferences change in time as well as the optimization criteria (that correspond to a normative continuum of fairness definitions) desired from an aggregation method---that outputs a continuous, one-dimensional curve---given such inputs. We discuss the applicability of the model to different real-world situations and, as a first step towards an analysis of the different model realizations, we concentrate on identifying those cases that are computationally feasible to compute.

AAMAS Conference 2024 Conference Paper

Controlling Delegations in Liquid Democracy

• Shiri Alouf-Heffetz
• Tanmay Inamdar
• Pallavi Jain
• Nimrod Talmon
• Yash More Hiren

In liquid democracy, agents can either vote directly or delegate their vote to a different agent of their choice. This results in a power structure in which certain agents possess more voting weight than others. As a result, it opens up certain possibilities of vote manipulation, including control and bribery, that do not exist in standard voting scenarios of direct democracy. Here we formalize a certain kind of election control – in which an external agent may change certain delegation arcs – and study the computational complexity of the corresponding combinatorial problem.

AAMAS Conference 2024 Conference Paper

Fine-Grained Liquid Democracy for Cumulative Ballots

• Matthias Köppe
• Martin Koutecký
• Krzysztof Sornat
• Nimrod Talmon

We investigate efficient ways for the incorporation of liquid democracy into election settings in which voters submit cumulative ballots, i. e. , when each voter is assigned a virtual coin that she can then distribute as she wishes among the available election options. In particular, aiming at improving the quality of decision making, we are interested in fine-grained liquid democracy, meaning that voters are able to designate a partial coin to a set of election options and delegate the decision on how to further split this partial coin among those election options to another voter of her choice. The fact that we wish such delegations to be transitive—combined with our aim at fully respecting such delegations—means that inconsistencies and cycles can occur, thus we set to find computationallyefficient ways of resolving voters’ delegations. To this end we develop a theory based on fixed-point theorems and mathematical programming techniques and we show that for various variants of definitions regarding how to resolve such transitive delegations, there is always a feasible resolution; and we identify under which conditions such solutions are efficiently computable. For example, we provide a parameterized algorithm whose running time depends on a distance from triviality of a given instance.

IJCAI Conference 2024 Conference Paper

Optimizing Viscous Democracy

• Ben Armstrong
• Shiri Alouf-Heffetz
• Nimrod Talmon

Viscous democracy is a generalization of liquid democracy, a social choice framework in which voters may transitively delegate their votes. In viscous democracy, a "viscosity" factor decreases the weight of a delegation the further it travels, reducing the chance of excessive weight flowing between ideologically misaligned voters. We demonstrate that viscous democracy often significantly improves the quality of group decision-making over liquid democracy. We first show that finding optimal delegations within a viscous setting is NP-hard. However, simulations allow us to explore the practical effects of viscosity. Across social network structures, competence distributions, and delegation mechanisms we find high viscosity reduces the chance of ``super-voters'' attaining large amounts of weight and increases the number of voters that are able to affect the outcome of elections. This, in turn, improves group accuracy as a whole. As a result, we argue that viscosity should be considered a core component of liquid democracy.

ECAI Conference 2023 Conference Paper

Complexity of Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games

• Joanna Kaczmarek 0001
• Jörg Rothe
• Nimrod Talmon

Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only connected coalitions are taken into consideration for calculating the players’ power indices. We focus on the probabilistic Penrose–Banzhaf index [5] and the Shapley–Shubik index [18] and study the computational complexity of manipulating these games by an external agent who can add edges to or delete edges from the graph. For the problems modeling such scenarios, we raise some of the lower bounds obtained by Kaczmarek and Rothe [9] from NP- or DP-hardness to PP-hardness, where PP is probabilistic polynomial time. We also solve one of their open problems by showing that it is a coNP-hard problem to maintain the Shapley–Shubik index of a given player in a graph-restricted weighted voting game when edges are deleted.

ECAI Conference 2023 Conference Paper

Efficiently Computing Smallest Agreeable Sets

• Robert Bredereck
• Till Fluschnik
• Nimrod Talmon

We study the computational complexity of identifying a small agreeable subset of items. A subset of items is agreeable if every agent does not prefer its complement set. We study settings in which agents either can assign arbitrary utilities to the items; can approve or disapprove the items; or can rank the items (in which case we consider Borda utilities). We prove that deciding whether an agreeable set exists is NP-hard for all variants; and we perform a parameterized analysis regarding the following natural parameters: the number of agents, the number of items, and the upper bound on the size of the agreeable set in question.

EUMAS Conference 2023 Conference Paper

Multiple Attribute List Aggregation and an Application to Democratic Playlist Editing

• Eyal Briman
• Nimrod Talmon

Abstract We present a social choice model that incorporates time-based constraints, where the goal is to produce an ordered list that satisfies both agent preferences (based on approval ballots) and global constraints. First, we analyze the general model, showing that it is generally NP-hard, but admits polynomial-time algorithms for a special case; we also develop heuristic solutions for the general case. Furthermore, we explore potential applications of the model and demonstrate its relevance by focusing on the use case of democratic playlist editing. In this scenario, our aim is to generate a playlist that reflects agent preferences for a given set of musical tracks while also considering soft constraints regarding the sequencing and transitions of tracks over time. We illustrate how the problem of democratic playlist editing can be translated into our model, and present simulation results where we apply our heuristics to solve specific instances of the problem. We contend that our results are promising, not only for the specific use case of democratic playlist editing, but also for a plethora of other use cases that we introduce here.

IJCAI Conference 2023 Conference Paper

Participatory Budgeting: Data, Tools and Analysis

• Piotr Faliszewski
• Jarosław Flis
• Dominik Peters
• Grzegorz Pierczyński
• Piotr Skowron
• Dariusz Stolicki
• Stanisław Szufa
• Nimrod Talmon

We provide a library of participatory budgeting data (Pabulib) and open source tools (Pabutools and Pabustats) for analysing this data. We analyse how the results of participatory budgeting elections would change if a different selection rule was applied. We provide evidence that the outcomes of the Method of Equal Shares would be considerably fairer than those of the Utilitarian Greedy rule that is currently in use. We also show that the division of the projects into districts and/or categories can in many cases be avoided when using proportional rules. We find that this would increase the overall utility of the voters.

AAMAS Conference 2023 Conference Paper

Social Choice Around Decentralized Autonomous Organizations: On the Computational Social Choice of Digital Communities

• Nimrod Talmon

Decentralized Autonomous Organizations (DAOs) are sovereign digital communities that are owned by their members and that are algorithmically-controlled, usually by encoding their rules of conduct as smart contracts. Even though such communities become more popular and influential, their governance capabilities are still limited and lacking in quality. We argue that the MAS community holds the keys to improving the governance capabilities of DAOs; and that the challenge of DAO governance constitutes an important, new application area for MAS research that has the potential to have both scientific and societal impacts. Concretely, we describe DAOs and their governance needs and highlight gaps between the state of the art of MAS research and the governance needs of DAOs.

IJCAI Conference 2022 Conference Paper

Better Collective Decisions via Uncertainty Reduction

• Shiri Alouf-Heffetz
• Laurent Bulteau
• Edith Elkind
• Nimrod Talmon
• Nicholas Teh

We consider an agent community wishing to decide on several binary issues by means of issue-by-issue majority voting. For each issue and each agent, one of the two options is better than the other. However, some of the agents may be confused about some of the issues, in which case they may vote for the option that is objectively worse for them. A benevolent external party wants to help the agents to make better decisions, i. e. , select the majority-preferred option for as many issues as possible. This party may have one of the following tools at its disposal: (1) educating some of the agents, so as to enable them to vote correctly on all issues, (2) appointing a subset of highly competent agents to make decisions on behalf of the entire group, or (3) guiding the agents on how to delegate their votes to other agents, in a way that is consistent with the agents' opinions. For each of these tools, we study the complexity of the decision problem faced by this external party, obtaining both NP-hardness results and fixed-parameter tractability results.

AAMAS Conference 2022 Conference Paper

Foundations for Grassroots Democratic Metaverse

• Ehud Shapiro
• Nimrod Talmon

While the physical lives of many of us are in democracies (one person, one vote — e. g. , the EU and the US), our digital lives are mostly in autocracies (one person, all votes — e. g. , Facebook). Cryptocurrencies promise liberation but stop short, at plutocracy (one coin, one vote). What would it take for us to live in a digital democracy? This paper offers a vision, a theoretical framework, and an architecture for a grassroots network of autonomous, people-owned, people-operated, and people-governed digital communities, namely a grassroots democratic metaverse. It also charts a roadmap towards realizing it, and identifies unexplored territory for MAS research.

IJCAI Conference 2022 Conference Paper

How Should We Vote? A Comparison of Voting Systems within Social Networks

• Shiri Alouf-Heffetz
• Ben Armstrong
• Kate Larson
• Nimrod Talmon

Voting is a crucial methodology for eliciting and combining agents' preferences and information across many applications. Just as there are numerous voting rules exhibiting different properties, we also see many different voting systems. In this paper we investigate how different voting systems perform as a function of the characteristics of the underlying voting population and social network. In particular, we compare direct democracy, liquid democracy, and sortition in a ground truth voting context. Through simulations -- using both real and artificially generated social networks -- we illustrate how voter competency distributions and levels of direct participation affect group accuracy differently in each voting mechanism. Our results can be used to guide the selection of a suitable voting system based on the characteristics of a particular voting setting.

IJCAI Conference 2022 Conference Paper

How to Sample Approval Elections?

• Stanisław Szufa
• Piotr Faliszewski
• Łukasz Janeczko
• Martin Lackner
• Arkadii Slinko
• Krzysztof Sornat
• Nimrod Talmon

We extend the map-of-elections framework to the case of approval elections. While doing so, we study a number of statistical cultures, including some new ones, and we analyze their properties. We find that approval elections can be understood in terms of the average number of approvals in the votes, and the extent to which the votes are chaotic.

EUMAS Conference 2022 Conference Paper

Preserving Consistency for Liquid Knapsack Voting

• Pallavi Jain 0001
• Krzysztof Sornat
• Nimrod Talmon

Abstract Liquid Democracy (LD) uses transitive delegations to facilitate joint decision making. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. Here we consider LD in the context of Participatory Budgeting (PB), which is a direct democracy approach to budgeting, most usually done in municipal budgeting processes. In particular, we study Knapsack Voting, in which PB voters can approve projects, however the sum of costs of voter-approved projects must respect the global budget limit. We observe inconsistency issues when allowing delegations, as the cost of voter-approved projects may go over the budget limit; we offer ways to overcome such inconsistencies by studying the computational complexity of a related combinatorial problem in which the task is to update as few delegations as possible to arrive—after following all project delegations—to a consistent profile.

EUMAS Conference 2022 Conference Paper

Sybil-Resilient Social Choice with Low Voter Turnout

• Reshef Meir
• Nimrod Talmon
• Gal Shahaf
• Ehud Shapiro

Abstract We address social choice in the presence of sybils (fake or duplicate votes) and low turnout, two behaviors that may each distort the will of the society. To do so we assume the status quo as an ever-present distinguished alternative. We propose a general Reality Enforcing mechanism, which can be combined with arbitrary voting rules and operates by adding virtual votes that support the status quo. We measure the tradeoff between safety and liveness (the ability of non-abstaining non-sybil voters to maintain or to change the status quo, respectively) in a variety of voting domains and show a tight inherent limit to the amount of sybils and abstentions that can be tolerated.

JAIR Journal 2021 Journal Article

Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation

• Laurent Bulteau
• Gal Shahaf
• Ehud Shapiro
• Nimrod Talmon

We present a unifying framework encompassing a plethora of social choice settings. Viewing each social choice setting as voting in a suitable metric space, we offer a general model of social choice over metric spaces, in which—similarly to the spatial model of elections—each voter specifies an ideal element of the metric space. The ideal element acts as a vote, where each voter prefers elements that are closer to her ideal element. But it also acts as a proposal, thus making all participants equal not only as voters but also as proposers. We consider Condorcet aggregation and a continuum of solution concepts, ranging from minimizing the sum of distances to minimizing the maximum distance. We study applications of our abstract model to various social choice settings, including single-winner elections, committee elections, participatory budgeting, and participatory legislation. For each setting, we compare each solution concept to known voting rules and study various properties of the resulting voting rules. Our framework provides expressive aggregation for a broad range of social choice settings while remaining simple for voters; and may enable a unified and integrated implementation for all these settings, as well as unified extensions such as sybil-resiliency, proxy voting, and deliberative decision making.

AAMAS Conference 2021 Conference Paper

Egalitarian and Just Digital Currency Networks

• Gal Shahaf
• Ehud Shapiro
• Nimrod Talmon

We explore the possibility of an alternative cryptocurrency that is egalitarian in control, just in the distribution of its created wealth, and forms and grows in a grassroots way; we analyze it via a mathematical entity called a currency network. Our main result states sufficient conditions for the establishment of 1: 1 exchange rates and distributive justice in a currency network.

IJCAI Conference 2021 Conference Paper

Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules

• Sushmita Gupta
• Pallavi Jain
• Saket Saurabh
• Nimrod Talmon

Multiwinner elections have proven to be a fruitful research topic with many real world applications. We contribute to this line of research by improving the state of the art regarding the computational complexity of computing good committees. More formally, given a set of candidates C, a set of voters V, each ranking the candidates according to their preferences, and an integer k; a multiwinner voting rule identifies a committee of size k, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian OWA (ordered weighted average) scoring rules, which are an extensively researched family of rules (and a subfamily of the family of committee scoring rules). First, we improve the result of Betzler et al. [JAIR, 2013], which gave a O(n^n) algorithm for computing winner under the Chamberlin Courant rule (CC), where n is the number of voters; to a running time of O(2^n), which is optimal. Furthermore, we study the parameterized complexity of the Pessimist voting rule and describe a few tractable and intractable cases. Apart from such utilitarian voting rules, we extend our study and consider egalitarian median and egalitarian mean (both committee scoring rules), showing some tractable and intractable results, based on nontrivial structural observations.

AAMAS Conference 2021 Conference Paper

How to Amend a Constitution? Model, Axioms, and Supermajority Rules

• Ben Abramowitz
• Ehud Shapiro
• Nimrod Talmon

A self-governed society must have decision rules by which group decisions are made, and these rules are often codified in a written constitution. One of the defining features of a constitution is its degree of entrenchment, or how hard it is to change by amendment. If it is too easy to make amendments, then the constitution can change too frequently, leading to chaos. On the other hand, if it is too hard to make amendments, then this can also be destabilizing, as voters may begin to see the rules as less legitimate, or even seek to overturn the status quo in a revolt. As norms, priorities, and circumstances change over time and over generations a constitution must be able to adapt. Our work considers a stylized model of constitutions that use reality-aware supermajority rules to make decisions. We propose principles for designing amendment procedures for changing decision rules in these constitutions and propose a novel procedure based on these principles.

AAAI Conference 2021 Conference Paper

Multi-Party Campaigning

• Martin Koutecký
• Nimrod Talmon

We study a social choice setting of manipulation in elections and extend the usual model in two major ways: first, instead of considering a single manipulating agent, in our setting there are several, possibly competing ones; second, instead of evaluating an election after the first manipulative action, we allow several back-and-forth rounds to take place. We show that in certain situations, such as in elections with only a few candidates, optimal strategies for each of the manipulating agents can be computed efficiently. Our algorithmic results rely on formulating the problem of finding an optimal strategy as sentences of Presburger arithmetic that are short and only involve small coefficients, which we show is fixed-parameter tractable – indeed, one of our contributions is a general result regarding fixed-parameter tractability of Presburger arithmetic that might be useful in other settings. Following our general theorem, we design quite general algorithms; in particular, we describe how to design efficient algorithms for various settings, including settings in which we model diffusion of opinions in a social network, complex budgeting schemes available to the manipulating agents, and various realistic restrictions on adversary actions.

IJCAI Conference 2021 Conference Paper

Participatory Budgeting with Project Groups

• Pallavi Jain
• Krzysztof Sornat
• Nimrod Talmon
• Meirav Zehavi

We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and---in addition to a global budget limit---there are several groupings of the projects, each group with its own budget limit. We study the computational complexity of identifying project bundles that maximize voter satisfaction while respecting all budget limits. We show that the problem is generally intractable and describe efficient exact algorithms for several special cases, including instances with only few groups and instances where the group structure is close to being hierarchical, as well as efficient approximation algorithms. Our results could allow, e. g. , municipalities to hold richer PB processes that are thematically and geographically inclusive.

AAMAS Conference 2021 Conference Paper

Partition Aggregation for Participatory Budgeting

• Pallavi Jain
• Nimrod Talmon
• Laurent Bulteau

Recently, Jain et al. [IJCAI, 2019] studied the effect of project interactions in participatory budgeting (PB) by assuming an existing partition of the projects to interaction structures, namely a grouping of the projects into substitution and complementarity groups. Motivated by their study, here we take voter preferences to find such interaction structures. In our model, voters submit interaction structures, and the goal is to find an aggregated structure. Formally, given a set 𝑃 of 𝑚 projects, and 𝑛 partitions of 𝑃, the task is to aggregate these 𝑛 partitions into one aggregated partition. We consider this partition aggregation task both for substitution structures and for complementarity structures, studying several aggregation methods for each, including utility-based methods and Condorcet-based methods; we evaluate these methods by analyzing their computational complexity and their behavior with respect to certain relevant axiomatic properties.

AAMAS Conference 2021 Conference Paper

Preserving Consistency for Liquid Knapsack Voting

• Pallavi Jain
• Krzysztof Sornat
• Nimrod Talmon

Liquid Democracy (LD) uses transitive delegations in voting. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. Here we consider LD in the context of Participatory Budgeting (PB), which is a direct democracy approach to budgeting, most usually done in municipal budgeting processes. In particular, we study Knapsack Voting, in which PB voters approve projects, such that the sum of costs of projects each voter approves must respect the budget limit. We observe possible inconsistencies, as the cost of voter-approved projects may go over the budget limit after resolving delegations. We offer ways to overcome them by studying the computational complexity of updating as few delegations as possible to arrive— after following all project delegations—to a consistent profile.

AIJ Journal 2021 Journal Article

Robustness among multiwinner voting rules

• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Rolf Niedermeier
• Piotr Skowron
• Nimrod Talmon

We investigate how robust the results of committee elections are with respect to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member might be replaced, or (2) it is possible that the whole committee will be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically NP-hard, but there are natural FPT algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.

AAAI Conference 2021 Conference Paper

United for Change: Deliberative Coalition Formation to Change the Status Quo

• Edith Elkind
• Davide Grossi
• Ehud Shapiro
• Nimrod Talmon

We study a setting in which a community wishes to identify a strongly supported proposal from a large space of alternatives, in order to change the status quo. We describe a deliberation process in which agents dynamically form coalitions around proposals that they prefer over the status quo. We formulate conditions on the space of proposals and on the ways in which coalitions are formed that guarantee deliberation to succeed, that is, to terminate by identifying a proposal with the largest possible support. Our results provide theoretical foundations for the analysis of deliberative processes in systems for democratic deliberation support, such as, e. g. , LiquidFeedback or Polis.

ECAI Conference 2020 Conference Paper

Committee Selection with Multimodal Preferences

• Pallavi Jain 0001
• Nimrod Talmon

We study committee selection with multimodal preferences: Assuming a set of candidates A, a set of voters V, and ℓ layers, where each voter v ∈ V has ordinal preferences over the alternatives for each layer separately, the task is to select a committee S ⊆ A of size k. We discuss applications of our model and study the computational complexity of several generalizations of known committee scoring rules (specifically, k-Borda and Chamberlin–Courant) to our setting, as well as discuss domain restrictions for our model. While most problems we encounter are computationally intractable in general, we nevertheless design efficient algorithms for certain cases.

TCS Journal 2020 Journal Article

Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting

• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Piotr Skowron
• Nimrod Talmon

A classic result of Lenstra [Math. Oper. Res. 1983] says that an integer linear program can be solved in fixed-parameter tractable ( FPT ) time for the parameterization by the number of variables. We extend this result by incorporating piecewise linear convex or concave functions to our (mixed) integer programs. This general technique allows us to analyze the parameterized complexity of a number of classic NP -hard computational problems. In particular, we prove that Weighted Set Multicover is in FPT when parameterized by the number of elements to cover, and that there exists an FPT -time approximation scheme for Multiset Multicover for the same parameter—this is our most technical result. Further, we use our general technique to prove that a number of problems from computational social choice (e. g. , problems related to bribery and control in elections) are in FPT when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems, and for weighted electoral control of Approval voting, this improves some previously known XP -memberships to FPT -memberships.

ECAI Conference 2020 Conference Paper

Multiwinner Rules with Variable Number of Winners

• Piotr Faliszewski
• Arkadii M. Slinko
• Nimrod Talmon

We consider voting rules for approval-based elections that select committees whose size is not predetermined. Unlike the study of rules that output committees with a predetermined number of winning candidates, the study of rules that select a variable number of winners has only recently been initiated. We first mention some scenarios for which such rules are applicable. Then, aiming at better understanding these rules, we study their computational properties and report on simulations regarding the sizes of their committees.

IJCAI Conference 2020 Conference Paper

Participatory Budgeting with Project Interactions

• Pallavi Jain
• Krzysztof Sornat
• Nimrod Talmon

Participatory budgeting systems allow city residents to jointly decide on projects they wish to fund using public money, by letting residents vote on such projects. While participatory budgeting is gaining popularity, existing aggregation methods do not take into account the natural possibility of project interactions, such as substitution and complementarity effects. Here we take a step towards fixing this issue: First, we augment the standard model of participatory budgeting by introducing a partition over the projects and model the type and extent of project interactions within each part using certain functions. We study the computational complexity of finding bundles that maximize voter utility, as defined with respect to such functions. Motivated by the desire to incorporate project interactions in real-world participatory budgeting systems, we identify certain cases that admit efficient aggregation in the presence of such project interactions.

AAAI Conference 2019 Conference Paper

A Framework for Approval-Based Budgeting Methods

• Nimrod Talmon
• Piotr Faliszewski

We define and study a general framework for approval-based budgeting methods and compare certain methods within this framework by their axiomatic and computational properties. Furthermore, we visualize their behavior on certain Euclidean distributions and analyze them experimentally.

AAMAS Conference 2019 Conference Paper

Approximation Algorithms for BalancedCC Multiwinner Rules

• Markus Brill
• Piotr Faliszewski
• Frank Sommer
• Nimrod Talmon

X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin–Courant rule. We show how to use the Greedy- Monroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin–Courant rule, by appropriately setting a “schedule” for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.

AIJ Journal 2019 Journal Article

Distributed monitoring of election winners

• Arnold Filtser
• Nimrod Talmon

We consider distributed elections, where there is a center and k sites. In such distributed elections, each voter has preferences over some set of candidates, and each voter is assigned to exactly one site such that each site is aware only of the voters assigned to it. The center is able to directly communicate with all sites. We are interested in designing communication-efficient protocols, allowing the center to maintain a candidate which, with arbitrarily high probability, is guaranteed to be a winner, or at least close to being a winner. We consider various single-winner voting rules, such as variants of Approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules. For the voting rules we consider, we show that, using communication which is logarithmic in the number of voters, it is possible for the center to maintain such approximate winners; that is, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. We complement our protocols with lower bounds. Our results are theoretical in nature and relate to various scenarios, such as aggregating customer preferences in online shopping websites or supermarket chains and collecting votes from different polling stations of political elections.

AAAI Conference 2019 Conference Paper

How Similar Are Two Elections?

• Piotr Faliszewski
• Piotr Skowron
• Arkadii Slinko
• Stanisław Szufa
• Nimrod Talmon

We introduce the ELECTION ISOMORPHISM problem and a family of its approximate variants, which we refer to as d- ISOMORPHISM DISTANCE (d-ID) problems (where d is a metric between preference orders). We show that ELECTION ISOMORPHISM is polynomial-time solvable, and that the d- ISOMORPHISM DISTANCE problems generalize various classic rank-aggregation methods (e. g. , those of Kemeny and Litvak). We establish the complexity of our problems (including their inapproximability) and provide initial experiments regarding the ability to solve them in practice.

IJCAI Conference 2019 Conference Paper

Multigoal Committee Selection

• Maciej Kocot
• Anna Kolonko
• Edith Elkind
• Piotr Faliszewski
• Nimrod Talmon

We study the problem of computing committees that perform well according to several different criteria, which are expressed as committee scoring rules. We analyze the computational complexity of computing such committees and provide an experimental evaluation of the compromise levels that can be achieved between several well-known rules, including k-Borda, SNTV, Bloc, and the Chamberlin--Courant rule.

AAMAS Conference 2019 Conference Paper

Proportional Representation in Elections: STV vs PAV

• Piotr Faliszewski
• Piotr Skowron
• Stanislaw Szufa
• Nimrod Talmon

We consider proportionality in multiwinner elections and observe that PAV and STV are fundamentally different. We argue that the former is proportional and the latter is degressively proportional.

IJCAI Conference 2019 Conference Paper

Sybil-Resilient Reality-Aware Social Choice

• Gal Shahaf
• Ehud Shapiro
• Nimrod Talmon

Sybil attacks, in which fake or duplicate identities (a. k. a. , Sybils) infiltrate an online community, pose a serious threat to such communities, as they might tilt community-wide decisions in their favor. While the extensive research on sybil identification may help keep the fraction of sybils in such communities low, it cannot however ensure their complete eradication. Thus, our goal here is to enhance social choice theory with effective group decision mechanisms for communities with bounded sybil penetration. Inspired by Reality-Aware Social Choice, we use the status quo as the anchor of Sybil Resilience, characterized by Sybil Safety -- the inability of sybils to change the status quo against the will of the genuine agents, and Sybil Liveness -- the ability of the genuine agents to change the status quo against the will of the sybils. We consider the social choice settings of deciding on a single proposal, on multiple proposals, and on updating a parameter. For each, we present social choice rules that are sybil-safe and, under certain conditions, satisfy sybil-liveness.

AAMAS Conference 2018 Conference Paper

Between Proportionality and Diversity: Balancing District Sizes under the Chamberlin-Courant Rule

• Piotr Faliszewski
• Nimrod Talmon

The Monroe and Chamberlin–Courant (CC) multiwinner rules proceed by partitioning the voters into virtual districts and assigning a unique committee member to each district, so that the voters are as satisfied with the assignment as possible. The difference between Monroe and CC is that the former creates equal-sized districts, while the latter has no constraints. We generalize these rules by requiring that the largest district can be at most X times larger than the smallest one (where X is a parameter). We show that our new rules inherit worst-case computational properties from their ancestors; evaluate the rules experimentally (in particular, we provide their visualizations, analyze actual district sizes and voter satisfaction); and analyze their approximability.

AAAI Conference 2018 Conference Paper

Committee Selection with Intraclass and Interclass Synergies

• Rani Izsak
• Nimrod Talmon
• Gerhard Woeginger

Voting is almost never done in void, as usually there are some relations between the alternatives on which the voters vote on. These relations shall be taken into consideration when selecting a winning committee of some given multiwinner election. As taking into account all possible relations between the alternatives is generally computationally intractable, in this paper we consider classes of alternatives; intuitively, the number of classes is significantly smaller than the number of alternatives, and thus there is some hope in reaching computational tractability. We model both intraclass relations and interclass relations by functions, which we refer to as synergy functions, and study the computational complexity of identifying the best committee, taking into account those synergy functions. Our model accommodates both positive and negative relations between alternatives; further, our efficient algorithms can also deal with a rich class of diversity wishes, which we show how to model using synergy functions.

AAAI Conference 2018 Conference Paper

Effective Heuristics for Committee Scoring Rules

• Piotr Faliszewski
• Martin Lackner
• Dominik Peters
• Nimrod Talmon

Committee scoring rules form an important class of multiwinner voting rules. As computing winning committees under such rules is generally intractable, in this paper we investigate efficient heuristics for this task. We design two novel heuristics for computing approximate results of multiwinner elections under arbitrary committee scoring rules; notably, one of these heuristics uses concepts from cooperative game theory. We then provide an experimental evaluation of our heuristics (and two others, known from the literature): we compare the scores of the committees output by our algorithms to the scores of the optimal committees, and also use the two-dimensional Euclidean domain to compare the visual representations of the outputs of our algorithms.

IJCAI Conference 2018 Conference Paper

Egalitarian Committee Scoring Rules

• Haris Aziz
• Piotr Faliszewski
• Bernard Grofman
• Arkadii Slinko
• Nimrod Talmon

We introduce and study the class of egalitarian variants of committee scoring rules, where instead of summing up the scores that voters assign to committees---as is done in the utilitarian variants---the score of a committee is taken to be the lowest score assigned to it by any voter. We focus on five rules, which are egalitarian analogues of SNTV, the k-Borda rule, the Chamberlin--Courant rule, the Bloc rule, and the Pessimist rule. We establish their computational complexity, provide their initial axiomatic study, and perform experiments to represent the action of these rules graphically.

AAMAS Conference 2018 Conference Paper

Incorporating Reality into Social Choice

• Ehud Shapiro
• Nimrod Talmon

When voting on a proposal one in fact chooses between two alternatives: (i) A new hypothetical social state depicted by the proposal and (ii) the status quo (henceforth: Reality); a Yes vote favors a transition to the proposed hypothetical state, while a No vote favors Reality. Social Choice theory generalizes voting on one proposal to ranking multiple proposals; that Reality was forsaken during this generalization is, in our view, inexplicable. Here we propose to rectify this neglect and incorporate Reality into Social Choice, distinguishing Reality from hypothesis. We show that doing so: (i) Offers a natural resolution to Condorcet’s paradox; (ii) Explains what approval voters approve; (iii) Produces a simple and efficient Condorcet-consistent show-of-hands agenda; (iv) Produces democratic action plans, which start with Reality and proceed in democratically-supported transitions; and (v) Nullifies Independence of Irrelevant Alternatives and hence abdicates Arrow’s Theorem. Arrow’s theorem was taken to show that democracy, conceived as government by the will of the people, is an incoherent illusion. Incorporating Reality into Social Choice may clear this intellectual blemish on democracy and offer a coherent, simple, efficient, easy to communicate, and trustworthy path forward to democracy.

IJCAI Conference 2018 Conference Paper

Opinion Diffusion and Campaigning on Society Graphs

• Piotr Faliszewski
• Rica Gonen
• Martin Koutecký
• Nimrod Talmon

We study the effects of campaigning, where the society is partitioned into voter clusters and a diffusion process propagates opinions in a network connecting those clusters. Our model is very general and can incorporate many campaigning actions, various partitions of the society into voter clusters, and very general diffusion processes. Perhaps surprisingly, we show that computing the cheapest campaign for rigging a given election can usually be done efficiently, even with arbitrarily-many voters.

AAMAS Conference 2018 Conference Paper

Optimization-Based Voting Rule Design: The Closer to Utopia the Better

• Piotr Faliszewski
• Stanislaw Szufa
• Nimrod Talmon

In certain situations, such as elections in the Euclidean domain, it is possible to specify clear requirements for the operation of a multiwinner voting rule, for it to provide committees that correspond to some desirable intuitive notions (such as individual excellence of the committee members or their diversity). We formally describe several such requirements, which we refer to as “utopias”. Supplied with such utopias, we develop an optimization-based mechanism for constructing committee scoring rules that provide results as close to these utopias as possible; we test our mechanism on weakly separable and OWA-based rules. In particular, using our method we recover some connections between known multiwinner voting rules and certain applications.

IJCAI Conference 2018 Conference Paper

Pairwise Liquid Democracy

• Markus Brill
• Nimrod Talmon

In a liquid democracy, voters can either vote directly or delegate their vote to another voter of their choice. We consider ordinal elections, and study a model of liquid democracy in which voters specify partial orders and use several delegates to refine them. This flexibility, however, comes at a price, as individual rationality (in the form of transitive preferences) can no longer be guaranteed. We discuss ways to detect and overcome such complications. Based on the framework of distance rationalization, we introduce novel variants of voting rules that are tailored to the liquid democracy context.

AAMAS Conference 2018 Conference Paper

Proportionally Representative Participatory Budgeting: Axioms and Algorithms

• Haris Aziz
• Barton E. Lee
• Nimrod Talmon

Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axioms in participatory budgeting, by generalizing relevant axioms for approvalbased multi-winner elections. We observe a rich landscape with respect to the computational complexity of identifying proportional budgets and computing such, and present budgeting methods that satisfy these axioms by identifying budgets that are representative to the demands of vast segments of the voters.

TCS Journal 2018 Journal Article

Structured proportional representation

• Nimrod Talmon

Multi-winner voting rules aiming at proportional representation, 1 such as those suggested by Chamberlin and Courant [2] and by Monroe [5], partition an electorate into virtual districts, such that a representative is assigned to each district; these districts are formed based on the voters' preferences. In some applications it is beneficial to require certain structural properties to be satisfied by these virtual districts. In this paper we consider situations where the voters are embedded in a network, modeled as an undirected graph, and we require the virtual districts to satisfy certain structural properties with respect to this network. Specifically, we consider two structural properties, corresponding to two different combinatorial problems: in the first problem, we require each virtual district to be connected, while in the second problem, we require the diameter of each virtual district to be small. We discuss applications of these combinatorial problems and study their computational complexity, identifying several variants and special cases which can be solved efficiently.

AAMAS Conference 2017 Conference Paper

Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules

• Piotr Faliszewski
• Piotr Skowron
• Nimrod Talmon

We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i. e. , sets of candidates they approve) and the bribery actions are limited to: adding an approval to a vote, deleting an approval from a vote, or moving an approval within a vote from one candidate to the other. We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin–Courant, and PAV). We find the landscape of complexity results quite rich, going from polynomial-time algorithms through NP-hardness with constant-factor approximations, to outright inapproximability. Moreover, in general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee (i. e. , adding approvals only for this preferred candidate, or moving approvals only to him or her). We also study parameterized complexity of our problems, with a focus on parameterizations by the numbers of voters or candidates.

AAMAS Conference 2017 Conference Paper

Distributed Monitoring of Election Winners

• Arnold Filtser
• Nimrod Talmon

We consider distributed elections, where there is a center and k sites. In such distributed elections, each voter has preferences over some set of candidates, and each voter is assigned to exactly one site such that each site is aware only of the voters assigned to it. The center is able to directly communicate with each of the sites. We are interested in designing communication-efficient protocols, allowing the center to maintain (i. e. , declare) a candidate which, with arbitrary high probability, is guaranteed to be a winner, or at least close to being a winner. We consider various single-winner voting rules, such as variants of Approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules. For these voting rules, we show that, using communication which is logarithmic in the number of voters, it is possible for the center to maintain such approximate winners. We complement our protocols with lower bounds. Our results have implications in various scenarios, such as aggregating customer preferences in online shopping websites or supermarket chains and collecting votes from different polling stations of political elections.

JAIR Journal 2017 Journal Article

Elections with Few Voters: Candidate Control Can Be Easy

• Jiehua Chen
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a parameter. We consider both the standard scenario of adding and deleting candidates, where one asks whether a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding or deleting few candidates, as well as a combinatorial scenario where adding/deleting a candidate automatically means adding or deleting a whole group of candidates. Considering several fundamental voting rules, our results show that the parameterized complexity of candidate control, with the number of voters as the parameter, is much more varied than in the setting with many voters.

IJCAI Conference 2017 Conference Paper

Multiwinner Rules on Paths From k-Borda to Chamberlin–Courant

• Piotr Faliszewski
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

The classical multiwinner rules are designed for particular purposes. For example, variants of k-Borda are used to find k best competitors in judging contests while the Chamberlin-Courant rule is used to select a diverse set of k products. These rules represent two extremes of the multiwinner world. At times, however, one might need to find an appropriate trade-off between these two extremes. We explore continuous transitions from k-Borda to Chamberlin-Courant and study intermediate rules.

AAMAS Conference 2017 Conference Paper

Proportional Representation in Vote Streams

• Palash Dey
• Nimrod Talmon
• Otniel van Handel

We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respect to common multiwinner proportional representation voting rules; specifically, we consider the Approval-based and the Borda-based variants of both the Chamberlin– Courant rule and the Monroe rule. We complement our algorithms with lower bounds. Somewhat surprisingly, our results imply that, using space which does not depend on the number of voters it is possible to efficiently identify an approximate representative committee of fixed size over vote streams with huge number of voters. CCS Concepts •Computing methodologies → Multi-agent systems; •Theory of computation → Streaming, sublinear and near linear time algorithms;

AAMAS Conference 2017 Conference Paper

Structured Proportional Representation

• Nimrod Talmon

Multi-winner voting rules aiming at proportional representation, such as those suggested by Chamberlin and Courant [9] and by Monroe [20], partition an electorate into virtual districts, such that a representative is assigned to each district; these districts are formed based on the voters’ preferences. In some applications it is beneficial to require certain structural properties to be satisfied by these virtual districts. In this paper we consider situations where the voters are embedded in a network, and we require each virtual district to be connected (with respect to the network). We discuss applications of a corresponding combinatorial problem and study its computational complexity, identifying several variants and special cases which can be solved efficiently. CCS Concepts •Computing methodologies → Multi-agent systems; •Theory of computation → Problems, reductions and completeness;

AAAI Conference 2017 Conference Paper

Teams in Online Scheduling Polls: Game-Theoretic Aspects

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier
• Svetlana Obraztsova
• Nimrod Talmon

Consider an important meeting to be held in a team-based organization. Taking availability constraints into account, an online scheduling poll is being used in order to decide upon the exact time of the meeting. Decisions are to be taken during the meeting, therefore each team would like to maximize its relative attendance (i. e. the proportional number of its team members attending the meeting). We introduce a corresponding game, where each team can declare a lower total availability in the scheduling poll in order to improve its relative attendance—the pay-off. We are especially interested in situations where teams can form coalitions. We provide an efficient algorithm that, given a coalition, finds an optimal way for each team in a coalition to improve its pay-off. In contrast, we show that deciding whether such a coalition exists is NP-hard. We also study the existence of Nash equilibria: Finding Nash equilibria for various small sizes of teams and coalitions can be done in polynomial time while it is coNP-hard if the coalition size is unbounded.

AAAI Conference 2017 Conference Paper

What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain

• Edith Elkind
• Piotr Faliszewski
• Jean-Francois Laslier
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

We visualize aggregate outputs of popular multiwinner voting rules—SNTV, STV, Bloc, k-Borda, Monroe, Chamberlin– Courant, and PAV—for elections generated according to the two-dimensional Euclidean model. We consider three applications of multiwinner voting, namely, parliamentary elections, portfolio/movie selection, and shortlisting, and use our results to understand which of our rules seem to be best suited for each application. In particular, we show that STV (one of the few nontrivial rules used in real high-stake elections) exhibits excellent performance, whereas the Bloc rule (also often used in practice) performs poorly.

AAMAS Conference 2016 Conference Paper

Achieving Fully Proportional Representation by Clustering Voters

• Piotr Faliszewski
• Arkadii Slinko
• Kolja Stahl
• Nimrod Talmon

Both the Chamberlin–Courant and Monroe rules are voting rules solving the problem of so-called fully proportional representation: they select committees whose members represent the voters so that voters’ satisfaction with their assigned representatives is maximized. These rules suffer from a common disadvantage, being that it is computationally intractable to compute the winning committee exactly. As both of these rules, explicitly or implicitly, partition voters, they can be seen as clustering the voters so that the voters in each group share the same representative. This suggests studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. We develop several algorithms based on clustering the voters and analyze their performance experimentally. General Terms Algorithms, Experimentation

IJCAI Conference 2016 Conference Paper

Committee Scoring Rules: Axiomatic Classification and Hierarchy

• Piotr Faliszewski
• Piotr Skowron
• Arkadii Slinko
• Nimrod Talmon

We consider several natural classes of committee scoring rules, namely, weakly separable, representation-focused, top-k-counting, OWA-based, and decomposable rules. We study some of their axiomatic properties, especially properties of monotonicity, and concentrate on containment relations between them. We characterize SNTV, Bloc, and k-approval Chamberlin-Courant, as the only rules in certain intersections of these classes. We introduce decomposable rules, describe some of their applications, and show that the class of decomposable rules strictly contains the class of OWA-based rules.

AAAI Conference 2016 Conference Paper

Complexity of Shift Bribery in Committee Elections

• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the (parameterized) complexity of SHIFT BRIBERY for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin–Courant rules, as well as on approximate variants of the Chamberlin–Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be significantly harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin–Courant rule sometimes affects the complexity of SHIFT BRIBERY.

JAIR Journal 2016 Journal Article

Large-Scale Election Campaigns: Combinatorial Shift Bribery

• Robert Bredereck
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the set of candidates and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable; specifically, NP-hard, hard in the parameterized sense, and hard to approximate. Nevertheless, we provide parameterized algorithms and approximation algorithms for natural restricted cases.

AAAI Conference 2016 Conference Paper

Multiwinner Analogues of the Plurality Rule: Axiomatic and Algorithmic Perspectives

• Piotr Faliszewski
• Piot Skowron
• Arkadii Slinko
• Nimrod Talmon

We characterize the class of committee scoring rules that satisfy the fixed-majority criterion. In some sense, the committee scoring rules in this class are multiwinner analogues of the single-winner Plurality rule, which is uniquely characterized as the only single-winner scoring rule that satisfies the simple majority criterion. We find that, for most of the rules in our new class, the complexity of winner determination is high (i. e. , the problem of computing the winners is NP-hard), but we also show some examples of polynomial-time winner determination procedures, exact and approximate.

IJCAI Conference 2016 Conference Paper

Voting-Based Group Formation

• Piotr Faliszewski
• Arkadii Slinko
• Nimrod Talmon

We study a combinatorial problem formulated in terms of the following group-formation scenario. Given some agents, where each agent has preferences over the set of potential group leaders, the task is to partition the agents into groups and assign a group leader to each of them, so that the group leaders have as high support as possible from the groups they are assigned to lead. We model this scenario as a voting problem, where the goal is to partition a set of voters into a prescribed number of groups so that each group elects its leader, i. e. , their leader is a unique winner in the corresponding election. We study the computational complexity of this problem (and several of its variants) for Approval elections.

TCS Journal 2015 Journal Article

Combinatorial voter control in elections

• Laurent Bulteau
• Jiehua Chen
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

Voter control problems model situations such as an external agent trying to affect the result of an election by adding voters, for example by convincing some voters to vote who would otherwise not attend the election. Traditionally, voters are added one at a time, with the goal of making a distinguished alternative win by adding a minimum number of voters. In this paper, we initiate the study of combinatorial variants of control by adding voters. In our setting, when we choose to add a voter v, we also have to add a whole bundle κ ( v ) of voters associated with v. We study the computational complexity of this problem for two of the most basic voting rules, namely the Plurality rule and the Condorcet rule.

AAAI Conference 2015 Conference Paper

Elections with Few Voters: Candidate Control Can Be Easy

• Jiehua Chen
• Piotr Faliszewski
• Rolf Niedermeier
• Nimrod Talmon

We study the computational complexity of candidate control in elections with few voters (that is, we take the number of voters as a parameter). We consider both the standard scenario of adding and deleting candidates, where one asks if a given candidate can become a winner (or, in the destructive case, can be precluded from winning) by adding/deleting some candidates, and a combinatorial scenario where adding/deleting a candidate automatically means adding/deleting a whole group of candidates. Our results show that the parameterized complexity of candidate control (with the number of voters as the parameter) is much more varied than in the setting with many voters.

TCS Journal 2015 Journal Article

The complexity of degree anonymization by vertex addition

• Robert Bredereck
• Vincent Froese
• Sepp Hartung
• André Nichterlein
• Rolf Niedermeier
• Nimrod Talmon

Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results.