STSM IC0602-3368, COST Action IC0602, Mirco Gelain
11th September to 10th December 2008, Sydney (Australia)


I worked on the Stable Marriage Problem all the time, under the supervision of the prof. Toby Walsh. This problem consists in matching persons in two disjoint sets of cardinality n. Each parson has a strict ranking of the other group. We want to find a matching that is stable, that is no man-woman pair simultaneously
ranks each other higher than their respective spouses. There is a famous algorithm by Gale and Shapley that finds a stable marriage in polynomial time but the marriage is optimal for one of the two gender. Our aim is to find a gender neutral procedure.
During the first 2-3 weeks investigating the use of some voting rules (that are hard to manipulate) to see if could made a gender neutral hard to manipulate stable marriage procedure.
Then, we focused on local search procedures to solve that problem. We developed some gender neutral algorithms based on the classical local search schema and we did various experiments to see empirically which was the best one. At the end, our best procedure had a time complexity of O(n^4). This is not a great result applied to complete problems that are easy to solve (specially if it is enough a male or a female optimal matching) but we think that it could be good if we consider harder problems, for example with incomplete preference lists and ties. In particular when the ties occur at the tails of lists and on one side only, there is at most one tie per list, and each tie is of length 2, the problem is np-hard. We are now working in this direction.