Andrzej Kaczmarczyk

AAAI Conference 2026 Conference Paper

Putting Fair Division on the Map

• Paula Böhm
• Robert Bredereck
• Paul Gölz
• Andrzej Kaczmarczyk
• Stanisław Szufa

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 platforms. Little is known, however, about the characteristics of real-world allocation instances and how they compare to synthetic instances. Using dimensionality reduction, we compute a map of allocation instances: a 2-dimensional embedding such that an instance's location on the map is predictive of the instance's origin and other key instance features. Because the axes of this map closely align with the utility matrix's two largest singular values, we define a second, explicit map, which we theoretically characterize.

AAMAS Conference 2025 Conference Paper

Computing Efficient Envy-Free Partial Allocations of Indivisible Goods

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Bin Sun

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 this is not true when one additionally requires some efficiency concept (e. g. , completeness, Pareto-efficiency, or social welfare maximization). In fact, in such case even deciding the existence of an efficient envy-free allocation is notoriously computationally hard. In this paper, we explore the limits of efficient computability by relaxing standard efficiency concepts and analyzing how this impacts the computational complexity of the respective problems. Specifically, we allow partial allocations (where not all goods are allocated) and impose only very mild efficiency constraints, such as ensuring each agent receives a bundle with positive utility. Surprisingly, even such seemingly weak efficiency requirements lead to a diverse computational complexity landscape. We identify several polynomial-time solvable or fixed-parameter tractable cases for binary utilities, yet we also find NP-hardness in very restricted scenarios involving ternary utilities.

IJCAI Conference 2025 Conference Paper

Efficient Algorithms for Electing Successive Committees

• Pallavi Jain
• Andrzej Kaczmarczyk

In a recently introduced model of successive committee elections, for a given set of ordinal or approval preferences one aims to find a sequence of a given length of “best” same-size committees such that each candidate is a member of a limited number of consecutive committees. However, the practical usability of this model remains limited, as the described task turns out to be NP-hard for most selection criteria already for seeking committees of size three. Non-trivial or somewhat efficient algorithms for these cases are lacking too. Motivated by a desire to unlock the full potential of the described temporal model of committee elections, we devise (parameterized) algorithms that effectively solve the mentioned hard cases in realistic scenarios of a moderate number of candidates or of a limited time horizon.

AAMAS Conference 2025 Conference Paper

Learning Real-Life Approval Elections

• Piotr Faliszewski
• Lukasz Janeczko
• Andrzej Kaczmarczyk
• Marcin Kurdziel
• Grzegorz Pierczynski
• Stanislaw Szufa

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.

NeurIPS Conference 2025 Conference Paper

Strategic Cost Selection in Participatory Budgeting

• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Piotr Skowron
• Stanisław Szufa
• Mateusz Szwagierczak

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 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 (NE) in such games, focusing on the AV/Cost, Phragmen, and Method of Equal Shares rules. We also provide an experimental study of cost selection on real-life PB election data.

IJCAI Conference 2024 Conference Paper

Guide to Numerical Experiments on Elections in Computational Social Choice

• Niclas Boehmer
• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Grzegorz Pierczyński
• Simon Rey
• Dariusz Stolicki

We analyze how numerical experiments regarding elections were conducted within computational social choice literature (focusing on papers published in the IJCAI, AAAI, and AAMAS conferences). We analyze the sizes of the studied elections and the methods of generating preference data, thereby making previously hidden standards and practices explicit. In particular, we survey a number of statistical cultures for generating elections and their commonly used parameters.

IJCAI Conference 2024 Conference Paper

Selecting the Most Conflicting Pair of Candidates

• Théo Delemazure
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Stanisław Szufa

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. By proposing basic axioms to capture this objective, we show that none of the prominent multiwinner voting rules meet them. Consequently, we design committee voting rules 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.

AAMAS Conference 2024 Conference Paper

Strategic Cost Selection in Participatory Budgeting

• Piotr Faliszewski
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Grzegorz Lisowski
• Piotr Skowron
• Stanisław Szufa

We study strategic behavior of project proposers in the context of participatory budgeting. We assume 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 Nash equilibria in such games. Furthermore, we report an experimental study of the games we propose.

AAMAS Conference 2023 Conference Paper

Bribery Can Get Harder in Structured Multiwinner Approval Election

• Bartosz Kusek
• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Dušan Knop

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.

IJCAI Conference 2023 Conference Paper

Diversity, Agreement, and Polarization in Elections

• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Krzysztof Sornat
• Stanisław Szufa
• Tomasz Wąs

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 offers good measures of agreement between the voters, such measures for the other two notions are lacking. We attempt to rectify this issue by designing appropriate measures, providing means of their (approximate) computation, and arguing that they, indeed, capture diversity and polarization well. In particular, we present "maps of preference orders" that highlight relations between the votes in a given election and which help in making arguments about their nature.

JAIR Journal 2023 Journal Article

Improving Resource Allocations by Sharing in Pairs

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Rolf Niedermeier
• Florian Sachse

Given an initial resource allocation, where some agents may envy others or where a different distribution of resources might lead to a higher social welfare, our goal is to improve the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. More precisely, our model allows agents to form pairs which then may share a limited number of resources. Sharing a resource can come at some costs or loss in utility. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and tree-like (hierarchical) social networks.

AAAI Conference 2023 Conference Paper

Properties of Position Matrices and Their Elections

• Niclas Boehmer
• Jin-Yi Cai
• Piotr Faliszewski
• Austen Z. Fan
• Łukasz Janeczko
• Andrzej Kaczmarczyk
• Tomasz Wąs

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). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.

AIJ Journal 2022 Journal Article

Envy-free allocations respecting social networks

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

AAAI Conference 2022 Conference Paper

On Improving Resource Allocations by Sharing

• Robert Bredereck
• Andrzej Kaczmarczyk
• Junjie Luo
• Rolf Niedermeier
• Florian Sachse

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 the allocation without reassigning resources. We consider a sharing concept allowing resources being shared with social network neighbors of the resource owners. To this end, we introduce a formal model that allows a central authority to compute an optimal sharing between neighbors based on an initial allocation. Advocating this point of view, we focus on the most basic scenario where a resource may be shared by two neighbors in a social network and each agent can participate in a bounded number of sharings. We present algorithms for optimizing utilitarian and egalitarian social welfare of allocations and for reducing the number of envious agents. In particular, we examine the computational complexity with respect to several natural parameters. Furthermore, we study cases with restricted social network structures and, among others, devise polynomial-time algorithms in path- and treelike (hierarchical) social networks.

IJCAI Conference 2022 Conference Paper

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 two time-dependent multistage models based on simple scoring-based voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be "easier" than being conservative.

AAAI Conference 2021 Conference Paper

A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem

• Matthias Bentert
• Robert Bredereck
• Péter Györgyi
• Andrzej Kaczmarczyk
• Rolf Niedermeier

The NP-hard MATERIAL CONSUMPTION SCHEDULING PROBLEM and related problems have been thoroughly studied since the 1980’s. Roughly speaking, the problem deals with minimizing the makespan when scheduling jobs that consume non-renewable resources. We focus on the singlemachine case without preemption: from time to time, the resources of the machine are (partially) replenished, thus allowing for meeting a necessary pre-condition for processing further jobs, each of which having individual resource demands. We initiate a systematic exploration of the parameterized computational complexity landscape of the problem, providing parameterized tractability as well as intractability results. Doing so, we mainly investigate how parameters related to the resource supplies influence the computational complexity. Thereby, we get a deepened understanding of this fundamental scheduling problem.

AAMAS Conference 2021 Conference Paper

High-Multiplicity Fair Allocation Made More Practical

• Robert Bredereck
• Aleksander Figiel
• Andrzej Kaczmarczyk
• Dušan Knop
• Rolf Niedermeier

The envy-free, Pareto-efficient allocation of indivisible goods leads to computationally hard problems. There is a big variety of modeling issues, such as agent-specific utility functions or (high numbers of) different types of goods. In recent work, Bredereck et al. [ACM EC 2019] addressed this topic by showing (theoretical) fixed-parameter tractability results for “high-multiplicity fair allocation”, exploiting parameters such as number of agents or maximum absolute utility values. To this end, they used a number of tools from (theoretical) integer linear programming. We “engineer” their work towards practical usefulness, thereby being able to solve all realworld instances from the state-of-art online platform “spliddit. org for provably fair solutions”. Besides providing the foundations for a fast tool for fair allocations, we also offer a flexible framework with the possibility to relax fairness or efficiency demands so to, e. g. , allow tradeoffs between fairness and social welfare. Moreover, our framework provides ways to interpret and explain “solution paths” which makes it possible to perform further explorations in cases when no envy-free and efficient allocations exist.

JAAMAS Journal 2021 Journal Article

On coalitional manipulation for multiwinner elections: shortlisting

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

Abstract 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 of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario, \(\ell \) -Bloc (every voter approves \(\ell \) candidates). In particular, we investigate the influence of several different group evaluation functions (e. g. , egalitarian versus utilitarian) and tie-breaking mechanisms modeling pessimistic and optimistic manipulators. Among other things, we conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we provide a fairly comprehensive picture of the computational complexity landscape of this scenario.

AIJ Journal 2021 Journal Article

Robustness among multiwinner voting rules

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

AAAI Conference 2020 Conference Paper

Electing Successive Committees: Complexity and Algorithms

• Robert Bredereck
• Andrzej Kaczmarczyk
• Rolf Niedermeier

We introduce successive committees elections. The point is that our new model additionally takes into account that “committee members” shall have a short term of office possibly over a consecutive time period (e. g. , to limit the influence of elitist power cartels or to keep the social costs of overloading committees as small as possible) but at the same time overly frequent elections are to be avoided (e. g. , for the sake of long-term planning). Thus, given voter preferences over a set of candidates, a desired committee size, a number of committees to be elected, and an upper bound on the number of committees that each candidate can participate in, the goal is to find a “best possible” series of committees representing the electorate. We show a sharp complexity dichotomy between computing series of committees of size at most two (mostly in polynomial time) and of committees of size at least three (mostly NP-hard). Depending on the voting rule, however, even for larger committee sizes we can spot some tractable cases.

AAAI Conference 2020 Conference Paper

Parameterized Algorithms for Finding a Collective Set of Items

• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Dušan Knop
• Rolf Niedermeier

We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.

IJCAI Conference 2020 Conference Paper

Strategic Campaign Management in Apportionment Elections

• Robert Bredereck
• Piotr Faliszewski
• Michal Furdyna
• Andrzej Kaczmarczyk
• Martin Lackner

In parliamentary elections, parties compete for a limited, typically fixed number of seats. We study the complexity of the following bribery-style problem: Given the distribution of votes among the parties, what is the smallest number of voters that need to be convinced to vote for our party, so that it gets a desired number of seats. We also run extensive experiments on real-world election data and measure the effectiveness of our method.

JAAMAS Journal 2019 Journal Article

Algorithms for destructive shift bribery

• Andrzej Kaczmarczyk
• Piotr Faliszewski

Abstract 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 best to the worst), a despised candidate d, a budget B, and prices for shifting d back in the voters’ rankings. The goal is to ensure that d is not a winner of the election. We show that this problem is polynomial-time solvable for scoring protocols (encoded in unary), the Bucklin and Simplified Bucklin rules, and the Maximin rule, but is \(\mathrm {NP}\) -hard for the Copeland rule. This stands in contrast to the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for k -Approval family of rules, but is \(\mathrm {NP}\) -hard for the Borda, Copeland, and Maximin rules. We complement the analysis of the Copeland rule showing \(\mathrm {W}\) -hardness for the parameterization by the budget value, and by the number of affected voters. We prove that the problem is \(\mathrm {W}\) -hard when parameterized by the number of voters even for unit prices. From the positive perspective we provide an efficient algorithm for solving the problem parameterized by the combined parameter the number of candidates and the maximum bribery price (alternatively the number of different bribery prices).

IJCAI Conference 2019 Conference Paper

An Experimental View on Committees Providing Justified Representation

• Robert Bredereck
• Piotr Faliszewski
• Andrzej Kaczmarczyk
• Rolf Niedermeier

We provide an experimental study of committees that achieve (proportional/extended) justified representation (JR/PJR/EJR). In particular, we ask how many such committees exist and how varied they are in terms of voter satisfaction and coverage. We find that under many natural distributions of preferences a large fraction of randomly selected JR committees also provide PJR and EJR. Further, we find that the sets of JR committees for our elections are very varied and include both high-quality ones and not-so-appealing ones.

AAMAS Conference 2018 Conference Paper

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 finding them can be a computationally hard task. Classic envy-freeness requires that every agent likes the resources allocated to it at least as much as the resources allocated to any other agent. In many situations this assumption can be relaxed since agents often do not even know each other. We enrich the envy-freeness concept by taking into account (directed) social networks of the agents. Thus, we require that every agent likes its own allocation at least as much as those of all its (out)neighbors. This leads to a “more local” concept of envyfreeness. We also consider a strong variant where every agent must like its own allocation more than those of all its (out)neighbors. We analyze the classic and the parameterized complexity of finding allocations that are envy-free with respect to one of the variants of our new concept, and that either are complete, are Paretoefficient, or optimize the utilitarian social welfare. To this end, we study different restrictions of the agents’ preferences and of the social network structure. We identify cases that become easier (from ΣP 2-hard or NP-hard to P) and cases that become harder (from P to NP-hard) when comparing classic envy-freeness with our graphbased envy-freeness. Furthermore, we spot cases where graph envyfreeness is easier to decide than strong graph envy-freeness, and vice versa.

IJCAI Conference 2017 Conference Paper

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 of strategic voting for shortlisting based on the most natural and simple voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several tie-breaking mechanisms (e. g. pessimistic versus optimistic) and group evaluation functions (e. g. egalitarian versus utilitarian) and conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. We provide a fairly comprehensive picture of the computational complexity landscape of this neglected scenario.

AAMAS Conference 2016 Conference Paper

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 (ranking the candidates from best to worst, each), a despised candidate d (typically, one of the current winners), a budget B, and prices for shifting d down in voters’ rankings. The goal is to ensure that d is not a winner of the election. We show that this problem is polynomial-time solvable for all scoring protocols (encoded in unary) and the Maximin rule, but is NP-hard for the Copeland rule. This contrasts with the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for k-Approval family of rules, but is NP-hard for the Borda, Copeland, and Maximin rules.