Prix ​​de l'anarchie dans les enchères - Price of anarchy in auctions

Partie d' une série sur
Enchères
Les types
Tout payant Troc double brésilien Calcutta Bougie chinois Combinatoire Valeur commune Acceptation différée Prix ​​discriminatoire Double néerlandais Anglais Effronté français Premier prix généralisé Second prix généralisé Japonais Multi-attribut Multiunité Pas de réserve Sens inverse Écossais Premier prix scellé suédois Prix ​​uniforme Enchère unique Valeur des revenus Vickrey Walrasian yankee
Enchère
Ombrage des enchères Calor licitantis Chasseur d'annulation Connivence Jump bidding Sniping
Contextes
Algorithmes Autos Art Charité Enfants Joueurs de cricket Noms de domaine Permis d'émission Fleurs Des esclaves Spectre Timbres Virginité Vin épouses
Théorie
Biens numériques Prix ​​de l'anarchie Équivalence des revenus Malédiction du gagnant
En ligne
Ebidding Marché électronique privé Logiciel
v t e

Le prix de l'anarchie ( PoA ) est un concept de la théorie des jeux et de la conception de mécanismes qui mesure comment le bien - être social d'un système se dégrade en raison du comportement égoïste de ses agents. Elle a été étudiée de manière approfondie dans divers contextes, notamment dans les enchères .

Dans une vente aux enchères, il y a un ou plusieurs articles et un ou plusieurs agents avec des évaluations différentes pour les articles. Les articles doivent être répartis entre les agents. Il est souhaitable que le bien - être social - la somme des valeurs de tous les agents - soit aussi élevé que possible.

Une approche pour maximiser le bien-être social consiste à concevoir un mécanisme véridique . Dans un tel mécanisme, chaque agent est incité à rapporter ses vraies évaluations aux articles. Ensuite, le commissaire-priseur peut calculer et mettre en œuvre une allocation qui maximise la somme des valeurs. Un exemple d'un tel mécanisme est l' enchère VCG .

Dans la pratique, cependant, il n'est pas toujours possible d'utiliser des mécanismes véridiques. Le mécanisme VCG, par exemple, pourrait être trop compliqué à comprendre pour les participants, prendre trop de temps à calculer par le commissaire-priseur et présenter d'autres inconvénients. Dans la pratique, des mécanismes non véridiques sont souvent utilisés, et il est intéressant de calculer combien de bien-être social est perdu par cette non-véracité.

On suppose souvent que, dans une vente aux enchères non véridique, les participants jouent une stratégie d'équilibre, telle qu'un équilibre de Nash . Le prix de l'anarchie de l'enchère est défini comme le rapport entre le bien-être social optimal et le bien-être social dans le pire équilibre:

${\ displaystyle PoA = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ min _ {s \ in EquilibriumAllocations} Welf (s)}}}$

Une notion connexe est le prix de la stabilité ( PoS ) qui mesure le rapport entre le bien-être social optimal et le bien-être social dans le meilleur équilibre:

${\ displaystyle PoS = {\ frac {\ max _ {s \ in Allocations} Welf (s)} {\ max _ {s \ in EquilibriumAllocations} Welf (s)}}}$

Evidemment . ${\ displaystyle 1 \ leq PoS \ leq PoA \ leq \ infty}$

Lorsqu'il y a des informations complètes (chaque agent connaît les évaluations de tous les autres agents), le type d'équilibre commun est l'équilibre de Nash - pur ou mixte. Lorsqu'il y a des informations incomplètes , le type d'équilibre commun est l'équilibre de Bayes-Nash . Dans ce dernier cas, il est courant de parler du prix bayésien de l'anarchie , ou BPoA.

Ventes aux enchères d'articles uniques

Dans une vente aux enchères au premier prix d'un seul article, un équilibre de Nash est toujours efficace, donc le PoA et le PoS sont 1.

Dans une enchère au second prix , il y a un équilibre de Nash dans lequel les agents rapportent honnêtement; il est efficace, donc le PoS est de 1. Cependant, le PoA est illimité! Par exemple, supposons qu'il y ait deux joueurs: Alice valorise l'élément comme a et Bob comme b , avec a > b .

Il existe un «bon» équilibre de Nash dans lequel Alice enchérit a et Bob enchérit b ; Alice reçoit l'article et paie b . Le bien-être social est un , ce qui est optimal.

Cependant, il existe également un "mauvais" équilibre de Nash dans lequel Alice enchérit 0 et Bob enchérit par exemple un +1; Bob reçoit l'article et ne paie rien. C'est un équilibre puisqu'Alice ne veut pas surenchérir sur Bob. Le bien-être social est b . Par conséquent, le PoA est a / b , qui est illimité.

Ce résultat semble trop pessimiste:

• Premièrement, dans une enchère au second prix, c'est une stratégie faiblement dominante pour chaque agent de déclarer sa véritable évaluation. Si nous supposons que les agents suivent leurs stratégies dominantes, alors le PoA est 1.
• De plus, c'est une stratégie dominée pour chaque agent de déclarer toute valeur supérieure à sa véritable évaluation.

Par conséquent, il est courant d'analyser le PoA sous une hypothèse de non surenchère - aucun agent n'offre au-dessus de sa véritable évaluation. Dans cette hypothèse, le PoA d'une enchère à un seul article est de 1.

Enchères parallèles

Dans une vente aux enchères parallèle (simultanée), les articles sont vendus en même temps au même groupe de participants. Contrairement à une vente aux enchères combinatoire - dans laquelle les agents peuvent enchérir sur des lots d'articles, ici les agents ne peuvent enchérir que sur des articles individuels indépendamment des autres. C'est-à-dire qu'une stratégie d'un agent est un vecteur d'enchères, une enchère par article. Le PoA dépend du type d'évaluation des acheteurs et du type d'enchère utilisé pour chaque article individuel. ${\ displaystyle m}$${\ displaystyle n}$

Cas 1: acheteurs submodulaires , enchères au second prix , informations complètes :

• Il existe un équilibre de Nash pur avec un bien-être social optimal. Par conséquent, le PoS est 1.
• Il est possible de calculer en temps polynomial un équilibre de Nash pur avec un bien-être social au moins la moitié de l'optimum. Par conséquent, le prix de la "stabilité polynomiale en temps" est d'au plus 2.
• Le PoA est illimité - comme déjà montré par l'exemple d'élément unique ci-dessus. Cependant, dans l' hypothèse d' une forte non surenchère (la somme des offres de tout acheteur sur n'importe quel bundle est au plus la valeur de ce bundle pour l'acheteur), le PoA est au plus 2. Ce dernier résultat est également valable lorsque les acheteurs les évaluations sont fractionnellement sous-additives .

Cas 2: acheteurs faiblement sous- additifs, enchères au deuxième prix, informations incomplètes . En supposant une forte surenchère , tout équilibre Bayes-Nash (mixte) atteint en espérant au moins la moitié du bien-être optimal; par conséquent, le BPoA est d'au plus 2. Ce résultat ne dépend pas du prieur commun des agents.

Cas 3: acheteurs sous- additifs, enchères au 2ème prix . Sous une hypothèse forte de non surenchère :

• Avec des informations complètes, le bien-être de chaque équilibre de Nash pur est au moins 1/2 de l'optimum, donc le PoA est au plus de 2.
• Avec des informations incomplètes, il existe des équilibres Bayes-Nash avec un bien-être inférieur à la moitié de l'optimum, donc le BPoA est supérieur à 2.
• Le BPoA est au plus , où est le nombre d'articles. Cette garantie est également valable pour l' équilibre corrélé grossier - et donc pour les cas particuliers d'équilibre de Nash mixte et d' équilibre corrélé . ${\ displaystyle 2 \ log {m}}$${\ displaystyle m}$
• Les deux limites supérieures ci-dessus sur le PoA se dégradent gracieusement lorsque les hypothèses de sous-additivité et de non-surenchère sont relâchées. Par exemple: si nous supposons que chaque joueur surenchère d'au plus un facteur constant, alors le PoA augmente d'au plus un facteur constant.

Cas 4: acheteurs généraux (monotones), enchères au premier prix , informations complètes :

• L'ensemble des équilibres de Nash purs du jeu sont exactement les équilibres walrasiens (équilibres de prix) du marché.
• Puisque de tels équilibres sont socialement optimaux (par le premier théorème de bien-être ), le PoA des équilibres de Nash purs est 1. Malheureusement, de tels équilibres peuvent ne pas exister.
• Un équilibre de Nash mixte existe toujours (lors du choix de la bonne règle de départage). Cependant, ce n'est pas nécessairement socialement optimal. Le PoA pourrait être aussi élevé que , et même le PoS pourrait être aussi élevé que . ${\ displaystyle \ Omega ({\ sqrt {m}})}$${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
  • Ce résultat s'étend également aux enchères au deuxième prix, même avec une hypothèse faible de surenchère .
• Le PoA est tout au plus . ${\ displaystyle O (m)}$
• Lorsque toutes les évaluations sont sous-additives, le PoA l'est tout au plus . ${\ displaystyle O (\ log {m})}$
• Lorsque toutes les évaluations sont - fractionnellement sous - additives , le PoA est au plus (en particulier, pour les acheteurs XOS, le PoA est au plus 2). ${\ displaystyle \ beta}$${\ displaystyle 2 \ beta}$
• Les trois dernières bornes valent également pour les équilibres à corrélation grossière; ils ne nécessitent PAS une hypothèse «pas de surenchère».

Cas 5: acheteurs généraux, enchères au 2ème prix, informations complètes . Avec des évaluations générales (qui peuvent avoir des complémentarités), l'hypothèse forte de non surenchère est trop forte, car elle empêche les acheteurs de proposer des valeurs élevées sur des lots d'articles complémentaires. Par exemple, si l'évaluation d'un acheteur est de 100 $ pour une paire de chaussures mais de 1 $ pour chaque chaussure individuelle, alors l'hypothèse forte de non surenchère l'empêche d'enchérir plus de 1 $ sur chaque chaussure, de sorte qu'il a peu de chances de gagner la paire. . Par conséquent, elle est remplacée par une hypothèse de faible surenchère , ce qui signifie que la condition de non surenchère n'est valable que pour le lot que l'agent remporte finalement (c'est-à-dire que la somme des offres de l'acheteur sur son lot alloué est au plus valeur pour ce bundle spécifique). Sous cette hypothèse de faible surenchère:

• L'ensemble des équilibres de Nash purs du jeu sont exactement les équilibres-prix conditionnels du marché.
• Étant donné que ces équilibres sont à moitié socialement optimaux (atteignent au moins la moitié du bien-être social maximum), le PoA des équilibres de Nash purs est au plus de 2. Malheureusement, de tels équilibres peuvent ne pas exister.

Cas 6: acheteurs généraux, enchères au 1er prix, informations incomplètes . Pour tout prieur commun:

• Le BPoA est tout au plus . ${\ displaystyle O (mn)}$
• Lorsque toutes les évaluations sont fractionnellement sous-additives, le BPoA est au plus (en particulier, pour les acheteurs XOS, le BPoA est au plus 2, et pour les acheteurs sous-additifs, il l'est ). ${\ displaystyle \ beta}$${\ displaystyle 4 \ beta}$${\ displaystyle O (\ log m)}$

Cas 7: acheteurs sous-additifs, informations incomplètes :

• Lorsque les articles sont vendus aux enchères au premier prix, le BPoA est au maximum de 2.
• Lorsque les articles sont vendus dans le cadre d'enchères au second prix, le BPoA est au maximum de 4. Cela est vrai à la fois dans l'hypothèse d'une surenchère forte (la somme des offres de tout acheteur sur n'importe quel lot est au plus la valeur de ce lot à l'acheteur), et selon l' hypothèse de faible surenchère (la somme attendue des offres gagnantes de tout acheteur est au plus la valeur gagnante attendue de cet acheteur).

Enchères séquentielles

Dans une vente aux enchères séquentielle , les articles sont vendus dans des enchères consécutives, les uns après les autres. Le type d'équilibre commun est l'équilibre parfait de sous-jeu dans les stratégies pures (SPEPS). Lorsque les acheteurs ont des informations complètes (c'est-à-dire qu'ils connaissent à l'avance la séquence des enchères) et qu'un seul article est vendu à chaque tour, un SPEPS existe toujours. ${\ displaystyle m}$

Le PoA de ce SPEPS dépend des fonctions d'utilité des soumissionnaires et du type d'enchère utilisé pour chaque article individuel.

Les cinq premiers résultats ci-dessous s'appliquent aux agents disposant d' informations complètes (tous les agents connaissent les évaluations de tous les autres agents):

Cas 1: Articles identiques, deux acheteurs, enchères au 2ème prix :

• Lorsqu'au moins un acheteur a une fonction de valorisation concave ( rendements décroissants ), le PoA est au plus . ${\ displaystyle 1 / (1-e) \ approx 1.58}$
• Les résultats numériques montrent que, lorsqu'il y a de nombreux soumissionnaires avec des fonctions de valorisation concaves, la perte d'efficacité diminue à mesure que le nombre d'utilisateurs augmente.

Cas 2: acheteurs additifs :

• Avec les enchères au second prix, le PoA est illimité - le bien-être dans un SPEPS peut être arbitrairement petit!

Cas 3: acheteurs à la demande unitaire :

• Avec les enchères au premier prix, le PoA est au plus de 2 - le bien-être dans un SPEPS est toujours au moins la moitié du maximum (si les stratégies mixtes sont autorisées, le PoA est au plus de 4).
• Avec les enchères au second prix, le PoA est à nouveau illimité.

Ces résultats sont surprenants et ils soulignent l'importance de la décision de conception d'utiliser une enchère au premier prix (plutôt qu'une enchère au second prix) à chaque tour.

Cas 4: acheteurs sous - modulaires (notez que l'additif et la demande unitaire sont des cas particuliers de sous-modulaire):

• Avec les enchères au 1er prix et au 2ème prix, le PoA est illimité, même s'il n'y a que quatre soumissionnaires. L'intuition est que le soumissionnaire de grande valeur pourrait préférer laisser un soumissionnaire de faible valeur gagner, afin de réduire la concurrence à laquelle il pourrait faire face dans les prochains tours.

Cas 5: additif + UD . Supposons que certains soumissionnaires ont des évaluations additives tandis que d'autres ont des évaluations de la demande unitaire. Dans une séquence d'enchères au premier prix, le PoA peut être au moins , où m est le nombre d'articles et n est le nombre de soumissionnaires. De plus, les équilibres inefficaces persistent même en cas d'élimination répétée des stratégies faiblement dominées. Cela implique une inefficacité linéaire pour de nombreux milieux naturels, notamment: ${\ Displaystyle \ min (n, m)}$

• acheteurs avec des évaluations de remplacement brutes ,
• évaluations capacitives,
• les évaluations budgétaires additives,
• des évaluations additives avec des contraintes budgétaires strictes sur les paiements.

Cas 6: acheteurs à demande unitaire, informations incomplètes, enchères au 1er prix : le BPoA est au maximum de 3.

Enchères utilisant des algorithmes gourmands

Voir

Enchères généralisées au second prix

Voir

Rubriques connexes

Des études sur le PoA dans les enchères ont fourni des informations sur d'autres paramètres qui ne sont pas liés aux enchères, tels que les jeux de formation de réseau.

Sommaire

[Le tableau partiel - ne contient que des enchères parallèles - doit être rempli]

Multi-enchères	Enchère unique	Informations	Évaluations	Hypothèses	PoA	Pos	commentaires
Parallèle	2ème prix	Achevée	submodulaire	forte-sans-surenchère	2	pure: 1 [existe toujours]
Parallèle	2ème prix	Bayésien	XOS	forte-sans-surenchère	2
Parallèle	2ème prix	Achevée	sous-additif	forte-sans-surenchère	2
Parallèle	2ème prix	Bayésien	sous-additif	forte-sans-surenchère	> 2, <2 log (m)
Parallèle	1er prix	Achevée	monotone	Aucun	pure: 1 [quand existe]		NE pur = NOUS.
Parallèle	1er prix	Achevée	monotone	Aucun	mixte: ${\ displaystyle \ Omega ({\ sqrt {m}})}$	${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
Parallèle	1er prix	Bayésien	monotone	Aucun	${\ displaystyle O (mn)}$	${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
Parallèle	2ème prix	Achevée	monotone	faible surenchère	pure: 2 [quand existe]		NE pur = WE conditionnel
Parallèle	1er prix	Bayésien	sous-additif	Aucun	2	${\ displaystyle \ Omega ({\ sqrt {m}} / \ log {m})}$
Parallèle	2ème prix	Bayésien	sous-additif	faible / forte-sans surenchère	4

Les références