Pseudo-Substitutability: A Maximal Domain for Pairwise Stability in Matching Markets with Contracts

1. Problématique et Contexte

L'article s'inscrit dans le cadre de la théorie des appariements (matching theory), spécifiquement dans les modèles d'appariement multi-à-multi avec contrats. Dans ces marchés, les agents (médecins et hôpitaux, par exemple) peuvent signer plusieurs contrats simultanément avec des contreparties différentes, mais avec une contrainte d'unité (un agent ne peut signer qu'un seul contrat avec une même contrepartie donnée).

Le problème central abordé est l'existence d'allocation stables. La littérature distingue deux notions de stabilité :

• Stabilité au sens du cœur (Corewise stability) : Aucune coalition d'agents ne peut dévier en formant un ensemble de contrats.
• Stabilité paire (Pairwise stability) : Aucune paire d'agents (médecin-hôpital) ne peut dévier en signant un contrat mutuellement acceptable en dehors de l'allocation actuelle.

Dans les environnements généraux multi-à-multi, les allocations stables (même au sens pair) n'existent pas nécessairement. La condition classique garantissant l'existence de la stabilité est la substituabilité des préférences (introduite par Kelso et Crawford, 1982, et Hatfield et Milgrom, 2005). Cependant, la substituabilité est une condition restrictive qui interdit toute forme de complémentarité entre les contrats.

La question de recherche : Existe-t-il un domaine de préférences plus large que celui de la substituabilité classique, qui garantisse toujours l'existence d'une allocation stable au sens pair, et qui soit maximal (c'est-à-dire qu'aucune préférence supplémentaire ne puisse être ajoutée sans risquer de faire disparaître l'existence de la stabilité) ?

2. Méthodologie et Concepts Clés

Les auteurs introduisent une nouvelle notion de domaine de préférences appelée préférences pseudo-substituables. La méthodologie repose sur la décomposition structurelle des préférences via le concept de sous-préférence (sub-preference).

A. La Sous-Préférence ($P' \sqsubseteq P$)

Une préférence $P'$ est dite une sous-préférence d'une préférence $P$ si elle satisfait deux conditions :

1. Rationalité individuelle préservée : Tout ensemble de contrats acceptable sous $P'$ (c'est-à-dire choisi par l'agent) est également acceptable sous $P$.
2. Stabilité des blocages préservée : Si un contrat $x$ bloque un ensemble $X'$ sous la préférence originale $P$ (c'est-à-dire que l'agent préfère $x$ à son choix actuel dans $X' \cup \{x\}$), alors ce contrat $x$ doit également bloquer $X'$ sous la sous-préférence $P'$.

Cette relation définit un ordre hiérarchique où la sous-préférence est une version « restreinte » ou « simplifiée » de la préférence originale, conservant sa structure de choix essentielle.

B. Définition de la Pseudo-Substituabilité

Une préférence $P$ est dite pseudo-substitutable si elle admet au moins une sous-préférence substituable ($P'$ telle que $P' \sqsubseteq P$ et $P'$ est substituable).

• Cela signifie qu'une préférence peut contenir des complémentarités (violant la substituabilité globale), tant qu'il existe une « partie » de cette préférence qui est substituable et qui capture la structure minimale nécessaire à la stabilité.
• Les auteurs montrent que les sous-préférences substituables d'une préférence pseudo-substitutable sont minimales et partagent le même ensemble de contrats acceptables, ainsi que l'ordre partiel de Blair.

3. Résultats Principaux

L'article établit trois résultats théoriques majeurs :

Théorème 1 : Existence

Si le profil de préférences d'un marché est pseudo-substitutable, alors l'ensemble des allocations stables au sens pair $S(P)$ est non vide.

• Preuve : Puisque $P$ admet une sous-préférence substituable $P'$, et que l'ensemble des allocations stables pour $P'$ est non vide (résultat classique), la propriété d'inclusion $S(P') \subseteq S(P)$ (démontrée via la proposition 1) garantit que toute allocation stable pour $P'$ est également stable pour $P$.

Théorème 2 : Nécessité (Maximalité)

Si la préférence d'un seul agent n'est pas pseudo-substitutable, alors il est possible de construire un profil de préférences pour les autres agents (qui sont tous pseudo-substituables) tel qu'aucune allocation stable au sens pair n'existe.

• Cela démontre que le domaine des préférences pseudo-substituables est maximal : on ne peut pas l'étendre davantage sans perdre la garantie d'existence de la stabilité.

Propriétés Structurelles

• Les préférences pseudo-substituables ne satisfont pas nécessairement l'indépendance du chemin (path-independence), une propriété caractéristique des préférences substituables.
• Cependant, elles conservent une structure interne cohérente via leurs sous-préférences substituables minimales.

4. Positionnement par rapport à la Littérature

Les auteurs comparent leur domaine avec d'autres relaxations de la substituabilité :

• Substituabilité faible (Hatfield & Kojima, 2008) : La pseudo-substituabilité est une réponse structurelle à la question ouverte de l'existence d'un domaine nécessaire et suffisant. Contrairement à la décomposition par agents (hospitaux virtuels) de Hatfield et Kojima, la pseudo-substituabilité opère une décomposition au niveau des préférences.
• Substituabilité bilatérale (Hatfield & Kojima, 2010) : Les domaines de la substituabilité bilatérale et de la pseudo-substituabilité sont indépendants. L'un n'implique pas l'autre. La substituabilité bilatérale impose des restrictions comportementales sur les fonctions de choix, tandis que la pseudo-substituabilité est une condition structurelle sur les préférences elles-mêmes.
• Complétion substituable (Hatfield & Kominers, 2019) : La pseudo-substituabilité ne nécessite pas d'étendre le marché à un environnement multi-à-multi virtuel pour retrouver la stabilité ; elle extrait la stabilité directement des préférences originales.
• WOSAD (Weak Observable Substitutability Across Doctors) : Les deux domaines sont indépendants. La pseudo-substituabilité capture des structures de préférences qui échappent aux conditions observables basées sur les algorithmes d'offre cumulative.

5. Signification et Implications

Indépendance de la Représentation Contractuelle

Une contribution majeure est que la pseudo-substituabilité est définie directement au niveau des préférences, et non via la structure des contrats.

• Contrairement à d'autres relaxations (comme la substituabilité bilatérale ou WOSAD) qui s'effondrent vers la substituabilité classique dans les modèles sans contrats, la pseudo-substituabilité reste un sur-domaine strict de la substituabilité, même dans les modèles d'appariement classiques sans contrats. Cela en fait une généralisation fondamentale de la structure des préférences.

Robustesse dans les Marchés Non-Binding

L'article discute de l'importance de la stabilité paire dans les marchés réels où les accords ne sont pas contraignants (ex: marché des résidents médicaux).

• Une allocation stable au sens pair issue d'une sous-préférence substituable possède une propriété de robustesse : si un agent se retire unilatéralement, l'allocation restante reste individuellement rationnelle pour les autres. Cela contraste avec certaines allocations stables au sens du cœur qui pourraient s'effondrer complètement en cas de retrait d'un agent.

Conclusion

Ce papier établit que la pseudo-substituabilité constitue le domaine maximal de préférences garantissant l'existence d'allocation stables au sens pair dans les marchés multi-à-multi avec contrats. En introduisant la notion de sous-préférence, les auteurs parviennent à intégrer des complémentarités limitées tout en préservant la structure nécessaire à la stabilité, offrant ainsi un cadre théorique plus large et plus robuste que la substituabilité classique, applicable aussi bien aux marchés avec contrats qu'aux modèles d'appariement standards.