Stable marriage and genetic algorithms: A fertile union

We describe a pair of genetic algorithms for solving two stable matching pr oblems. Both stable matching problems we will consider involve a set of app licants for positions and a set of employers. Each applicant and each emplo yer 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 ap plicant a is not assigned to employer b then either a prefers his assignmen t to b or b prefers its assignment to a. In other words, no applicant/emplo yer pair can both improve their situations by dropping their current assign ments in favor of each other. Our goal will be to enumerate the stable matc hings. One of the problems we will consider is the well-known stable marriage prob lem, in which neither applicant nor employer preference lists are linked. I n the other problem, we will allow pairs of applicants who form a couple to submit joint rank order lists of ordered pairs of employers.