Arrow Research search

Author name cluster

Markus Brill

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.

45 papers
2 author rows

Possible papers

45

AAAI Conference 2026 Conference Paper

The River Voting Method

  • Michelle Döring
  • Markus Brill
  • Jobst Heitzig

We introduce River, a novel Condorcet-consistent voting method that is based on pairwise majority margins and can be seen as a simplified variation of Tideman's Ranked Pairs method. River is simple to explain, simple to compute even "by hand," and gives rise to an easy-to-interpret certificate in the form of a directed tree. Like Ranked Pairs and Schulze's Beat Path method, River is a refinement of the Split Cycle method and shares with those many desirable properties, including independence of clones. Unlike the other three methods, River satisfies a strong form of resistance to agenda-manipulation that is known as independence of Pareto-dominated alternatives.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Utilitarian Guarantees for the Method of Equal Shares

  • Anton Baychkov
  • Markus Brill
  • Jannik Peters

In recent years, research in Participatory Budgeting (PB) has put a greater emphasis on rules satisfying notions of fairness and proportionality, with the Method of Equal Shares (MES) being a prominent example. However, proportionality can come at a cost to the total utilitarian welfare. Our work formalizes this relationship, by deriving minimum utilitarian welfare guarantees for MES for a subclass of satisfaction functions called DNS functions, which includes two of the most popular ways of measuring a voter’s utility in the PB setting: considering (1) the total cost of approved projects or (2) the total number of those projects. Our results are parameterized in terms of minimum and maximum project costs, which allows us to improve on the mostly negative results found in prior studies, and reduce to the existing multiwinner guarantee when project costs are equal. We show that our guarantees are asymptotically tight for rules satisfying Extended Justified Representation up to one project, showing that no proportional rule can achieve a better utilitarian guarantee than MES.

PDF Details DOI

AIJ Journal 2025 Journal Article

Approval-based committee voting under incomplete information

  • Aviram Imber
  • Jonas Israel
  • Markus Brill
  • Benny Kimelfeld

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved , disapproved , and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin–Courant. These problems include determining whether a given set of candidates is a possible or necessary winning committee and whether a given candidate is possibly or necessarily a member of the winning committee. We also consider proportional representation axioms and the problem of deciding whether a given committee is possibly or necessarily representative.

Details DOI

AAAI Conference 2025 Conference Paper

Proportional Representation in Practice: Quantifying Proportionality in Ordinal Elections

  • Tuva Bardal
  • Markus Brill
  • David McCune
  • Jannik Peters

Proportional representation plays a crucial role in electoral systems. In ordinal elections, where voters rank candidates based on their preferences, the Single Transferable Vote (STV) is the most widely used proportional voting method. STV is considered proportional because it satisfies an axiom requiring that large enough "solid coalitions" of voters are adequately represented. Using real-world data from local Scottish elections, we observe that solid coalitions of the required size rarely occur in practice. This observation challenges the importance of proportionality axioms and raises the question of how the proportionality of voting methods can be assessed beyond their axiomatic performance. We address these concerns by developing quantitative measures of proportionality. We apply these measures to evaluate the proportionality of voting rules on real-world election data. Besides STV, we consider SNTV, the Expanding Approvals Rule, and Sequential Ranked-Choice Voting. We also study the effects of ballot truncation by artificially completing truncated ballots and comparing the proportionality of outcomes under complete and truncated ballots.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Approval-Based Committee Voting in Practice: A Case Study of (over-)Representation in the Polkadot Blockchain

  • Niclas Boehmer
  • Markus Brill
  • Alfonso Cevallos
  • Jonas Gehrlein
  • Luis Sánchez-Fernández
  • Ulrike Schmidt-Kraepelin

We provide the first large-scale data collection of real-world approval-based committee elections. These elections have been conducted on the Polkadot blockchain as part of their Nominated Proof-of-Stake mechanism and contain around one thousand candidates and tens of thousands of (weighted) voters each. We conduct an in-depth study of application-relevant questions, including a quantitative and qualitative analysis of the outcomes returned by different voting rules. Besides considering proportionality measures that are standard in the multiwinner voting literature, we pay particular attention to less-studied measures of overrepresentation, as these are closely related to the security of the Polkadot network. We also analyze how different design decisions such as the committee size affect the examined measures.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Completing Priceable Committees: Utilitarian and Representation Guarantees for Proportional Multiwinner Voting

  • Markus Brill
  • Jannik Peters

When selecting committees based on preferences of voters, a variety of different criteria can be considered. Two natural objectives are maximizing the utilitarian welfare (the sum of voters' utilities) and coverage (the number of represented voters) of the selected committee. Previous work has studied the impact on utilitarian welfare and coverage when requiring the committee to satisfy minimal requirements such as justified representation or weak proportionality. In this paper, we consider the impact of imposing much more demanding proportionality axioms. We identify a class of voting rules that achieve strong guarantees on utilitarian welfare and coverage when combined with appropriate completions. This class is defined via a weakening of priceability and contains prominent rules such as the Method of Equal Shares. We show that committees selected by these rules (i) can be completed to achieve optimal coverage and (ii) can be completed to achieve an asymptotically optimal approximation to the utilitarian welfare if they additionally satisfy EJR+. Answering an open question of Elkind et al. (2022), we use the Greedy Justified Candidate Rule to obtain the best possible utilitarian guarantee subject to proportionality. We also consider completion methods suggested in the participatory budgeting literature and other objectives besides welfare and coverage.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Selecting Representative Bodies: An Axiomatic View

  • Manon Revel
  • Niclas Boehmer
  • Rachael Colley
  • Markus Brill
  • Piotr Faliszewski
  • Edith Elkind

As the world’s democratic institutions are challenged by dissatisfied citizens, political scientists and computer scientists have proposed and analyzed various (innovative) methods to select representative bodies, a crucial task in every democracy. However, a unified framework to analyze and compare different selection mechanisms is largely missing. To address this gap, we advocate employing concepts and tools from computational social choice to devise a model in which different selection mechanisms can be formalized. Such a model would allow for conceptualizing and evaluating desirable representation axioms. We make the first step in this direction by proposing a unifying mathematical formulation of different selection mechanisms as well as various social-choice-inspired axioms such as proportionality and monotonicity.

PDF

AAAI Conference 2024 Conference Paper

Spatial Voting with Incomplete Voter Information

  • Aviram Imber
  • Jonas Israel
  • Markus Brill
  • Hadas Shachnai
  • Benny Kimelfeld

We consider spatial voting where candidates are located in the Euclidean d-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Multiwinner Voting with Possibly Unavailable Candidates

  • Markus Brill
  • Hayrullah Dindar
  • Jonas Israel
  • Jérôme Lang
  • Jannik Peters
  • Ulrike Schmidt-Kraepelin

Selecting a committee that meets diversity and proportionality criteria is a challenging endeavor that has been studied extensively in recent years. This task becomes even more challenging when some of the selected candidates decline the invitation to join the committee. Since the unavailability of one candidate may impact the rest of the selection, inviting all candidates at the same time may lead to a suboptimal committee. Instead, invitations should be sequential and conditional on which candidates invited so far accepted the invitation: the solution to the committee selection problem is a query policy. If invitation queries are binding, they should be safe: one should not query a candidate without being sure that whatever the set of available candidates possible at that stage, her inclusion will not jeopardize committee optimality. Assuming approval-based inputs, we characterize the set of rules for which a safe query exists at every stage. In order to parallelize the invitation process, we investigate the computation of safe parallel queries, and show that it is often hard. We also study the existence of safe parallel queries with respect to proportionality axioms such as extended justified representation.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Proportionality Guarantees in Elections with Interdependent Issues

  • Markus Brill
  • Evangelos Markakis
  • Georgios Papasotiropoulos
  • Jannik Peters

We consider a multi-issue election setting over a set of possibly interdependent issues with the goal of achieving proportional representation of the views of the electorate. To this end, we employ a proportionality criterion suggested recently in the literature, that guarantees fair representation for all groups of voters of sufficient size. For this criterion, there exist rules that perform well in the case where all the issues have a binary domain and are independent of each other. In particular, this has been shown for Proportional Approval Voting (PAV) and for the Method of Equal Shares (MES). In this paper, we go two steps further: we generalize these guarantees for issues with a non-binary domain, and, most importantly, we consider extensions to elections with dependencies among issues, where we identify restrictions that lead to analogous results. To achieve this, we define appropriate generalizations of PAV and MES to handle conditional ballots. In addition to proportionality considerations, we also examine the computational properties of the conditional version of MES. Our findings indicate that the conditional case poses additional challenges and differs significantly from the unconditional one, both in terms of proportionality guarantees and computational complexity.

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

AAAI Conference 2022 Conference Paper

Approval-Based Committee Voting under Incomplete Information

  • Aviram Imber
  • Jonas Israel
  • Markus Brill
  • Benny Kimelfeld

We investigate approval-based committee voting with incomplete information about the approval preferences of voters. We consider several models of incompleteness where each voter partitions the set of candidates into approved, disapproved, and unknown candidates, possibly with ordinal preference constraints among candidates in the latter category. This captures scenarios where voters have not evaluated all candidates and/or it is unknown where voters draw the threshold between approved and disapproved candidates. We study the complexity of some fundamental computational problems for a number of classic approval-based committee voting rules including Proportional Approval Voting and Chamberlin–Courant. These problems include that of determining whether a given set of candidates is a possible or necessary winning committee and whether it forms a committee that possibly or necessarily satisfies representation axioms. We also consider the problem whether a given candidate is possibly or necessarily a member of the winning committee.

PDF Details

AAAI Conference 2022 Conference Paper

Individual Representation in Approval-Based Committee Voting

  • Markus Brill
  • Jonas Israel
  • Evi Micha
  • Jannik Peters

When selecting multiple candidates based on approval preferences of agents, the proportional representation of agents’ opinions is an important and well-studied desideratum. Existing criteria for evaluating the representativeness of outcomes focus on groups of agents and demand that sufficiently large and cohesive groups are “represented” in the sense that candidates approved by some group members are selected. Crucially, these criteria say nothing about the representation of individual agents, even if these agents are members of groups that deserve representation. In this paper, we formalize the concept of individual representation (IR) and explore to which extent, and under which circumstances, it can be achieved. We show that checking whether an IR outcome exists is computationally intractable, and we verify that all common approval-based voting rules may fail to provide IR even in cases where this is possible. We then focus on domain restrictions and establish an interesting contrast between “voter interval” and “candidate interval” preferences. This contrast can also be observed in our experimental results, where we analyze the attainability of IR for realistic preference profiles.

PDF Details

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

AIJ Journal 2022 Journal Article

Margin of victory for tournament solutions

  • Markus Brill
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between them. Prior work has shown that several common tournament solutions tend to select large winner sets and therefore have low discriminative power. In this paper, we propose a general framework for refining tournament solutions. In order to distinguish between winning alternatives, and also between non-winning ones, we introduce the notion of margin of victory ( MoV ) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV captures the distance from dropping out of the winner set, and for non-winners, the distance from entering the set. In each case, distance is measured in terms of which pairwise comparisons would have to be reversed in order to achieve the desired outcome. For common tournament solutions, including the top cycle, the uncovered set, and the Banks set, we determine the complexity of computing the MoV and provide bounds on the MoV for both winners and non-winners. We then reveal a number of structural insights on the MoV by investigating fundamental properties such as monotonicity and consistency with respect to the covering relation. Furthermore, we provide experimental evidence on the extent to which the MoV notion refines winner sets in tournaments generated according to various stochastic models. Our results can also be viewed from the perspective of bribery and manipulation.

Details DOI

AAMAS Conference 2022 Conference Paper

Proportional Representation in Matching Markets: Selecting Multiple Matchings under Dichotomous Preferences

  • Niclas Boehmer
  • Markus Brill
  • Ulrike Schmidt-Kraepelin

Given a set of agents with approval preferences over each other, we study the task of finding k matchings fairly representing everyone’s preferences. We model the problem as an approval-based multiwinner election where the set of candidates consists of matchings of the agents, and agents’ preferences over each other are lifted to preferences over matchings. Due to the exponential number of candidates in such elections, standard algorithms for classical sequential voting rules (such as those proposed by Thiele and Phragmén) are rendered inefficient. We show that the computational tractability of these rules can be regained by exploiting the structure of the approval preferences. Moreover, we establish algorithmic results and axiomatic guarantees that go beyond those obtainable in the classical approval-based multiwinner setting: Assuming that approvals are symmetric, we show that Proportional Approval Voting (PAV), a well-established but computationally intractable voting rule, becomes polynomial-time computable, and that its sequential variant, which does not provide any proportionality guarantees in general, fulfills a rather strong guarantee known as extended justified representation. Some of our algorithmic results extend to other types of compactly representable elections with an exponential candidate space.

PDF

IJCAI Conference 2021 Conference Paper

Dynamic Proportional Rankings

  • Jonas Israel
  • Markus Brill

Proportional ranking rules aggregate approval-style preferences of agents into a collective ranking such that groups of agents with similar preferences are adequately represented. Motivated by the application of live Q&A platforms, where submitted questions need to be ranked based on the interests of the audience, we study a dynamic extension of the proportional rankings setting. In our setting, the goal is to maintain the proportionality of a ranking when alternatives (i. e. , questions)---not necessarily from the top of the ranking---get selected sequentially. We propose generalizations of well-known aggregation rules to this setting and study their monotonicity and proportionality properties. We also evaluate the performance of these rules experimentally, using realistic probabilistic assumptions on the selection procedure.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

From Computational Social Choice to Digital Democracy

  • Markus Brill

Digital Democracy (aka e-democracy or interactive democracy) aims to enhance democratic decision-making processes by utilizing digital technology. A common goal of these approaches is to make collective decision-making more engaging, inclusive, and responsive to participants' opinions. For example, online decision-making platforms often provide much more flexibility and interaction possibilities than traditional democratic systems. It is without doubt that the successful design of digital democracy systems presents a multidisciplinary research challenge. I argue that tools and techniques from computational social choice should be employed to aid the design of online decision-making platforms and other digital democracy systems.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Margin of Victory in Tournaments: Structural and Experimental Results

  • Markus Brill
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

Tournament solutions are standard tools for identifying winners based on pairwise comparisons between competing alternatives. The recently studied notion of margin of victory (MoV) offers a general method for refining the winner set of any given tournament solution, thereby increasing the discriminative power of the solution. In this paper, we reveal a number of structural insights on the MoV by investigating fundamental properties such as monotonicity and consistency with respect to the covering relation. Furthermore, we provide experimental evidence on the extent to which the MoV notion refines winner sets in tournaments generated according to various stochastic models.

PDF Details

AAAI Conference 2021 Conference Paper

The Maximin Support Method: An Extension of the D’Hondt Method to Approval-Based Multiwinner Elections

  • Luis Sánchez-Fernández
  • Norberto Fernández García
  • Jesús A. Fisteus
  • Markus Brill

We propose the maximin support method, a novel extension of the D’Hondt apportionment method to approval-based multiwinner elections. The maximin support method is a sequential procedure that aims to maximize the support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D’Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relationship between the maximin support method and alternative D’Hondt extensions due to Phragmén.

PDF Details

AAAI Conference 2020 Conference Paper

Approval-Based Apportionment

  • Markus Brill
  • Paul Gölz
  • Dominik Peters
  • Ulrike Schmidt-Kraepelin
  • Kai Wilker

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we are able to provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Second, we demonstrate that extended justified representation is compatible with committee monotonicity.

PDF Details

AAAI Conference 2020 Conference Paper

Refining Tournament Solutions via Margin of Victory

  • Markus Brill
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

Tournament solutions are frequently used to select winners from a set of alternatives based on pairwise comparisons between alternatives. Prior work has shown that several common tournament solutions tend to select large winner sets and therefore have low discriminative power. In this paper, we propose a general framework for refining tournament solutions. In order to distinguish between winning alternatives, and also between non-winning ones, we introduce the notion of margin of victory (MoV) for tournament solutions. MoV is a robustness measure for individual alternatives: For winners, the MoV captures the distance from dropping out of the winner set, and for non-winners, the distance from entering the set. In each case, distance is measured in terms of which pairwise comparisons would have to be reversed in order to achieve the desired outcome. For common tournament solutions, including the top cycle, the uncovered set, and the Banks set, we determine the complexity of computing the MoV and provide worst-case bounds on the MoV for both winners and non-winners. Our results can also be viewed from the perspective of bribery and manipulation.

PDF Details

AAMAS Conference 2019 Conference Paper

Approximation Algorithms for BalancedCC Multiwinner Rules

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

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

PDF

AAMAS Conference 2018 Conference Paper

Interactive Democracy

  • Markus Brill

Interactive Democracy is an umbrella term that encompasses a variety of approaches to make collective decision making processes more engaging and responsive. A common goal of these approaches is to utilize modern information technology—in particular, the Internet—in order to enable more interactive decision making processes. An integral part of many interactive democracy proposals are online decision platforms that provide much more flexibility and interaction possibilities than traditional democratic systems. This is achieved by embracing the novel paradigm of delegative voting, often referred to as liquid democracy, which aims to reconcile the idealistic appeal of direct democracy with the practicality of representative democracy. The successful design of interactive democracy systems presents a multidisciplinary research challenge; one important aspect concerns the elicitation and aggregation of preferences. However, existing proposals are mostly disconnected from the vast body of scientific literature on preference aggregation and related topics. In this article, I argue that tools and techniques developed in the multiagent systems literature should be employed to aid the design of online decision platforms and other interactive democracy systems. Insights from computational social choice, an emerging research area at the intersection of computer science and economics, will be particularly relevant for this endeavor.

PDF

IJCAI Conference 2018 Conference Paper

Pairwise Liquid Democracy

  • Markus Brill
  • Nimrod Talmon

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

PDF Details

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

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

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 2016 Conference Paper

Computing Possible and Necessary Equilibrium Actions (and Bipartisan Set Winners)

  • Markus Brill
  • Rupert Freeman
  • Vincent Conitzer

In many multiagent environments, a designer has some, but limited control over the game being played. In this paper, we formalize this by considering incompletely specified games, in which some entries of the payoff matrices can be chosen from a specified set. We show that it is NP-hard for the designer to make this choices optimally, even in zero-sum games. In fact, it is already intractable to decide whether a given action is (potentially or necessarily) played in equilibrium. We also consider incompletely specified symmetric games in which all completions are required to be symmetric. Here, hardness holds even in weak tournament games (symmetric zero-sum games whose entries are all −1, 0, or 1) and in tournament games (symmetric zero-sum games whose non-diagonal entries are all −1 or 1). The latter result settles the complexity of the possible and necessary winner problems for a social-choice-theoretic solution concept known as the bipartisan set. We finally give a mixed-integer linear programming formulation for weak tournament games and evaluate it experimentally.

PDF Details

AAMAS Conference 2016 Conference Paper

False-Name-Proof Recommendations in Social Networks

  • Markus Brill
  • Vincent Conitzer
  • Rupert Freeman
  • Nisarg Shah

We study the problem of finding a recommendation for an uninformed user in a social network by weighting and aggregating the opinions offered by the informed users in the network. In social networks, an informed user may try to manipulate the recommendation by performing a false-name manipulation, wherein the user submits multiple opinions through fake accounts. To that end, we impose a no harm axiom: false-name manipulations by a user should not reduce the weight of other users in the network. We show that this axiom has deep connections to false-nameproofness. While it is impossible to design a mechanism that is best for every network subject to this axiom, we propose an intuitive mechanism LEGIT +, and show that it is uniquely optimized for small networks. Using real-world datasets, we show that our mechanism performs very well compared to two baseline mechanisms in a number of metrics, even on large networks.

PDF

IJCAI Conference 2016 Conference Paper

Pairwise Diffusion of Preference Rankings in Social Networks

  • Markus Brill
  • Edith Elkind
  • Ulle Endriss
  • Umberto Grandi

We introduce a model of preference diffusion in which agents in a social network update their preferences based on those of their influencers in the network, and we study the dynamics of this model. Preferences are modelled as ordinal rankings over a finite set of alternatives. At each time step, some of the agents update the relative ordering of two alternatives adjacent in their current ranking with the majority view of their influencers. We consider both a synchronous and an asynchronous variant of this model. Our results show how the graph-theoretic structure of the social network and the structure of the agents' preferences affect the termination of the diffusion process and the properties of the preference profile at the time of termination.

PDF Details

AAAI Conference 2016 Conference Paper

Rules for Choosing Societal Tradeoffs

  • Vincent Conitzer
  • Rupert Freeman
  • Markus Brill
  • Yuqian Li

We study the societal tradeoffs problem, where a set of voters each submit their ideal tradeoff value between each pair of activities (e. g. , “using a gallon of gasoline is as bad as creating 2 bags of landfill trash”), and these are then aggregated into the societal tradeoff vector using a rule. We introduce the family of distance-based rules and show that these can be justified as maximum likelihood estimators of the truth. Within this family, we single out the logarithmic distance-based rule as especially appealing based on a social-choice-theoretic axiomatization. We give an efficient algorithm for executing this rule as well as an approximate hill climbing algorithm, and evaluate these experimentally.

PDF Details

JAIR Journal 2015 Journal Article

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

  • Felix Brandt
  • Markus Brill
  • Edith Hemaspaandra
  • Lane A. Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. This paper shows that for voters who follow the most central political-science model of electorates---single-peaked preferences---those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the first time show that NP-hard bribery problems---including those for Kemeny and Llull elections---fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the first time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Theta-two-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

PDF Details DOI

AAAI Conference 2015 Conference Paper

Justified Representation in Approval-Based Committee Voting

  • Haris Aziz
  • Markus Brill
  • Vincent Conitzer
  • Edith Elkind
  • Rupert Freeman
  • Toby Walsh

We consider approval-based committee voting, i. e. , the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.

PDF Details

JAIR Journal 2015 Journal Article

Possible and Necessary Winners of Partial Tournaments

  • Haris Aziz
  • Markus Brill
  • Felix Fischer
  • Paul Harrenstein
  • Jerome Lang
  • Hans Georg Seedig

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.

PDF Details DOI

AAAI Conference 2015 Conference Paper

Strategic Voting and Strategic Candidacy

  • Markus Brill
  • Vincent Conitzer

Models of strategic candidacy analyze the incentives of candidates to run in an election. Most work on this topic assumes that strategizing only takes place among candidates, whereas voters vote truthfully. In this paper, we extend the analysis to also include strategic behavior on the part of the voters. (We also study cases where only candidates or only voters are strategic.) We consider two settings in which strategic voting is well-defined and has a natural interpretation: majorityconsistent voting with single-peaked preferences and voting by successive elimination. In the former setting, we analyze the type of strategic behavior required in order to guarantee desirable voting outcomes. In the latter setting, we determine the complexity of computing the set of potential outcomes if both candidates and voters act strategically.

PDF Details

AAAI Conference 2014 Conference Paper

Extending Tournament Solutions

  • Felix Brandt
  • Markus Brill
  • Paul Harrenstein

An important subclass of social choice functions, so-called majoritarian (or C1) functions, only take into account the pairwise majority relation between alternatives. In the absence of majority ties—e. g. , when there is an odd number of agents with linear preferences—the majority relation is antisymmetric and complete and can thus conveniently be represented by a tournament. Tournaments have a rich mathematical theory and many formal results for majoritarian functions assume that the majority relation constitutes a tournament. Moreover, most majoritarian functions have only been defined for tournaments and allow for a variety of generalizations to unrestricted preference profiles, none of which can be seen as the unequivocal extension of the original function. In this paper, we argue that restricting attention to tournaments is justified by the existence of a conservative extension, which inherits most of the commonly considered properties from its underlying tournament solution.

PDF Details

AAAI Conference 2014 Conference Paper

On the Axiomatic Characterization of Runoff Voting Rules

  • Rupert Freeman
  • Markus Brill
  • Vincent Conitzer

Runoff voting rules such as single transferable vote (STV) and Baldwin’s rule are of particular interest in computational social choice due to their recursive nature and hardness of manipulation, as well as in (human) practice because they are relatively easy to understand. However, they are not known for their compliance with desirable axiomatic properties, which we attempt to rectify here. We characterize runoff rules that are based on scoring rules using two axioms: a weakening of local independence of irrelevant alternatives and a variant of population-consistency. We then show, as our main technical result, that STV is the only runoff scoring rule satisfying an independence-of-clones property. Furthermore, we provide axiomatizations of Baldwin’s rule and Coombs’ rule.

PDF Details

AAMAS Conference 2012 Conference Paper

Possible and Necessary Winners of Partial Tournaments

  • Haris Aziz
  • Markus Brill
  • Felix Fischer
  • Paul Harrenstein
  • J
  • eacute; r
  • ocirc; me Lang
  • Hans Georg Seedig

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.

PDF

AAAI Conference 2012 Conference Paper

The Price of Neutrality for the Ranked Pairs Method

  • Markus Brill
  • Felix Fischer

The complexity of the winner determination problem has been studied for almost all common voting rules. A notable exception, possibly caused by some confusion regarding its exact definition, is the method of ranked pairs. The original version of the method, due to Tideman, yields a social preference function that is irresolute and neutral. A variant introduced subsequently uses an exogenously given tie-breaking rule and therefore fails neutrality. The latter variant is the one most commonly studied in the area of computational social choice, and it is easy to see that its winner determination problem is computationally tractable. We show that by contrast, computing the set of winners selected by Tideman’s original ranked pairs method is NP-complete, thus revealing a trade-off between tractability and neutrality. In addition, several known results concerning the hardness of manipulation and the complexity of computing possible and necessary winners are shown to follow as corollaries from our findings.

PDF Details

TARK Conference 2011 Conference Paper

Necessary and sufficient conditions for the strategyproofness of irresolute social choice functions

  • Felix Brandt 0001
  • Markus Brill

While the Gibbard-Satterthwaite theorem states that every non-dictatorial and resolute, i. e. , single-valued, social choice function is manipulable, it was recently shown that a number of appealing irresolute Condorcet extensions are strategyproof according to Kelly’s preference extension. In this paper, we study whether these results carry over to stronger preference extensions due to Fishburn and Gärdenfors. For both preference extensions, we provide sufficient conditions for strategyproofness and identify social choice functions that satisfy these conditions, answering a question by Gärdenfors [15] in the affirmative. We also show that some more discriminatory social choice functions fail to satisfy necessary conditions for strategyproofness.

Details

IJCAI Conference 2011 Conference Paper

On the Fixed-Parameter Tractability of Composition-Consistent Tournament Solutions

  • Felix Brandt
  • Markus Brill
  • Hans Georg Seedig

Tournament solutions, i. e. , functions that associate with each complete and asymmetric relation on a set of alternatives a non-empty subset of the alternatives, play an important role within social choice theory and the mathematical social sciences at large. Laffond et al. have shown that various tournament solutions satisfy composition-consistency, a structural invariance property based on the similarity of alternatives. We define the decomposition degree of a tournament as a parameter that reflects its decomposability and show that computing any composition-consistent tournament solution is fixed-parameter tractable with respect to the decomposition degree. Furthermore, we experimentally investigate the decomposition degree of two natural distributions of tournaments and its impact on the running time of computing the tournament equilibrium set.

PDF Details DOI

AAAI Conference 2010 Conference Paper

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

  • Felix Brandt
  • Markus Brill
  • Edith Hemaspaandra
  • Lane Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. This paper shows that for voters who follow the most central political-science model of electorates—single-peaked preferences—those protections vanish. By using singlepeaked preferences to simplify combinatorial covering challenges, we show that NP-hard bribery problems—including those for Kemeny and Llull elections—fall to polynomial time. By using single-peaked preferences to simplify combinatorial partition challenges, we show that NP-hard partitionof-voters problems fall to polynomial time. We furthermore show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θp 2-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

PDF Details

AAMAS Conference 2010 Conference Paper

Minimal Retentive Sets in Tournaments

  • Felix Brandt
  • Markus Brill
  • Felix Fischer
  • Paul Harrenstein

Many problems in multiagent decision making can be addressed using tournament solutions, i. e. , functions that associate with each completeand asymmetric relation on a set of alternatives a non-empty subset of the alternatives. For any given tournemant solution $S$, there is another tournament solution $\dot{S}$, which returns the union of all inclusion-minimal sets that satisfy S-retentiveness, a natural stability criterion with respect to S. Schwartz's tournament equilibrium set ($TEQ$) is then defined as $TEQ = T\dot{E}Q$. Due to this unwieldy recursive definition, preciously little is known about $TEQ$. Contingent on a well-known conjecture about $TEQ$, we show that $\dot{S}$ inherits a number of important and desirable properties from $S$. We thus obtain an infinite hierarchy of attractive and efficiently computable tournament solutions that "approximate" $TEQ$, which itself is intractable. This hierarchy contains well-known tournament solutions such as the top cycle ($TC$) and the minimal covering set ($MC$). We further pove a weaker version of the conjecture mentioned above, which establishes $\dot{T}C$ as an attractive new tournament solution.

PDF

AAMAS Conference 2009 Conference Paper

Computational Aspects of Shapley's Saddles

  • Felix Brandt
  • Markus Brill
  • Felix Fischer
  • Paul Harrenstein

Game-theoretic solution concepts, such as Nash equilibrium, are playing an ever increasing role in the study of systems of autonomous computational agents. A common criticism of Nash equilibrium is that its existence relies on the possibility of randomizing over actions, which in many cases is deemed unsuitable, impractical, or even infeasible. In work dating back to the early 1950s Lloyd Shapley proposed ordinal setvalued solution concepts for zero-sum games that he refers to as strict and weak saddles. These concepts are intuitively appealing, they always exist, and are unique in important subclasses of games. We initiate the study of computational aspects of Shapley’s saddles and provide polynomial-time algorithms for computing strict saddles in normal-form games and weak saddles in a subclass of symmetric zero-sum games. On the other hand, we show that certain problems associated with weak saddles in bimatrix games are NP-hard. Finally, we extend our results to mixed refinements of Shapley’s saddles introduced by Duggan and Le Breton.

PDF
v2026.09.13