
Many important stable matching problems are known to be NPhard, even when
strong restrictions are placed on the input. In this paper we seek to identify
structural properties of instances of stable matching problems which will allow
us to design efficient algorithms using elementary techniques. We focus on the
setting in which all agents involved in some matching problem can be
partitioned into k different types, where the type of an agent determines his
or her preferences, and agents have preferences over types (which may be
refined by more detailed preferences within a single type). This situation
would arise in practice if agents form preferences solely based on some small
collection of agents' attributes. We also consider a generalisation in which
each agent may consider some small collection of other agents to be
exceptional, and rank these in a way that is not consistent with their types;
this could happen in practice if agents have prior contact with a small number
of candidates. We show that (for the case without exceptions), several
wellstudied NPhard stable matching problems including Max SMTI (that of
finding the maximum cardinality stable matching in an instance of stable
marriage with ties and incomplete lists) belong to the parameterised complexity
class FPT when parameterised by the number of different types of agents needed
to describe the instance. For Max SMTI this tractability result can be extended
to the setting in which each agent promotes at most one `exceptional' candidate
to the top of his/her list (when preferences within types are not refined), but
the problem remains NPhard if preference lists can contain two or more
exceptions and the exceptional candidates can be placed anywhere in the
preference lists, even if the number of types is bounded by a constant.

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 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.

The stable marriage problem and its extensions have been extensively studied,
with much of the work in the literature assuming that agents fully know their
own preferences over alternatives. This assumption however is not always
practical (especially in large markets) and agents usually need to go through
some costly deliberation process in order to learn their preferences. In this
paper we assume that such deliberations are carried out via interviews, where
an interview involves a man and a woman, each of whom learns information about
the other as a consequence. If everybody interviews everyone else, then clearly
agents can fully learn their preferences. But interviews are costly, and we may
wish to minimize their use. It is often the case, especially in practical
settings, that due to correlation between agents' preferences, it is
unnecessary for all potential interviews to be carried out in order to obtain a
stable matching. Thus the problem is to find a good strategy for interviews to
be carried out in order to minimize their use, whilst leading to a stable
matching. One way to evaluate the performance of an interview strategy is to
compare it against a naive algorithm that conducts all interviews. We argue
however that a more meaningful comparison would be against an optimal offline
algorithm that has access to agents' preference orderings under complete
information. We show that, unless P=NP, no offline algorithm can compute the
optimal interview strategy in polynomial time. If we are additionally aiming
for a particular stable matching (perhaps one with certain desirable
properties), we provide restricted settings under which efficient optimal
offline algorithms exist.

We consider Paretooptimal matchings (POMs) in a manytomany market of
applicants and courses where applicants have preferences, which may include
ties, over individual courses and lexicographic preferences over sets of
courses. Since this is the most general setting examined so far in the
literature, our work unifies and generalizes several known results.
Specifically, we characterize POMs and introduce the \emph{Generalized Serial
Dictatorship Mechanism with Ties (GSDT)} that effectively handles ties via
properties of network flows. We show that GSDT can generate all POMs using
different priority orderings over the applicants, but it satisfies truthfulness
only for certain such orderings. This shortcoming is not specific to our
mechanism; we show that any mechanism generating all POMs in our setting is
prone to strategic manipulation. This is in contrast to the onetoone case
(with or without ties), for which truthful mechanisms generating all POMs do
exist.

We study the House Allocation problem (also known as the Assignment problem),
i.e., the problem of allocating a set of objects among a set of agents, where
each agent has ordinal preferences (possibly involving ties) over a subset of
the objects. We focus on truthful mechanisms without monetary transfers for
finding large Pareto optimal matchings. It is straightforward to show that no
deterministic truthful mechanism can approximate a maximum cardinality Pareto
optimal matching with ratio better than 2. We thus consider randomised
mechanisms. We give a natural and explicit extension of the classical Random
Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation
problem where preference lists can include ties. We thus obtain a universally
truthful randomised mechanism for finding a Pareto optimal matching and show
that it achieves an approximation ratio of $\frac{e}{e1}$. The same bound
holds even when agents have priorities (weights) and our goal is to find a
maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On
the other hand we give a lower bound of $\frac{18}{13}$ on the approximation
ratio of any universally truthful Pareto optimal mechanism in settings with
strict preferences. In the case that the mechanism must additionally be
nonbossy with an additional technical assumption, we show by utilising a
result of Bade that an improved lower bound of $\frac{e}{e1}$ holds. This
lower bound is tight since RSDM for strict preference lists is nonbossy. We
moreover interpret our problem in terms of the classical secretary problem and
prove that our mechanism provides the best randomised strategy of the
administrator who interviews the applicants.