Two-Sided Matching for mentor-mentee allocations—Algorithms and manipulation strategies

In scenarios where allocations are determined by participant’s preferences, Two-Sided Matching is a well-established approach with applications in College Admissions, School Choice, and Mentor-Mentee matching problems. In such a context, participants in the matching have preferences with whom they want to be matched with. This article studies two important concepts in Two-Sided Matching: multiple objectives when finding a solution, and manipulation of preferences by participants. We use real data sets from a Mentor-Mentee program for the evaluation to provide insight on realistic effects and implications of the two concepts. In the first part of the article, we consider the quality of solutions found by different algorithms using a variety of solution criteria. Most current algorithms focus on one criterion (number of participants matched), while not directly taking into account additional objectives. Hence, we evaluate different algorithms, including multi-objective heuristics, and the resulting trade-offs. The evaluation shows that existing algorithms for the considered problem sizes perform similarly well and close to the optimal solution, yet multi-objective heuristics provide the additional benefit of yielding solutions with better quality on multiple criteria. In the second part, we consider the effects of different types of preference manipulation on the participants and the overall solution. Preference manipulation is a concept that is well established in theory, yet its practical effects on the participants and the solution quality are less clear. Hence, we evaluate the effects of three manipulation strategies on the participants and the overall solution quality, and investigate if the effects depend on the used solution algorithm as well.