Enchères généralisées au second prix - Generalized second-price auction

Partie d' une série sur
Les enchères
Les types
Tout payant Amsterdam Anglo-néerlandais Troc double Meilleur / pas meilleur brésilien Calcutta Bougie chinois Combinatoire Valeur commune Acceptation différée Prix ​​discriminatoire Double néerlandais Anglais Avant français Premier prix généralisé Second prix généralisé Japonais Multi-attribut Multiunité Pas de réserve Rang Sens inverse Écossais Premier prix scellé Ascendant simultané Prix ​​unique Feu de circulation 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 De l'art Charité Enfants Joueurs de cricket Noms de domaine Permis d'émission Fleurs Les chevaux Prêts 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

L' enchère au deuxième prix généralisée (GSP) est un mécanisme d'enchères non véridique pour plusieurs articles. Chaque enchérisseur place une offre. Le plus offrant obtient le premier emplacement, le deuxième plus élevé, le deuxième emplacement et ainsi de suite, mais le plus offrant paie l'offre de prix du deuxième plus offrant, le deuxième paie l'offre de prix par le troisième plus élevé, et bientôt. D'abord conçu comme une extension naturelle de la vente aux enchères Vickrey , il conserve certaines des propriétés souhaitables de la vente aux enchères Vickrey. Il est principalement utilisé dans le contexte des enchères de mots clés, où les emplacements de recherche sponsorisés sont vendus aux enchères. Les premières analyses du SPG se trouvent dans la littérature économique d'Edelman, Ostrovsky et Schwarz et de Varian . Il est utilisé par la technologie AdWords de Google et par Facebook, qui est désormais passé aux enchères Vickrey – Clarke – Groves

Modèle formel

Supposons qu'il y ait des soumissionnaires et des emplacements. Chaque emplacement a une probabilité d'être cliqué . Nous pouvons supposer que les emplacements supérieurs ont une plus grande probabilité d'être cliqué, donc: ${\ displaystyle n}$${\ Displaystyle k <n}$${\ displaystyle \ alpha _ {i}}$

${\ displaystyle \ alpha _ {1} \ geq \ alpha _ {2} \ geq \ cdots \ geq \ alpha _ {k}. \,}$

Nous pouvons penser à des emplacements virtuels supplémentaires avec un taux de clics nul, donc pour . Désormais, chaque enchérisseur soumet une offre indiquant le maximum qu'il est prêt à payer pour un créneau. Chaque enchérisseur a également une valeur intrinsèque pour l'achat d'une machine à sous . Notez que l' offre d' un joueur n'a pas besoin d'être la même que sa véritable évaluation . Nous ordonnons les soumissionnaires par leur offre, disons: ${\ displaystyle nk}$${\ displaystyle \ alpha _ {m} = 0}$${\ Displaystyle k <m \ leq n}$${\ displaystyle b_ {i}}$${\ displaystyle v_ {i}}$ ${\ displaystyle b_ {i}}$ ${\ displaystyle v_ {i}}$

${\ displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n}, \,}$

et facturer à chaque soumissionnaire un prix . Le prix sera de 0 s'ils n'ont pas gagné une machine à sous. Les machines à sous sont vendues dans un modèle de paiement au clic , de sorte qu'un enchérisseur ne paie que pour un emplacement si l'utilisateur clique réellement dans cet emplacement. Nous disons que l' utilité du soumissionnaire qui est alloué à l'emplacement est . Le bien-être social total résultant de la possession ou de la vente de tous les créneaux horaires est donné par: Le revenu total attendu est donné par: ${\ displaystyle p_ {i}}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle u_ {i} = \ alpha _ {i} (v_ {i} -p_ {i})}$${\ displaystyle SW = \ sum _ {i} \ alpha _ {i} v_ {i}.}$${\ displaystyle TR = \ sum _ {i} \ alpha _ {i} p_ {i}.}$

Mécanisme GSP

Pour spécifier un mécanisme, nous devons définir la règle d'allocation (qui obtient quel créneau) et les prix payés par chaque enchérisseur. Dans une enchère généralisée au second prix, nous ordonnons les enchérisseurs en fonction de leur enchère et attribuons la première place au plus offrant, la deuxième au deuxième plus offrant, etc. Ensuite, en supposant que les offres sont classés par ordre décroissant l'appel d' offres des soumissionnaires se emplacement pour . Chaque soumissionnaire gagnant une fente paie l'offre du plus offrant prochain, donc: . ${\ displaystyle b_ {1} \ geq b_ {2} \ geq \ cdots \ geq b_ {n}, \,}$${\ displaystyle b_ {i}}$${\ displaystyle i}$${\ displaystyle 1 \ leq i \ leq k}$${\ displaystyle p_ {i} = b_ {i + 1}}$

Non-véracité

Il y a des cas où l'offre de la vraie valeur n'est pas un équilibre de Nash . Par exemple, considérons deux créneaux avec et et trois soumissionnaires avec des évaluations , et et des offres , et respectivement. Ainsi , et . L'utilité pour le soumissionnaire est Cet ensemble d'offres n'est pas un équilibre de Nash, puisque le premier enchérisseur pourrait réduire son offre à 5 et obtenir le deuxième créneau pour le prix de 1, augmentant ainsi son utilité à . ${\ displaystyle \ alpha _ {1} = 1}$${\ displaystyle \ alpha _ {2} = 0,4}$${\ displaystyle v_ {1} = 7}$${\ displaystyle v_ {2} = 6}$${\ displaystyle v_ {3} = 1}$${\ displaystyle b_ {1} = 7}$${\ displaystyle b_ {2} = 6}$${\ displaystyle b_ {3} = 1}$${\ displaystyle p_ {1} = b_ {2} = 6}$${\ displaystyle p_ {2} = b_ {3} = 1}$${\ displaystyle 1}$${\ displaystyle u_ {1} = \ alpha _ {1} (v_ {1} -p_ {1}) = 1 (7-6) = 1.}$${\ displaystyle 0.4 (5-1) = 1.6}$

Équilibres du SPG

Edelman, Ostrovsky et Schwarz, travaillant sous des informations complètes, montrent que le SPG (dans le modèle présenté ci-dessus) a toujours un équilibre efficace localement sans envie, c'est-à-dire un équilibre maximisant le bien-être social, qui est mesuré comme où le soumissionnaire se voit attribuer un créneau en fonction de le vecteur d'enchères décroissant . En outre, le revenu total attendu dans tout équilibre local sans envie est au moins aussi élevé que dans le résultat VCG (véridique) . ${\ displaystyle SW = \ sum _ {i} \ alpha _ {i} v_ {i}}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle (b_ {1}, \ dots, b_ {n})}$

Les limites du bien-être à l'équilibre de Nash sont données par Caragiannis et al., Prouvant un prix de la limite de l' anarchie . Dütting et coll. et Lucier et al. prouver que tout équilibre de Nash extrait au moins la moitié des revenus véridiques de VCG de tous les créneaux horaires sauf le premier. L'analyse informatique de ce jeu a été réalisée par Thompson et Leyton-Brown . ${\ displaystyle 1.282}$

SPG et incertitude

Les résultats classiques dus à Edelman, Ostrovsky et Schwarz et Varian sont valables dans le cadre de l'information complète - lorsqu'il n'y a pas d'incertitude impliquée. Des résultats récents tels que Gomes et Sweeney et Caragiannis et al. et aussi empiriquement par Athey et Nekipelov discutent de la version bayésienne du jeu - où les joueurs ont des croyances sur les autres joueurs mais ne connaissent pas nécessairement les évaluations des autres joueurs.

Gomes et Sweeney prouvent qu'un équilibre efficace pourrait ne pas exister dans le cadre d'informations partielles. Caragiannis et coll. considérons la perte de bien-être à l'équilibre Bayes – Nash et prouvons une borne du prix de l'anarchie de 2,927. Les bornes du revenu à l'équilibre Bayes – Nash sont données par Lucier et al. et Caragiannis et al.

Contraintes budgétaires

L'impact des contraintes budgétaires dans le modèle d'enchères de recherche / position sponsorisées est discuté dans Ashlagi et al. et dans le problème d'attribution plus général d'Aggarwal et al. et Dütting et al.

Voir également

• Vente aux enchères Vickrey – Clarke – Groves
• Enchères généralisées au premier prix
• Google Ads
• Théorie des enchères
• Vente aux enchères japonaise

Références

• S. Lahaie, D. Pennock, A. Saberi et R. Vohra. Théorie algorithmique des jeux , chapitre "Ventes aux enchères avec recherche sponsorisée", pages 699–716. Cambridge University Press, 2007
• Notes de cours sur la publicité basée sur les mots-clés