13 citations · 17 across the 15 of their papers we have counts for
22 papers
Learning Real-Life Approval Elections
Piotr Faliszewski, Łukasz Janeczko, Andrzej Kaczmarczyk +3
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 mo…
How to Tamper with a Parliament: Strategic Campaigns in Apportionment Elections
Robert Bredereck, Piotr Faliszewski, Michał Furdyna +6
In parliamentary elections, parties compete for a limited, typically fixed number of seats. Most parliaments are assembled using apportionment methods that distribute the seats bas…
Project Submission Games in Participatory Budgeting
Piotr Faliszewski, Łukasz Janeczko, Andrzej Kaczmarczyk +2
We introduce the framework of project submission games, capturing the behavior of project proposers in participatory budgeting (and multiwinner elections). Here, each proposer subm…
Efficient Algorithms for Electing Successive Committees
Pallavi Jain, Andrzej Kaczmarczyk
In a recently introduced model of successive committee elections (Bredereck et al., AAAI-20) for a given set of ordinal or approval preferences one aims to find a sequence of a giv…
Putting Fair Division on the Map
Paula Böhm, Robert Bredereck, Paul Gölz +2
The fair division of indivisible goods is not only a subject of theoretical research, but also an important problem in practice, with solutions being offered on several online plat…
Computing Efficient Envy-Free Partial Allocations of Indivisible Goods
Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo +1
Envy-freeness is one of the most prominent fairness concepts in the allocation of indivisible goods. Even though trivial envy-free allocations always exist, rich literature shows t…
Strategic Cost Selection in Participatory Budgeting
Piotr Faliszewski, Łukasz Janeczko, Andrzej Kaczmarczyk +3
We study strategic behavior of project proposers in the context of approval-based participatory budgeting (PB). In our model we assume that the votes are fixed and known and the pr…
Selecting the Most Conflicting Pair of Candidates
Théo Delemazure, Łukasz Janeczko, Andrzej Kaczmarczyk +1
We study committee elections from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per voter preferences.…
Guide to Numerical Experiments on Elections in Computational Social Choice
Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko +7
We analyze how numerical experiments regarding elections were conducted within the computational social choice literature (focusing on papers published in the IJCAI, AAAI, and AAMA…
Diversity, Agreement, and Polarization in Elections
Piotr Faliszewski, Andrzej Kaczmarczyk, Krzysztof Sornat +2
We consider the notions of agreement, diversity, and polarization in ordinal elections (that is, in elections where voters rank the candidates). While (computational) social choice…
Robustness of Participatory Budgeting Outcomes: Complexity and Experiments
Niclas Boehmer, Piotr Faliszewski, Łukasz Janeczko +1
We study the robustness of approval-based participatory budgeting (PB) rules to random noise in the votes. Our contributions are twofold. First, we study the computational complexi…
Properties of Position Matrices and Their Elections
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski +4
We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix).…
Bribery Can Get Harder in Structured Multiwinner Approval Election
Bartosz Kusek, Robert Bredereck, Piotr Faliszewski +2
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…
On Improving Resource Allocations by Sharing
Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo +2
Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to higher social welfare, our goal is to improve t…
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
Matthias Bentert, Robert Bredereck, Péter Györgyi +2
The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related problems have been thoroughly studied since the 1980's. Roughly speaking, the problem deals with minimizing…
Envy-Free Allocations Respecting Social Networks
Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier
Finding an envy-free allocation of indivisible resources to agents is a central task in many multiagent systems. Often, non-trivial envy-free allocations do not exist, and, when th…
Line-Up Elections: Parallel Voting with Shared Candidate Pool
Niclas Boehmer, Robert Bredereck, Piotr Faliszewski +2
We introduce the model of line-up elections which captures parallel or sequential single-winner elections with a shared candidate pool. The goal of a line-up election is to find a…
High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
Robert Bredereck, Andrzej Kaczmarczyk, Dušan Knop +1
Using insights from parametric integer linear programming, we significantly improve on our previous work [Proc. ACM EC 2019] on high-multiplicity fair allocation. Therein, answerin…
When Votes Change and Committees Should (Not)
Robert Bredereck, Till Fluschnik, Andrzej Kaczmarczyk
Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce and study two time-depen…
Algorithms for Destructive Shift Bribery
Andrzej Kaczmarczyk, Piotr Faliszewski
We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (each ranking the candidates from the b…
On Coalitional Manipulation for Multiwinner Elections: Shortlisting
Robert Bredereck, Andrzej Kaczmarczyk, Rolf Niedermeier
Shortlisting of candidates--selecting a group of "best" candidates--is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity…
Robustness Among Multiwinner Voting Rules
Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk +3
We investigate how robust the results of committee elections are to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules…