On coalitional manipulation for multiwinner elections: shortlisting [original]

Vol.:(0123456789)

Autonomous Agents and Multi-Agent Systems (2021) 35:38

https://doi.org/10.1007/s10458-021-09507-9

1 3

On coalitional manipulation formultiwinner elections:

shortlisting

RobertBredereck2 · AndrzejKaczmarczyk1 · RolfNiedermeier1

Accepted: 12 May 2021 / Published online: 8 July 2021

Abstract

Shortlisting of candidates—selecting a group of“best” candidates—is a special case of

multiwinner elections. We provide the first in-depth study of the computational complex-

ity of strategic voting for shortlisting based on the perhaps most basic voting rule in this

scenario,

𝓁

-Bloc (every voter approves

𝓁

candidates). In particular, we investigate the influ-

ence of several different group evaluation functions (e.g., egalitarian versus utilitarian) and

tie-breaking mechanisms modeling pessimistic and optimistic manipulators. Among other

things, we conclude that in an egalitarian setting strategic voting may indeed be computa-

tionally intractable regardless of the tie-breaking rule. Altogether, weprovide afairly com-

prehensive picture of the computational complexity landscape of this scenario.

Keywords Computational social choice· Utility aggregation· Strategic voting·

Parameterized computational complexity· Tie-breaking· SNTV· Bloc

1 Introduction

Assume that a university wants to select the two favorite pieces in classical style to be

played during the next graduation ceremony. The students were asked to submit their

favorite pieces. Then a jury consisting of seven members (three juniors and four seniors)

A preliminary version of this article appeared in the Proceedings of the Twenty-Sixth International

Joint Conference on Artificial Intelligence (IJCAI ’17)[12]. In this full version we included all proofs

and algorithms (together with our ILP formulations). Furthermore, we formalized the concept of

simulation among tie-breaking rules.

* Robert Bredereck

[email protected]

Andrzej Kaczmarczyk

[email protected]

Rolf Niedermeier

[email protected]

1 FacultyIV, Algorithmics andComputational Complexity, Technische Universität Berlin,

Ernst-Reuter-Platz 7, 10587Berlin, Germany

2 Institut für Informatik, Algorithm Engineering, Humboldt-Universität zu Berlin, Rudower Chausse

25, 12489Berlin, Germany

Autonomous Agents and Multi-Agent Systems (2021) 35:38

1 3

38 Page 2 of 41

from the university staff selects from the six most frequently submitted pieces as follows:

Each jury member approves two pieces and the two winners are those obtaining most

of the approvals. The six options provided by the students are “Beethoven: Piano Con-

certo No.5(

)”, “Beethoven: Symphony No.6(

)”, “Mozart: Clarinet Concerto(

)”,

“Mozart: Jeunehomme Piano Concerto(

)”, “Uematsu: Final Fantasy(

)”, and “Badelt:

Pirates of the Caribbean(

).” The three junior jury members are excited about recent

audio-visual presentation arts (both interactive and passive) and approve

and

. Two of

the senior jury members are Mozart enthusiasts, and the other two senior jury members are

Beethoven enthusiasts. Hence, when voting truthfully, two of them would approve the two

Mozart pieces and the other two would approve the two Beethoven pieces. The winners

of the selection process would be

and

, both receiving three approvals whereas every

other piece receives only two approvals.

The senior jury members meet every Friday evening and discuss important academic

issues which include the graduation ceremony music selection processes, why “movie

background noise” recently counts as classical music,1 and the influence of video games on

the ability of making important decisions. During such a meeting they agreed that a gradu-

ation ceremony should always be accompanied by pieces of traditional, first-class compos-

ers. Thus, finally all four senior jury members decide to approve

and

so these two

pieces are played during the graduation ceremony.

Already this toy example above (which will be the basis of our running example

throughout the paper) illustrates important aspects of strategic voting in multiwinner elec-

tions. In case of coalitional manipulation for single-winner elections (where a coalition of

voters casts untruthful votes in order to influence the outcome of an election; a topic which

has been intensively studied in the literature[9, 16]) one can always assume that a coali-

tion of manipulators agrees on trying to make a distinguished alternative win the election.

In case of multiwinner elections, however, already determining concrete possible goals of

a coalition seems to be a non-trivial task: There may be exponentially many different out-

comes which can be reached through strategic votes of the coalition members and each

member could have its individual evaluation of these outcomes.

Multiwinner voting rules come up very naturally whenever one has to select from a

large set of candidates a smaller set of “the best” candidates. Surprisingly, although at least

as practically relevant as single-winner voting rules, the multiwinner literature is much less

developed than the single-winner literature. In recent years (see a survey ofFaliszewski

etal. [26]), however, research into multiwinner voting rules, their properties, and algorith-

mic complexity grew significantly[1–5, 7, 10, 23, 25, 27, 33, 38, 42, 44, 45]. When select-

ing a group of winning candidates, various criteria can be interesting; namely, proportional

representation, diversity, or excellence (seeElkind etal. [23]). We focus on the last sce-

nario, where the goal is to select the best (say highest-scoring) group ofcandidates.

Aiming at excellence comes very naturally in the context of shortlisting, where the

objective is ashort list of candidates selected from an initial, much larger list of candidates.

For instance, a human resource department wanting to fill a vacancy would select, from

all job candidates, a short list of prospective applicants who should be further assessed

to find the best fitting applicant. This example neatly illustrates the universal purpose of

shortlisting, that is, saving effort at the same time increasing the quality of evaluating suit-

able candidates. Indeed, human resource departments will either waste a lot of time and

1 http:// www. class icfm. com/ radio/ hall- of- fame/.

Autonomous Agents and Multi-Agent Systems (2021) 35:38

1 3

Page 3 of 41 38

effort interviewing every applicant in detail or they will significantly decrease the quality

of interviewing to speed up the process unless they apply shortlisting beforehand.

A standard way of candidate selection in the context of shortlisting is to use scoring-

based voting rules. We focus on the two most natural ones: SNTV (single non-transferable

vote—each voter gives one point to one candidate) and

𝓁

-Bloc (each voter gives one point

to each of

𝓁

different candidates, so SNTV is the same as

-Bloc).2 Obviously, for such vot-

ing rules it is trivial to determine the score of each individual candidate.

The main goal of our work is to model and understand coalitional manipulation in a

computational sense—that is, to introduce a formal description of how a group of manipu-

lators can influence the election outcome by casting strategic votes and whether it is possi-

ble to find an effective strategy for the manipulators to change the outcome in some desired

way. We find studying coalitional manipulability from the computational complexity point

of view relevant for two main reasons. First, in natural way we complement well-known

work on manipulation for single-winner rules initiated byBartholdi III etal. [8], coalitional

manipulation for single-winner rules initiated byConitzer etal. [17], and (non-coalitional)

manipulation for multiwinner rules initiated byMeir etal. [38]. Second, we provide effi-

cient algorithms that allow for experimental study of coalitional manipulation that might

be interesting both for verifying how likely is or what is an impact of coalitional manipula-

tion in practice (analogously to studies for the single-winner case[15, 19, 24, 36, 47]) and

for interdisciplinary study on human’s behavior when manipulating (like the one recently

conducted for multiwinner elections byScheuerman etal. [43]).

In coalitional manipulation scenarios, given full knowledge about other voters’ prefer-

ences, one has a set of manipulative voters who want to influence the election outcome in

a favorable way by casting their votes strategically. To come up with a useful framework

for coalitional manipulation for multiwinner elections, we first have to identify the exact

mathematical model and questions to be asked. A couple of straightforward extensions of

coalitional manipulation for single-winner elections or (non-coalitional) manipulation for

multiwinner elections do not fit. Extending the single-winner variant directly, one would

probably assume that the coalition agrees on making a distinguished candidate part of the

winners or that the coalition agrees on making a distinguished candidate group part of

the winners. The former is unrealistic because in multiwinner settings one typically cares

about more than just one candidate—especially in shortlisting it is natural that one wants

rather some group of “similarly good” candidates to be winning instead of only one repre-

sentative of such a group. The latter, that is, agreeing on a distinguished candidate group to

be part of the winners is also problematic since there may be exponentially many “equally

good” candidate groups for the coalition.3 Notably, this was not a problem in the single-

winner case; there, one can test for a successful manipulation towards each possible candi-

date avoiding an exponential increase of the running time (compared to the running time of

such a test for a single candidate).

We address the aforementioned issue of modeling coalitional manipulation for mul-

tiwinner election by extending a single-manipulator model for multiwinner rules ofMeir

2 Although, in general,

𝓁

-Bloc does not satisfy committee monotonicity which is considered as a neces-

sary condition for shortlisting[26], this rule seems quite frequent in practice—for example The Board of

Research Excellence in Poland was elected using a variant of

𝓁

-Bloc[39].

3 Indeed, assume a coalition has

x=20

favorite candidates that the coalition members equally prefer to be

winning but the voting rule will select at most

k=10

of them. This means, when manipulating the election

the coalition may support only one out of

(

)

184756

possible candidate groups.

Autonomous Agents and Multi-Agent Systems (2021) 35:38

1 3

38 Page 4 of 41

etal. [38]. In their work, the manipulator specifies the utility of each candidate and the util-

ity for a candidate group is obtained by adding up the utilities of each group member. We

build on their idea and let each manipulator report the utility of each candidate. However,

aggregating utilities for a coalition of manipulators (in other words, computing a collec-

tive utility of manipulators) becomes conceptually nontrivial—especially for a coalition of

manipulators who have diverse utilities for single candidates but still have strong incentives

to work together (e.g., as we have seen in our introductory example).

In fact, in our paper we only consider coalitions that are fixed, that is, irrespectively of

how different the opinions of manipulators are, none of them leaves the coalition. For some

situations and applications, this assumption might look too restrictive and unrealistic. In

many situations, however, we believe there are good reasons for making this assumption.

First, changing already existing coalitions in the real world usually requires a significant

overhead (e.g., formal agreements and negotiations that cost both money and time) which

makes such a change rather a last, not a first, resort. This holds true especially if a coali-

tion is aimed at long-term benefits as, for example, strategic cooperations among firms or

governments. Second, there are real-world cases where coalitions are forced, for example,

in hierarchical administrative divisions (and their local governments) in countries. Third,

computing a best possible manipulation for a given coalition is an important step in decid-

ing whether it might be useful to actually form such a coalition in possible future. To wrap

up, instead of focusing on coalitions dynamics (which is important work but not part of this

paper), we rather concentrate on an analysis of a strength of, intuitively speaking, potential,

fixed, or forced coalitions.

Our Contributions. We devise a formal description of coalitional manipulation in mul-

tiwinner elections arriving at a new, nontrivial model capturing twotypes of manipulators’

attitudes and a few natural ways of utility aggregation. To this end, in our model, we dis-

tinguish between optimistic and pessimistic manipulators and we formalize aggregation of

utilities in a utilitarian and an egalitarian way.

Using our model, we analyze the computational complexity of finding a successful

manipulation for a coalition of voters, assuming elections under rules from the family of

𝓁

-Bloc voting rules. We show that, even for these fairly simple rules, the computational

complexity of coalitional manipulation is diverse. In particular, we observe that finding a

manipulation maximizing the utility of a worst-off manipulator (egalitarian aggregation)

is

-hard (regardless of the manipulators’ attitude). This result stands in sharp contrast

to the polynomial-time algorithms that we give for finding a manipulation maximizing the

sum of manipulators’ utilities (utilitarian aggregation). Additionally, we show how to cir-

cumvent the cumbersome

-hardness for the egalitarian aggregation providing an (FPT)

algorithm that is efficient for scenarios with few manipulators and few different values of

utility that manipulators assign to agents. We survey all our computational complexity

results in Table1 (Sect.6).

Related Work. To the best of our knowledge, there is no previous work on coalitional

manipulation in the context of multiwinner elections. We refer to recent textbooks for an

overview of the huge literature on single-winner (coalitional) manipulation[9, 16]. Most

relevant to our work, Lin [35] showed that coalitional manipulation in single-winner elec-

tions under

𝓁

-Approval is solvable in linear time by a greedy algorithm. Meir etal. [38]

introduced (non-coalitional) manipulation for multiwinner elections. While pinpointing

manipulation for several voting rules as NP-hard, they showed that manipulation remains

polynomial-time solvable for Bloc (which can be interpreted as a multiwinner equivalent

of 1-Approval). Obraztsova etal. [42] extended the latter result for different tie-breaking

strategies and identified further tractable special cases of multiwinner scoring rules but

Autonomous Agents and Multi-Agent Systems (2021) 35:38

1 3

Page 5 of 41 38

conjectured manipulation to be hard in general for (other) scoring rules. Summarizing,

Bloc is simple but comparably well-studied, and hence we selected it as a showcase for our

study of the presumably computationally harder coalitional manipulation.

As mentioned above, our model assumes an existing fixed coalition of manipulators.

There is a significant amount of research on coalition dynamics and coalition forming in

context of cooperative games. We refer to recent text books for an overview on this rich

research area [22, 32]. Notably, our model is relevant for situations after some dynamic

coalition forming process lead to a fixed coalition as well as during a coalition forming

process when a group of agents wants to compute their potential utility from working

together. Our aggregation models may be used for transferable utilities (utilitarian aggrega-

tion) as well as non-transferable utilities (egalitarian aggregation).

Another closely related model is the

-hard multiwinner voting rule Minimax

Approval Voting [13] which selects a group of candidates that maximizes the minimum

satisfaction over all voters. This rule almost resembles the tie-breaking issue of our model

for the egalitarian case and 0/1 utility values only. Each voter in a Minimax Approval Vot-

ing election can, however, approve an arbitrary number of candidates as opposed to the

𝓁

-Blocrule that we consider, where each voter approves exactly

𝓁

candidates.

Organization. Section 2 introduces basic notation and formal concepts. In Sect. 3,

we develop our model for coalitional manipulation in multiwinner elections. Its variants

respect different ways of evaluating candidate groups (utilitarian vs. egalitarian) and two

kinds of manipulators behavior (optimistic vs. pessimistic). In Sect.4, we present algo-

rithms and complexity results for computing the output of several tie-breaking rules that

allow to model optimistic and pessimistic manipulators. In Sect.5, we formally define the

coalitional manipulation problem and explore its computational complexity using

𝓁

-Bloc

as a showcase. We refer to our conclusion and Table1 (Sect.6) for a detailed overview of

our findings.

2 Preliminaries

For a positive integer n, let

[n] ∶= {1, 2, …,n}

. We use the toolbox of parameterized

complexity[18, 21, 29, 40] to analyze the computational complexity of our problems in

a fine-grained way. To this end, we always identify a parameter

𝜌

that is typically a posi-

tive integer. We call a problem parameterized by

𝜌

fixed-parameter tractable (in

FPT

) if

it is solvable in

f(𝜌)

⋅

|I|O(1)

time, where |I| is the size of a given instance encoding,

𝜌

the value of the parameter, and f is an arbitrary computable (typically super-polynomial)

function. To preclude fixed-parameter tractability, we use an established complexity hier-

archy of classes of parameterized problems,

FPT ⊆W[1] ⊆W[2] ⊆⋯⊆XP

. It is widely

believed that all inclusions are proper. The notions of hardness for parameterized classes

are defined through parameterized reductions similar to classical polynomial-time many-

one reductions—in this work, it suffices to ensure that the value of the parameter in the

problem we reduce to depends only on the value of the parameter of the problem we reduce

from. Occasionally, we use a combined parameter

𝜌�+𝜌��

which is a more explicit way of

expressing a parameter

𝜌=𝜌�+𝜌��

An election(C,V) consists of a setC of mcandidates and a multisetV of nvotes.

Votes are linear orders overC—for example, for

C={c1,c2,c3}

we write

c1≻vc2≻vc3

to express that candidate

is the most preferred and candidate

is the least preferred

according to votev. Wewrite

≻

if the corresponding vote is clear from the context.

Loading more pages...