Stable marriage and genetic algorithms: A fertile union

We describe a pair of genetic algorithms for solving two stable matching problems. Both stable matching problems we will consider involve a set of applicants for positions and a set of employers. Each applicant and each employer prepares a rank order list of a subset of the actors in the other set. The goal is to find an assignment of applicants to employers in which if applicant a is not assigned to employer b then either a prefers his assignment to b or b prefers its assignment to a. In other words, no applicant/employer pair can both improve their situations by dropping their current assignments in favor of each other. Our goal will be to enumerate the stable matchings. One of the problems we will consider is the well-known stable marriage problem, in which neither applicant nor employer preference lists are linked. In the other problem, we will allow pairs of applicants who form a couple to submit joint rank order lists of ordered pairs of employers.