
Ranking alternatives is a natural way for humans to explain their
preferences. It is being used in many settings, such as school choice, course
allocations and residency matches. In some cases, several `items' are given to
each participant. Without having any information on the underlying cardinal
utilities, arguing about fairness of allocation requires extending the ordinal
item ranking to ordinal bundle ranking. The most commonly used such extension
is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if
its score is better according to all additive score functions. SD is a very
conservative extension, by which few allocations are necessarily fair while
many allocations are possibly fair. We propose to make a natural assumption on
the underlying cardinal utilities of the players, namely that the difference
between two items at the top is larger than the difference between two items at
the bottom. This assumption implies a preference extension which we call
diminishing differences (DD), where X is preferred over Y if its score is
better according to all additive score functions satisfying the DD assumption.
We give a full characterization of allocations that are
necessarilyproportional or possiblyproportional according to this assumption.
Based on this characterization, we present a polynomialtime algorithm for
finding a necessarilyDDproportional allocation if it exists. Using
simulations, we show that with high probability, a necessarilyproportional
allocation does not exist but a necessarilyDDproportional allocation exists,
and moreover, that allocation is proportional according to the underlying
cardinal utilities. We also consider chore allocation under the analogous
condition  increasingdifferences.

Proportional representation (PR) is often discussed in voting settings as a
major desideratum. For the past century or so, it is common both in practice
and in the academic literature to jump to single transferable vote (STV) as the
solution for achieving PR. Some of the most prominent electoral reform
movements around the globe are pushing for the adoption of STV. It has been
termed a major open problem to design a voting rule that satisfies the same PR
properties as STV and better monotonicity properties. In this paper, we first
present a taxonomy of proportional representation axioms for general weak order
preferences, some of which generalise and strengthen previously introduced
concepts. We then present a rule called Expanding Approvals Rule (EAR) that
satisfies properties stronger than the central PR axiom satisfied by STV, can
handle indifferences in a convenient and computationally efficient manner, and
also satisfies better candidate monotonicity properties. In view of this, our
proposed rule seems to be a compelling solution for achieving proportional
representation in voting settings.

The housing market setting constitutes a fundamental model of exchange
economies of goods. Most of the work concerning housing markets does not cater
for randomized assignments or allocation of timeshares. House allocation with
fractional endowments of houses was considered by Athanassoglou and Sethuraman
(2011) who posed the open problem whether individual rationality, weak
strategyproofness, and efficiency are compatible for the setting. We show that
the three axioms are incompatible.

Reallocating resources to get mutually beneficial outcomes is a fundamental
problem in various multiagent settings. While finding an arbitrary Pareto
optimal allocation is generally easy, checking whether a particular allocation
is Pareto optimal can be much more difficult. This problem is equivalent to
checking that the allocated objects cannot be reallocated in such a way that at
least one agent prefers her new share to his old one, and no agent prefers her
old share to her new one. We consider the problem for two related types of
preference relations over sets of objects. In the first part of the paper we
focus on the setting in which agents express additive cardinal utilities over
objects. We present computational hardness results as well as polynomialtime
algorithms for testing Pareto optimality under different restrictions such as
two utility values or lexicographic utilities. In the second part of the paper
we assume that agents express only their (ordinal) preferences over single
objects, and that their preferences are additively separable. In this setting,
we present characterizations and polynomialtime algorithms for possible and
necessary Pareto optimality.

Committee selection with diversity or distributional constraints is a
ubiquitous problem. However, many of the formal approaches proposed so far have
certain drawbacks including (1) computationally intractability in general, and
(2) inability to suggest a solution for certain instances where the hard
constraints cannot be met. We propose a practical and polynomialtime algorithm
for diverse committee selection that draws on the idea of using soft bounds and
satisfies natural axioms.

Selecting a set of alternatives based on the preferences of agents is an
important problem in committee selection and beyond. Among the various criteria
put forth for the desirability of a committee, Pareto optimality is a minimal
and important requirement. As asking agents to specify their preferences over
exponentially many subsets of alternatives is practically infeasible, we assume
that each agent specifies a weak order on single alternatives, from which a
preference relation over subsets is derived using some preference extension. We
consider five prominent extensions (responsive, downward lexicographic, upward
lexicographic, best, and worst). For each of them, we consider the
corresponding Pareto optimality notion, and we study the complexity of
computing and verifying Pareto optimal outcomes. We also consider strategic
issues: for four of the set extensions, we present a lineartime, Pareto
optimal and strategyproof algorithm that even works for weak preferences.

Proportional representation (PR) is one of the central principles in voting.
Elegant rules with compelling PR axiomatic properties have the potential to be
adopted for several important collective decision making settings. I survey
some recent ideas and results on axioms and rules for proportional
representation in committee voting.

Peer reviews, evaluations, and selections are a fundamental aspect of modern
science. Funding bodies the world over employ experts to review and select the
best proposals from those submitted for funding. The problem of peer selection,
however, is much more general: a professional society may want to give a subset
of its members awards based on the opinions of all members; an instructor for a
Massive Open Online Course (MOOC) or an online course may want to crowdsource
grading; or a marketing company may select ideas from group brainstorming
sessions based on peer evaluation.
We make three fundamental contributions to the study of peer selection, a
specific type of group decisionmaking problem, studied in computer science,
economics, and political science. First, we propose a novel mechanism that is
strategyproof, i.e., agents cannot benefit by reporting insincere valuations.
Second, we demonstrate the effectiveness of our mechanism by a comprehensive
simulationbased comparison with a suite of mechanisms found in the literature.
Finally, our mechanism employs a randomized rounding technique that is of
independent interest, as it solves the apportionment problem that arises in
various settings where discrete resources such as parliamentary representation
slots need to be divided proportionally.

We consider the wellstudied cake cutting problem in which the goal is to
find an envyfree allocation based on queries from $n$ agents. The problem has
received attention in computer science, mathematics, and economics. It has been
a major open problem whether there exists a discrete and bounded envyfree
protocol. We resolve the problem by proposing a discrete and bounded envyfree
protocol for any number of agents. The maximum number of queries required by
the protocol is $n^{n^{n^{n^{n^n}}}}$. We additionally show that even if we do
not run our protocol to completion, it can find in at most $n^3{(n^2)}^n$
queries a partial allocation of the cake that achieves proportionality (each
agent gets at least $1/n$ of the value of the whole cake) and envyfreeness.
Finally we show that an envyfree partial allocation can be computed in at most
$n^3{(n^2)}^n$ queries such that each agent gets a connected piece that gives
the agent at least $1/(3n)$ of the value of the whole cake.

We consider stability concepts for random matchings where agents have
preferences over objects and objects have priorities for the agents. When
matchings are deterministic, the standard stability concept also captures the
fairness property of no (justified) envy. When matchings can be random, there
are a number of natural stability / fairness concepts that coincide with
stability / no envy whenever matchings are deterministic. We formalize known
stability concepts for random matchings for a general setting that allows weak
preferences and weak priorities, unacceptability, and an unequal number of
agents and objects. We then present a clear taxonomy of the stability concepts
and identify logical relations between them. Furthermore, we provide no envy /
claims interpretations for some of the stability concepts that are based on a
consumption process interpretation of random matchings. Finally, we present a
transformation from the most general setting to the most restricted setting,
and show how almost all our stability concepts are preserved by that
transformation.

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.

Sequential allocation is a simple mechanism for sharing multiple indivisible
items. We study strategic behavior in sequential allocation. In particular, we
consider Nash dynamics, as well as the computation and Pareto optimality of
pure equilibria, and Stackelberg strategies. We first demonstrate that, even
for two agents, better responses can cycle. We then present a lineartime
algorithm that returns a profile (which we call the "bluff profile") that is in
pure Nash equilibrium. Interestingly, the outcome of the bluff profile is the
same as that of the truthful profile and the profile is in pure Nash
equilibrium for \emph{all} cardinal utilities consistent with the ordinal
preferences. We show that the outcome of the bluff profile is Pareto optimal
with respect to pairwise comparisons. In contrast, we show that an assignment
may not be Pareto optimal with respect to pairwise comparisons even if it is a
result of a preference profile that is in pure Nash equilibrium for all
utilities consistent with ordinal preferences. Finally, we present a dynamic
program to compute an optimal Stackelberg strategy for two agents, where the
second agent has a constant number of distinct values for the items.

When aggregating preferences of agents via voting, two desirable goals are to
incentivize agents to participate in the voting process and then identify
outcomes that are Pareto efficient. We consider participation as formalized by
Brandl, Brandt, and Hofbauer (2015) based on the stochastic dominance (SD)
relation. We formulate a new rule called RMEC (Rank Maximal Equal Contribution)
that satisfies the strongest notion of participation and is also ex post
efficient. The rule is polynomialtime computable and also satisfies many other
desirable fairness properties. The rule suggests a general approach to
achieving ex post efficiency and very strong participation.

We consider a committee voting setting in which each voter approves of a
subset of candidates and based on the approvals, a target number of candidates
are to be selected. In particular we focus on the axiomatic property called
extended justified representation (EJR). Although a committee satisfying EJR is
guaranteed to exist, the computational complexity of finding such a committee
has been an open problem and explicitly mentioned in multiple recent papers. We
settle the complexity of finding a committee satisfying EJR by presenting a
polynomialtime algorithm for the problem. Our algorithmic approach may be
useful for constructing other voting rules in multiwinner voting.

We consider a committee voting setting in which each voter approves of a
subset of candidates and based on the approvals, a target number of candidates
are selected. Aziz et al. (2015) proposed two representation axioms called
justified representation and extended justified representation. Whereas the
former can be tested as well as achieved in polynomial time, the latter
property is coNPcomplete to test and no polynomialtime algorithm is known to
achieve it. Interestingly, S{\'a}nchezFern{\'a}ndez et~al. (2016) proposed an
intermediate property called proportional justified representation that admits
a polynomialtime algorithm to achieve. The complexity of testing proportional
justified representation has remained an open problem. In this paper, we settle
the complexity by proving that testing proportional justified representation is
coNPcomplete. We complement the complexity result by showing that the problem
admits efficient algorithms if any of the following parameters are bounded: (1)
number of voters (2) number of candidates (3) maximum number of candidates
approved by a voter (4) maximum number of voters approving a given candidate.

The Adjusted Winner procedure is an important fair division mechanism
proposed by Brams and Taylor for allocating goods between two parties. It has
been used in practice for divorce settlements and analyzing political disputes.
Assuming truthful declaration of the valuations, it computes an allocation that
is envyfree, equitable and Pareto optimal.
We show that Adjusted Winner admits several elegant characterizations, which
further shed light on the outcomes reached with strategic agents. We find that
the procedure may not admit pure Nash equilibria in either the discrete or
continuous variants, but is guaranteed to have $\epsilon$Nash equilibria for
each $\epsilon$ > 0. Moreover, under informed tiebreaking, exact pure Nash
equilibria always exist, are Pareto optimal, and their social welfare is at
least 3/4 of the optimal.

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.

When aggregating preferences of agents via voting, two desirable goals are to
identify outcomes that are Pareto optimal and to incentivize agents to
participate in the voting process. We consider participation notions as
formalized by Brandl, Brandt, and Hofbauer (2015) and study how far efficiency
and participation are achievable by randomized social choice functions in
particular when agents' preferences are downward lexicographic (DL) or satisfy
stochastic dominance (SD). Our results include the followings ones: we prove
formal relations between the participation notions with respect to SD and DL
and we show that the maximal recursive rule satisfies very strong participation
with respect to both SD and DL.

The assignment problem is one of the most wellstudied settings in social
choice, matching, and discrete allocation. We consider the problem with the
additional feature that agents' preferences involve uncertainty. The setting
with uncertainty leads to a number of interesting questions including the
following ones. How to compute an assignment with the highest probability of
being Pareto optimal? What is the complexity of computing the probability that
a given assignment is Pareto optimal? Does there exist an assignment that is
Pareto optimal with probability one? We consider these problems under two
natural uncertainty models: (1) the lottery model in which each agent has an
independent probability distribution over linear orders and (2) the joint
probability model that involves a joint probability distribution over
preference profiles. For both of the models, we present a number of algorithmic
and complexity results.

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.

We consider the twosided stable matching setting in which there may be
uncertainty about the agents' preferences due to limited information or
communication. We consider three models of uncertainty: (1) lottery model 
in which for each agent, there is a probability distribution over linear
preferences, (2) compact indifference model  for each agent, a weak
preference order is specified and each linear order compatible with the weak
order is equally likely and (3) joint probability model  there is a lottery
over preference profiles. For each of the models, we study the computational
complexity of computing the stability probability of a given matching as well
as finding a matching with the highest probability of being stable. We also
examine more restricted problems such as deciding whether a certainly stable
matching exists. We find a rich complexity landscape for these problems,
indicating that the form uncertainty takes is significant.

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.

We consider house allocation with existing tenants in which each agent has
dichotomous preferences. We present strategyproof, polynomialtime, and
(strongly) individually rational algorithms that satisfy the maximum number of
agents. For the endowment only model, one of the algorithms also returns a
corestable allocation.

A fundamental resource allocation setting is the random assignment problem in
which agents express preferences over objects that are then randomly allocated
to the agents. In 2001, Bogomolnaia and Moulin presented the probabilistic
serial (PS) mechanism that is an anonymous, neutral, Pareto optimal, and weak
strategyproof mechanism when the preferences are considered with respect to
stochastic dominance. The result holds when agents have strict preferences over
individual objects. It has been an open problem whether there exists a
mechanism that satisfies the same properties when agents may have indifference
among the objects. We show that for this more general domain, there exists no
extension of PS that is ex post efficient and weak strategyproof. The result is
surprising because it does not even require additional symmetry or fairness
conditions such as anonymity, neutrality, or equal treatment of equals. Our
result further demonstrates that the lack of weak SDstrategyproofness of the
extended PS mechanism of Katta and Sethuraman (2006) is not a design flaw of
extended PS but is due to an inherent incompatibility of efficiency and
strategyproofness of PS in the full preference domain.

We consider Maxmin Share (MmS) allocations of items both in the case where
items are goods (positive utility) and when they are chores (negative utility).
We show that fair allocations of goods and chores have some fundamental
connections but differences as well. We prove that like in the case for goods,
an MmS allocation does not need to exist for chores and computing an MmS
allocation  if it exists  is strongly NPhard. In view of these nonexistence
and complexity results, we present a polynomialtime 2approximation algorithm
for MmS fairness for chores. We then introduce a new fairness concept called
optimal MmS that represents the best possible allocation in terms of MmS that
is guaranteed to exist. For both goods and chores, we use connections to
parallel machine scheduling to give (1) an exponentialtime exact algorithm and
(2) a polynomialtime approximation scheme for computing an optimal MmS
allocation when the number of agents is fixed.