
This paper contains an extensive combinatorial analysis of the singlepeaked
domain restriction and investigates the likelihood that an election is
singlepeaked. We provide a very general upper bound result for domain
restrictions that can be defined by certain forbidden configurations. This
upper bound implies that many domain restrictions (including the singlepeaked
restriction) are very unlikely to appear in a random election chosen according
to the Impartial Culture assumption. For singlepeaked elections, this upper
bound can be refined and complemented by a lower bound that is asymptotically
tight. In addition, we provide exact results for elections with few voters or
candidates. Moreover, we consider the P\'{o}lya urn model and the Mallows model
and obtain lower bounds showing that singlepeakedness is considerably more
likely to appear for certain parameterizations.

This paper is an axiomatic study of consistent approvalbased multiwinner
rules, i.e., voting rules that select a fixedsize group of candidates based on
approval ballots. We introduce the class of counting rules and provide an
axiomatic characterization of this class based on the consistency axiom.
Building upon this result, we axiomatically characterize three important
consistent multiwinner rules: Proportional Approval Voting, MultiWinner
Approval Voting and the Approval ChamberlinCourant rule. Our results
demonstrate the variety of multiwinner rules and illustrate three different,
orthogonal principles that multiwinner voting rules may represent: individual
excellence, diversity, and proportionality.

Liquid democracy is a proxy voting method where proxies are delegable. We
propose and study a gametheoretic 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 purestrategy Nash equilibria in this model, and how
group accuracy is affected by them. We complement these results by means of
simulations to study the effects of delegations on group's accuracy on various
network structures.

To choose a multiwinner rule, i.e., a voting rule that selects a subset of
$k$ alternatives based on preferences of a certain population, is a hard and
ambiguous task. Depending on the context, it varies widely what constitutes an
"optimal" committee. In this paper, we offer a new perspective to measure the
quality of committees andconsequentlymultiwinner rules. We provide a
quantitative analysis using methods from the theory of approximation algorithms
and estimate how well multiwinner rules approximate two extreme objectives:
diversity as captured by the (Approval) ChamberlinCourant rule (CC) and
individual excellence as captured by Approval Voting (AV). With both
theoretical and experimental methods we establish a classification of
multiwinner rules in terms of their quantitative alignment with these two
opposing objectives.

Manipulation, bribery, and control are wellstudied 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 singlepeaked electorates, these rules suddenly become easy to
manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the
computational complexity of strategic behavior in nearly singlepeaked
electorates. These are electorates that are not singlepeaked but close to it
according to some distance measure.
In this paper we introduce several new distance measures regarding
singlepeakedness. We prove that determining whether a given profile is nearly
singlepeaked is NPcomplete in many cases. For one case we present a
polynomialtime algorithm. In case the singlepeaked 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.

We identify a whole family of approvalbased multiwinner voting rules that
satisfy PJR. Moreover, we identify a subfamily of voting rules within this
family that satisfy EJR. All these voting rules can be computed in polynomial
time as long as the subalgorithms that characterize each rule within the family
are polynomial. One of the voting rules that satisfy EJR can be computed in
$O(n m k)$.

In this short note, we describe an approvalbased committee selection rule
that admits a polynomialtime algorithm and satisfies the Extended Justified
Representation (EJR) axiom. This rule is based on approximately maximizing the
PAV score, by means of local search. Our proof strategy is to show that this
rule provides almost optimal average satisfaction to all cohesive groups of
voters, and that high average satisfaction for cohesive groups implies extended
justified representation.

We study two notions of stability in multiwinner elections that are based on
the Condorcet criterion. The first notion was introduced by Gehrlein: A
committee is stable if each committee member is preferred to each nonmember by
a (possibly weak) majority of voters. The second notion is called local
stability (introduced in this paper): A size$k$ committee is locally stable in
an election with $n$ voters if there is no candidate $c$ and no group of more
than $\frac{n}{k+1}$ voters such that each voter in this group prefers $c$ to
each committee member. We argue that Gehrleinstable committees are appropriate
for shortlisting tasks, and that locally stable committees are better suited
for applications that require proportional representation. The goal of this
paper is to analyze these notions in detail, explore their compatibility with
notions of proportionality, and investigate the computational complexity of
related algorithmic tasks.

The Permutation Pattern Matching problem, asking whether a pattern
permutation $\pi$ is contained in a permutation $\tau$, is known to be
NPcomplete. In this paper we present two polynomial time algorithms for
special cases. The first algorithm is applicable if both $\pi$ and $\tau$ are
$321$avoiding; the second is applicable if $\pi$ and $\tau$ are skewmerged.
Both algorithms have a runtime of $O(kn)$, where $k$ is the length of $\pi$ and
$n$ the length of $\tau$.

In this paper we extend the principle of proportional representation to
rankings. We consider the setting where alternatives need to be ranked based on
approval preferences. In this setting, proportional representation requires
that cohesive groups of voters are represented proportionally in each initial
segment of the ranking. Proportional rankings are desirable in situations where
initial segments of different lengths may be relevant, e.g., hiring decisions
(if it is unclear how many positions are to be filled), the presentation of
competing proposals on a liquid democracy platform (if it is unclear how many
proposals participants are taking into consideration), or recommender systems
(if a ranking has to accommodate different user types). We study the
proportional representation provided by several ranking methods and prove
theoretical guarantees. Furthermore, we experimentally evaluate these methods
and present preliminary evidence as to which methods are most suitable for
producing proportional rankings.

The goal of multiwinner elections is to choose a fixedsize 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\ge 6$. Second, we
observe that EJR is incompatible with the Perfect Representation criterion,
which is important for many applications of multiwinner 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.

Many hard computational social choice problems are known to become tractable
when voters' preferences belong to a restricted domain, such as those of
singlepeaked or singlecrossing 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
singlepeaked and singlecrossing 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 approvalbased multiwinner rules.

The NPcomplete Permutation Pattern Matching problem asks whether a
$k$permutation $P$ is contained in a $n$permutation $T$ as a pattern. This is
the case if there exists an orderpreserving embedding of $P$ into $T$. In this
paper, we present a fixedparameter algorithm solving this problem with a
worstcase runtime of $\mathcal{O}(1.79^{\mathsf{run}(T)}\cdot n\cdot k)$,
where $\mathsf{run}(T)$ denotes the number of alternating runs of $T$. This
algorithm is particularly wellsuited for instances where $T$ has few runs,
i.e., few ups and downs. Moreover, since $\mathsf{run}(T)<n$, this can be seen
as a $\mathcal{O}(1.79^{n}\cdot n\cdot k)$ algorithm which is the first to beat
the exponential $2^n$ runtime of bruteforce search. Furthermore, we prove that
under standard complexity theoretic assumptions such a fixedparameter
tractability result is not possible for $\mathsf{run}(P)$.

In the last years, different types of patterns in permutations have been
studied: vincular, bivincular and mesh patterns, just to name a few. Every type
of permutation pattern naturally defines a corresponding computational problem:
Given a pattern P and a permutation T (the text), is P contained in T? In this
paper we draw a map of the computational landscape of permutation pattern
matching with different types of patterns. We provide a classical complexity
analysis and investigate the impact of the pattern length on the computational
hardness. Furthermore, we highlight several directions in which the study of
computational aspects of permutation patterns could evolve.

The NPcomplete Permutation Pattern Matching problem asks whether a
permutation P (the pattern) can be matched into a permutation T (the text). A
matching is an orderpreserving embedding of P into T. In the Generalized
Permutation Pattern Matching problem one can additionally enforce that certain
adjacent elements in the pattern must be mapped to adjacent elements in the
text. This paper studies the parameterized complexity of this more general
problem. We show W[1]completeness with respect to the length of the pattern P.
Under standard complexity theoretic assumptions this implies that no
fixedparameter tractable algorithm can be found for any parameter depending
solely on P.