
We propose the maximin support method, a novel extension of the D'Hondt
apportionment method to approvalbased multiwinner elections. The maximin
support method is based on maximizing 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
Phragm\'{e}n's voting rules.

Dynamic time warping constitutes a major tool for analyzing time series. In
particular, computing a mean series of a given sample of series in dynamic time
warping spaces (by minimizing the Fr\'echet function) is a challenging
computational problem, so far solved by several heuristic, inexact strategies.
We spot several inaccuracies in the literature on exact mean computation in
dynamic time warping spaces. Our contributions comprise an exact dynamic
program computing a mean (useful for benchmarking and evaluating known
heuristics). Empirical evaluations reveal significant deficits of the
stateoftheart heuristics in terms of their output quality. Finally, we give
an exact polynomialtime algorithm for the special case of binary time series.

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.

We establish a link between multiwinner elections and apportionment problems
by showing how approvalbased multiwinner election rules can be interpreted as
methods of apportionment. We consider several multiwinner rules and observe
that they induce apportionment methods that are wellestablished in the
literature on proportional representation. For instance, we show that
Proportional Approval Voting induces the D'Hondt method and that Monroe's rule
induces the largest reminder method. We also consider properties of
apportionment methods and exhibit multiwinner rules that induce apportionment
methods satisfying these properties.

We consider approvalbased committee voting, i.e. the setting where each
voter approves a subset of candidates, and these votes are then used to select
a fixedsize 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. However, it turns out that several
prominent approvalbased voting rules may fail to output such a committee. In
particular, while Proportional Approval Voting (PAV) always outputs a committee
that provides JR, Reweighted Approval Voting (RAV), a tractable approximation
to PAV, does not have this property. 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 we consider do not; indeed, EJR can
be used to characterize PAV within the class of weighted PAV rules. We also
consider several other questions related to JR and EJR, including the
relationship between JR/EJR and core stability, and the complexity of the
associated algorithmic problems.

In the early 1950s Lloyd Shapley proposed an ordinal and setvalued solution
concept for zerosum games called \emph{weak saddle}. We show that all weak
saddles of a given zerosum game are interchangeable and equivalent. As a
consequence, every such game possesses a unique setbased value.

In social choice settings with linear preferences, random dictatorship is
known to be the only social decision scheme satisfying strategyproofness and ex
post efficiency. When also allowing indifferences, random serial dictatorship
(RSD) is a wellknown generalization of random dictatorship that retains both
properties. RSD has been particularly successful in the special domain of
random assignment where indifferences are unavoidable. While executing RSD is
obviously feasible, we show that computing the resulting probabilities is
#Pcomplete and thus intractable, both in the context of voting and assignment.

In manytomany matching models, substitutable preferences constitute the
largest domain for which a pairwise stable matching is guaranteed to exist. In
this note, we extend the recently proposed algorithm of Hatfield et al. [3] to
test substitutability of weak preferences. Interestingly, the algorithm is
faster than the algorithm of Hatfield et al. by a linear factor on the domain
of strict preferences.