New algorithms for the allocation of positions problem with double preference list

Abstract

The allocation of positions with double preference
list model [2] is an extension of the Stable Marriage Problem in
which fundamental elements of the basic version of this problem
can be found: two sets of agents and their respective preference
lists. In this extension, the two sets of agents, which are called
positions and applicants in order to fit the new model to the
scenario in which the problem develops, are partitioned into
several subsets, establishing an association between the subsets
of every set.
Each applicant specifies his/her preferences on the preference
list, including elements from the set of positions, some of which
may be vetoed for certain applicants, according to the subset of
the partition of the set of positions to which they belong.
The preference lists of positions are designed on the basis of
master lists. In this new extension, these lists are called rankings.
The main differentiating element with respect to the basic model,
considering these rankings, is that two given applicants from the
same subset are subject to two different rankings, which are not
always consistent.
The hypothesis made in this paper in relation to the rankings as
a tool to assign positions to applicants has lead to three different
models, which have been called JE1, JE2 and JE3. In this paper
the algorithms JE1, JE2 and JE3 are presented, which solve
these variants, establishing the optimal allocations in every case.
Undoubtedly, the third one allows a more clear perception of all
the features of the double ranking, and the lack of consistencies.