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

Cet article propose une approche d'expansion de capacité en deux étapes pour les marchés d'appariement stables, modélisant l'incertitude des préférences (exogène ou stratégique) via une approximation par moyenne d'échantillons et des heuristiques pour optimiser les décisions de capacité avant l'appariement.

L'essentiel

Imaginez que vous êtes le directeur d'un grand festival de musique. Vous devez décider maintenant combien de places ajouter à chaque tente (les écoles) avant même de savoir quels genres de musique les gens (les étudiants) vont vraiment aimer.

C'est le cœur de ce papier de recherche : comment planifier l'avenir quand on ne connaît pas encore les désirs des gens, et surtout, quand ces gens pourraient mentir ou tricher pour avoir une meilleure chance.

Voici l'explication simple, étape par étape, avec quelques images pour rendre les choses claires.

1. Le Problème : Le Dilemme du Directeur de Festival

Dans la vraie vie, comme pour l'inscription à l'école ou la résidence médicale, il y a deux étapes :

1. La construction (Le 1er étage) : On décide d'agrandir les écoles (ajouter des salles de classe) avant de savoir ce que les élèves veulent.
2. L'inscription (Le 2ème étage) : Les élèves disent ce qu'ils veulent, et on les place dans les écoles.

Le piège : Souvent, on suppose que les élèves vont dire la vérité. Mais en réalité, les élèves sont intelligents. Ils savent que si une école est trop petite, ils n'auront aucune chance. Alors, ils ne la mettent pas sur leur liste, même s'ils l'aiment, par peur d'être rejetés. Ils jouent le jeu. C'est ce qu'on appelle une incertitude stratégique.

Si vous construisez des écoles en pensant que les élèves seront honnêtes, mais qu'ils sont en fait malins et stratégiques, vous risquez de construire des écoles géantes pour des sujets que personne ne choisit, et de laisser d'autres écoles trop petites.

2. La Solution : Une "Boule de Cristal" Mathématique

Les auteurs proposent une méthode pour prendre la bonne décision, même sans boule de cristal. Ils utilisent une technique appelée SAA (Approximation par Moyenne d'Échantillons).

L'analogie du Chef de Cuisine :
Imaginez que vous devez préparer un grand banquet pour 1000 personnes, mais vous ne savez pas exactement ce qu'ils vont manger.

• L'approche ancienne (Déterministe) : Vous demandez à un seul client : "Qu'est-ce que tu veux ?" Il dit "Pâtes". Vous faites 1000 portions de pâtes. Si les autres veulent du poisson, c'est le désastre.
• L'approche de ce papier (Stochastique) : Vous simulez 100 repas différents avec des clients fictifs. Certains veulent des pâtes, d'autres du poisson, d'autres des légumes. Vous voyez que 60% veulent des pâtes, 30% du poisson, 10% des légumes. Vous préparez un menu équilibré.

Même mieux : vous simulez aussi ce que les clients feraient s'ils savaient que le poisson est rare. Peut-être qu'ils ne commanderont pas de poisson s'ils pensent qu'il n'y en aura pas assez. C'est ça, la stratégie.

3. Les Trois Types de "Clients" (Étudiants)

Le papier étudie trois façons dont les étudiants peuvent se comporter :

1. L'Honnête (UM) : Il dit exactement ce qu'il aime. C'est le cas idéal, mais souvent faux dans la réalité.
2. Le Stratège "Super Calculateur" (CEUM) : Il est très intelligent. Il dit : "J'aime l'école A, mais elle est petite. Si je la mets en premier, je risque d'être rejeté. Je vais mettre l'école B en premier, même si j'aime moins, car j'ai plus de chances d'y entrer." Il joue au poker.
3. Le Stratège "Simplifié" (IEUM) : Il est un peu moins calculateur. Il dit : "L'école A a 10% de chances d'acceptation, l'école B en a 50%. Je vais choisir B." Il ne pense pas à la complexité des autres choix, juste à la probabilité simple.

4. Pourquoi c'est important ? (Les Résultats)

Les chercheurs ont fait des milliers de simulations informatiques pour voir ce qui se passe. Voici ce qu'ils ont découvert :

• Mentir coûte cher : Si vous construisez des écoles en pensant que les élèves sont honnêtes, alors qu'ils sont en fait des stratèges, vous faites de mauvaises décisions. Vous gaspillez de l'argent et les élèves sont moins heureux.
• La "Boule de Cristal" gagne toujours : La méthode qui prend en compte toutes les possibilités (la méthode SAA) donne toujours de meilleurs résultats que de simplement faire une moyenne des préférences. Elle permet d'accepter plus d'étudiants et de les mettre dans des écoles qu'ils aiment vraiment.
• La taille de la liste compte : Si les élèves peuvent choisir beaucoup d'écoles (une longue liste), ils se comportent un peu plus comme des gens honnêtes. Si la liste est courte, ils deviennent très stratégiques.

5. Comment ils ont résolu le problème ? (Les Outils)

Le problème est mathématiquement très difficile (comme essayer de résoudre un Sudoku géant où les règles changent selon votre décision).

• Pour les petits problèmes, ils ont utilisé des solveurs exacts (comme un super-calculateur qui trouve la solution parfaite).
• Pour les grands problèmes (des milliers d'étudiants), ils ont créé des algorithmes intelligents (des heuristiques) qui trouvent une solution "presque parfaite" très rapidement, comme un expert qui devine la meilleure stratégie en regardant les tendances.

En Résumé

Ce papier nous dit : "Ne construisez pas votre avenir en supposant que tout le monde dira la vérité."

Dans un monde où les gens adaptent leurs choix en fonction des règles du jeu (comme les élèves qui choisissent des écoles selon leurs chances d'admission), les décideurs doivent anticiper ces stratégies. En utilisant des modèles mathématiques avancés qui simulent le chaos et les stratégies, on peut créer un système plus juste, où plus d'étudiants sont admis et où les ressources (les places dans les écoles) sont utilisées là où elles sont vraiment nécessaires.

C'est un peu comme dire à un architecte : "Ne dessine pas ta maison en pensant que les visiteurs vont toujours entrer par la porte principale. Prépare-toi aussi au cas où ils essaieraient de passer par la fenêtre parce qu'ils pensent que la porte est verrouillée !"

Résumé technique

Voici un résumé technique détaillé de l'article de recherche en français, structuré selon les sections demandées.

Titre de l'article

Extension stochastique à deux étapes de la capacité dans l'appariement stable sous incertitude de préférences véridiques ou stratégiques

1. Problème Étudié

L'article introduit et formalise un nouveau problème d'optimisation appelé 2-STMMP (Two-Stage Stochastic Capacity Expansion in Two-Sided Many-to-One Matching Problem with Uncertain Preferences). Ce problème modélise des marchés d'appariement à deux faces (comme le choix scolaire ou l'affectation de résidents en médecine) où les décisions de capacité doivent être prises avant que les préférences des agents ne soient révélées.

Le problème se décompose en deux étapes :

• Étape 1 (Décision de capacité) : Le centre de clearing (ex: ministère de l'éducation) décide d'augmenter les capacités des écoles (ajout de places) dans le cadre d'un budget donné. À ce stade, les préférences réelles des étudiants sont inconnues.
• Étape 2 (Appariement) : Une fois les capacités fixées, les préférences des étudiants se réalisent (scénarios). Les étudiants soumettent leurs préférences déclarées, puis le centre calcule un appariement stable optimal pour les étudiants (basé sur l'algorithme de Deferred Acceptance - DAA).

L'incertitude et le comportement stratégique :
Le papier distingue deux types d'incertitude et de comportement des étudiants :

1. Comportement Véridique (UM - Utility Maximization) : Les étudiants rapportent leurs vraies préférences. L'incertitude est exogène (indépendante des décisions de capacité).
2. Comportement Stratégique (CEUM et IEUM) : Les étudiants ajustent leurs préférences déclarées en fonction de leurs vraies préférences et de leurs chances perçues d'admission, qui dépendent directement des capacités décidées à l'étape 1. Cela crée une incertitude endogène (dépendante de la décision).
   • CEUM (Conjoint Expected Utility Maximization) : Modèle complexe où les étudiants maximisent l'utilité espérée conjointe, tenant compte du risque de rejet par les écoles préférées.
   • IEUM (Individual Expected Utility Maximization) : Modèle simplifié où les étudiants maximisent la somme des utilités espérées individuelles, ignorant le risque de rejet en cascade.

L'objectif est de minimiser l'espérance mathématique du coût de l'appariement (somme des rangs des écoles attribuées) sur tous les scénarios possibles de préférences.

2. Méthodologie

Pour résoudre ce problème complexe, les auteurs utilisent l'approche d'Approximation par Moyenne Échantillonnaire (SAA - Sample Average Approximation) pour gérer l'espace continu des préférences et l'incertitude endogène.

Modélisation Mathématique :

• Transformation de variables : Pour gérer l'incertitude endogène (stratégique), l'article utilise une méthode de transformation de variables (inspirée de Bazotte et al., 2025). Les préférences déclarées endogènes sont définies comme une fonction des décisions de capacité et des préférences exogènes vraies.
• Formulations Exactes :
  • Pour le cas UM, une formulation par contraintes modifiées de type "L-constraints" est utilisée.
  • Pour les cas stratégiques (CEUM/IEUM), le problème devient un programme bi-niveau (la décision de capacité influence le problème d'optimisation interne des étudiants). Les auteurs proposent des reformulations en un seul niveau (single-level) exactes en intégrant des algorithmes spécifiques (MIA pour CEUM, IOA pour IEUM) directement dans les contraintes MILP (Mixed-Integer Linear Programming).
• Heuristiques : En raison de la complexité NP-difficile et de la taille des instances, des heuristiques sont développées :
  • Relaxation Lagrangienne (LR) : Spécifique au cas UM, elle relâche les contraintes de stabilité pour fournir des bornes inférieures fortes.
  • Recherche Locale (LS) et Recuit Simulé (SA) : Des heuristiques génériques explorant l'espace des décisions de capacité (ajout, transfert ou échange de places) et évaluant chaque solution via les algorithmes de comportement étudiant et le DAA.

Algorithme de résolution (SAA) :

1. Génération d'un ensemble de scénarios ($W_N$).
2. Résolution du programme SAA (exactement ou via heuristiques) pour obtenir une décision de capacité $x$.
3. Évaluation de la qualité de cette décision sur un ensemble de test plus large ($W_{N'}$) pour estimer la valeur objective réelle.

3. Contributions Clés

1. Modélisation Unifiée : Introduction du premier cadre intégrant simultanément l'expansion de capacité, l'incertitude des préférences et les comportements stratégiques des agents dans un marché d'appariement stable.
2. Gestion de l'Incertitude Endogène : Définition formelle des préférences déclarées comme des transformations des décisions de capacité, permettant de traiter l'incertitude de type 1 (distribution dépendante de la décision) dans un contexte d'appariement.
3. Boîte à Outils Algorithmique : Développement d'une suite complète de méthodes de résolution :
   • Formulations exactes MILP pour les trois comportements.
   • Heuristiques de haute performance (LR, LS, SA) capables de traiter de grandes instances en temps raisonnable.
4. Analyse Empirique Rigoureuse : Évaluation de la valeur de la solution stochastique (VSS) et de l'impact de la mauvaise spécification du comportement des étudiants.

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances réalistes (choix scolaire) avec des tailles allant de 50 à 1000 étudiants et 6 à 60 écoles.

• Avantage de l'approche Stochastique (SAA) : Les décisions basées sur le modèle SAA surpassent systématiquement l'approche déterministe classique (basée sur la moyenne des préférences - EV).
  • Amélioration significative de la qualité des appariements (réduction des rangs moyens).
  • Augmentation du nombre d'étudiants admis et de ceux améliorant leur affectation (jusqu'à +45% pour le cas UM).
• Impact du Comportement Stratégique :
  • Ignorer le comportement stratégique (en supposant que les étudiants sont véridiques alors qu'ils sont stratégiques) conduit à des décisions de capacité sous-optimales et à une baisse de qualité des appariements.
  • La méconnaissance du type de stratégie (confondre CEUM et IEUM) est également préjudiciable, bien que l'impact soit moindre que de supposer la véridicité alors qu'il y a stratégie.
  • Effet de la taille de la liste (K) : Lorsque les étudiants peuvent lister beaucoup d'écoles (K grand), le comportement stratégique se rapproche du comportement véridique, rendant l'approche UM une approximation acceptable. Pour de petites listes (K petit), les stratégies diffèrent fortement.
• Performance Computationnelle :
  • Le cas UM est résoluble exactement pour des instances moyennes, mais les heuristiques (notamment LR) sont très efficaces.
  • Les cas stratégiques (CEUM/IEUM) sont beaucoup plus difficiles à résoudre exactement (écarts d'optimalité élevés même après 8h). Les heuristiques (notamment le Recuit Simulé - SA) fournissent des solutions de très haute qualité (écarts < 0.5%) en quelques secondes, surpassant les méthodes exactes en efficacité.

5. Signification et Implications

• Pour la Politique Publique : Ce travail démontre que la planification des capacités (écoles, hôpitaux, etc.) ne peut plus se baser sur des hypothèses de préférences déterministes ou véridiques. Ignorer l'incertitude et la stratégie des agents entraîne un gaspillage de ressources et une détérioration du bien-être social.
• Robustesse des Mécanismes : Même dans des mécanismes "incitation-compatible" (comme le DAA), les agents peuvent se comporter stratégiquement en raison de leurs croyances sur les chances d'admission. Les concepteurs de mécanismes doivent anticiper ces comportements lors de la phase de conception des ressources.
• Avancement Théorique : L'article comble un vide majeur en combinant la programmation stochastique (avec incertitude endogène) et la théorie des appariements stables, offrant un cadre méthodologique applicable à d'autres domaines comme la réinstallation de réfugiés ou l'allocation de ressources médicales.

En conclusion, l'article prouve que l'intégration de modèles comportementaux réalistes et de l'incertitude stochastique est cruciale pour optimiser l'allocation des ressources dans les marchés d'appariement, et propose des outils pratiques pour mettre en œuvre ces décisions complexes.