Random Matching with Minimums

Résumé technique : Appariement aléatoire avec contraintes minimales

Énoncé du problème
Ce papier aborde les problèmes d'affectation stochastique d'objets où les objets sont soumis à la fois à des contraintes de capacité maximale ($c_j$) et à des contraintes de exigence minimale ($m_j$). Alors que les mécanismes standards d'affectation aléatoire (tels que le Dictateur Séquentiel Aléatoire ou le mécanisme de la Série Probabiliste) gèrent les contraintes de capacité, ils échouent à garantir des affectations réalisables lorsque des quotas minimaux sont présents. Le défi central consiste à construire un mécanisme d'affectation aléatoire qui :

1. Produit une affectation aléatoire réalisable (c'est-à-dire une affectation qui peut être décomposée en une loterie sur des affectations déterministes réalisables satisfaisant toutes les $m_j$ et $c_j$).
2. Atteint l'efficacité par dominance stochastique (DS) (efficacité de Pareto sous dominance stochastique du premier ordre).
3. Maintient des propriétés d'équité (absence d'envie et anonymat).
4. Préserve la faible invulnérabilité à la manipulation (weak strategyproofness) dans le cadre de la demande unitaire.

La littérature existante fait face à un compromis : des mécanismes comme la Série Probabiliste Généralisée (GPS) de Budish et al. (2013) gèrent les contraintes bihiérarchiques (maximaux uniquement) mais ne peuvent pas représenter les minimaux. Inversement, la Série Probabiliste Contrainte Généralisée (GCPS) de Balbuzanov (2022) gère des contraintes arbitraires mais nécessite d'énumérer toutes les affectations déterministes autorisées pour caractériser le polytope réalisable. Cette énumération est de complexité factorielle, rendant la GCPS computationnellement ingérable même pour des tailles de problèmes modestes.

Méthodologie
Les auteurs proposent le mécanisme de la Série Probabiliste des Minimaux (MPS). La méthodologie se déroule en deux étapes principales :

1. Caractérisation du polytope réalisable :
   Au lieu d'énumérer l'ensemble des affectations déterministes $D$ (ce qui est computationnellement prohibitif), les auteurs caractérisent directement l'ensemble des affectations aléatoires réalisables, noté $\Delta_D$, en utilisant un système d'inégalités linéaires positives.

   • Pour le cas de la demande unitaire ($d=1$), ils dérivent un système spécifique d'inégalités (Proposition 3) qui définit l'ensemble de contour inférieur $lcs(\Delta_D)$. Ce système inclut :
     • Les contraintes de demande unitaire ($\sum_j \mu_{ij} \leq 1$).
     • Les contraintes de capacité ($\mu_j \leq c_j$).
     • Un nouvel ensemble de contraintes (Min-III) assurant que pour tout sous-ensemble d'objets $S$ avec des minimaux, la probabilité totale assignée aux objets hors de $S$ ne dépasse pas la capacité des agents restants à satisfaire les minimaux de $S$.
   • Cette caractérisation est ensuite simplifiée en une forme compacte (Proposition 4) impliquant $\sum_j \max\{m_j, \mu_j\} \leq N$, ce qui facilite une implémentation algorithmique.
   • Pour la demande générale ($d > 1$), ils fournissent un système d'inégalités plus complexe (Proposition 5) dérivé en utilisant le théorème d'existence de Hoffman pour les circulations dans les réseaux.

2. Conception du mécanisme et algorithme :

   • Définition en temps continu : Le mécanisme MPS est défini comme un processus continu de « consommation » (analogue à la Série Probabiliste) où les agents consomment leur objet disponible le plus préféré à une vitesse uniforme. Un objet est « disponible » uniquement si le consommer ne viole pas les inégalités linéaires dérivées.
   • Algorithme en temps discret : Tirant parti de la structure spécifique des inégalités de demande unitaire, les auteurs construisent l'Algorithme 1, un algorithme discret de temps polynomial. L'algorithme procède par étapes où les agents consomment des objets jusqu'à ce qu'une contrainte devienne active. Crucialement, l'algorithme identifie un temps critique $\tau$ où les contraintes minimales globales deviennent actives. À $\tau$, tout objet ayant satisfait son exigence minimale est fermé à toute consommation ultérieure, garantissant que les agents restants sont forcés de satisfaire les minimaux des autres objets.

Résultats clés
Le papier établit les propriétés théoriques suivantes pour le mécanisme MPS :

• Efficacité DS : Le mécanisme MPS produit des affectations qui sont efficaces par dominance stochastique. Aucune autre affectation aléatoire réalisable n'est préférée par tous les agents via la dominance stochastique du premier ordre.
• Équité : Le mécanisme est anonyme (invariant par rapport au ré-indexage des agents) et sans envie (aucun agent ne préfère strictement la loterie d'un autre agent).
• Invulnérabilité à la manipulation : Dans le cas de la demande unitaire, MPS est faiblement invulnérable à la manipulation. Les agents ne peuvent pas obtenir une affectation stochastiquement dominante en déclarant faussement leurs préférences. La preuve repose sur le fait que manipuler les préférences pour altérer le temps critique $\tau$ ou les temps de fermeture des objets n'apporte jamais un bénéfice net au menteur.
  • Note : Pour la demande générale ($d > 1$), le mécanisme reste efficace par DS, anonyme et sans envie, mais la faible invulnérabilité à la manipulation est perdue, ce qui est cohérent avec les résultats de Kojima (2009b).
• Implémentation : L'affectation aléatoire résultante est garantie réalisable. Puisque les contraintes sont bihiérarchiques (au sens de Budish et al., 2013), le théorème de Birkhoff-von Neumann (ou sa généralisation dans BCKM13) assure que l'affectation aléatoire peut être décomposée en une loterie sur des affectations déterministes réalisables.

Portée et affirmations
Le papier prétend combler le fossé entre les mécanismes théoriques d'affectation aléatoire et les applications pratiques impliquant des quotas minimaux (par exemple, clubs scolaires, équipes de projets, sélection de jurys).

• Faisabilité computationnelle : La contribution principale est de fournir le premier algorithme réalisable pour l'appariement aléatoire avec minimaux. En évitant la complexité factorielle de l'énumération des affectations déterministes et la complexité exponentielle du problème d'énumération des facettes (FEP) requise par Balbuzanov (2022), les auteurs fournissent un algorithme de temps polynomial pour le cas de la demande unitaire.
• Préservation des incitations : Contrairement au mécanisme GCPS plus général, qui perd la faible invulnérabilité à la manipulation, le mécanisme MPS préserve cette propriété dans le cadre de la demande unitaire.
• Extension théorique : Ce travail généralise le mécanisme de la Série Probabiliste aux cadres avec bornes inférieures, démontrant que l'efficacité et l'équité peuvent être maintenues même lorsque la structure des contraintes empêche l'utilisation des cadres standards bihiérarchiques à maximaux uniquement.

Les auteurs déclarent explicitement que, bien qu'ils fournissent un algorithme de temps polynomial pour la demande unitaire, la description algorithmique pour la demande générale ($d > 1$) reste une question ouverte pour la recherche future en raison de la complexité accrue du système d'inégalités.