A volte la matematica può mostrare con chiarezza che le discussioni ideologiche, quando non basate su chiari presupposti, possono essere non solo sterili, ma controproducenti. La teoria dei giochi, una parte moderna e interessante della matematica, propone da questo punto di vista esempi illuminanti. Eccone uno, molto famoso. Riguarda il problema di formare, da due gruppi di agenti distinti, a seconda delle loro preferenze, delle coppie.
Ad esempio, consideriamo i due insiemi, chiamati D(onne) e U(omini) rispettivamente, i quali desiderano formare coppie. Ogni elemento di un gruppo ha delle preferenze sugli elementi dell’altro gruppo. Vediamo un caso semplice: D={Anna, Elena, Ilaria}, U={Filippo, Giovanni, Marco}. Il problema consiste nel formare coppie in maniera “ottimale”. Ma che significa ottimale? Un criterio logico è quello di formare coppie stabili. Per capire, sviluppiamo l’esempio precedente, supponendo le seguenti preferenze:

È opportuno suggerire l’insieme di accoppiamenti {(AM),(EF),(IG)}? Ovviamente no! Elena e Giovanni (o anche Giovanni e Anna) romperanno le loro coppie per mettersi assieme: naturalmente non hanno bisogno del permesso dei loro partners… Ecco allora apparire in maniera naturale l’idea di insieme stabile.
Un insieme è stabile, cioè rappresenta una soluzione del problema, se chiunque sia interessato a rompere la propria coppia riceverà un rifiuto.
Stabilito questo, si tratta di capire se una soluzione esiste sempre, a partire da un qualunque sistema di preferenze e numero di persone. La risposta è positiva, non solo ma è possibile suggerire una procedura concreta per arrivare alla soluzione. Ecco l’algoritmo:
Al primo passo, diciamo la prima sera,
ogni donna si reca in casa dell’uomo preferito.
Quindi, nel nostro esempio,
Anna da Filippo
Elena e Ilaria da Giovanni.

Chi si trova con più di una scelta, tiene la sua preferita, e rifiuta le altre. Chi viene rifiutata, va al passo successivo. Se tutti risultano accoppiati, l’algoritmo termina.
Quindi dopo la prima sera
Anna con Filippo
Elena con Giovanni
Ilaria a spasso, Marco da solo.

Secondo passo, cioè seconda sera.
Chi è stata rifiutata, va a visitare la sua scelta successiva. Se un uomo si trova con più di una scelta, comprendendo eventualmente quella fatta precedentemente, tiene la sua preferita, e rifiuta le altre.
Quindi dopo la seconda sera:
Ilaria con Filippo
Elena con Giovanni
Anna a spasso, Marco da solo.
Al passo successivo Anna va da Giovanni, che caccia Elena, al terzo passo Elena va da Marco, e l’algoritmo si ferma. Soluzione {(EM),(AG),(IF)}.

È facile capire che si è trovato un insieme stabile. Anzi, in generale così se ne trovano due. Infatti se si mandano gli uomini in visita, la soluzione di solito è differente (qui {(AG),(EF),(IM)}).
Balza però immediatamente all’occhio l’estrema rudezza della procedura! Infatti, la povera Anna, che era stata accettata da Filippo la prima sera, si vede rifiutata la seconda in favore di Ilaria, e non è che alle altre vada molto meglio! Tutto questo sembra molto, molto scorretto. Che i teorici dei giochi siano persone maleducate? Non è proprio così. Ricordiamoci che occorre trovare un insieme stabile di coppie. Così ci siamo riusciti, con una procedura politicamente più corretta non ci riusciremmo. Ma c’è molto di più. Un risultato, assai semplice da dimostrare, afferma che la procedura precedente assegna a ogni donna la sua prima scelta, ovviamente all’interno dell’insieme degli uomini che sono assegnati a lei in qualche insieme stabile.  La conclusione sembra molto interessante: se vogliamo un risultato ragionevole, dobbiamo forse utilizzare una procedura apparentemente brutale. Ma quel che succede è in realtà che la soluzione così determinata è quella più favorevole, tra le possibili, per un insieme prescelto. Gli autori del modello segnalavano come applicazione possibile il matching degli allievi e delle scuole di dottorato negli Stati Uniti. La procedura di accettazione provvisoria della domanda di uno studente, con possibilità di rifiuto successivo, in realtà rappresenta il servizio migliore che si possa loro offrire. Un’altra applicazione simile, l’assegnazione di medici che devono fare la specialità in vari reparti dell’ospedale.
È possibile generalizzare il modello, supponendo ad esempio che gli insiemi abbiano un numero diverso di elementi, e che a un certo punto uno degli agenti preferisca rimanere solo piuttosto che inserito in una coppia. I risultati non variano molto. Inoltre, è possibile considerare situazioni simili ma non identiche, come ad esempio quella di una casa dello studente che ha camere doppie e deve sistemare i ragazzi che sono stati accettati. Invitiamo chi vuole a dirci come trovare la soluzione in questo caso, ovviamente nel caso ci sia sempre una soluzione!

di Roberto Lucchetti