Problema del matrimonio stabile

In Matematica, Economia e Informatica, il problema del matrimonio stabile o problema dell'abbinamento stabile è il problema di trovare un abbinamento stabile tra gli elementi di due insiemi di cardinalità uguale, dato un certo ordine di preferenze per ogni elemento. Un abbinamento è stabile se non esistono coppie, in base all'ordinamento scelto, che sarebbero meglio assortite. In altre parole, l'abbinamento (a,b), con a elemento dell'insieme A e b elemento dell'insieme B, non è stabile se:

1. a sarebbe meglio abbinato con un elemento di B diverso da b
2. b sarebbe meglio abbinato con un elemento di A diverso da a.

Il nome deriva dalla possibilità di formularlo in termini di coppie uomo-donna come segue:

Dati n uomini e n donne, dove ogni persona ha classificato tutti i membri del sesso opposto in ordine di preferenza, far sposare tra loro gli uomini e le donne in modo tale che non ci siano due persone di sesso opposto che preferirebbero avere un altro partner, piuttosto che il loro attuale. Quando tutte le coppie soddisfano queste condizioni, l'insieme dei matrimoni è considerato stabile.