La conception de mécanismes (mechanism design) est la théorie des jeux inversee : au lieu de predire l’issue d’un jeu donne, on concoit les règles (le mécanisme) pour qu’un résultat souhaite (efficacite, equite, sincerite) emerge des stratégies des joueurs. Le principe de revelation (Myerson 1979) garantit que tout equilibre d’un mécanisme quelconque peut etre reproduit par un mécanisme sincere ou declarer sa vraie valeur est optimal.
Plan pedagogique
Principe de revelation — primitives Bidder / utilite / allocation
Encheres premier et second prix — Vickrey, sincerite
Mécanisme VCG — Vickrey-Clarke-Groves, règle de Clarke
Parite #4956 : la version Python s’appuie sur numpy/scipy (vecteurs) et matplotlib. Ce twin C# (BCL .NET 9, 0 NuGet) deroule les mêmes mécanismes from-scratch ; la viz matplotlib devient des tables console (convention GT-4c). L’eleve voit le coeur combinatoire des mécanismes dans deux langages.
1. Principe de revelation et primitives
Un mécanisme demande a chaque joueur \(i\) un report\(r_i\) de sa valeur privee \(v_i\), calcule une allocation\(x(r)\) et des paiements\(p(r)\). L’utilite quasi-lineaire du joueur \(i\) vaut :
\[u_i(r) = v_i \cdot x_i(r) - p_i(r)\]
Un mécanisme est sincere (strategy-proof / IC) si declarer \(r_i = v_i\) est une stratégie faiblement dominante pour tout \(i\), quelles que soient les valeurs des autres.
using System.Linq;using System.Text;using System.Collections.Generic;staticvoidShow(string s){ s.Display();}// Bidder : identite + valeur privee (typee).public record Bidder(int Id,double Value);// Utilite quasi-lineaire : u = value*allocation - payment.staticdoubleUtility(Bidder b,double allocation,double payment)=> b.Value* allocation - payment;// Apercu : un joueur qui recoit l'objet (allocation=1) a value=10 et paie 6.var me =newBidder(0,10.0);$"Utilite si alloue a 10, paiement 6 : u = {Utility(me, 1.0, 6.0)} (doit valoir 4)".Display();$"Utilite si non-alloue (allocation=0), paiement 0 : u = {Utility(me, 0.0, 0.0)} (doit valoir 0)".Display();
The below script needs to be able to find the current output cell; this is an easy method to get it.
Utilite si alloue a 10, paiement 6 : u = 4 (doit valoir 4)
Utilite si non-alloue (allocation=0), paiement 0 : u = 0 (doit valoir 0)
2. Encheres premier et second prix
2.1 Enchere premier-prix (first-price sealed-bid)
Chaque joueur soumet une enchere \(r_i\). Le plus haut enchérisseur gagne l’objet et paie son enchere. Stratégie optimale : sous-encherir (bid shading \(r_i < v_i\)) — ce mécanisme n’est pas sincere.
2.2 Enchere second-prix (Vickrey, 1961)
Le plus haut enchérisseur gagne mais paie le second prix (la deuxieme enchere la plus elevee). Theoreme de Vickrey : declarer \(r_i = v_i\) est une stratégie faiblement dominante.
Lecture des resultats : pourquoi le premier-prix laisse zero surplus
La sortie oppose les deux encheres sur la meme instance (valeurs 10, 8, 6, 4) :
Premier-prix : le gagnant (enchérisseur 0, valeur 10) paie sa propre enchere (10). Son utilite vaut donc 10 - 10 = 0. C’est le winner’s curse — remporter l’objet au prix exact de sa valeur ne laisse aucun gain. La colonne sincerity: NON confirme qu’un joueur a interet a sous-encherir (offrir moins que sa valeur vraie) pour degager un surplus : le premier-prix n’est pas sincere (pas strategy-proof).
Vickrey (second-prix) : le meme gagnant paie la deuxieme meilleure enchere (8), soit 10 - 8 = 2 d’utilite. declarer sa valeur vraie r = v est ici une strategie dominante (la cellule suivante le demontre empiriquement) : Vickrey est strategy-proof.
Ce contraste utilite 0 vs utilite 2 est le coeur pedagogique du principe de revelation : deux regles d’enchere en apparence proches (toutes deux « le plus offrant gagne ») ont des proprietes strategiques radicalement differentes selon ce que le gagnant paie — son propre prix, ou celui du second.
2.3 Preuve de la sincerite de Vickrey
Soit un joueur de valeur \(v\), les autres enchères ayant un maximum \(m\) (second prix effectif si le joueur gagne). En declarant \(r\) :
\(r \geq m\) : gagne, paie \(m\), utilite \(v - m\) (indépendant de \(r\) tant que \(r \geq m\)).
\(r < m\) : perd, utilite \(0\).
Donc : si \(v \geq m\), gagner donne \(v - m \geq 0\), declare \(r = v\) gagne. Si \(v < m\), declarer \(r = v\) perd sagement (utilite 0), alors que surencherir (\(r > m > v\)) ferait gagner a perte. Dans tous les cas, \(r = v\) est optimal.
// Verification empirique : pour un joueur de valeur v, aucune enchere r != v// ne bat l'utilite de l'enchere sincere r=v, quel que soit le max m des autres.static(double bestR,double bestU,bool sincereIsOptimal)VickreyTruthfulness(double v,double m,double rMax=15.0,double step=0.1){double bestR = v, bestU =double.NegativeInfinity;var others = m;// second prix effectif si le joueur gagnefor(double r =0; r <= rMax; r += step){double u =(r >= m)?(v - m):0.0;// gagne et paie m, ou perdif(u > bestU +1e-9){ bestU = u; bestR = r;}}// sincereIsOptimal : r=v donne une utilite egale au meilleur (a tolerance pres)double uSincere =(v >= m)?(v - m):0.0;return(bestR, bestU, Math.Abs(uSincere - bestU)<1e-6);}var cases =new[]{(v:10.0, m:8.0),(v:5.0, m:8.0),(v:7.0, m:7.0),(v:12.0, m:3.0)};var sb2 =newStringBuilder();sb2.AppendLine(" v | m | meilleure enchere r | u optimale | sincere optimal ?");sb2.AppendLine(newstring('-',60));foreach(var(v, m)in cases){var(br, bu, ok)=VickreyTruthfulness(v, m); sb2.AppendLine($"{v,3} | {m,3} | r >= {m,3} (ex. {br,4:F1}) | {bu,10:F2} | {(ok ? "OUI" : "NON")}");}Show(sb2.ToString());"Verdict : dans tous les cas, declarer r=v atteint l'utilite optimale. Vickrey est sincere (strategy-proof).".Display();
v | m | meilleure enchere r | u optimale | sincere optimal ?
------------------------------------------------------------
10 | 8 | r >= 8 (ex. 8,1) | 2,00 | OUI
5 | 8 | r >= 8 (ex. 0,0) | 0,00 | OUI
7 | 7 | r >= 7 (ex. 0,0) | 0,00 | OUI
12 | 3 | r >= 3 (ex. 3,0) | 9,00 | OUI
Verdict : dans tous les cas, declarer r=v atteint l'utilite optimale. Vickrey est sincere (strategy-proof).
3. Mécanisme VCG (Vickrey-Clarke-Groves)
Pour \(n\) objets et \(n\) enchérisseurs (cas simple : un objet par personne), VCG :
Allocation : maximise le bien-etre social \(\sum_i v_i x_i\) (chaque objet au plus haut enchérisseur).
Paiement (règle de Clarke) : le joueur \(i\) paie son externalite = (bien-etre des autres sans \(i\)) \(-\) (bien-etre des autres avec \(i\) present).
VCG est sincere et efficace (maximise le surplus social).
// VCG multi-objets (matrice valuations[objet][enchérisseur]) avec regle de Clarke.// Retourne : allocation (objet -> gagnant) et paiements (par enchérisseur).static(int[] allocation,double[] payments)Vcg(double[,] valuations){int nItems = valuations.GetLength(0);int nBidders = valuations.GetLength(1);// Allocation : chaque objet au plus haut enchérisseur.int[] alloc =newint[nItems];for(int it =0; it < nItems; it++){double best =double.NegativeInfinity;int w =0;for(int b =0; b < nBidders; b++)if(valuations[it, b]> best){ best = valuations[it, b]; w = b;} alloc[it]= w;}// Bien-etre social total et par joueur.doubleWelfareWithout(int excluded){double sum =0;for(int it =0; it < nItems; it++){double best =double.NegativeInfinity;for(int b =0; b < nBidders; b++)if(b != excluded && valuations[it, b]> best) best = valuations[it, b];if(best >0) sum += best;}return sum;}double[] payments =newdouble[nBidders];for(int b =0; b < nBidders; b++){double welfareOthersWith =0;// bien-etre des autres AVEC b present (sous l'allocation VCG)for(int it =0; it < nItems; it++)if(alloc[it]!= b) welfareOthersWith += valuations[it, alloc[it]];double welfareOthersWithout =WelfareWithout(b); payments[b]= welfareOthersWithout - welfareOthersWith;// externalite = regle de Clarke}return(alloc, payments);}// 3 objets, 3 enchérisseurs. valuations[objet, enchérisseur].double[,] V ={{10,8,4},// objet 0 : joueur 0 l'apprecie le plus{6,9,5},// objet 1 : joueur 1{3,2,7},// objet 2 : joueur 2};var(alloc, pay)=Vcg(V);var sb3 =newStringBuilder();sb3.AppendLine(" Objet | Enchérisseur gagnant | Valeur | Paiement VCG | Utilite");sb3.AppendLine(newstring('-',58));for(int it =0; it <3; it++){int w = alloc[it]; sb3.AppendLine($" {it} | {w} | {V[it,w],3} | {pay[w],4:F1} | {Utility(new Bidder(w, V[it,w]), 1, pay[w]):F1}");}Show(sb3.ToString());$"Somme des paiements VCG = {pay.Sum():F1} (regle de Clarke : chaque gagnant paie son externalite sur les autres).".Display();
Somme des paiements VCG = 17,0 (regle de Clarke : chaque gagnant paie son externalite sur les autres).
Lecture du resultat VCG : la regle de Clarke et l’externalite
Chaque gagnant paie non pas sa valeur, mais le cout qu’il impose aux autres (son externalite), calculee par la regle de Clarke : le paiement d’un gagnant = (somme des valeurs des autres dans l’allocation optimale SANS lui) - (somme des valeurs des autres dans l’allocation optimale AVEC lui).
Sur la sortie : objet 0 gagne par l’enchérisseur 0 (valeur 10), paiement VCG 8 — soit exactement la valeur qu’aurait recue le second meilleur (8) si l’enchérisseur 0 avait ete absent. De meme pour les objets 1 et 2 (paiements 6 et 3). La somme des paiements (17) est inferieure a la somme des valeurs attribuees (10+9+7 = 26) : le mecanisme VCG n’est pas equilibre budgetairement (il laisse un deficit cote vendeur). C’est le compromis fondamental de VCG : il garantit simultanement effacite (allocation optimale) et sincerite (strategy-proof), mais au prix d’un budget non equilibre — on ne peut pas avoir les trois (Myerson-Satterthwaite pour les echanges bilateraux).
4. Gale-Shapley (stable marriages, 1962)
\(n\) hommes et \(n\) femmes, chacun avec un ordre de préférence strict sur l’autre groupe. L’algorithme deferred acceptance (Gale-Shapley 1962) :
Chaque homme non-fiance propose a sa femme preferee qui ne l’a pas encore rejete.
Chaque femme garde temporairement le meilleur (selon sa préférence) parmi ses prétendants + son fiance courant, rejette les autres.
Repeter jusqu’a ce que tout le monde soit fiance.
Theoreme : l’algorithme termine en au plus \(n^2\) étapes et produit un matching stable (aucune paire bloquante). Cote proposeurs, il est optimal (chaque homme a le meilleur partenaire stable possible).
// Gale-Shapley (deferred acceptance). hommes = proposeurs.// preferencesH[h] = liste ordonnee des femmes (indice 0 = preferee).// preferencesF[w] = liste ordonnee des hommes.static Dictionary<int,int>GaleShapley(List<List<int>> preferencesH, List<List<int>> preferencesF){int n = preferencesH.Count;int[] nextProposal =newint[n];// index de la prochaine femme a qui l'homme h va proposerint[] fianceOfWoman = Enumerable.Repeat(-1, n).ToArray(); Queue<int> free =new Queue<int>(Enumerable.Range(0, n));while(free.Count>0){int h = free.Dequeue();if(nextProposal[h]>= n)continue;int w = preferencesH[h][nextProposal[h]];// prochaine femme preferee nextProposal[h]++;if(fianceOfWoman[w]==-1)// femme libre : engagement temporaire{ fianceOfWoman[w]= h;}else{int curr = fianceOfWoman[w];// La femme garde celui qu'elle prefere entre curr et h.bool prefersNew = preferencesF[w].IndexOf(h)< preferencesF[w].IndexOf(curr);if(prefersNew){ fianceOfWoman[w]= h; free.Enqueue(curr);// curr redevient libre}else{ free.Enqueue(h);// h rejete, retentera la suivante}}}// Resultat : homme -> femmevar matching =new Dictionary<int,int>();for(int w =0; w < n; w++) matching[fianceOfWoman[w]]= w;return matching;}// Cas canonique (Gale-Shapley 1962), n=4.var pH =new List<List<int>>{new(){0,1,2,3},// homme 0 prefere femme 0, puis 1, ...new(){1,0,3,2},new(){0,2,1,3},new(){1,3,0,2},};var pF =new List<List<int>>{new(){1,0,2,3},// femme 0 prefere homme 1, puis 0, ...new(){0,1,3,2},new(){2,0,1,3},new(){3,1,0,2},};var matching =GaleShapley(pH, pF);var sb4 =newStringBuilder();sb4.AppendLine(" Homme | Femme (cote-H optimal)");sb4.AppendLine(newstring('-',26));foreach(var(h, w)in matching.OrderBy(kv => kv.Key)) sb4.AppendLine($" {h} | {w}");Show(sb4.ToString());// Verifier la stabilite : aucune paire (h,w) bloquante.staticintCountBlockingPairs(Dictionary<int,int> matching, List<List<int>> pH, List<List<int>> pF){int n = pH.Count;int blocks =0;var womanOfH = matching;var manOfW =newint[n];foreach(var(h, w)in matching) manOfW[w]= h;for(int h =0; h < n; h++)for(int w =0; w < n; w++){if(womanOfH[h]== w)continue;int currH = manOfW[w];int currW = womanOfH[h];// (h,w) bloquante si chacun prefere l'autre a son partenaire courant.bool hPrefersW = pH[h].IndexOf(w)< pH[h].IndexOf(currW);bool wPrefersH = pF[w].IndexOf(h)< pF[w].IndexOf(currH);if(hPrefersW && wPrefersH) blocks++;}return blocks;}int blocks =CountBlockingPairs(matching, pH, pF);$"Nombre de paires bloquantes : {blocks} (doit valoir 0 => matching stable)".Display();
Nombre de paires bloquantes : 0 (doit valoir 0 => matching stable)
Lecture du resultat : stabilite et avantage du coté proposeur
La sortie affiche Nombre de paires bloquantes : 0 — c’est la definition meme d’un matching stable : aucune paire (homme, femme) ne prefersrait s’etre mutuellement a leur partenaire actuel. L’algorithme de Gale-Shapley (deferred acceptance) termine toujours en au plus \(n^2\) iterations sur un tel etat stable.
Un point subtil, invisible dans le compte rendu mais crucial : comme ce sont les hommes qui proposent (cote proposeur), le resultat est optimal pour les hommes ET pessimal pour les femmes parmi tous les matchings stables. Chaque homme obtient la meilleure partenaire qu’il puisse avoir dans AUCUN matching stable ; chaque femme, la pire. Inverser les roles (femmes proposent) donne le matching dual — egal en stabilite mais inverse en satisfaction. C’est pourquoi Gale-Shapley est utilise en affectation internats-medecins (cote etudiant proposeur) : le coté proposeur est avantagé par construction.
5. Double auction (echange bilateral)
Un acheteur (valeur \(v_b\)) et un vendeur (cout \(c_s\)). Un mécanisme simple : si \(v_b \geq c_s\), echange a un prix \(p\) intermediaire (ex. milieu \((v_b + c_s)/2\)), sinon pas d’echange. L’efficacite requiert l’echange exactement quand \(v_b \geq c_s\).
// Double auction bilateral : trade si v_b >= c_s, au prix median.static(bool trade,double price)BilateralTrade(double vBuyer,double cSeller){if(vBuyer >= cSeller){double p =(vBuyer + cSeller)/2.0;return(true, p);}return(false,0.0);}var cases2 =new[]{(vb:10.0, cs:4.0),(vb:5.0, cs:8.0),(vb:7.0, cs:7.0),(vb:12.0, cs:12.0)};var sb5 =newStringBuilder();sb5.AppendLine(" v_b | c_s | Echange | Prix | Surplus acheteur | Surplus vendeur");sb5.AppendLine(newstring('-',60));foreach(var(vb, cs)in cases2){var(t, p)=BilateralTrade(vb, cs);double sb_u = t ?(vb - p):0;double ss_u = t ?(p - cs):0; sb5.AppendLine($"{vb,3} | {cs,3} | {(t ? "OUI" : "non")} | {p,4:F1} | {sb_u,15:F1} | {ss_u,14:F1}");}Show(sb5.ToString());"Verdict : echange efficace (OUI ssi v_b >= c_s). Le prix median partage le surplus.".Display();
Verdict : echange efficace (OUI ssi v_b >= c_s). Le prix median partage le surplus.
Lecture du resultat : efficacite et partage du surplus
Deux leçons se lisent dans la sortie :
Efficacite : l’echange a lieu (OUI) si et seulement si la valeur de l’acheteur \(v_b\) est au moins egale au cout du vendeur \(c_s\) — cas v_b=10, c_s=4 (echange) vs v_b=5, c_s=8 (pas d’echange). C’est exactement le critere d’efficacite de Pareto : transferer l’objet au plus haut valeurant cree du surplus ssi \(v_b \geq c_s\).
Partage du surplus : le prix median \((v_b + c_s)/2\) partage equitablement le surplus total \((v_b - c_s)\) entre acheteur et vendeur. Pour \(v_b=10, c_s=4\) : surplus total 6, prix 7 → acheteur gagne \(10-7=3\), vendeur gagne \(7-4=3\). Symetrique, donc equitable — mais ce mecanisme median n’est pas strategy-proof (chaque coté a interet a manipuler sa declaration pour rapprocher le prix de son coté), contrairement a VCG ci-dessus. La double-auction mediane sacrifie la sincerite pour la simplicite et l’equilibre budgetaire.
6. Exercices
Convention C.1 : les stubs s’executent sans erreur (jamais throw). Remplir le corps, re-executer, verifier.
Exercice 1 — Enchere all-pay
Dans une enchere all-pay, tous les joueurs paient leur enchere, mais seul le plus haut enchérisseur gagne l’objet. Implementer l’allocation + les paiements.
Indices : - Étape 1 : le gagnant est argmax(bids). - Étape 2 : tous les joueurs paient leur enchere (pas seulement le gagnant).
// Exercice 1 : enchere all-pay.// TODO etudiant : retourner (gagnant, tableau des paiements par joueur).static(int winner,double[] payments)AllPay(double[] bids){// Indice : tous paient leur enchere ; seul le gagnant recoit l'objet.double[] pay =newdouble[bids.Length];// TODO etudiant : chaque joueur paie bids[i]int w =0;// TODO etudiant : argmaxreturn(w, pay);}"Exercice a completer".Display();
Exercice a completer
Exercice 2 — Moyenne des rangs (qualite d’un matching)
Après un matching stable, le rang moyen des conjoints mesure l’equite : un rang faible (proche de 0) signifie que chacun epouse quelqu’un haut dans sa préférence.
Indice : pour chaque homme \(h\), rang = preferencesH[h].IndexOf(femme(h)). Moyenner sur tous les \(h\), puis sur les \(f\).
// Exercice 2 : rang moyen cote hommes et cote femmes.// TODO etudiant : retourner (rangMoyenHommes, rangMoyenFemmes).static(double avgMen,double avgWomen)AverageRanks(Dictionary<int,int> matching, List<List<int>> pH, List<List<int>> pF){// Indice : pH[h].IndexOf(matching[h]) = rang de la femme attribuee pour l'homme h.double avgMen =0.0;double avgWomen =0.0;return(avgMen, avgWomen);// TODO etudiant}"Exercice a completer".Display();
Exercice a completer
Exercice 3 — VCG sur 2 objets, verifier la sincerite
Reconstruire une instance VCG a 2 objets et 2 enchérisseurs, puis verifier qu’aucun joueur n’ameliore son utilite en sous-declarant sa valeur.
Indice : faire varier le report du joueur 0 de sa vraie valeur vers le bas ; comparer les utilites VCG obtenues.
// Exercice 3 : verifier que sous-declarer dans VCG n'ameliore pas l'utilite.// TODO etudiant : retourner (utiliteSincere, utiliteOptimale, sincereIsOptimal).static(double uSincere,double uOptimal,bool sincereOptimal)VcgTruthfulness2x2(double v0_true,double v1,double v0_other){// Indice : fixer l'autre objet et l'autre joueur, balayer le report du joueur 0.return(0,0,false);// TODO etudiant}"Exercice a completer".Display();
Exercice a completer
Conclusion
Ce que vous avez appris
Principe de revelation — tout equilibre d’un mécanisme se reproduit par un mécanisme sincere (Myerson 1979) ; utilite quasi-lineaire \(u_i = v_i x_i - p_i\).
Enchere premier-prix — le gagnant paie son enchere ; non sincere (bid shading).
Enchere second-prix (Vickrey 1961) — le gagnant paie le second prix ; sincere : declarer \(r = v\) est faiblement dominant (verifie empiriquement).
VCG (Vickrey-Clarke-Groves) — allocation efficace (max surplus social), paiement = externalite (règle de Clarke) ; sincere et efficient.
Gale-Shapley (1962) — deferred acceptance ; termine en \(\leq n^2\) étapes, produit un matching stable (0 paire bloquante), optimal cote proposeurs.
Double auction — echange efficace ssi \(v_b \geq c_s\), prix median partageant le surplus.
Pont avec la version Python
La version Python (GameTheory-16-MechanismDesign-Python.ipynb) deroule les mêmes mécanismes avec numpy/scipy (vecteurs) et matplotlib pour les figures. Ce twin C# traduit la logique en C# pur (BCL .NET 9, 0 NuGet), la viz matplotlib devient des tables console. Le notebook GameTheory-15-CooperativeGames-Python couvre la théorie cooperative (Shapley, core), complementaire de la théorie des mécanismes (non-cooperative / incitations).
Parite #4956
Twin de parite legitime : les deux langages implementent les mécanismes from-scratch. L’intérêt est la traduction du coeur combinatoire (argmax, externalite, deferred acceptance, stabilite) et la confirmation des cas canoniques (sincerite de Vickrey, optimalite cote proposeurs de Gale-Shapley, règle de Clarke).