La conception de mécanismes : écrire les règles du jeu
La théorie des jeux prend d'habitude les règles comme données et cherche ce que feront les joueurs. La conception de mécanismes renverse la question : on sait quel résultat on voudrait obtenir, et l'on cherche les règles qui y mèneront, alors que chacun garde pour lui une information privée et ne pense qu'à son intérêt. C'est de l'« ingénierie à l'envers ». Leonid Hurwicz, Eric Maskin et Roger Myerson ont reçu pour elle le prix Nobel d'économie en 2007. Cette page montre comment amener chacun à dire la vérité, présente le mécanisme VCG, l'applique au financement d'un pont, puis bute sur une limite : il existe des situations où aucune règle ne peut tout réussir à la fois.
Les mots du concepteur
| Mot | Sens |
|---|---|
| Mécanisme | Une règle qui, à partir des annonces des participants, fixe une décision et des paiements. |
| Efficace | La décision maximise la somme des valeurs de tous : on construit le pont s'il vaut plus qu'il ne coûte. |
| Incitatif | Dire la vérité est le meilleur choix pour chacun : quoi que fassent les autres (au sens fort), ou en moyenne (au sens bayésien). |
| Équilibré | Les paiements s'annulent : on ne reçoit pas d'argent de l'extérieur, et l'on n'en jette pas. |
| Participation volontaire | Personne ne perd à participer par rapport à rester à l'écart. |
Faire dire la vérité : pourquoi la règle naïve échoue
Cinq habitants d'un village envisagent de construire une passerelle qui coûte 500 €. Chacun sait ce qu'elle vaut pour lui, entre 0 et 200 €. Règle naïve du maire : « Chacun annonce sa valeur ; si la somme des annonces atteint 500 €, on construit, et chacun paie 100 €. » Celui qui tient beaucoup à la passerelle a intérêt à exagérer, pour la faire construire ; celui qui y tient peu a intérêt à annoncer zéro, pour l'empêcher. Comme chacun ignore les annonces des autres, le plus sûr est d'exagérer au maximum : 200 € pour qui veut la passerelle, 0 € pour qui n'en veut pas. L'animation montre les annonces filer vers ces extrêmes : la décision devient un simple vote à la majorité, qui se trompe parfois.
Le mécanisme VCG : payer le tort que l'on cause aux autres
Vickrey (1961), Clarke (1971) et Groves (1973) ont trouvé la clef. On choisit la décision qui maximise la somme des valeurs annoncées, et chacun paie le tort que sa présence cause aux autres : ce qu'ils auraient obtenu sans lui, moins ce qu'ils obtiennent avec lui. Chacun touche alors la valeur totale créée, moins une somme qui ne dépend pas de son annonce : il a intérêt à ce que la décision maximise le total, donc à dire la vérité. Exemple : deux objets A et B. L'enchérisseur 1 ne veut que les deux ensemble ; le 2 ne veut que A ; le 3 ne veut que B.
Financer un pont : le pivot de Clarke
Revenons à la passerelle de 500 €, appliquons VCG. Chacun paie toujours sa part de 100 € si l'on construit, et annonce sa valeur nette (valeur moins 100 €). On construit si la somme des valeurs nettes est positive. En plus, celui qui est pivot — celui dont l'annonce fait basculer la décision — paie un impôt égal au tort causé aux autres : l'écart entre leur somme et zéro. Personne n'a alors intérêt à mentir : mentir ne change l'issue que pour la rendre moins bonne pour soi.
Le mécanisme d'espérance : équilibré, mais seulement en moyenne
Si l'on se contente d'une incitation « en moyenne » — dire la vérité est optimal quand on ignore les valeurs des autres et qu'on les suppose sincères —, on peut équilibrer le budget. Claude d'Aspremont et Louis-André Gérard-Varet (1979), et Kenneth Arrow la même année, ont trouvé comment : chacun reçoit le bien-être moyen que son annonce procurerait aux autres, et finance cette somme en payant sa part de ce que reçoivent les autres. Les transferts s'annulent exactement. Ici, trois habitants ont des valeurs nettes entre −100 € et +100 €, notées en centaines d'euros de −1 à +1.
Le théorème de Myerson et Satterthwaite : l'impossible trilemme
Le cas le plus simple : un vendeur, un acheteur, un objet. Le vendeur sait ce que l'objet lui coûte (c), l'acheteur ce qu'il vaut pour lui (v) ; tous deux sont tirés au hasard entre 0 et 1. Il faudrait échanger chaque fois que v > c. Roger Myerson et Mark Satterthwaite ont démontré en 1983 qu'aucun mécanisme ne peut à la fois être efficace, incitatif, équilibré (sans subvention extérieure) et laisser chacun libre de ne pas participer. Il faut renoncer à l'un des quatre. La page compare trois règles sur des milliers de rencontres.
Ce qu'il faut retenir
Faire dire la vérité
Le principe de révélation ramène la recherche aux règles où la vérité est optimale. VCG en fournit une : chacun paie le tort qu'il cause aux autres.
Ce que coûte la sincérité
Le pivot de Clarke jette de l'argent ; le mécanisme d'espérance équilibre le budget mais n'assure pas la participation.
Les théorèmes d'impossibilité
Green-Laffont, Myerson-Satterthwaite : on ne peut pas tout avoir. Concevoir un mécanisme, c'est choisir son compromis.
Pour aller plus loin
Les calculs de la page. Pivot de Clarke : l'habitant i paie |Σj≠iθj| s'il fait basculer la décision. Mécanisme d'espérance : ti = g(θi) − ½ Σj≠i g(θj), où g(r) est le bien-être moyen des deux autres quand i annonce r. Échange bilatéral : gains maximaux 1/6 ; prix affiché p : p(1 − p)/2 ; double enchère, équilibre linéaire : offre de l'acheteur 2v/3 + 1/12, demande du vendeur 2c/3 + 1/4, échange si v ≥ c + 1/4, gains 9/64.
Références. W. Vickrey (1961) ; E. Clarke, « Multipart pricing of public goods » (1971) ; T. Groves, « Incentives in teams » (1973) ; A. Gibbard (1973) ; J. Green et J.-J. Laffont, « Characterization of satisfactory mechanisms for the revelation of preferences for public goods » (1977) ; C. d'Aspremont et L.-A. Gérard-Varet, « Incentives and incomplete information » (1979) ; R. Myerson, « Incentive compatibility and the bargaining problem » (1979) ; R. Myerson et M. Satterthwaite, « Efficient mechanisms for bilateral trading », Journal of Economic Theory (1983) ; K. Chatterjee et W. Samuelson, « Bargaining under incomplete information » (1983).
Pages voisines. Les enchères (Vickrey, équivalence des revenus), les jeux bayésiens, les mariages stables, le marchandage de Nash et Rubinstein.