
We prove that every Condorcetconsistent voting rule can be manipulated by a
voter who completely reverses their preference ranking, assuming that there are
at least 4 alternatives. This corrects an error and improves a result of
[Sanver, M. R. and Zwicker, W. S. (2009). Oneway monotonicity as a form of
strategyproofness. Int J Game Theory 38(4), 553574.] For the case of
precisely 4 alternatives, we exactly characterise the number of voters for
which this impossibility result can be proven. We also show analogues of our
result for irresolute voting rules. We then leverage our result to state a
strong form of the GibbardSatterthwaite Theorem.

We consider fair allocation of indivisible items under an additional
constraint: there is an undirected graph describing the relationship between
the items, and each agent's share must form a connected subgraph of this graph.
This framework captures, e.g., fair allocation of land plots, where the graph
describes the accessibility relation among the plots. We focus on agents that
have additive utilities for the items, and consider several common fair
division solution concepts, such as proportionality, envyfreeness and maximin
share guarantee. While finding good allocations according to these solution
concepts is computationally hard in general, we design efficient algorithms for
special cases where the underlying graph has simple structure, and/or the
number of agents or, less restrictively, the number of agent types is small.
In particular, despite nonexistence results in the general case, we prove that
for acyclic graphs a maximin share allocation always exists and can be found
efficiently.

Hedonic games provide a general model of coalition formation, in which a set
of agents is partitioned into coalitions, with each agent having preferences
over which other players are in her coalition. We prove that with additively
separable preferences, it is $\Sigma_2^p$complete to decide whether a core or
strictcorestable partition exists, extending a result of Woeginger (2013).
Our result holds even if valuations are symmetric and nonzero only for a
constant number of other agents. We also establish $\Sigma_2^p$completeness of
deciding nonemptiness of the strict core for hedonic games with dichotomous
preferences. Such results establish that the core is much less tractable than
solution concepts such as individual stability.

The work we present in this paper initiated the formal study of fractional
hedonic games, coalition formation games in which the utility of a player is
the average value he ascribes to the members of his coalition. Among other
settings, this covers situations in which players only distinguish between
friends and nonfriends and desire to be in a coalition in which the fraction
of friends is maximal. Fractional hedonic games thus not only constitute a
natural class of succinctly representable coalition formation games, but also
provide an interesting framework for network clustering. We propose a number of
conditions under which the core of fractional hedonic games is nonempty and
provide algorithms for computing a core stable outcome. By contrast, we show
that the core may be empty in other cases, and that it is computationally hard
in general to decide nonemptiness of the core.

Many hardness results in computational social choice make use of the fact
that every directed graph may be induced as the pairwise majority relation of
some preference profile. However, this fact requires a number of voters that is
almost linear in the number of alternatives. It is therefore unclear whether
these results remain intact when the number of voters is bounded, as is, for
example, typically the case in search engine aggregation settings. In this
paper, we provide a systematic study of majority digraphs for a constant number
of voters resulting in analytical, experimental, and complexitytheoretic
insights. First, we characterize the set of digraphs that can be induced by two
and three voters, respectively, and give sufficient conditions for larger
numbers of voters. Second, we present a surprisingly efficient implementation
via SAT solving for computing the minimal number of voters that is required to
induce a given digraph and experimentally evaluate how many voters are required
to induce the majority digraphs of realworld and generated preference
profiles. Finally, we leverage our sufficient conditions to show that the
winner determination problem of various wellknown voting rules remains hard
even when there is only a small constant number of voters. In particular, we
show that Kemeny's rule is hard to evaluate for 7 voters, while previous
methods could only establish such a result for constant even numbers of voters.

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 propose a new variant of the group activity selection problem (GASP),
where the agents are placed on a social network and activities can only be
assigned to connected subgroups. We show that if multiple groups can
simultaneously engage in the same activity, finding a stable outcome is easy as
long as the network is acyclic. In contrast, if each activity can be assigned
to a single group only, finding stable outcomes becomes intractable, even if
the underlying network is very simple: the problem of determining whether a
given instance of a GASP admits a Nash stable outcome turns out to be NPhard
when the social network is a path, a star, or if the size of each connected
component is bounded by a constant. On the other hand, we obtain
fixedparameter tractability results for this problem with respect to the
number of activities.

Many NPhard winner determination problems admit polynomialtime algorithms
when restricting inputs to be singlepeaked. Commonly, such algorithms employ
dynamic programming along the underlying axis. We introduce a new technique:
carefully chosen integer linear programming (IP) formulations for certain
voting problems admit an LP relaxation which is totally unimodular if
preferences are singlepeaked, and which thus admits an integral optimal
solution. This technique gives fast algorithms for finding optimal committees
under the PAV and ChamberlinCourant voting rules under singlepeaked
preferences, as well as for certain OWAbased rules. Under singlecrossing
preferences, Young scores can also be calculated. An advantage of this
technique is that no specialpurpose algorithm needs to be used to exploit
structure in the input preferences: any standard IP solver will terminate in
the first iteration if the input is singlepeaked, and will continue to work
otherwise.

We propose a model of interdependent scheduling games in which each player
controls a set of services that they schedule independently. A player is free
to schedule his own services at any time; however, each of these services only
begins to accrue reward for the player when all predecessor services, which may
or may not be controlled by the same player, have been activated. This model,
where players have interdependent services, is motivated by the problems faced
in planning and coordinating largescale infrastructures, e.g., restoring
electricity and gas to residents after a natural disaster or providing medical
care in a crisis when different agencies are responsible for the delivery of
staff, equipment, and medicine. We undertake a gametheoretic analysis of this
setting and in particular consider the issues of welfare maximization,
computing best responses, Nash dynamics, and existence and computation of Nash
equilibria.

Voting rules allow multiple agents to aggregate their preferences in order to
reach joint decisions. Perhaps one of the most important desirable properties
in this context is Condorcetconsistency, which requires that a voting rule
should return an alternative that is preferred to any other alternative by some
majority of voters. Another desirable property is participation, which requires
that no voter should be worse off by joining an electorate. A seminal result in
social choice theory by Moulin (1998) has shown that Condorcetconsistency and
participation are incompatible whenever there are at least 4 alternatives and
25 voters. We leverage SAT solving to obtain an elegant humanreadable proof of
Moulin's result that requires only 12 voters. Moreover, the SAT solver is able
to construct a Condorcetconsistent voting rule that satisfies participation as
well as a number of other desirable properties for up to 11 voters, proving the
optimality of the above bound. We also obtain tight results for setvalued and
probabilistic voting rules, which complement and significantly improve existing
theorems.

Euclidean preferences are a widely studied preference model, in which
decision makers and alternatives are embedded in ddimensional Euclidean space.
Decision makers prefer those alternatives closer to them. This model, also
known as multidimensional unfolding, has applications in economics,
psychometrics, marketing, and many other fields. We study the problem of
deciding whether a given preference profile is dEuclidean. For the
onedimensional case, polynomialtime algorithms are known. We show that, in
contrast, for every other fixed dimension d > 1, the recognition problem is
equivalent to the existential theory of the reals (ETR), and so in particular
NPhard. We further show that some Euclidean preference profiles require
exponentially many bits in order to specify any Euclidean embedding, and prove
that the domain of dEuclidean preferences does not admit a finite forbidden
minor characterisation for any d > 1. We also study dichotomous preferencesand
the behaviour of other metrics, and survey a variety of related work.

Hedonic games provide a natural model of coalition formation among
selfinterested agents. The associated problem of finding stable outcomes in
such games has been extensively studied. In this paper, we identify simple
conditions on expressivity of hedonic games that are sufficient for the problem
of checking whether a given game admits a stable outcome to be computationally
hard. Somewhat surprisingly, these conditions are very mild and intuitive. Our
results apply to a wide range of stability concepts (core stability, individual
stability, Nash stability, etc.) and to many known formalisms for hedonic games
(additively separable games, games with Wpreferences, fractional hedonic
games, etc.), and unify and extend known results for these formalisms. They
also have broader applicability: for several classes of hedonic games whose
computational complexity has not been explored in prior work, we show that our
framework immediately implies a number of hardness results for them.