Strateji geçirmezlik - Strategyproofness

In oyun teorisi , bir asimetrik oyun oyuncuların özel olması bilgiyi olduğu söylenir strategyproof veya strategyproof (SP) bir weakly- ise baskın strateji hakkında hiçbir bilgi verilmiş her oyuncu onun / onu özel bilgileri ortaya çıkarmak için için, yani diğerleri yapar, dürüst olmakla en iyisini yaparsınız veya en azından daha kötü olmazsınız.

SP, diğer teşvik uyumluluğu türlerinden ayırt etmek için doğru veya baskın-strateji-teşvik-uyumlu (DSIC) olarak da adlandırılır .

Bir SP oyunu her zaman gizli anlaşmalara karşı bağışık değildir, ancak sağlam çeşitleri şunlardır; ile grup strategyproofness insanların hiçbir grup her üyenin daha iyi olduğunu kılan bir şekilde tercihlerini misreport için anlaşabilir ve birlikte güçlü grup strategyproofness insanların hiçbir grup bir şekilde tercihlerini misreport için anlaşabilir bu grubun markaları en az bir üye kalan üyelerden herhangi birini daha da kötüleştirmeden daha iyi durumda.

Örnekler

SP mekanizmalarının tipik örnekleri, iki alternatif arasında çoğunluk oylaması , ikinci fiyat açık artırması ve herhangi bir VCG mekanizmasıdır .

SP olmayan mekanizmaların tipik örnekleri, üç veya daha fazla alternatif arasında çoğul oylama ve ilk fiyat açık artırmasıdır .

SP, ağ yönlendirmede de geçerlidir . Bir şekilde bir ağ göz önünde grafik her kenar (yani bağlantı) bir ilişkili olan maliyet arasında iletimi özel bağlantının sahibi tarafından bilinen,. Bir bağlantının sahibi, iletileri ilettiği için tazmin edilmek ister. Ağdaki bir mesajı gönderen kişi en düşük maliyetli yolu bulmak ister. Büyük ağlarda bile bunu yapmak için etkili yöntemler vardır. Ancak bir sorun var: Her bağlantının maliyeti bilinmiyor. Naif bir yaklaşım, her bağlantının sahibine maliyeti sormak, en düşük maliyetli yolu bulmak için bu beyan edilen maliyetleri kullanmak ve yoldaki tüm bağlantılara beyan edilen maliyetlerini ödemek olacaktır. Ancak bu ödeme planının SP olmadığı, yani bazı linklerin sahiplerinin maliyet konusunda yalan söyleyerek fayda sağlayabileceği gösterilebilir. Gerçek maliyetten çok daha fazlasını ödeyebiliriz. Ağ ve oyuncular (bağlantı sahipleri) hakkında belirli varsayımlar verildiğinde, VCG mekanizmasının bir çeşidinin SP olduğu gösterilebilir.

gösterim

Bir dizi olası sonuç vardır. ${\görüntüleme stili X}$

Orada her bir sonuç için farklı değerleme sahip ajanlar. Aracının değerlemesi bir fonksiyon olarak temsil edilir: ${\görüntüleme stili n}$${\görüntüleme stili ben}$

${\displaystyle v_{i}:X\longrightarrow R_{+}}$

her bir alternatif için sahip olduğu değeri parasal olarak ifade eder.

Etmenlerin Yarı Doğrusal fayda fonksiyonlarına sahip olduğu varsayılır ; bunun anlamı, eğer sonuç ise ve ek olarak vekil bir ödeme alırsa (olumlu veya olumsuz), o zaman acentenin toplam faydası : ${\görüntüleme stili x}$${\displaystyle p_{i}}$${\görüntüleme stili ben}$

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

Tüm değer fonksiyonlarının vektörü ile gösterilir . ${\görüntüleme stili v}$

Her ajan için , diğer ajanların tüm değer fonksiyonlarının vektörü ile gösterilir . Yani . ${\görüntüleme stili ben}$${\ Displaystyle v_{-i}}$${\displaystyle v\eş (v_{i},v_{-i})}$

Bir mekanizma bir çift fonksiyondur:

• Bir giriş olarak değer vektörü alır fonksiyonu, ve bir sonuç verir (aynı zamanda adı sosyal seçim işlevi);${\ Displaystyle Sonucu}$${\görüntüleme stili v}$${\displaystyle x\in X}$
• Bir giriş olarak değer vektörü alır fonksiyonu, ödemeler bir vektör ve döndürür, belirlenmesi her oyuncu (oyuncu pozitif miktar ödeme gerektiğine olumsuz ödeme aracı) almalıdır ne kadar.${\ Displaystyle Ödeme}$${\görüntüleme stili v}$${\displaystyle (p_{1},\dots ,p_{n})}$

Her oyuncu için ve diğer oyuncuların her değer vektörü için bir mekanizma stratejiye dayanıklı olarak adlandırılır : ${\görüntüleme stili ben}$${\ Displaystyle v_{-i}}$

${\displaystyle v_{i}(Sonuç(v_{i},v_{-i}))+Ödeme_{i}(v_{i},v_{-i})\geq v_{i}(Sonuç(v_{ i}',v_{-i}))+Ödeme_{i}(v_{i}',v_{-i})}$

karakterizasyon

Belirli bir mekanizmanın SP olup olmadığını kontrol etmek için basit koşullara sahip olmak yararlıdır. Bu alt bölüm, hem gerekli hem de yeterli olan iki basit koşulu gösterir.

Bir mekanizma SP ise, her etmen için aşağıdaki iki koşulu sağlamalıdır : ${\görüntüleme stili ben}$

1. Temsilciye ödeme , seçilen sonucun ve diğer aracıların değerlemelerinin bir işlevidir - ancak aracının kendi değerlemesinin doğrudan bir işlevi değildir . Resmi olarak, girdi olarak diğer aracılar için bir sonuç ve bir değerleme vektörü alan ve aşağıdaki durumlarda her biri için aracı için ödemeyi döndüren bir fiyat işlevi vardır : ${\görüntüleme stili ben}$${\ Displaystyle v_{-i}}$${\displaystyle v_{i}}$${\ Displaystyle Fiyatı_{i}}$${\displaystyle x\in X}$${\ Displaystyle v_{-i}}$${\görüntüleme stili ben}$${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle Sonuç(v_{i},v_{-i})=Sonuç(v_{i}',v_{-i})}$

sonra:

${\displaystyle Ödeme_{i}(v_{i},v_{-i})=Ödeme_{i}(v_{i}',v_{-i})}$

KANIT: Değerleme sahibi bir temsilci , kendisine aynı sonucu ve daha büyük bir ödeme sağladığı için raporlamayı tercih ederse ; benzer şekilde, eğer öyleyse, değerlemeye sahip bir aracı raporlamayı tercih eder . ${\displaystyle Ödeme_{i}(v_{i},v_{-i})>Ödeme_{i}(v_{i}',v_{-i})}$${\displaystyle v_{i}'}$${\displaystyle v_{i}}$${\displaystyle Ödeme_{i}(v_{i},v_{-i})<Ödeme_{i}(v_{i}',v_{-i})}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$

Sonuç olarak, girdi olarak diğer aracılar için bir sonuç ve bir değerleme vektörü alan ve aşağıdaki durumlarda aracı Her için ödemeyi döndüren bir "fiyat etiketi" işlevi vardır : ${\ Displaystyle Fiyatı_{i}}$${\displaystyle x\in X}$${\ Displaystyle v_{-i}}$${\görüntüleme stili ben}$${\displaystyle v_{i},v_{-i}}$

${\displaystyle Sonuç(v_{i},v_{-i})=x}$

sonra:

${\displaystyle Ödeme_{i}(v_{i},v_{-i})=Fiyat_{i}(x,v_{-i})}$

2. Seçilen sonuç, diğer ajanların değerlendirmeleri göz önüne alındığında, ajan için optimaldir . Resmi olarak: ${\görüntüleme stili ben}$

${\displaystyle Sonuç(v_{i},v_{-i})\in \arg \max _{x}[v_{i}(x)+Fiyat_{i}(x,v_{-i})]}$

maksimizasyonun aralığındaki tüm sonuçların üzerinde olduğu yerde . ${\displaystyle Sonucu(\cdot ,v_{-i})}$

PROOF: Başka bir sonuç varsa öyle ki , daha sonra değerleme ile bir ajan raporuna tercih bu ona büyük bir toplam yarar verir, çünkü. ${\displaystyle x'=Sonuç(v_{i}',v_{-i})}$${\displaystyle v_{i}(x')+Fiyat_{i}(x',v_{-i})>v_{i}(x)+Fiyat_{i}(x,v_{-i})}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$

1. ve 2. koşullar sadece gerekli değil, aynı zamanda yeterlidir: 1. ve 2. koşulları karşılayan herhangi bir mekanizma SP'dir.

KANIT: Bir aracıyı ve değerlemeleri düzeltin . Belirtmek: ${\görüntüleme stili ben}$${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle x:=Sonuç(v_{i},v_{-i})}$ - vekil dürüst davrandığında ortaya çıkan sonuç.

${\displaystyle x':=Sonuç(v_{i}',v_{-i})}$ - temsilcinin gerçeğe aykırı davrandığı durumlarda ortaya çıkan sonuç.

Özellik 1'e göre, aracının dürüstçe oynarken faydası:

${\displaystyle u_{i}(v_{i})=v_{i}(x)+Fiyat_{i}(x,v_{-i})}$

ve doğru olmayan bir şekilde oynarken aracının faydası şudur:

${\displaystyle u_{i}(v_{i}')=v_{i}(x')+Fiyat_{i}(x',v_{-i})}$

Özellik 2'ye göre:

${\displaystyle u_{i}(v_{i})\geq u_{i}(v_{i}')}$

bu nedenle, ajanın dürüstçe hareket etmesi baskın bir stratejidir.

Sonuç-fonksiyon karakterizasyonu

Bir mekanizmanın asıl amacı, işlevidir; ödeme işlevi, oyuncuları dürüst olmaya teşvik etmek için sadece bir araçtır. Bu nedenle, belirli bir sonuç işlevi verildiğinde, bunun bir SP mekanizması kullanılarak gerçekleştirilip gerçekleştirilemeyeceğini bilmek faydalıdır (bu özellik aynı zamanda uygulanabilirlik olarak da adlandırılır ). Monotonluk (mekanizma tasarımı) özelliği, gerekli ve genellikle de yeterlidir. ${\ Displaystyle Sonucu}$

Tek parametreli alanlarda doğru mekanizmalar

Bir tek parametreli alanı her oyuncunun olduğu bir oyundur belli pozitif bir değer alır "kazanan" ve "kaybeden" için bir değer 0. Basit bir örnek, oyuncunun öğeye atadığı değer olan tek öğeli bir açık artırmadır . ${\görüntüleme stili ben}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\görüntüleme stili ben}$

Bu ayar için, doğru mekanizmaları karakterize etmek kolaydır. Bazı tanımlarla başlayın.

Her kaybeden teklif 0 ödüyorsa , bir mekanizma normalleştirilmiş olarak adlandırılır .

Bir oyuncu teklifini yükselttiğinde kazanma şansı (zayıf olarak) artarsa, bir mekanizma monoton olarak adlandırılır .

Monoton bir mekanizma için, her oyuncu i ve diğer oyuncuların tekliflerinin her kombinasyonu için , oyuncunun kaybetmeden kazanmaya geçtiği kritik bir değer vardır.

Tek parametreli bir etki alanındaki normalleştirilmiş bir mekanizma, aşağıdaki iki koşul geçerliyse doğrudur:

1. Atama işlevi, tekliflerin her birinde monotondur ve:
2. Her kazanan teklif kritik değeri öder.

Yüksek olasılıklı doğruluk

Her sabit için , randomize bir mekanizma olarak adlandırılan bir olasılık ile doğru her ajan için ve teklif her vektörü, olasılık ise Bununla madde avantajları teklif olmayan gerçeğe en olan olasılık mekanizmasının rastgelelik üzerinden alınır burada. ${\displaystyle \epsilon >0}$${\displaystyle 1-\epsilon }$${\görüntüleme stili \epsilon }$

Teklif verenlerin sayısı arttığında sabit 0'a giderse, mekanizma yüksek olasılıkla doğru olarak adlandırılır . Bu kavram tam doğruluktan daha zayıftır, ancak bazı durumlarda yine de yararlıdır; bkz. örneğin fikir birliği tahmini . ${\görüntüleme stili \epsilon }$

Yanlış isim kanıtı

İnternet tabanlı müzayedelerin bolluğu ile yaygın hale gelen yeni bir dolandırıcılık türü, sahte isim teklifleridir - birden fazla e-posta adresi gibi birden çok tanımlayıcı kullanarak tek bir teklif veren tarafından sunulan teklifler.

Yanlış isim kanıtı , oyuncuların hiçbirinin sahte isim teklifleri vermesi için herhangi bir teşvik olmadığı anlamına gelir. Bu, stratejiden daha güçlü bir kavramdır. Özellikle, Vickrey–Clarke–Groves (VCG) müzayedesi sahte isme karşı kanıt değildir.

Yanlış isim kanıtı, grup stratejisinden önemli ölçüde farklıdır, çünkü bir bireyin tek başına, normalde birden fazla bireyin danışıklı koordinasyonunu gerektiren belirli davranışları simüle edebileceğini varsayar.

Ayrıca bakınız

• Teşvik uyumluluğu
• Bireysel rasyonellik - bir oyuncunun oyunu oynayarak kaybetmeyeceği anlamına gelir (yani, bir oyuncunun oyunu oynamaktan kaçınmaya teşviki yoktur).

daha fazla okuma

• Parkes, David C. (2004), Öğrenilebilir Mekanizma Tasarımı Üzerine, içinde: Tumer, Kagan ve David Wolpert (Ed.): Collectives and the Design of Complex Systems, New York uaO, s. 107–133.
• Klasik Sosyal Seçim Kurallarının Asimptotik Strateji Kanıtı Üzerine Arkadii Slinko'nun oylama sistemlerinde strateji kanıtı hakkında bir makalesi.

Referanslar