address the Stable Roommates Problem introduced by Gale and Shapley .
Irving  resolved a question raised by Knuth  and obtained a
polynomial-time algorithm, that determines if a stable matching exists for a
given problem and constructs one when the answer is positive. Irving's
algorithm considers instances when the number of agents is even and any agent
prefers all the other agents than to be single. We simplify Irving's algorithm
and extend it to fit the general case, when the number of agents is arbitrary
and preferences are partial. We use the extended algorithm as a basis for
developing other polynomial-time algorithms, which address several problems:
(i) List all the possible stable partners of a given agent, (ii) Splitting the
set of agents in a given Stable Roommates Problem into those that can be
matched in a stable way and those that their presence disrupts stability and
(iii) Exploring truth revelations and the existence of a mechanism that
enforces truth revelations in the Stable Roommates Problem.
We also show
that Pareto-optimal matching, a notion introduced by Morrill , always
exists for the general case of the Roommates Problem and introduce an extended
polynomial-time algorithm, which determines if a given Roommates matching is
Pareto-optimal and if it is not, modifies it to be one. Here, again, we extend
results (of Morrill), who considered the special case when the number of agents
is even and any agent prefers all the other agents than to be single.