
We consider social welfare functions that satisfy Arrow's classic axioms of
independence of irrelevant alternatives and Pareto optimality when the outcome
space is the convex hull of some finite set of alternatives. Individual and
collective preferences are assumed to be continuous and convex, which
guarantees the existence of maximal elements and the consistency of choice
functions that return these elements, even without insisting on transitivity.
We provide characterizations of both the domains of preferences and the social
welfare functions that allow for anonymous Arrovian aggregation. The domains
admit arbitrary preferences over alternatives, which completely determine an
agent's preferences over all mixed outcomes. On these domains, Arrow's
impossibility turns into a complete characterization of a unique social welfare
function, which can be readily applied in settings involving divisible
resources such as probability, time, or money.

Two important requirements when aggregating the preferences of multiple
agents are that the outcome should be economically efficient and the
aggregation mechanism should not be manipulable. In this paper, we provide a
computeraided proof of a sweeping impossibility using these two conditions for
randomized aggregation mechanisms. More precisely, we show that every efficient
aggregation mechanism can be manipulated for all expected utility
representations of the agents' preferences. This settles an open problem and
strengthens a number of existing theorems, including statements that were shown
within the special domain of assignment. Our proof is obtained by formulating
the claim as a satisfiability problem over predicates from realvalued
arithmetic, which is then checked using an SMT (satisfiability modulo theories)
solver. In order to verify the correctness of the result, a minimal
unsatisfiable set of constraints returned by the SMT solver was translated back
into a proof in higherorder logic, which was automatically verified by an
interactive theorem prover. To the best of our knowledge, this is the first
application of SMT solvers in computational social choice.

Given a skewsymmetric matrix, the corresponding twoplayer symmetric
zerosum game is defined as follows: one player, the row player, chooses a row
and the other player, the column player, chooses a column. The payoff of the
row player is given by the corresponding matrix entry, the column player
receives the negative of the row player. A randomized strategy is optimal if it
guarantees an expected payoff of at least 0 for a player independently of the
strategy of the other player. We determine the probability that an optimal
strategy randomizes over a given set of actions when the game is drawn from a
distribution that satisfies certain regularity conditions. The regularity
conditions are quite general and apply to a wide range of natural
distributions.

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.

Two fundamental axioms in social choice theory are consistency with respect
to a variable electorate and consistency with respect to components of similar
alternatives. In the context of traditional nonprobabilistic social choice,
these axioms are incompatible with each other. We show that in the context of
probabilistic social choice, these axioms uniquely characterize a function
proposed by Fishburn (Rev. Econ. Stud., 51(4), 683692, 1984). Fishburn's
function returns socalled maximal lotteries, i.e., lotteries that correspond
to optimal mixed strategies of the underlying plurality game. Maximal lotteries
are guaranteed to exist due to von Neumann's Minimax Theorem, are almost always
unique, and can be efficiently computed using linear programming.

Random dictatorship has been characterized as the only social decision scheme
that satisfies efficiency and strategyproofness when individual preferences are
strict. We show that no extension of random dictatorship to weak preferences
satisfies these properties, even when significantly weakening the required
degree of strategyproofness.

We consider randomized mechanisms with optional participation. Preferences
over lotteries are modeled using skewsymmetric bilinear (SSB) utility
functions, a generalization of classic von NeumannMorgenstern utility
functions. We show that every welfaremaximizing mechanism entices
participation and that the converse holds under additional assumptions. Two
important corollaries of our results are characterizations of an attractive
randomized voting rule that satisfies Condorcetconsistency and entices
participation. This stands in contrast to a wellknown result by Moulin (1988),
who proves that no deterministic voting rule can satisfy both properties
simultaneously.

The purpose of this note is to prove the existence of a randomized mechanism,
a social decision scheme (SDS), with desirable fairness, efficiency, and
strategyproofness properties unmatched by all known SDSs. In particular, we
disprove a conjecture by Aziz et al. (2013). Additionally, we obtain a strong
existence result for the domain of random assignment. Both, the notion of
efficiency and strategyproofness are based on stochastic dominance and have
been studied extensively for random assignment. The proof makes crucial use of
Brouwer's fixedpoint theorem and is hence nonconstructive. To the best of our
knowledge, this is the first application of a fixedpoint theorem to show the
existence of a social choice function or mechanism.

In this paper, we examine \emph{hedonic coalition formation games} in which
each player's preferences over partitions of players depend only on the members
of his coalition. We present three main results in which restrictions on the
preferences of the players guarantee the existence of stable partitions for
various notions of stability. The preference restrictions pertain to \emph{top
responsiveness} and \emph{bottom responsiveness} which model optimistic and
pessimistic behavior of players respectively. The existence results apply to
natural subclasses of \emph{additive separable hedonic games} and \emph{hedonic
games with \Bpreferences}. It is also shown that our existence results cannot
be strengthened to the case of stronger known stability concepts.