DOI: 10.5176/2251-3388_1.1.9
Authors: Eduardo Ramos M´endez and Jos´e Antonio Carrillo Ruiz
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.
Keywords: Stable marriage, Double preference list, Algorithm.
Updating...