MenuNet: A Strategy-Proof Mechanism for Matching Markets

Résumé Technique : MenuNet

Énoncé du Problème
Dans les marchés d'appariement tels que le choix scolaire et l'allocation de la main-d'œuvre, deux desiderata fondamentaux sont la non-manipulabilité (garantissant que les agents n'ont aucun incitatif à déclarer faussement leurs préférences) et la stabilité (garantissant qu'aucune paire d'agents ne peut dévier de manière profitable). Alors que des mécanismes comme l'Acceptation Différée (DA) atteignent les deux dans des contextes classiques avec des capacités rigides, les applications réelles impliquent souvent des contraintes distributionnelles complexes (par exemple, quotas de diversité, équilibre régional, quotas minimaux). Sous ces contraintes, l'existence d'appariements stables n'est pas garantie.

La littérature existante aborde généralement cela en relâchant la stabilité vers l'équité (absence d'envie justifiée) et la non-gaspillage. Cependant, les approches actuelles se concentrent souvent sur des objectifs agrégés, échouant à contrôler comment l'instabilité inévitable est distribuée parmi les agents. Cela peut conduire à des déséquilibres systémiques où un petit sous-ensemble d'agents supporte l'essentiel des violations, provoquant une insatisfaction individuelle extrême. Le défi central est de concevoir un mécanisme non-manipulable qui non seulement équilibre équité et efficacité, mais partitionne équitablement l'instabilité inévitable entre tous les agents.

Méthodologie : Le Cadre MenuNet
Les auteurs proposent MenuNet, un cadre de conception de mécanismes neuronaux qui génère des menus probabilistes personnalisés plutôt que des affectations discrètes directes. Le cadre opère en deux étapes :

1. Génération de Menu (Construction Leave-One-Out) :

   • Un réseau neuronal partagé $F_\theta$ génère une distribution de probabilité personnalisée (menu) $p_s$ pour chaque étudiant $s$.
   • Pour garantir la non-manipulabilité, le réseau emploie une architecture leave-one-out : le menu pour l'étudiant $s$ est calculé en utilisant la matrice de priorité $U$, le vecteur de capacité $q$, et les rapports de préférences de tous les autres agents ($V_{-s}$), mais exclut explicitement le rapport de $s$ lui-même. Cela assure que le menu est fonctionnellement indépendant de la stratégie propre de l'étudiant.

2. Choix Séquentiel Structuré :

   • Étant donné le menu probabiliste, l'affectation finale est réalisée via une règle de choix séquentielle. Les étudiants postulent aux écoles selon l'ordre de leurs préférences déclarées. Une école $c_j$ est assignée à l'étudiant $s$ si elle est disponible dans le menu et que toutes les écoles mieux classées étaient indisponibles.
   • Cette construction assure que le mécanisme est non-manipulable par construction (Théorème 1), car le menu est invariant par rapport au rapport de l'étudiant, et la règle de choix est monotone par rapport aux préférences réelles.

Objectifs Différentiables et Optimisation
Pour gérer le compromis entre équité et non-gaspillage sous des contraintes de capacité globales (spécifiquement le relâchement de capacité global $k$), MenuNet décompose la stabilité en quantités vectorielles :

• Envie Ex-Ante ($E(P)$) : Mesure l'intensité de l'envie justifiée basée sur les différences de priorité et d'utilité.
• Gaspillage Ex-Ante ($W(P)$) : Mesure l'inefficacité basée sur les gains d'utilité potentiels et le relâchement disponible (local et global).

Le cadre optimise une fonction de perte composite $L(P)$ comprenant :

• Perte de Bien-être : Utilité espérée moyenne négative.
• Perte de Faisabilité (Pénalité K-Barrier) : Une pénalité lisse qui est linéaire dans le budget de relâchement $k$ et super-linéaire (quadratique + linéaire) au-delà, assurant que la contrainte de capacité globale est respectée en espérance.
• Perte de Stabilité : Une somme pondérée de trois principes appliqués aux vecteurs d'envie et de gaspillage :
  • Égalitariste : Minimisation de la magnitude agrégée (MSE).
  • Rawlsien : Minimisation de la mécontentement maximum (approximé via log-sum-exp).
  • Équilibré : Minimisation de la variance pour empêcher la concentration de l'instabilité sur des agents spécifiques.

Contributions Clés

1. Mécanisme Neuron Non-Manipulable : Introduction d'un cadre garantissant la non-manipulabilité structurellement via une génération de menu leave-one-out et une règle de choix séquentielle, évitant le besoin de régularisation empirique ou de minimisation du regret.
2. Contrôle Distributionnel de l'Instabilité : Déplacement de l'objectif de conception de l'élimination de l'instabilité (impossible sous contraintes) vers sa distribution équitable. En modélisant l'envie et le gaspillage comme des vecteurs et en optimisant pour la variance et l'équité rawlsienne, le mécanisme empêche la perte individuelle disproportionnée.
3. Évolutivité et Efficacité : L'approche est computationnellement efficace. Une fois entraîné hors ligne, le mécanisme ne nécessite qu'un seul passage avant pour toute nouvelle instance de marché, s'échelle linéairement avec la taille du marché et reste traitable sur des CPU standards.

Résultats Expérimentaux
Les auteurs évaluent MenuNet par rapport au Dictateur Séquentiel Aléatoire (RSD) et à l'Acceptation Différée (DA) sous des contraintes de relâchement de capacité globale sur des tailles de marché allant de 100 à 2 000 étudiants.

• Compromis de Performance : MenuNet atteint constamment un compromis supérieur entre équité et non-gaspillage. Il obtient une envie plus faible que RSD et un gaspillage plus faible que DA.
• Distribution de l'Instabilité : Crucialement, MenuNet distribue l'insatisfaction inévitable plus uniformément à travers la population d'agents, réduisant significativement la variance et l'envie/gaspillage maximum par rapport aux références.
• Faisabilité : Le mécanisme respecte le budget de relâchement de capacité globale avec une haute précision, avec seulement des déviations négligeables dans un petit sous-ensemble d'instances.
• Efficacité Computationnelle : L'entraînement est faisable sur CPU (environ 10 minutes pour 1 000 étudiants), et l'inférence est instantanée, démontrant l'applicabilité pratique sans matériel spécialisé.

Signification et Revendications
L'article revendique que MenuNet fournit un paradigme flexible et évolutif pour la conception de mécanismes dans des environnements réels hautement contraints. En exploitant des mécanismes de menu basés sur l'apprentissage, il offre une manière principielle de naviguer la tension inhérente entre des axiomes concurrents (équité, efficacité et faisabilité). Les auteurs positionnent ce travail comme une étape vers la gestion de contraintes distributionnelles complexes où les mécanismes d'appariement stables traditionnels échouent, offrant une solution qui équilibre les objectifs à l'échelle du système tout en protégeant les agents individuels contre un préjudice disproportionné.

Directions Futures
Les auteurs suggèrent modestement un travail futur comparant MenuNet à des mécanismes non-manipulables spécialisés pour des contraintes structurées (par exemple, la $M^\natural$-convexité), la conception d'architectures neuronales plus expressives, et l'extension du cadre à des classes plus riches de contraintes distributionnelles multidimensionnelles.