Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty

Questo articolo introduce un problema di espansione stocastica della capacità in due stadi per il matching stabile, analizzando come l'incertezza sulle preferenze degli studenti, sia esogena (veridiche) che endogena (strategiche), influenzi le decisioni di pianificazione delle capacità e proponendo approcci basati sull'approssimazione della media campionaria e euristiche per ottimizzare i risultati di assegnazione.

L'essenziale

Immagina di essere il direttore di una grande scuola o di un ospedale che deve assumere nuovi medici. Devi decidere oggi quanti nuovi posti letto o quante nuove aule costruire, ma c'è un grosso problema: non sai ancora chi vorrà venire da te l'anno prossimo.

Inoltre, anche se pensi che gli studenti o i medici siano onesti, spesso agiscono in modo strategico: scelgono di candidarsi solo dove pensano di avere buone probabilità di essere accettati, basandosi su quanto spazio c'è.

Questo articolo scientifico, scritto da Maria Bazotte e colleghi, risolve proprio questo dilemma. Ecco la spiegazione semplice, con qualche analogia per renderla più chiara.

1. Il Problema: Costruire al buio

Immagina di dover organizzare una grande festa. Devi decidere ora quanti tavoli e quante sedie comprare (la capacità), ma non sai ancora:

• Chi verrà esattamente.
• Chi preferirà sedersi vicino alla musica o vicino al buffet.
• Se le persone sceglieranno di venire solo se pensano che ci sarà posto per loro.

Nella vita reale, le scuole devono espandere le classi prima di sapere quali scuole gli studenti preferiranno davvero. Se sbagli il calcolo, rischi di avere aule vuote (spreco di soldi) o classi sovraffollate (studenti arrabbiati).

2. La Scelta: Onestà vs. Strategia

Gli autori del paper studiano due modi in cui le persone (studenti) potrebbero comportarsi:

• Il "Santo Onesto" (Comportamento Veritiero): Gli studenti dicono semplicemente: "Preferisco la scuola A, poi la B, poi la C". Non calcolano le probabilità. È come se dicessero la verità senza pensare alle conseguenze.
• Il "Giocatore Astuto" (Comportamento Strategico): Gli studenti pensano: "Se mi iscrivo alla scuola A, che è molto richiesta, forse non mi accettano. Meglio iscrivermi alla scuola B, che è meno ambita, così ho più chance".
  • L'analogia: Immagina di voler entrare in un club esclusivo. Se sai che c'è una fila lunghissima, potresti decidere di non fare nemmeno la domanda, o di provare un club più piccolo dove la probabilità di entrare è più alta, anche se il club grande ti piace di più.

3. La Soluzione: La "Sfera di Cristallo" Matematica

Il paper introduce un metodo chiamato 2-STMMP. In parole povere, è un modo per prendere decisioni oggi basandosi su molti possibili futuri, non solo su un solo "scenario medio".

• L'approccio vecchio (Scenario Medio): I pianificatori pensavano: "In media, il 50% degli studenti vuole la scuola A". Quindi costruiscono aule per il 50%.
  • Il problema: Se l'anno prossimo il 70% vuole la scuola A, sei in crisi. Se il 30% la vuole, hai sprecato soldi.
• L'approccio nuovo (Stocastico/Simulazione): Il metodo degli autori crea migliaia di "mondi paralleli" (simulazioni). In alcuni mondi gli studenti sono onesti, in altri sono astuti. In alcuni mondi la scuola A è di moda, in altri no.
  • L'analogia: È come un metereologo che non guarda solo la temperatura media di luglio, ma simula migliaia di possibili estati (sole, pioggia, uragani) per decidere se costruire un tetto rinforzato o una tenda leggera.

4. Cosa hanno scoperto?

Gli autori hanno fatto esperimenti al computer con migliaia di scenari e hanno scoperto tre cose fondamentali:

1. Non fidarti della "media": Pianificare basandosi su una media fissa funziona male. Considerare l'incertezza (usando il loro metodo) porta a decisioni molto migliori, con meno studenti esclusi e più studenti felici.
2. Il comportamento conta: Se pensi che gli studenti siano onesti, ma in realtà sono astuti (e calcolano le probabilità), le tue decisioni sulle aule saranno sbagliate. Devi capire come pensano le persone.
3. La strategia cambia tutto: Se gli studenti sono molto astuti, le scuole devono espandersi in modo diverso rispetto a quando sono onesti. Ignorare questo aspetto porta a sprechi enormi.

5. Come lo hanno risolto? (I "Trucchi" Matematici)

Il problema è matematicamente molto difficile (come un puzzle gigante che cambia forma mentre lo stai risolvendo). Gli autori hanno creato due tipi di strumenti:

• Metodi Esatti: Come un super-calcolatore che trova la soluzione perfetta, ma ci mette molto tempo (utile se hai anni per pianificare).
• Euristiche (Scorciatoie intelligenti): Sono come "regole pratiche" molto veloci che trovano una soluzione quasi perfetta in pochi secondi. Sono utili quando devi prendere decisioni rapide, come quando arriva un finanziamento urgente e devi decidere subito dove mettere i soldi.

In Sintesi

Questo studio ci insegna che quando devi allocare risorse scarse (posti a scuola, posti in ospedale, case per rifugiati) prima di sapere cosa vogliono le persone, non puoi basarti su una previsione semplice. Devi:

1. Immaginare molti scenari possibili.
2. Capire se le persone saranno oneste o se giocheranno d'astuzia per massimizzare le loro chance.
3. Usare la matematica per trovare il piano migliore che funzioni bene in tutti questi scenari, non solo in quello "medio".

È come preparare un viaggio: non pianifichi il percorso basandoti sul tempo "medio" di guida, ma prepari un piano B e un piano C per quando piove, quando c'è traffico o quando l'auto si rompe, assicurandoti di arrivare a destinazione comunque.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del documento "Two-Stage Stochastic Capacity Expansion in Stable Matching under Truthful or Strategic Preference Uncertainty", tradotta e strutturata in italiano.

1. Introduzione e Definizione del Problema

Il paper introduce il 2-STMMP (Two-Stage Stochastic Capacity Expansion in Two-Sided Many-to-One Matching Problem with Uncertain Preferences), un modello di programmazione stocastica a due stadi applicato ai mercati di matching "molti-a-uno" (es. assegnazione studenti-scuole o medici-residenze).

Il Problema:
In molte applicazioni reali, le decisioni di espansione della capacità (es. costruire nuove aule o assumere docenti) devono essere prese prima che le preferenze degli agenti (studenti) siano rivelate. Tuttavia, la letteratura precedente assume spesso che le preferenze siano note e deterministiche al momento della pianificazione, o che gli agenti si comportino sempre in modo veritiero.
Il 2-STMMP affronta tre sfide critiche simultaneamente:

1. Incertezza Temporale: Le decisioni di capacità (Primo Stadio) precedono la rivelazione delle preferenze.
2. Comportamento Strategico: Gli studenti possono non riportare le loro vere preferenze, ma modificare le liste in base alle loro credenze sulle probabilità di ammissione (che dipendono dalle capacità delle scuole).
3. Incertezza Endogena: Le preferenze riportate dagli studenti non sono indipendenti dalle decisioni di capacità; sono una funzione di esse (incertezza endogena).

Obiettivo:
Il Clearinghouse (l'ente centrale) deve decidere un piano di espansione delle capacità delle scuole entro un budget prefissato, minimizzando l'atteso costo del matching (definito come la somma dei ranghi delle scuole assegnate agli studenti nel matching stabile ottimale), considerando tutte le possibili realizzazioni delle preferenze.

2. Metodologia e Modelli di Comportamento

Il problema è formulato come un programma stocastico a due stadi.

Fasi del Processo:

1. Primo Stadio (Decisione di Capacità): Il clearinghouse decide quante sedie aggiuntive allocare a ogni scuola ($x$).
2. Realizzazione dello Scenario: Si realizza la vera preferenza degli studenti ($u$).
3. Comportamento degli Studenti (Secondo Stadio): Gli studenti riportano le preferenze ($\succ^a_S$) in base al loro comportamento $a$.
4. Matching: Viene calcolato il matching stabile ottimale per gli studenti (Student-Optimal Stable Matching - SOSM) basato sulle capacità espanso e sulle preferenze riportate.

Modelli di Comportamento Analizzati:
Il paper definisce tre modelli comportamentali ($a \in A$):

1. Utility Maximization (UM - Veritiero): Gli studenti riportano le loro $K$ vere preferenze. L'incertezza è esogena (indipendente dalle decisioni di capacità).
2. Conjoint Expected Utility Maximization (CEUM - Strategico): Gli studenti risolvono un problema di ottimizzazione (basato sul modello di portfolio choice di Chade e Smith, 2006) per massimizzare l'utilità attesa congiunta. Considerano sia la probabilità di ammissione a una scuola che il rischio di essere rifiutati dalle scuole preferite. Le preferenze riportate sono endogene (dipendono da $x$).
3. Individual Expected Utility Maximization (IEUM - Strategico Semplificato): Gli studenti massimizzano la somma delle utilità attese individuali, ignorando il rischio di rifiuto dalle scuole superiori (bounded rationality). Anche qui, le preferenze sono endogene.

Trasformazione dell'Incertezza:
Per gestire l'incertezza endogena, il paper utilizza il metodo di trasformazione delle variabili casuali (Bazotte et al., 2025). Le preferenze riportate endogene sono definite come una funzione trasformata delle decisioni di primo stadio ($x$) e delle preferenze vere esogene ($u$). Questo permette di riformulare il problema in un programma stocastico con incertezza solo esogena, risolvibile tramite metodi standard.

3. Algoritmi e Soluzioni Proposte

Poiché l'enumerazione completa degli scenari è intrattabile, gli autori utilizzano l'Approssimazione della Media Campionaria (SAA - Sample Average Approximation).

Formulazioni Matematiche:

• Comportamento Veritiero (UM): Viene proposta una formulazione basata su vincoli L-modificati (estensione di Bobbio et al., 2025) risolvibile con solver MILP.
• Comportamento Strategico (CEUM/IEUM): La formulazione diventa un programma bilevel (l'ottimizzazione interna definisce le preferenze). Gli autori derivano formulazioni a singolo livello esatte utilizzando algoritmi specifici (MIA per CEUM, IOA per IEUM) per linearizzare le trasformazioni non lineari.

Euristiche Proposte:
Data la complessità computazionale (NP-hard), vengono sviluppate euristiche specifiche per comportamento:

1. Lagrangian Relaxation (LR): Specifica per il caso UM. Rilassa i vincoli di stabilità per fornire limiti inferiori più forti e utilizza un metodo del subgradiente.
2. Greedy Local Search (LS): Esplora lo spazio delle decisioni di capacità (aggiunta, trasferimento, scambio di posti) e valuta la qualità del matching.
3. Simulated Annealing (SA): Una ricerca locale probabilistica che permette movimenti in salita per evitare ottimi locali, dimostratasi molto robusta per i casi strategici.

4. Risultati Sperimentali

Gli autori hanno condotto estese sperimentazioni su istanze piccole e grandi (fino a 1000 studenti e 60 scuole).

Valore della Soluzione Stocastica (VSS):

• Le soluzioni ottenute tramite SAA superano significativamente l'approccio deterministico basato sullo scenario medio (EV - Expected Value).
• Il VSS è positivo per tutti i comportamenti, indicando che ignorare l'incertezza porta a decisioni di capacità subottimali.
• L'uso di SAA porta a un aumento significativo degli studenti assegnati alle loro prime scelte e a un aumento del numero di studenti che entrano nel matching (riduzione degli studenti non assegnati).

Impatto del Comportamento Strategico:

• Errore di Modellazione: Se il pianificatore assume un comportamento veritiero (UM) mentre gli studenti agiscono strategicamente (CEUM o IEUM), la qualità del matching peggiora drasticamente.
• Differenze tra CEUM e IEUM: Sbagliare nel distinguere tra CEUM e IEUM (assumendo uno quando è l'altro) porta a perdite di efficienza significative, specialmente quando il numero massimo di preferenze ($K$) è piccolo.
• Dimensione della Lista ($K$): Quando $K$ è grande, le decisioni basate su UM approssimano bene quelle di CEUM; quando $K$ è piccolo, approssimano meglio IEUM. Tuttavia, la modellazione corretta rimane cruciale.

Performance Computazionale:

• UM: Risolvibile esattamente con solver MILP per istanze moderate; le euristiche LR e SA sono estremamente veloci e di alta qualità.
• CEUM/IEUM: La presenza di incertezza endogena rende il problema molto più difficile. I solver esatti spesso falliscono nel trovare l'ottimo entro limiti di tempo ragionevoli (gap di ottimalità alti).
• Efficacia delle Euristiche: L'algoritmo Simulated Annealing (SA) si è dimostrato il più efficace per i casi strategici, offrendo un ottimo compromesso tra tempo di esecuzione e qualità della soluzione (gap superiore medio < 0.5% per istanze grandi), superando sia i metodi esatti che la ricerca locale pura (LS).

5. Significato e Contributi Chiave

1. Innovazione Teorica: È il primo studio che integra esplicitamente la pianificazione della capacità con l'incertezza endogena delle preferenze in mercati di matching stabili.
2. Modellazione Comportamentale: Dimostra che ignorare il comportamento strategico o trattare le preferenze come deterministiche porta a investimenti inefficienti (sovra- o sotto-dimensionamento delle scuole) e a un benessere inferiore per gli studenti.
3. Metodologia Risolutiva: Fornisce un toolkit completo (formulazioni esatte, rilassamenti lagrangiani, meta-euristiche) per risolvere problemi di matching stocastici complessi con incertezza decision-dependent.
4. Implicazioni Politiche: Suggerisce che i decisori pubblici (es. ministeri dell'istruzione) devono adottare modelli stocastici e comportamentali realistici per allocare le risorse, specialmente in contesti di alta domanda e preferenze limitate.

In sintesi, il paper dimostra che la combinazione di programmazione stocastica e modelli comportamentali realistici è essenziale per ottimizzare l'allocazione delle risorse nei mercati di matching, superando i limiti degli approcci deterministici tradizionali.