Genelleştirilmiş ikinci fiyat müzayedesi - Generalized second-price auction

Genelleştirilmiş ikinci fiyat açık artırma (GTS) birden çok öğe için olmayan bir gerçeğe açık artırma mekanizmasıdır. Her teklif veren bir teklif verir. En yüksek teklif veren ilk yuvayı, ikinci en yüksek, ikinci yuvayı vb. Alır, ancak en yüksek teklif veren ikinci en yüksek teklifi verenin fiyat teklifini öder, ikinci en yüksek teklifi üçüncü en yüksek olana göre öder ve yakında. İlk olarak, Vickrey müzayedesinin doğal bir uzantısı olarak tasarlanan bu müzayede , Vickrey müzayedesinin arzu edilen bazı özelliklerini koruyor. Esas olarak, sponsorlu arama alanlarının açık artırma temelinde satıldığı anahtar kelime açık artırmaları bağlamında kullanılır. GSP'nin ilk analizleri ekonomi literatüründe Edelman, Ostrovsky ve Schwarz ve Varian tarafından yapılmıştır . Google'ın AdWords teknolojisi tarafından kullanılıyor ve şu anda Vickrey – Clarke – Groves açık artırmasına geçen Facebook tarafından kullanılıyordu.

Biçimsel model

Teklif verenlerin ve yuvaların olduğunu varsayalım . Her yuvanın tıklanma olasılığı vardır . Üst alanların tıklanma olasılığının daha yüksek olduğunu varsayabiliriz, bu nedenle:

Biz aklınıza gelebilecek tıklama oranına sıfır, bu yüzden, ek sanal yuvaları için . Şimdi, her teklif veren , bir alan için ödemeye razı oldukları maksimum tutarı gösteren bir teklif sunar . Her teklif verenin ayrıca bir slot satın almak için kendine özgü bir değeri vardır . Bir oyuncunun teklifinin gerçek değerlemesi ile aynı olması gerekmediğine dikkat edin . İsteklileri tekliflerine göre sıralıyoruz, diyelim ki:

ve her teklif verenden bir fiyat alın . Bir yuva kazanmazlarsa fiyat 0 olacaktır. Yuvalar, tıklama başına ödeme modelinde satılır , bu nedenle, kullanıcı gerçekten o yuvayı tıklarsa, teklif veren yalnızca bir alan için ödeme yapar. Slot için tahsis edilen teklif verenin faydası diyoruz . Tüm slotlara sahip olmanın veya satmanın toplam sosyal refahı şu şekilde verilir: Beklenen toplam gelir şu şekilde verilir:

GSP mekanizması

Bir mekanizma belirlemek için, tahsis kuralını (kimin hangi yuvayı alacağını) ve her teklif veren tarafından ödenen fiyatları tanımlamamız gerekir. Genelleştirilmiş bir ikinci fiyat açık artırmasında, teklif verenleri tekliflerine göre sıralarız ve en yüksek alanı en yüksek teklifi verene, ikinci en yüksek yuvayı ikinci en yüksek teklifi verene veririz vb. Daha sonra, varsayarak teklif azalan listelenen İstekli, teklif yuvası alır için . Bir yuva kazanan her teklif sahibi böylece, sonraki en yüksek teklif teklifini öder: .

Doğruluk

Gerçek değerlemeyi teklif etmenin Nash dengesi olmadığı durumlar vardır . Örneğin, iki yuva düşünün ve kalemlerin üç istekliler , ve ve teklifleri , ve sırasıyla. Böylece, ve . Teklif veren için fayda şudur: Bu teklif seti Nash dengesi değildir, çünkü ilk teklif veren teklifini 5'e düşürebilir ve ikinci slotu 1 fiyatına alabilir, böylece faydasını artırabilir .

GSP Dengesi

Eksiksiz bilgi altında çalışan Edelman, Ostrovsky ve Schwarz, GSP'nin (yukarıda sunulan modelde) her zaman verimli bir yerel kıskançlık içermeyen bir dengeye sahip olduğunu, yani teklif sahibinin yuvaya göre yerleştirildiği yer olarak ölçülen sosyal refahı maksimize eden bir dengeye sahip olduğunu göstermektedir. azalan teklif vektörü . Ayrıca, herhangi bir yerel kıskançlık içermeyen dengede beklenen toplam gelir, en azından (doğru) VCG sonucundaki kadar yüksektir .

Nash dengesinde refah üzerindeki sınırlar Caragiannis ve diğerleri tarafından verilmiş olup, anarşi fiyatının sınırını kanıtlamaktadır . Dütting vd. ve Lucier ve ark. Herhangi bir Nash dengesinin ilki hariç tüm slotlardan gerçek VCG gelirinin en az yarısını elde ettiğini kanıtlayın. Bu oyunun hesaplamalı analizi Thompson ve Leyton-Brown tarafından yapılmıştır .

GSP ve belirsizlik

Edelman, Ostrovsky ve Schwarz ve Varian'dan kaynaklanan klasik sonuçlar , hiçbir belirsizlik olmadığında tam bilgi ortamında tutulur. Gomes ve Sweeney ve Caragiannis ve ark. ve ayrıca Athey ve Nekipelov tarafından deneysel olarak, oyunun Bayesçi versiyonunu tartışıyorlar - burada oyuncuların diğer oyuncular hakkında inançları var, ancak diğer oyuncuların değerlendirmelerini mutlaka bilmiyorlar.

Gomes ve Sweeney, kısmi bilgi ortamında verimli bir dengenin olmayabileceğini kanıtladı. Caragiannis vd. Bayes-Nash dengesinde refah kaybını düşünün ve 2,927'lik bir anarşi fiyatını kanıtlayın . Bayes-Nash dengesindeki gelir üzerindeki sınırlar Lucier ve diğerleri tarafından verilmiştir. ve Caragiannis vd.

Bütçe kısıtlamaları

Bütçe kısıtlamalarının sponsorlu arama / pozisyon açık artırma modelindeki etkisi Ashlagi ve ark. ve Aggarwal ve diğerleri tarafından daha genel atama probleminde. ve Dütting ve ark.

Ayrıca bakınız

Referanslar

  • S. Lahaie, D. Pennock, A. Saberi ve R. Vohra. Algorithmic Game Theory , "Sponsorlu arama müzayedeleri" bölümü, sayfa 699–716. Cambridge University Press, 2007
  • Anahtar Kelime Temelli Reklam ile ilgili ders notları