Algoritmi per un matrimonio stabile

L’idea di ricorrere alla logica e alla matematica per le nostre scelte quotidiane non è nuova. Già nel 1600 Gottfried Wilhelm Leibniz, inventore (con Isaac Newton) del calcolo infinitesimale, auspicava un momento in cui, in caso di controversia, i contendenti avrebbero potuto pacatamente dire «Calculemus!» e risolvere la questione con una manciata di calcoli.
Non è così, purtroppo. Siamo irrazionali e nemmeno molto trasparenti e affidabili, con tutte le conseguenze sulle nostre vicende umane. E così, almeno al momento, non è possibile, ad esempio, poter decidere con un algoritmo logico chi sposare, ed essere certi del buon risultato.
Se, però, si restringe e si precisa il significato di “matrimonio stabile“, applicandolo anche a contesti diversi dalla selezione del partner per la vita, allora risposte efficaci possono arrivare dall’esplorazione del territorio degli algoritmi.

La finalità?

Applicare tali algoritmi all’assegnazione di sedi di lavoro, per soddisfare al meglio i requisiti di tutti gli attori. Chi si interessa di cose della scuola ricorderà il delirio vissuto nel 2015, quando l’algoritmo utilizzato dal ministero generò un’autentica rivolta e portò il TAR del Lazio ad affermare che l’algoritmo impazzito ha fatto assumere decine di migliaia di docenti contro la Costituzione e la Convenzione europea dei diritti dell’uomo.


L’algoritmo impazzito

L’assegnazione di un gran numero di cattedre disperse in Italia ai docenti precari da stabilizzare, anch’essi dispersi in Italia ma in maniera ovviamente differente, sarebbe dovuta avvenire secondo questi criteri:

  • il ministero attribuisce la valutazione dei singoli candidati per legge e dove preferirebbero andare per un massimo di 15 opzioni possibili;
  • l’algoritmo processa i dati dovendo designare per ogni candidato il posto vacante, dando precedenza al voto della valutazione e poi alle 15 opzioni possibili;
  • le controlla una per una, e appena trova il posto libero assegna il nome.

L’operazione faceva parte della riforma delle Buona scuola, insieme ad altre iniziative, come l’insegnamento in classe del coding. Chissà se qualche allieva o allievo ha imparato davvero a programmare.

Cosa accadde in realtà?

Esempio estratto sempre dallo stesso articolo di agi.it:

Alcuni docenti con punteggio per esempio di 100, che avevano messo tra le destinazioni preferite Padova in seconda posizione, sono stati scavalcati da chi con punteggio 90 aveva messo Padova per prima.

Ne scaturirono moltissimi ricorsi, in parte poi risolti con una procedura di conciliazione. Una perizia, effettuata a seguito del ricorso al TAR del Lazio, giudicò severamente la qualità del software, sviluppato da società terze per conto del Ministero, con un costo che appariva elevato.

Il matrimonio stabile

L’esempio dell’assegnazione delle sedi di insegnamento ai docenti precari aiuta a comprendere il senso attribuito in questa sede al termine matrimonio stabile.

Il docente, guardando le varie sedi disponibili, avrà una propria lista di preferenze, che potrebbe anche non essere “più è vicina a casa mia, più mi piace“. E poi, naturalmente, ci sarà un ordine di precedenza tra i docenti nell’esprimere la propria preferenza (le graduatorie servono proprio a questo).

Allo stesso tempo anche le scuole potrebbero esprimere le proprie preferenze. Assumiamo che sia la distanza casa-lavoro il criterio guida in questo caso. In fondo, un docente che abita a pochi chilometri dalla scuola potrebbe essere meno soggetto ad assenze prolungate per motivi di famiglia, rispetto a chi abita ad alcune centinaia di chilometri dalla scuola stessa.

L’algoritmo

Bene, la definizione algoritmica del matrimonio stabile si può esprimere così:

Il matrimonio è stabile se non esiste nessun caso di docente D e sede S, in cui:

  • D è stato assegnato alla sede Sx, ma avrebbe preferito S;
  • S è stata assegnata al docente Dy. ma avrebbe preferito D.

In questo matrimonio, infatti, D ed S si guarderebbero con gli occhi languidi e vivrebbero tristemente l’anno scolastico. Non credo comunque che arriverebbero a consumare l’adulterio, no, questo no.

Una descrizione più rigorosa del matrimonio stabile

La solita Wikipedia espone, in modo più rigoroso ma comunque chiaro, il problema, le applicazioni e gli algoritmi risolutivi.

Cominciamo dalla prima domanda: quale che siano le preferenze degli N docenti e delle N sedi, esiste sempre almeno una soluzione ottimale? La risposta è  e fruttò nel 2012 il Nobel per l’Economia a  Lloyd S. Shapley and Alvin E. Roth.

Attenzione, non è che la soluzione consista nell’assegnare a ogni docente la sede più vicina, questo non sarebbe generalmente possibile, ma nell’assegnare a ogni docente la scuola più vicina che non sia stata già assegnata a un altro docente che abbia maggiore priorità.

L’algoritmo per il matrimonio stabile

Nel 1962 Lloyd Shapley e David Gale misero a punto questo algoritmo (senza ancora dimostrare che portava a una soluzione quale che fossero le preferenze dei singoli componenti):

  1. siano dati due insiemi: M composto da N maschi e F composto da N femmine;
  2. ognuno degli N maschi si propone alla femmina che è in cima alla propria lista di preferenze;
  3. ogni femmina risponderà “può darsi” al suo preferito tra i maschi che si sono proposti, “no” a tutti gli altri proponenti;
  4. tutti i maschi che hanno ricevuto un “no” si propongono alla loro preferenza successiva;
  5. ogni femmina risponderà “può darsi” al maschio che si è proposto ed è posizionato meglio nella sua lista; se aveva dato già un “può darsi” a un altro, lo tramuterà in “no“, liberandolo per il prossimo giro;
  6. si ripete dal passo 4, finché non sono state formate tutte le N coppie.

Come andrebbe applicato l’algoritmo nel caso di assegnazione delle sedi di lavoro?

Nel caso in questione il ruolo dei maschi dovrebbe essere svolto, almeno a mio parere, dai docenti.
Quindi l’algoritmo dovrebbe proporre i docenti, in ordine di graduatoria, alla sede che risulta in cima alle preferenze di ciascun docente. Ogni sede, a questo punto dovrebbe accettare temporaneamente l’accoppiamento migliore, rispondendo no a tutte le altre proposte. E così via, fino ad accoppiamenti esauriti.

Il problema è che questo algoritmo porterebbe proprio a casi come quelli denunciati dai ricorrenti:

  • il docente A precede in graduatoria il docente B ed entrambi hanno espresso preferenza per la sede S;
  • la sede S viene assegnata al docente B, perché abita più vicino rispetto al docente A.

Ma, almeno, non avverrebbe perché il programma è “un sistema ampolloso, ridondante e non orientato alla manutenibilità“, ma perché nella procedura si è tenuto conto non solo dei diritti dei docenti, ma anche dell’interesse della scuola ad avere una didattica più stabile.

Foto di apertura dell’articolo di ErikaWittlieb da Pixabay.

Ti è piaciuto? Condividilo!

Scritto da:

Pasquale

Mi chiamo Pasquale Petrosino, radici campane, da un paio d'anni sulle rive del lago di Lecco, dopo moltissimi anni vissuti a Ivrea.
Ho attraversato 40 anni di tecnologia informatica, da quando progettavo hardware maneggiando i primi microprocessori, la memoria si misurava in kByte, e Ethernet era una novità fresca fresca, fino alla comparsa ed esplosione di Internet.
Tre passioni: la Tecnologia, la Matematica per diletto e le mie tre donne: la piccola Luna, Orsella e Valentina.
Potete contattarmi scrivendo a: p.petrosino@inchiostrovirtuale.it