Multi-Dimensional Matching in Market Design

Résumé technique : Appariement multidimensionnel dans la conception de mécanismes

Énoncé du problème
Les mécanismes d'appariement traditionnels dans des marchés tels que le choix d'école, l'allocation de l'emploi et l'affectation de cours exigent que les agents déclarent des classements complets d'objets (par exemple, écoles, emplois, cours). Lorsque les objets sont caractérisés par plusieurs attributs (par exemple, salaire, localisation, rigueur du programme), les agents subissent une charge cognitive significative pour réduire ces dimensions en un seul classement ordinal. De plus, les mécanismes existants traitant des utilités cardinales, tels que le pseudo-marché Hylland-Zeckhauser (HZ) ou les extensions Gul-Pycia-Zhang (GPZ), se heurtent à des barrières computationnelles sévères. L'existence d'équilibres dans ces modèles est souvent démontrée via des théorèmes de point fixe non constructifs (Kakutani), et le calcul même d'équilibres approximaux est connu pour être PPAD-complet, les rendant irréalisables pour des marchés à grande échelle. De plus, Zhou (1990) a établi qu'aucun mécanisme ne peut simultanément atteindre une efficacité exacte, la véracité et la symétrie avec des utilités cardinales, nécessitant une recherche de solutions approchées.

Méthodologie
Cet article propose un mécanisme computationnellement efficace pour les marchés d'appariement unilatéraux où les agents déclarent des préférences sur des caractéristiques individuelles d'objets plutôt que sur des objets complets. L'innovation centrale réside dans l'utilisation de la décomposition en valeurs singulières (SVD) pour réduire le problème d'appariement multidimensionnel à un problème essentiellement unidimensionnel.

Le mécanisme fonctionne comme suit :

1. Représentation des caractéristiques : Les objets sont caractérisés par des vecteurs de caractéristiques $f_j \in \mathbb{R}^X$, et les agents déclarent des vecteurs de préférences $w_i \in \mathbb{R}^X$. L'utilité de l'agent $i$ pour l'objet $j$ est supposée additive : $U_{ij} = w_i \cdot f_j$.
2. Réduction de dimensionnalité : Le mécanisme calcule la SVD de la matrice de caractéristiques d'objets $F$. Il identifie le premier vecteur singulier droit $v_1$, qui représente la direction principale de variation dans l'espace des caractéristiques.
3. Projection et tri : Les préférences des agents et les caractéristiques des objets sont projetées sur $v_1$, produisant des scores scalaires $\tilde{w}_i = w_i \cdot v_1$ et $\tilde{f}_j = f_j \cdot v_1$.
4. Appariement : Les agents et les objets sont triés selon ces scores projetés, et un appariement déterministe est effectué en respectant les contraintes de capacité.

La validité théorique de cette approche repose sur la condition de faible dimensionnalité effective, définie formellement comme $\rho_1 = \sigma_1^2 / \sum \sigma_\ell^2 \gg 1/X$, où $\sigma_1$ et $\sigma_2$ sont respectivement les plus grandes et la deuxième plus grande valeurs singulières. Lorsque la première valeur singulière domine la variance, l'approximation de rang 1 capture l'essentiel de la variation pertinente pour les préférences.

Contributions clés

1. Cadre traitable : L'article formalise un cadre d'appariement où l'élicitation basée sur les caractéristiques réduit la charge cognitive, et la SVD permet une allocation efficace en temps $O(N \log N)$ (dominée par le tri et le calcul de la SVD), contournant la complétude PPAD des équilibres de pseudo-marchés traditionnels.
2. Garanties théoriques :
   • Efficacité : Sous la condition de faible dimensionnalité effective ($\sigma_1 \gg \sigma_2$), le mécanisme maximise approximativement le bien-être social de Nash (NSW). Le ratio d'approximation est borné par $(1 - O(\sigma_2^2/\sigma_1^2))$.
   • Véracité : L'article introduit une notion de véracité distributionnelle. Il démontre que si les agents déclarent sincèrement, la distance de Kolmogorov-Smirnov entre les distributions de préférences déclarées et réelles est bornée avec une forte probabilité, rendant les préférences déclarées statistiquement indiscernables des préférences réelles.
   • Symétrie : Le mécanisme satisfait une symétrie exacte ; les agents ayant des préférences déclarées identiques reçoivent des allocations identiques.
3. Nouvelle connexion : Les auteurs établissent un lien entre le bien-être social de Nash et l'optimisation robuste distributionnelle géométrique (GDRO), fournissant des garanties de robustesse face à l'incertitude distributionnelle des utilités des agents.
4. Validation empirique : Des expériences numériques démontrent que le mécanisme atteint 99 % du NSW optimal tout en étant trois ordres de grandeur plus rapide que l'optimisation non linéaire directe.

Résultats

• Performance : Dans des expériences synthétiques avec 100 agents et 20 objets, la méthode basée sur la SVD a atteint une utilité moyenne de 7,4 % supérieure à l'allocation aléatoire et 99,4 % du NSW optimal, en moins de 15 millisecondes. En revanche, l'optimisation directe du NSW a nécessité plus de 18 secondes.
• Robustesse : Le mécanisme est robuste à des déclarations erronées modérées (bruit dans les préférences de caractéristiques), la dégradation de l'utilité restant minime jusqu'à ce que les niveaux de bruit deviennent substantiels.
• Non-linéarité : Des expériences avec des fonctions d'utilité non linéaires (par exemple, interactions quadratiques, Cobb-Douglas, rendements décroissants) montrent que le mécanisme fonctionne bien lorsque l'utilité réelle est monotone par rapport à la somme linéaire des caractéristiques. Cependant, les performances se dégradent considérablement lorsque les utilités dépendent d'interactions complexes de caractéristiques (par exemple, structures de réseaux de neurones) qui sont orthogonales au produit scalaire, entraînant l'échec du proxy linéaire.
• Rationalité individuelle : Bien que le mécanisme satisfasse généralement la rationalité individuelle (utilité dépassant le point de désaccord), une petite fraction d'agents dont les préférences sont orthogonales au vecteur singulier principal peuvent recevoir des allocations inférieures à leur point de désaccord.

Signification et affirmations
L'article affirme que de nombreux marchés d'appariement multidimensionnels réels (choix d'école, marchés du travail, allocation de cours) présentent naturellement une faible dimensionnalité effective, où un petit nombre d'attributs corrélés (par exemple, qualité académique, salaire) dominent la variation. Dans de tels contextes, la méthode spectrale proposée offre une alternative pratique aux mécanismes computationnellement intraitables.

Les auteurs positionnent leur travail comme complémentaire aux mécanismes approximatifs existants (par exemple, Abebe et al., 2020). Alors que ces approches reposent sur l'échantillonnage aléatoire et nécessitent des rapports complets d'utilités, cette méthode exploite des techniques spectrales déterministes sur des préférences de caractéristiques décomposées. La signification réside dans le pont établi entre les techniques d'apprentissage automatique (SVD) et la conception de mécanismes pour résoudre efficacement des problèmes d'allocation à grande échelle tout en maintenant des garanties formelles sur le bien-être, l'équité et la compatibilité incitative sous des hypothèses structurelles spécifiques. L'article conclut que cette approche est la plus appropriée lorsque les caractéristiques sont bien définies, les utilités sont approximativement additives et la dimensionnalité effective du marché est faible.