Arrow Research search

Author name cluster

Piotr Skowron

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

51 papers
1 author row

Possible papers

51

AIJ Journal 2026 Journal Article

Proportional justified representation

  • Luis Sánchez-Fernández
  • Edith Elkind
  • Martin Lackner
  • Norberto Fernández García
  • Jesús A. Fisteus
  • Pablo Basanta Val
  • Piotr Skowron

The goal of multi-winner elections is to choose a fixed-size committee based on voters' preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. In an influential paper, Aziz et al. proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). We observe that EJR is incompatible with the highly desirable Perfect Representation (PR) criterion, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with PR, as well as with a stronger variant of this axiom, which we term Fractional Perfect Representation (FPR). Moreover, just like EJR, PJR can be used to characterise the classic Proportional Approval Voting (PAV) rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.

Details DOI

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.

Details DOI

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.

PDF Details

IJCAI Conference 2024 Conference Paper

Evaluation of Project Performance in Participatory Budgeting

  • Niclas Boehmer
  • Piotr Faliszewski
  • Łukasz Janeczko
  • Dominik Peters
  • Grzegorz Pierczyński
  • Šimon Schierreich
  • Piotr Skowron
  • Stanisław Szufa

We study ways of evaluating the performance of losing projects in participatory budgeting (PB) elections by seeking actions that would make them win. We focus on lowering their costs, obtaining additional approvals, and removing approvals for competing projects: The larger a change is needed, the less successful is the given project. We seek efficient algorithms for computing our measures and we analyze them experimentally, focusing on GreedyAV, Phragmen, and Equal-Shares PB rules.

PDF Details DOI

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.

PDF

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.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Online Approval Committee Elections

  • Virginie Do
  • Matthieu Hervouin
  • Jérôme Lang
  • Piotr Skowron

Assume k candidates need to be selected. The candidates appear over time. Each time one appears, it must be immediately selected or rejected---a decision that is made by a group of individuals through voting. Assume the voters use approval ballots, i. e. , for each candidate they only specify whether they consider it acceptable or not. This setting can be seen as a voting variant of choosing k secretaries. Our contribution is twofold. (1) We assess to what extent the committees that are computed online can proportionally represent the voters. (2) If a prior probability over candidate approvals is available, we show how to compute committees with maximal expected score.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Phragmén Rules for Degressive and Regressive Proportionality

  • Michał Jaworski
  • Piotr Skowron

We study two concepts of proportionality in the model of approval-based committee elections. In degressive proportionality small minorities of voters are favored in comparison with the standard linear proportionality. Regressive proportionality, on the other hand, requires that larger subdivisions of voters are privileged. We introduce a new family of rules that broadly generalize Phragmén's Sequential Rule spanning the spectrum between degressive and regressive proportionality. We analyze and compare the two principles of proportionality assuming the voters and the candidates can be represented as points in an Euclidean issue space.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Proportional Public Decisions

  • Piotr Skowron
  • Adrian Górecki

We consider a setting where a group of individuals make a number of independent decisions. The decisions should proportionally represent the views of the voters. We formulate new criteria of proportionality and analyse two rules, Proportional Approval Voting and the Metod of Equal Shares, inspired by the corresponding committee election rules. We prove that the two rules provide very strong proportionality guarantees when applied to the setting of public decisions.

PDF Details

AAAI Conference 2021 Conference Paper

Aggregating Binary Judgments Ranked by Accuracy

  • Daniel Halpern
  • Gregory Kehne
  • Dominik Peters
  • Ariel D. Procaccia
  • Nisarg Shah
  • Piotr Skowron

We revisit the fundamental problem of predicting a binary ground truth based on independent binary judgments provided by experts. When the accuracy levels of the experts are known, the problem can be solved easily through maximum likelihood estimation. We consider, however, a setting in which we are given only a ranking of the experts by their accuracy. Motivated by the worst-case approach to handle the missing information, we consider three objective functions and design efficient algorithms for optimizing them. In particular, the recently popular distortion objective leads to an intuitive new rule. We show that our algorithms perform well empirically using real and synthetic data in collaborative filtering and political prediction domains.

PDF Details

AAAI Conference 2021 Conference Paper

An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections

  • Michał T. Godziszewski
  • Paweł Batko
  • Piotr Skowron
  • Piotr Faliszewski

We study approval-based committee elections for the case where the voters’ preferences come from a 2D-Euclidean model. We consider two main issues: First, we ask for the complexity of computing election results. Second, we evaluate election outcomes experimentally, following the visualization technique of Elkind et al. (2017). Regarding the first issue, we find that many NP-hard rules remain intractable for 2D-Euclidean elections. For the second one, we observe that the behavior and nature of many rules strongly depend on the exact protocol for choosing the approved candidates.

PDF Details

AAAI Conference 2021 Conference Paper

Market-Based Explanations of Collective Decisions

  • Dominik Peters
  • Grzegorz Pierczyński
  • Nisarg Shah
  • Piotr Skowron

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

PDF Details

NeurIPS Conference 2021 Conference Paper

Proportional Participatory Budgeting with Additive Utilities

  • Dominik Peters
  • Grzegorz Pierczyński
  • Piotr Skowron

We study voting rules for participatory budgeting, where a group of voters collectively decides which projects should be funded using a common budget. We allow the projects to have arbitrary costs, and the voters to have arbitrary additive valuations over the projects. We formulate two axioms that guarantee proportional representation to groups of voters with common interests. To the best of our knowledge, all known rules for participatory budgeting do not satisfy either of the two axioms; in addition we show that the most prominent proportional rule for committee elections, Proportional Approval Voting, cannot be adapted to arbitrary costs nor to additive valuations so that it would satisfy our axioms of proportionality. We construct a simple and attractive voting rule that satisfies one of our axioms (for arbitrary costs and arbitrary additive valuations), and that can be evaluated in polynomial time. We prove that our other stronger axiom is also satisfiable, though by a computationally more expensive and less natural voting rule.

PDF Details

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.

Details DOI

AAAI Conference 2020 Conference Paper

Comparing Election Methods Where Each Voter Ranks Only Few Candidates

  • Matthias Bentert
  • Piotr Skowron

Election rules are formal processes that aggregate voters’ preferences, typically to select a single winning candidate. Most of the election rules studied in the literature require the voters to rank the candidates from the most to the least preferred one. This method of eliciting preferences is impractical when the number of candidates to be ranked is large. We ask how well certain election rules (focusing on positional scoring rules and the Minimax rule) can be approximated from partial preferences collected through one of the following procedures: (i) randomized—we ask each voter to rank a random subset of candidates, and (ii) deterministic—we ask each voter to provide a ranking of her most preferred candidates (the -truncated ballot). We establish theoretical bounds on the approximation ratios and complement our theoretical analysis with computer simulations. We find that it is usually better to use the randomized approach.

PDF Details

IJCAI Conference 2020 Conference Paper

Evaluating Committees for Representative Democracies: the Distortion and Beyond

  • Michał Jaworski
  • Piotr Skowron

We study a model where a group of representatives is elected to make a series of decisions on behalf of voters. The quality of such a representative committee is judged based on the extent to which the decisions it makes are consistent with the voters' preferences. We assume the set of issues on which the committee will make the decisions is unknown---a committee is elected based on the preferences of the voters over the candidates, which only reflect how similar are the preferences of the voters and candidates regarding the issues. In this model we theoretically and experimentally assess qualities of various multiwinner election rules.

PDF Details DOI

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.

Details DOI

AAAI Conference 2020 Conference Paper

Price of Fairness in Budget Division and Probabilistic Social Choice

  • Marcin Michorzewski
  • Dominik Peters
  • Piotr Skowron

A group of agents needs to divide a divisible common resource (such as a monetary budget) among several uses or projects. We assume that agents have approval preferences over projects, and their utility is the fraction of the budget spent on approved projects. If we maximize utilitarian social welfare, the entire budget will be spent on a single popular project, even if a substantial fraction of the agents disapprove it. This violates the individual fair share axiom (IFS) which requires that for each agent, at least 1/n of the budget is spent on approved projects. We study the price of imposing such fairness axioms on utilitarian social welfare. We show that no division rule satisfying IFS can guarantee to achieve more than an O(1/ √ m) fraction of maximum utilitarian welfare, in the worst case. However, imposing stronger group fairness conditions (such as the core) does not come with an increased price, since both the conditional utilitarian rule and the Nash rule match this bound and guarantee an Ω(1/ √ m) fraction. The same guarantee is attained by the rule under which the spending on a project is proportional to its approval score. We also study a family of rules interpolating between the utilitarian and the Nash rule, quantifying a trade-off between welfare and group fairness. An experimental analysis by sampling using several probabilistic models shows that the conditional utilitarian rule achieves very high welfare on average.

PDF Details

AIJ Journal 2020 Journal Article

Utilitarian welfare and representation guarantees of approval-based multiwinner rules

  • Martin Lackner
  • Piotr Skowron

To choose a suitable multiwinner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an “optimal” subset of alternatives. In this paper, we provide a quantitative analysis of multiwinner voting rules using methods from the theory of approximation algorithms—we estimate how well multiwinner rules approximate two extreme objectives: a representation criterion defined via the Approval Chamberlin–Courant rule and a utilitarian criterion defined via Multiwinner Approval Voting. With both theoretical and experimental methods, we classify multiwinner rules in terms of their quantitative alignment with these two opposing objectives. Our results provide fundamental information about the nature of multiwinner rules and, in particular, about the necessary tradeoffs when choosing such a rule.

Details DOI

IJCAI Conference 2019 Conference Paper

A Quantitative Analysis of Multi-Winner Rules

  • Martin Lackner
  • Piotr Skowron

To choose a suitable multi-winner voting rule is a hard and ambiguous task. Depending on the context, it varies widely what constitutes the choice of an "optimal" subset. In this paper, we offer a new perspective on measuring the quality of such subsets and---consequently---of multi-winner rules. We provide a quantitative analysis using methods from the theory of approximation algorithms and estimate how well multi-winner rules approximate two extreme objectives: diversity as captured by the Approval Chamberlin--Courant rule and individual excellence as captured by Multi-winner Approval Voting. With both theoretical and experimental methods we classify multi-winner rules in terms of their quantitative alignment with these two opposing objectives.

PDF Details

IJCAI Conference 2019 Conference Paper

Approval-Based Elections and Distortion of Voting Rules

  • Grzegorz Pierczyński
  • Piotr Skowron

We consider elections where both voters and candidates can be associated with points in a metric space and voters prefer candidates that are closer to those that are farther away. It is often assumed that the optimal candidate is the one that minimizes the total distance to the voters. Yet, the voting rules often do not have access to the metric space M and only see preference rankings induced by M. Consequently, they often are incapable of selecting the optimal candidate. The distortion of a voting rule measures the worst-case loss of the quality being the result of having access only to preference rankings. We extend the idea of distortion to approval-based preferences. First, we compute the distortion of Approval Voting. Second, we introduce the concept of acceptability-based distortion---the main idea behind is that the optimal candidate is the one that is acceptable to most voters. We determine acceptability-distortion for a number of rules, including Plurality, Borda, k-Approval, Veto, Copeland, Ranked Pairs, the Schulze's method, and STV.

PDF Details

AAAI Conference 2019 Conference Paper

Fair Knapsack

  • Till Fluschnik
  • Piotr Skowron
  • Mervin Triphaus
  • Kai Wilker

We study the following multiagent variant of the knapsack problem. We are given a set of items, a set of voters, and a value of the budget; each item is endowed with a cost and each voter assigns to each item a certain value. The goal is to select a subset of items with the total cost not exceeding the budget, in a way that is consistent with the voters’ preferences. Since the preferences of the voters over the items can vary significantly, we need a way of aggregating these preferences, in order to select the socially best valid knapsack. We study three approaches to aggregating voters’ preferences, which are motivated by the literature on multiwinner elections and fair allocation. This way we introduce the concepts of individually best, diverse, and fair knapsack. We study the computational complexity (including parameterized complexity, and complexity under restricted domains) of the aforementioned multiagent variants of knapsack.

PDF Details

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.

PDF Details

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.

PDF

IJCAI Conference 2018 Conference Paper

Approval-Based Multi-Winner Rules and Strategic Voting

  • Martin Lackner
  • Piotr Skowron

We investigate the possibility of strategic voting in approval-based multiwinner rules. In particular, we define three axiomatic properties that guarantee resilience to certain forms of strategic voting: independence of irrelevant alternatives (IIA), monotonicity, and SD-strategyproofness. In this paper, we systematically analyze multiwinner rules based on these axioms and provide a fine-grained picture of their resilience to strategic voting. Both our axiomatic and experimental analysis show that approval-based multiwinner rules are generally very susceptible to strategic voting---with one exception: multiwinner approval voting.

PDF Details

AIJ Journal 2018 Journal Article

Approximating optimal social choice under metric preferences

  • Elliot Anshelevich
  • Onkar Bhardwaj
  • Edith Elkind
  • John Postl
  • Piotr Skowron

We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are further away. In this setting, it is often desirable to select an alternative that minimizes the sum of distances to the voters, i. e. , the utilitarian social cost, or other similar measures of social cost. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify an optimal alternative. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of an alternative selected by the rule and that of an optimal alternative. Thus, distortion measures how good a voting rule is at approximating an alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that they form a metric space. The goal of our paper is to quantify the distortion of well-known voting rules. We first establish a lower bound on the distortion of any deterministic voting rule. We then show that the distortion of positional scoring rules cannot be bounded by a constant, and for several popular rules in this family distortion is linear in the number of alternatives. On the other hand, for Copeland and similar rules the distortion is bounded by a factor of 5. These results hold both for the sum of voters' cost and the median voter cost. For Single Transferable Vote (STV), we obtain an upper bound of O ( ln ⁡ m ) with respect to the sum of voters' costs, where m is the number of alternatives, as well as a lower bound of Ω ( ln ⁡ m ); thus, STV is a reasonable, though not a perfect rule from this perspective. Our results for median voter cost extend to more general objective functions.

Details DOI

AAMAS Conference 2018 Conference Paper

Collective Schedules: Scheduling Meets Computational Social Choice

  • Fanny Pascual
  • Krzysztof Rzadca
  • Piotr Skowron

When scheduling public works or events in a shared facility one needs to accommodate preferences of a population. We formalize this problem by introducing the notion of a collective schedule. We show how to extend fundamental tools from social choice theory—positional scoring rules, the Kemeny rule and the Condorcet principle—to collective scheduling. We study the computational complexity of finding collective schedules. We also experimentally demonstrate that optimal collective schedules can be found for instances with realistic sizes.

PDF

AIJ Journal 2018 Journal Article

Multi-attribute proportional representation

  • Jérôme Lang
  • Piotr Skowron

We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should have. We look for a set that fits as much as possible the desired distributions on all attributes. An example of application is the choice of members for a representative committee, where candidates are described by attributes such as gender, age and profession, and where we look for a committee that for each attribute offers a certain representation, i. e. , a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. Another example of application is the selection of a common set of items to be used by a group of users, where items are labelled by attribute values. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such a case the value of the single attribute would be a political affiliation of a candidate). We study the properties of the associated subset selection rules, as well as their computational complexity.

Details DOI

AAAI Conference 2018 Conference Paper

Multiwinner Elections With Diversity Constraints

  • Robert Bredereck
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Martin Lackner
  • Piotr Skowron

We develop a model of multiwinner elections that combines performance-based measures of the quality of the committee (such as, e. g. , Borda scores of the committee members) with diversity constraints. Specifically, we assume that the candidates have certain attributes (such as being a male or a female, being junior or senior, etc.) and the goal is to elect a committee that, on the one hand, has as high a score regarding a given performance measure, but that, on the other hand, meets certain requirements (e. g. , of the form “at least 30% of the committee members are junior candidates and at least 40% are females”). We analyze the computational complexity of computing winning committees in this model, obtaining polynomial-time algorithms (exact and approximate) and NPhardness results. We focus on several natural classes of voting rules and diversity constraints.

PDF Details

AAAI Conference 2018 Conference Paper

On the Complexity of Extended and Proportional Justified Representation

  • Haris Aziz
  • Edith Elkind
  • Shenwei Huang
  • Martin Lackner
  • Luis Sanchez-Fernandez
  • Piotr Skowron

We consider the problem of selecting a fixed-size committee based on approval ballots. It is desirable to have a committee in which all voters are fairly represented. Aziz et al. (2015a; 2017) proposed an axiom called extended justified representation (EJR), which aims to capture this intuition; subsequently, Sánchez-Fernández et al. (2017) proposed a weaker variant of this axiom called proportional justified representation (PJR). It was shown that it is coNP-complete to check whether a given committee provides EJR, and it was conjectured that it is hard to find a committee that provides EJR. In contrast, there are polynomial-time computable voting rules that output committees providing PJR, but the complexity of checking whether a given committee provides PJR was an open problem. In this paper, we answer open questions from prior work by showing that EJR and PJR have the same worst-case complexity: we provide two polynomial-time algorithms that output committees providing EJR, yet we show that it is coNP-complete to decide whether a given committee provides PJR. We complement the latter result by fixedparameter tractability results.

PDF Details

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.

PDF

JAIR Journal 2017 Journal Article

Chamberlin--Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time

  • Piotr Skowron
  • Piotr Faliszewski

We consider the problem of winner determination under Chamberlin--Courant's multiwinner voting rule with approval utilities. This problem is equivalent to the well-known NP-complete MaxCover problem and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1 - 1/e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.

PDF Details DOI

IS Journal 2017 Journal Article

Cooperation and Competition When Bidding for Complex Projects: Centralized and Decentralized Perspectives

  • Piotr Skowron
  • Krzysztof Rzadca
  • Anwitaman Datta

To successfully complete a complex project, agents (companies or individuals) must form a team with the required competencies and resources. A team can be formed either by the project issuer based on individual agents' offers (centralized formation) or by the agents themselves (decentralized formation) bidding for a project as a consortium. The authors investigate rational strategies for agents, propose concepts to characterize the stability of winning teams and study computational complexity of finding these concepts of stability.

Details DOI

I&C Journal 2017 Journal Article

FPT approximation schemes for maximizing submodular functions

  • Piotr Skowron

We investigate the existence of approximation algorithms for maximization of submodular functions, that run in a fixed parameter tractable (FPT) time. Given a non-decreasing submodular set function v: 2 X → R the goal is to select a subset S of K elements from X such that v ( S ) is maximized. We identify three properties of set functions, referred to as p-separability properties, and we argue that many real-life problems can be expressed as maximization of submodular, p-separable functions, with low values of the parameter p. We present FPT approximation schemes for the minimization and maximization variants of the problem, for several parameters that depend on characteristics of the optimized set function, such as p and K.

Details DOI

AAAI Conference 2017 Conference Paper

Multiwinner Approval Rules as Apportionment Methods

  • Markus Brill
  • Jean-Francois Laslier
  • Piotr Skowron

We establish a link between multiwinner elections and apportionment problems by showing how approval-based multiwinner election rules can be interpreted as methods of apportionment. We consider several multi-winner rules and observe that some, but not all, of them induce apportionment methods that are well established in the literature and in the actual practice of proportional representation. For instance, we show that Proportional Approval Voting induces the D’Hondt method and that Monroe’s rule induces the largest remainder method. We also consider properties of apportionment methods and exhibit multiwinner rules that induce apportionment methods satisfying these properties.

PDF Details

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.

PDF Details

AAAI Conference 2017 Conference Paper

Proportional Justified Representation

  • Luis S‡nchez-Fern‡ndez
  • Edith Elkind
  • Martin Lackner
  • Norberto Fern‡ndez
  • Jesœs Fisteus
  • Pablo Basanta Val
  • Piotr Skowron

The goal of multi-winner elections is to choose a fixed-size committee based on voters’ preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. Recently, Aziz et al. (2015a; 2017) proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). In this paper, we extend the work of Aziz et al. in several directions. First, we answer an open question of Aziz et al. , by showing that Reweighted Approval Voting satisfies JR for k = 3, 4, 5, but fails it for k ≥ 6. Second, we observe that EJR is incompatible with the Perfect Representation criterion, which is important for many applications of multi-winner voting, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with perfect representation, and a committee that provides PJR can be computed in polynomial time if the committee size divides the number of voters. Moreover, just like EJR, PJR can be used to characterize the classic PAV rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.

PDF Details

IJCAI Conference 2017 Conference Paper

Proportional Rankings

  • Piotr Skowron
  • Martin Lackner
  • Markus Brill
  • Dominik Peters
  • Edith Elkind

We extend the principle of proportional representation to rankings: given approval preferences, we aim to generate aggregate rankings so that cohesive groups of voters are represented proportionally in each initial segment of the ranking. Such rankings are desirable in situations where initial segments of different lengths may be relevant, e. g. , in recommender systems, for hiring decisions, or for the presentation of competing proposals on a liquid democracy platform. We define what it means for rankings to be proportional, provide bounds for well-known aggregation rules, and experimentally evaluate the performance of these rules.

PDF Details

AAAI Conference 2017 Conference Paper

Social Choice Under Metric Preferences: Scoring Rules and STV

  • Piotr Skowron
  • Edith Elkind

We consider voting under metric preferences: both voters and candidates are associated with points in a metric space, and each voter prefers candidates that are closer to her to ones that are further away. In this setting, it is often desirable to select a candidate that minimizes the sum of distances to the voters. However, common voting rules operate on voters’ preference rankings and therefore may be unable to identify the best candidate. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of a candidate selected by the rule and that of an optimal candidate. Anshelevich, Bhardwaj and Postl (2015) show that some popular rules such as Borda and Plurality do badly in this regard: their distortion scales linearly with the number of candidates. On the positive side, Anshelevich et al. identify a few voting rules whose distortion is bounded by a constant; however, these rules are rarely used in practice. In this paper, we analyze the distortion of two widely used (classes of) voting rules, namely, scoring rules and Single Transferable Vote (STV). We show that all scoring rules have super-constant distortion, answering a question that was left open by Anshelevich et al. ; however, we identify a scoring rule whose distortion is asymptotically better than that of Plurality and Borda. For STV, we obtain an upper bound of O(ln m), where m is the number of candidates, as well as a super-constant lower bound; thus, STV is a reasonable, though not a perfect rule from this perspective.

PDF Details

IJCAI Conference 2017 Conference Paper

The Condorcet Principle for Multiwinner Elections: From Shortlisting to Proportionality

  • Haris Aziz
  • Edith Elkind
  • Piotr Faliszewski
  • Martin Lackner
  • Piotr Skowron

We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein and is majoritarian in spirit. The second one, local stability, is introduced in this paper, and focuses on voter representation. The goal of this paper is to explore these two notions, their implications on restricted domains, and the computational complexity of rules that are consistent with them.

PDF Details

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.

PDF Details

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.

PDF Details

AAMAS Conference 2016 Conference Paper

Complexity of Finding Equilibria of Plurality Voting Under Structured Preferences

  • Edith Elkind
  • Evangelos Markakis
  • Svetlana Obraztsova
  • Piotr Skowron

We study the complexity of finding pure Nash equilibria in voting games over well-known restricted preference domains, such as the domains of single-peaked and single-crossing preferences. We focus on the Plurality rule, and, following the recent work of Elkind et al. [15], consider three popular tie-breaking rules (lexicographic, random-candidate, and random-voter) and two types of voters’ attitude: lazy voters, who prefer to abstain when their vote cannot affect the election outcome, and truth-biased voters, who prefer to vote truthfully in such cases. Elkind et al. [15] have shown that for most of these combinations of tie-breaking rules and voters’ attitudes finding a Nash equilibrium is NP-hard; in contrast, we demonstrate that in almost all cases this problem is tractable for preferences that are single-peaked or singlecrossing, under mild technical assumptions. General Terms Algorithms, Economics, Theory

PDF

AIJ Journal 2016 Journal Article

Finding a collective set of items: From proportional multirepresentation to group recommendation

  • Piotr Skowron
  • Piotr Faliszewski
  • Jérôme Lang

We consider the following problem: There is a set of items (e. g. , movies) and a group of agents (e. g. , passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i. e. , in our example we are to pick K movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

Details DOI

AAAI Conference 2016 Conference Paper

Multi-Attribute Proportional Representation

  • Jérôme Lang
  • Piotr Skowron

We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should fit. We look for a set that fits as much as possible the desired distributions on all attributes. Examples of applications include choosing members of a representative committee, where candidates are described by attributes such as sex, age and profession, and where we look for a committee that for each attribute offers a certain representation, i. e. , a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. With a single attribute the problem boils down to the apportionment problem for party-list proportional representation systems (in such case the value of the single attribute is the political affiliation of a candidate). We study some properties of the associated subset selection rules, and address their computation.

PDF Details

AIJ Journal 2015 Journal Article

Achieving fully proportional representation: Approximability results

  • Piotr Skowron
  • Piotr Faliszewski
  • Arkadii Slinko

We study the complexity of (approximate) winner determination under the Monroe and Chamberlin–Courant multiwinner voting rules, which determine the set of representatives by optimizing the total satisfaction or dissatisfaction of the voters with their representatives. The total (dis)satisfaction is calculated either as the sum of individual (dis)satisfactions in the utilitarian case or as the (dis)satisfaction of the worst off voter in the egalitarian case. We provide good approximation algorithms for the satisfaction-based utilitarian versions of the Monroe and Chamberlin–Courant rules, and inapproximability results for the dissatisfaction-based utilitarian versions of these rules and also for all egalitarian cases. Our algorithms are applicable and particularly appealing when voters submit truncated ballots. We provide experimental evaluation of the algorithms both on real-life preference-aggregation data and on synthetic preference data. These experiments show that our simple and fast algorithms can, in many cases, find near-perfect solutions.

Details DOI

AAAI Conference 2015 Conference Paper

Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation

  • Piotr Skowron
  • Piotr Faliszewski
  • Jerome Lang

We consider the following problem: There is a set of items (e. g. , movies) and a group of agents (e. g. , passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of K items that maximize the total derived utility of all the agents (i. e. , in our example we are to pick K movies that we put on the plane’s entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

PDF Details

AAAI Conference 2015 Conference Paper

Fully Proportional Representation with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time

  • Piotr Skowron
  • Piotr Faliszewski

We consider the problem of winner determination under Chamberlin–Courant’s multiwinner voting rule with approval utilities. This problem is equivalent to the wellknown NP-complete MaxCover problem (i. e. , a version of the SetCover problem where we aim to cover as many elements as possible) and, so, the best polynomial-time approximation algorithm for it has approximation ratio 1 − 1 e. We show exponential-time/FPT approximation algorithms that, on one hand, achieve arbitrarily good approximation ratios and, on the other hand, have running times much better than known exact algorithms. We focus on the cases where the voters have to approve of at most/at least a given number of candidates.

PDF Details

TCS Journal 2015 Journal Article

The complexity of fully proportional representation for single-crossing electorates

  • Piotr Skowron
  • Lan Yu
  • Piotr Faliszewski
  • Edith Elkind

We study the complexity of winner determination in single-crossing elections under two classic fully proportional representation rules—Chamberlin–Courant's rule and Monroe's rule. Winner determination for these rules is known to be NP-hard for unrestricted preferences. We show that for single-crossing preferences this problem admits a polynomial-time algorithm for Chamberlin–Courant's rule, but remains NP-hard for Monroe's rule. Our algorithm for Chamberlin–Courant's rule can be modified to work for elections with bounded single-crossing width. We then consider elections that are both single-peaked and single-crossing, and develop an efficient algorithm for the egalitarian variant of Monroe's rule for such elections. While Betzler et al. [3] have recently presented a polynomial-time algorithm for this rule under single-peaked preferences, our algorithm has considerably better worst-case running time than that of Betzler et al.

Details DOI

AAAI Conference 2014 Conference Paper

A Characterization of the Single-Peaked Single-Crossing Domain

  • Edith Elkind
  • Piotr Faliszewski
  • Piotr Skowron

We investigate elections that are simultaneously singlepeaked and single-crossing (SPSC). We show that the domain of 1-dimensional Euclidean elections (where voters and candidates are points on the real line, and each voter prefers the candidates that are close to her to the ones that are further away) is a proper subdomain of the SPSC domain, by constructing an election that is single-peaked and singlecrossing, but not 1-Euclidean. We then establish a connection between narcissistic elections (where each candidate is ranked first by at least one voter), single-peaked elections and single-crossing elections, by showing that an election is SPSC if and only if it can be obtained from a narcissistic singlecrossing election by deleting voters. We show two applications of our characterization.

PDF Details

IJCAI Conference 2013 Conference Paper

Fully Proportional Representation as Resource Allocation: Approximability Results

  • Piotr Skowron
  • Piotr Faliszewski
  • Arkadii Slinko

We study the complexity of (approximate) winner determination under Monroe’s and Chamberlin- Courant’s multiwinner voting rules, where we focus on the total (dis)satisfaction of the voters (the utilitarian case) or the (dis)satisfaction of the worstoff voter (the egalitarian case). We show good approximation algorithms for the satisfaction-based utilitarian cases, and inapproximability results for the remaining settings.

PDF Details DOI
v2026.09.13