Arrow Research search

Author name cluster

Martin Lackner

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.

43 papers
2 author rows

Possible papers

43

AAMAS Conference 2026 Conference Paper

Computational Social Choice: Research & Development

  • Dorothea Baumeister
  • Ratip Emin Berker
  • Niclas Boehmer
  • Sylvain Bouveret
  • Andreas Darmann
  • Piotr Faliszewski
  • Martin Lackner
  • Jérôme Lang

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. We articulate the defining features of COMSOC-R&D, argue for its value, and discuss various roadblocks and possible solutions.

PDF

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

AAAI Conference 2024 Conference Paper

Repeated Fair Allocation of Indivisible Items

  • Ayumi Igarashi
  • Martin Lackner
  • Oliviero Nardi
  • Arianna Novaro

The problem of fairly allocating a set of indivisible items is a well-known challenge in the field of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envy-freeness and proportionality) and economic efficiency (such as Pareto-optimality). However, in the real world, items are not always allocated once and for all, but often repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by this, we initiate the study of the repeated fair division of indivisible goods and chores, and propose a formal model for this scenario. In this paper, we show that, if the number of repetitions is a multiple of the number of agents, there always exists a sequence of allocations that is proportional and Pareto-optimal. On the other hand, irrespective of the number of repetitions, an envy-free and Pareto-optimal sequence of allocations may not exist. For the case of two agents, we show that if the number of repetitions is even, it is always possible to find a sequence of allocations that is overall envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envy-freeness. Finally, in case that the number of repetitions can be chosen freely, we show that envy-free and Pareto-optimal allocations are achievable for any number of agents.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

An Experimental Comparison of Multiwinner Voting Rules on Approval Elections

  • Piotr Faliszewski
  • Martin Lackner
  • Krzysztof Sornat
  • Stanisław Szufa

In this paper, we experimentally compare major approval based multiwinner voting rules. To this end, we define a measure of similarity between two equal sized committees subject to a given election. Using synthetic elections coming from several distributions, we analyze how similar are the committees provided by prominent voting rules. Our results can be visualized as maps of voting rules, which provide a counterpoint to a purely axiomatic classification of voting rules. The strength of our proposed method is its independence from preimposed classifications (such as the satisfaction of concrete axioms), and that it indeed offers a much finer distinction than the current state of axiomatic analysis.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Fairness in Participatory Budgeting via Equality of Resources

  • Jan Maly
  • Simon Rey
  • Ulle Endriss
  • Martin Lackner

We introduce a family of normative principles to assess fairness in the context of participatory budgeting. These principles are based on the fundamental idea that budget allocations should be fair in terms of the resources invested into meeting the wishes of individual voters. This is in contrast to earlier proposals that are based on specific assumptions regarding the satisfaction of voters with a given budget allocation. We analyse these new principles in axiomatic, algorithmic, and experimental terms.

PDF

AAMAS Conference 2023 Conference Paper

Free-Riding in Multi-Issue Decisions

  • Martin Lackner
  • Jan Maly
  • Oliviero Nardi

Voting in multi-issue domains allows for compromise outcomes that satisfy all voters to some extent. Such fairness considerations, however, open the possibility of a special form of manipulation: free-riding. By untruthfully opposing a popular opinion in one issue, voters can receive increased consideration in other issues. We study under which conditions this is possible. Additionally, we study free-riding from a computational and experimental point of view. Our results show that free-riding in multi-issue domains is largely unavoidable, but comes at a non-negligible individual risk for voters. Thus, the allure of free-riding is smaller than one could intuitively assume.

PDF

AAAI Conference 2023 Conference Paper

Proportional Decisions in Perpetual Voting

  • Martin Lackner
  • Jan Maly

Perpetual voting is a framework for long-term collective decision making. In this framework, we consider a sequence of subsequent approval-based elections and try to achieve a fair overall outcome. To achieve fairness over time, perpetual voting rules take the history of previous decisions into account and identify voters that were dissatisfied with previous decisions. In this paper, we look at perpetual voting rules from an axiomatic perspective. First, we define two classes of perpetual voting rules that are particularly easy to explain to voters and explore the bounds imposed by this simplicity. Second, we study proportionality in the perpetual setting and identify two rules with strong proportionality guarantees. However, both rules yield different guarantees and we prove them to be incompatible with each other.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Proportionality in Approval-Based Participatory Budgeting

  • Markus Brill
  • Stefan Forster
  • Martin Lackner
  • Jan Maly
  • Jannik Peters

The ability to measure the satisfaction of (groups of) voters is a crucial prerequisite for formulating proportionality axioms in approval-based participatory budgeting elections. Two common -- but very different -- ways to measure the satisfaction of a voter consider (i) the number of approved projects and (ii) the total cost of approved projects, respectively. In general, it is difficult to decide which measure of satisfaction best reflects the voters' true utilities. In this paper, we study proportionality axioms with respect to large classes of approval-based satisfaction functions. We establish logical implications among our axioms and related notions from the literature, and we ask whether outcomes can be achieved that are proportional with respect to more than one satisfaction function. We show that this is impossible for the two commonly used satisfaction functions when considering proportionality notions based on extended justified representation, but achievable for a notion based on proportional justified representation. For the latter result, we introduce a strengthening of priceability and show that it is satisfied by several polynomial-time computable rules, including the Method of Equal Shares and Phragmén's sequential rule.

PDF Details DOI

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.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Liquid Democracy with Ranked Delegations

  • Markus Brill
  • Théo Delemazure
  • Anne-Marie George
  • Martin Lackner
  • Ulrike Schmidt-Kraepelin

Liquid democracy is a novel paradigm for collective decisionmaking that gives agents the choice between casting a direct vote or delegating their vote to another agent. We consider a generalization of the standard liquid democracy setting by allowing agents to specify multiple potential delegates, together with a preference ranking among them. This generalization increases the number of possible delegation paths and enables higher participation rates because fewer votes are lost due to delegation cycles or abstaining agents. In order to implement this generalization of liquid democracy, we need to find a principled way of choosing between multiple delegation paths. In this paper, we provide a thorough axiomatic analysis of the space of delegation rules, i. e. , functions assigning a feasible delegation path to each delegating agent. In particular, we prove axiomatic characterizations as well as an impossibility result for delegation rules. We also analyze requirements on delegation rules that have been suggested by practitioners, and introduce novel rules with attractive properties. By performing an extensive experimental analysis on synthetic as well as real-world data, we compare delegation rules with respect to several quantitative criteria relating to the chosen paths and the resulting distribution of voting power. Our experiments reveal that delegation rules can be aligned on a spectrum reflecting an inherent trade-off between competing objectives.

PDF Details

AAAI Conference 2022 Conference Paper

Participatory Budgeting with Donations and Diversity Constraints

  • Jiehua Chen
  • Martin Lackner
  • Jan Maly

Participatory budgeting (PB) is a democratic process where citizens jointly decide on how to allocate public funds to indivisible projects. In this work, we focus on PB processes where citizens may provide additional money to projects they want to see funded. We introduce a formal framework for this kind of PB with donations. Our framework also allows for diversity constraints, meaning that each project belongs to one or more types, and there are lower and upper bounds on the number of projects of the same type that can be funded. We propose three general classes of methods for aggregating the citizens’ preferences in the presence of donations and analyze their axiomatic properties. Furthermore, we investigate the computational complexity of determining the outcome of a PB process with donations and of finding a citizen’s optimal donation strategy.

PDF Details

AAMAS Conference 2021 Conference Paper

Approval-Based Shortlisting

  • Martin Lackner
  • Jan Maly

Shortlisting is the task of reducing a long list of alternatives to a (smaller) set of best or most suitable alternatives from which a final winner will be chosen. Shortlisting is often used in the nomination process of awards or in recommender systems to display featured objects. In this paper, we analyze shortlisting methods that are based on approval data, a common type of preferences. Furthermore, we assume that the size of the shortlist, i. e. , the number of best or most suitable alternatives, is not fixed but determined by the shortlisting method. We axiomatically analyze established and new shortlisting methods and complement this analysis with an experimental evaluation based on imperfect quality estimates. Our results lead to recommendations which shortlisting methods to use, depending on the desired properties.

PDF

IJCAI Conference 2021 Conference Paper

Fairness in Long-Term Participatory Budgeting

  • Martin Lackner
  • Jan Maly
  • Simon Rey

Participatory Budgeting (PB) processes are usually designed to span several years, with referenda for new budget allocations taking place regularly. This paper presents a first formal framework for long-term PB, based on a sequence of budgeting problems as main input. We introduce a theory of fairness for this setting, focusing on three main concepts that apply to types (groups) of voters: (i) achieving equal welfare for all types, (ii) minimizing inequality of welfare (as measured by the Gini coefficient), and (iii) achieving equal welfare in the long run. We investigate under which conditions these criteria can be satisfied, and analyze the computational complexity of verifying whether they hold.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Fairness in Long-Term Participatory Budgeting

  • Martin Lackner
  • Jan Maly
  • Simon Rey

Participatory Budgeting processes are usually designed to span several years, with referenda for new budget allocations taking place regularly. This paper presents the first formalization of long-term PB. We introduce a theory of fairness for this setting, investigate under which conditions our fairness criteria can be satisfied, and analyze the computational complexity of verifying them.

PDF

JAIR Journal 2020 Journal Article

Incomplete Preferences in Single-Peaked Electorates

  • Zack Fitzsimmons
  • Martin Lackner

Incomplete preferences are likely to arise in real-world preference aggregation scenarios. This paper deals with determining whether an incomplete preference profile is single-peaked. This is valuable information since many intractable voting problems become tractable given singlepeaked preferences. We prove that the problem of recognizing single-peakedness is NP-complete for incomplete profiles consisting of partial orders. Despite this intractability result, we find several polynomial-time algorithms for reasonably restricted settings. In particular, we give polynomial-time recognition algorithms for weak orders, which can be viewed as preferences with indifference.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Perpetual Voting: Fairness in Long-Term Decision Making

  • Martin Lackner

In this paper we introduce a new voting formalism to support long-term collective decision making: perpetual voting rules. These are voting rules that take the history of previous decisions into account. Due to this additional information, perpetual voting rules may offer temporal fairness guarantees that cannot be achieved in singular decisions. In particular, such rules may enable minorities to have a fair (proportional) influence on the decision process and thus foster long-term participation of minorities. This paper explores the proposed voting rules via an axiomatic analysis as well as a quantitative evaluation by computer simulations. We identify two perpetual voting rules as particularly recommendable in long-term collective decision making.

PDF Details

JAIR Journal 2020 Journal Article

Preferences Single-Peaked on a Circle

  • Dominik Peters
  • Martin Lackner

We introduce the domain of preferences that are single-peaked on a circle, which is a generalization of the well-studied single-peaked domain. This preference restriction is useful, e.g., for scheduling decisions, certain facility location problems, and for one-dimensional decisions in the presence of extremist preferences. We give a fast recognition algorithm of this domain, provide a characterisation by finitely many forbidden subprofiles, and show that many popular single- and multi-winner voting rules are polynomial-time computable on this domain. In particular, we prove that Proportional Approval Voting can be computed in polynomial time for profiles that are single-peaked on a circle. In contrast, Kemeny's rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles in this domain.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Proportional Belief Merging

  • Adrian Haret
  • Martin Lackner
  • Andreas Pfandler
  • Johannes P. Wallner

In this paper we introduce proportionality to belief merging. Belief merging is a framework for aggregating information presented in the form of propositional formulas, and it generalizes many aggregation models in social choice. In our analysis, two incompatible notions of proportionality emerge: one similar to standard notions of proportionality in social choice, the other more in tune with the logic-based merging setting. Since established merging operators meet neither of these proportionality requirements, we design new proportional belief merging operators. We analyze the proposed operators against established rationality postulates, finding that current approaches to proportionality from the field of social choice are, at their core, incompatible with standard rationality postulates in belief merging. We provide characterization results that explain the underlying conflict, and provide a complexity analysis of our novel operators.

PDF Details

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.

PDF Details DOI

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

AAAI Conference 2019 Conference Paper

On Rational Delegations in Liquid Democracy

  • Daan Bloembergen
  • Davide Grossi
  • Martin Lackner

Liquid democracy is a proxy voting method where proxies are delegable. We propose and study a game-theoretic model of liquid democracy to address the following question: when is it rational for a voter to delegate her vote? We study the existence of pure-strategy Nash equilibria in this model, and how group accuracy is affected by them. We complement these theoretical results by means of agent-based simulations to study the effects of delegations on group’s accuracy on variously structured social networks.

PDF Details

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

IJCAI Conference 2018 Conference Paper

Computing the Schulze Method for Large-Scale Preference Data Sets

  • Theresa Csar
  • Martin Lackner
  • Reinhard Pichler

The Schulze method is a voting rule widely used in practice and enjoys many positive axiomatic properties. While it is computable in polynomial time, its straight-forward implementation does not scale well for large elections. In this paper, we develop a highly optimised algorithm for computing the Schulze method with Pregel, a framework for massively parallel computation of graph problems, and demonstrate its applicability for large preference data sets. In addition, our theoretic analysis shows that the Schulze method is indeed particularly well-suited for parallel computation, in stark contrast to the related ranked pairs method. More precisely we show that winner determination subject to the Schulze method is NL-complete, whereas this problem is P-complete for the ranked pairs method.

PDF Details

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.

PDF Details

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

JAIR Journal 2017 Journal Article

Computational Aspects of Nearly Single-Peaked Electorates

  • Gábor Erdélyi
  • Martin Lackner
  • Andreas Pfandler

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.

PDF Details DOI

AAAI Conference 2017 Conference Paper

PhragmŽnÕs Voting Methods and Justified Representation

  • Markus Brill
  • Rupert Freeman
  • Svante Janson
  • Martin Lackner

In the late 19th century, Lars Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants—one minimizing the maximal load and one minimizing the variance of loads—and a sequential variant. We study Phragmén’s methods from an axiomatic point of view, focussing on justified representation and related properties that have recently been introduced by Aziz et al. (2015a) and Sánchez-Fernández et al. (2017). We show that the sequential variant satisfies proportional justified representation, making it the first known polynomial-time computable method with this property. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmén’s methods and provide mixed-integer programming based algorithms for computing them.

PDF Details

AAAI Conference 2017 Conference Paper

Preferences Single-Peaked on a Circle

  • Dominik Peters
  • Martin Lackner

We introduce the domain of preferences that are singlepeaked on a circle, which is a generalization of the wellstudied single-peaked domain. This preference restriction is useful, e. g. , for scheduling decisions, and for one-dimensional decisions in the presence of extremist preferences. We give a fast recognition algorithm of this domain, provide a characterisation by finitely many forbidden subprofiles, and show that many popular single- and multi-winner voting rules are polynomialtime computable on this domain. In contrast, Kemeny’s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles that are single-peaked on a circle.

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

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

Winner Determination in Huge Elections with MapReduce

  • Theresa Csar
  • Martin Lackner
  • Reinhard Pichler
  • Emanuel Sallinger

In computational social choice, we are concerned with the development of methods for joint decision making. A central problem in this field is the winner determination problem, which aims at identifying the most preferred alternative(s). With the rise of modern e-business platforms, processing of huge amounts of preference data has become an issue. In this work, we apply the MapReduce framework – which has been specifically designed for dealing with big data – to various versions of the winner determination problem. We obtain efficient and highly parallel algorithms and provide a theoretical analysis and experimental evaluation.

PDF Details

IJCAI Conference 2015 Conference Paper

Structure in Dichotomous Preferences

  • Edith Elkind
  • Martin Lackner

Many hard computational social choice problems are known to become tractable when voters’ preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, all algorithmic results of this type have been obtained for the setting where each voter’s preference list is a total order of candidates. The goal of this paper is to extend this line of research to the setting where voters’ preferences are dichotomous, i. e. , each voter approves a subset of candidates and disapproves the remaining candidates. We propose several analogues of the notions of single-peaked and single-crossing preferences for dichotomous profiles and investigate the relationships among them. We then demonstrate that for some of these notions the respective restricted domains admit efficient algorithms for computationally hard approval-based multi-winner rules.

PDF Details

AAAI Conference 2015 Conference Paper

The Complexity of Recognizing Incomplete Single-Crossing Preferences

  • Edith Elkind
  • Piotr Faliszewski
  • Martin Lackner
  • Svetlana Obraztsova

We study the complexity of deciding if a given profile of incomplete votes (i. e. , a profile of partial orders over a given set of alternatives) can be extended to a singlecrossing profile of complete votes (total orders). This problem models settings where we have partial knowledge regarding voters’ preferences and we would like to understand whether the given preference profile may be single-crossing. We show that this problem admits a polynomial-time algorithm when the order of votes is fixed and the input profile consists of top orders, but becomes NP-complete if we are allowed to permute the votes and the input profile consists of weak orders or independent-pairs orders. Also, we identify a number of practical special cases of both problems that admit polynomial-time algorithms.

PDF Details

AAAI Conference 2014 Conference Paper

A Parameterized Complexity Analysis of Generalized CP-Nets

  • Martin Kronegger
  • Martin Lackner
  • Andreas Pfandler
  • Reinhard Pichler

Generalized CP-nets (GCP-nets) allow a succinct representation of preferences over multi-attribute domains. As a consequence of their succinct representation, many GCP-net related tasks are computationally hard. Even finding the more preferable of two outcomes is PSPACE-complete. In this work, we employ the framework of parameterized complexity to achieve two goals: First, we want to gain a deeper understanding of the complexity of GCP-nets. Second, we search for efficient fixed-parameter tractable algorithms.

PDF Details

AAAI Conference 2014 Conference Paper

Incomplete Preferences in Single-Peaked Electorates

  • Martin Lackner

Incomplete preferences are likely to arise in real-world preference aggregation and voting systems. This paper deals with determining whether an incomplete preference profile is single-peaked. This is essential information since many intractable voting problems become tractable for single-peaked profiles. We prove that for incomplete profiles the problem of determining single-peakedness is NP-complete. Despite this computational hardness result, we find four polynomial-time algorithms for reasonably restricted settings.

PDF Details

AAAI Conference 2014 Conference Paper

On Detecting Nearly Structured Preference Profiles

  • Edith Elkind
  • Martin Lackner

Structured preference domains, such as, for example, the domains of single-peaked and single-crossing preferences, are known to admit efficient algorithms for many problems in computational social choice. Some of these algorithms extend to preferences that are close to having the respective structural property, i. e. , can be made to enjoy this property by performing minor changes to voters’ preferences, such as deleting a small number of voters or candidates. However, it has recently been shown that finding the optimal number of voters or candidates to delete in order to achieve the desired structural property is NP-hard for many such domains. In this paper, we show that these problems admit efficient approximation algorithms. Our results apply to all domains that can be characterized in terms of forbidden configurations; this includes, in particular, single-peaked and single-crossing elections. For a large range of scenarios, our approximation results are optimal under a plausible complexity-theoretic assumption. We also provide parameterized complexity results for this class of problems.

PDF Details

AAAI Conference 2013 Conference Paper

Computational Aspects of Nearly Single-Peaked Electorates

  • Gábor Erdélyi
  • Martin Lackner
  • Andreas Pfandler

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra (2011b) studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. Furthermore, we explore the relations between several notions of nearly singlepeakedness.

PDF Details

ECAI Conference 2012 Conference Paper

Fixed-Parameter Algorithms for Closed World Reasoning

  • Martin Lackner
  • Andreas Pfandler

Closed world reasoning and circumscription are essential tasks in AI. However, their high computational complexity is a serious obstacle for their practical application. In this work we employ the framework of parameterized complexity theory in order to search for fixed-parameter algorithms. We consider eleven parameters describing different characteristics of the input. For several combinations of these parameters we are able to design efficient fixedparameter tractable algorithms. All our algorithms have a runtime only single-exponential in the parameters and linear in the input size. Furthermore, by providing parameterized hardness results we show that we have actually found all tractable fragments involving these eleven parameters. We hereby offer a complete picture of the parameterized complexity of brave closed world reasoning and circumscription.

Details

KR Conference 2012 Conference Paper

Fixed-Parameter Algorithms for Finding Minimal Models

  • Martin Lackner
  • Andreas Pfandler

Computing minimal models is an important task in Knowledge Representation and Reasoning that appears in formalisms such as circumscription, diagnosis and answer set programming. Even the most basic question of whether there exists a minimal model containing a given variable is known to be ΣP 2 -complete. In this work we study the problem of computing minimal models from the viewpoint of parameterized complexity theory. We perform an extensive complexity analysis of this problem with respect to eleven parameters. Tractable fragments based on combinations of these parameters are identified by giving several fixedparameter algorithms. For the remaining combinations we show parameterized hardness results and thus prove that under usual complexity theoretic assumptions no further fixed-parameter algorithms exist for these parameters.

v2026.09.13