Ballmer stratejisinden bağımsız olarak oyunun pozitif beklenen değeri

Steve Ballmer yanılıyordu

Birkaç gün önce John Graham-Cumming, "Steve Ballmer’ın hatalı ikili arama mülakat sorusu" hakkında bir yazı yayımladı ve bu yazı HackerNews’te büyük ilgi gördü. Ballmer’ın sevdiği beyin yakan soru şöyle:

1 ile 100 arasında bir sayı tutuyorum. Tahmin edebilirsin; her tahminden sonra daha yüksek mi daha düşük mü olduğunu söyleyeceğim. İlk tahminde bilirsen sana 5 dolar veririm. Sonra 4 dolar, 3 dolar, 2 dolar, 1 dolar, 0 dolar, ardından sen bana 1 dolar, 2 dolar, 3 dolar ödersin.

Bu oyunu oynar mıydın?

Steve Ballmer, bu YouTube röportajında bu oyunun oynanmaması için iki neden sunuyor:

1. 1 ile 100 arasındaki sayıların çoğu zarara yol açtığı için, sayı rastgele seçilse bile beklenen değer negatiftir.
2. Sayıyı bulmanın en uzun sürdüğü durumu stratejik olarak seçmek için ikili arama kullanabilir.

Ancak John, Ballmer sayıyı rastgele seçtiğinde oyunun beklenen değerinin aslında $0.20 ile pozitif olduğunu göstererek ilk noktayı çürütüyor.

Ben de ikinci noktayı çürütecek ve Ballmer’ın stratejisinden bağımsız olarak oyunun beklenen değerinin pozitif olduğunu kanıtlayacağım.

Ballmer sayıyı düşmanca nasıl seçebilir?

Sayıyı bulmak için her zaman ikili arama stratejisi kullandığını varsayalım. 100 sayıdan 37’si, tahmin edilebilmesi için 6 soru gerektirir. Ballmer senin stratejini biliyorsa, her oyunda zarara yol açacak bu "kaybettiren" sayılardan birini her zaman seçebilir. Bu, sabit bir arama düzeni için her zaman geçerlidir. En az 37 sayı zarara yol açacaktır ve Ballmer bunlardan birini seçebilir.

Buna nasıl karşılık verilebilir?

Burada oyun teorisi alanına giriyoruz. Tek bir sabit arama düzeni yerine, birden fazla arama düzeni kümesi hazırlayabilirsin. Ardından oyun başında bu düzenlerden birini olasılıksal olarak seçer ve oyun boyunca ona sadık kalırsın.

Oyun teorisinde buna karma strateji denir ve birden fazla saf strateji içeren bir strateji kümesine dayanır.

Aynı sayı, bir arama düzeninde "kazandıran", başka bir arama düzeninde ise "kaybettiren" olabilir. Bu nedenle böyle bir karma strateji, her sayının beklenen getirisini "dengeleyebilir". Hatta potansiyel olarak tüm sayıları "kazandıran" hale getirebilir; yani her sayı için pozitif beklenen getiri sağlayabilir. Aradığımız şey tam olarak bu.

Kazandıran bir karma strateji nasıl bulunur?

Not: Amacımız tüm sayılarda kazandıran bir strateji bulmak; en kötü durumda en yüksek beklenen değere sahip en iyi kazandıran stratejiyi (Nash dengesi) bulmak değil.

Nash dengesi ilgini çekiyorsa, Arthur O’Dwyer 5 sayıya kadar olan oyun için kapalı form çözümleri inceledi; Bo Waggoner ise 100 sayılık oyunun denge değerini regret-free online learning kullanarak yaklaşık hesapladı.

Tüm sayılarda kazandıran bir karma strateji bulmak, matematiksel bir optimizasyon problemi olarak görülebilir. Her strateji, bir "kazanç" vektörü V=(v1,..,v100) ile tanımlanabilir; burada vk, Ballmer k sayısını seçtiğinde beklenen kazancı ifade eder. Örneğin ikili arama, v50=5, v25=4, v0=−1 olan bir vektöre karşılık gelebilir.

Saf stratejilerin V1, V2, ..., Vn olduğunu ve karma stratejinin Vk stratejisini pk olasılığıyla seçtiğini varsayalım. O zaman karma stratejinin karşılık gelen "kazanç" vektörü basitçe doğrusal birleşimdir: Vmixed=∑i=1npiVi.

Bu yorumla, kazandıran bir strateji bulmak; iki kısıtı olan bir doğrusal birleşim bulmak anlamına gelir:

• Doğrusal birleşimin her bileşeni pozitiftir (her sayı için ortalamada para kazanabilirsin).
• Bu doğrusal birleşimin katsayıları negatif değildir (olasılıklara karşılık gelir).

Bu tipik bir doğrusal programlama problemidir ve scipy bunun için verimli bir çözüm sunar. Karma stratejiyi bulmak için çeşitli saf stratejiler (farklı ikili aramalar) düşündüm ve bunları scipy.linprog() içine verdim; voilà, çözüm kazandıran bir strateji ortaya koydu!

Örnek bir kazandıran strateji

Tüm kod gukoff/ballmer_puzzle içinde yer alıyor. Not: Başlangıçtaki $0.07 sonucu, Arthur O’Dwyer’ın yeni saf stratejiler eklemesiyle önemli ölçüde iyileştirildi.

• Ballmer rastgele seçerse ortalama kazanç: $0.16
• Ballmer düşmanca seçerse en kötü durumda kazanç: $0.14

Ortaya çıkan karma strateji şöyle:

• Olasılık %0.4714: ikili arama, ilk tahmin 29. Her adımda aralığın orta öğesi tahmin edilir. Eşitlik durumunda soldaki öğe tahmin edilir
• Olasılık %0.1691: ikili arama, ilk tahmin 33. Her adımda aralığın orta öğesi tahmin edilir. Eşitlik durumunda soldaki öğe tahmin edilir
• Olasılık %0.1299: ikili arama, ilk tahmin 36. Her adımda aralığın orta öğesi tahmin edilir. Eşitlik durumunda sağdaki öğe tahmin edilir
• Olasılık %3.3341: ikili arama, ilk tahmin 37. Her adımda aralığın orta öğesi tahmin edilir. Eşitlik durumunda sağdaki öğe tahmin edilir
• Olasılık %1.7818: ikili arama, ilk tahmin 43. Her adımda, en kötü durum karmaşıklığını artırmayan aralığın en sağdaki öğesi tahmin edilir
• Olasılık %1.1608: ikili arama, ilk tahmin 44. Her adımda, en kötü durum karmaşıklığını artırmayan aralığın en soldaki öğesi tahmin edilir
• Olasılık %2.1310: ikili arama, ilk tahmin 42. Her adımda, en kötü durum karmaşıklığını artırmayan aralığın uç öğesi tahmin edilir

...

Tam strateji 74 satırdan oluşuyor; kısalık adına burada verilmedi. İlgileniyorsan GitHub’da inceleyebilirsin.

Sonuç

Oyun başına ortalama 14 sent kazanabiliyorsan, Steve Ballmer bir dahaki sefere bu oyunu önerdiğinde kesinlikle katılmalısın.

GN⁺ Özeti

• Bu yazı, Steve Ballmer’ın ikili arama oyunu etrafındaki tartışmayı ele alıyor.
• Oyun teorisini kullanarak, Ballmer’ın stratejisinden bağımsız biçimde kazandıran bir karma stratejinin nasıl bulunacağını açıklıyor.
• Yazı, oyun teorisi ve optimizasyon problemleriyle ilgilenenler için faydalı olabilir.
• Benzer özelliklere sahip diğer projeler arasında çeşitli oyun teorisi araştırmaları ve makaleleri bulunuyor.

[GN⁺]

Hacker News görüşü

• Ballmer'ın iddiası kuyruk riskleriyle ilgili

  • Hayatta kalmayı önemsiyorsanız, beklenen değer iyi bir bahis yöntemi değildir
  • Bu, pokerde beklenen değer yüksek diye her seferinde all-in yapmamanızla aynı şeydir
  • Ortalama olarak kazanma olasılığınız daha yüksek olabilir, ancak yalnızca tek bir sonuç elde edebilirsiniz
  • Amaç kazanmaksa, Ballmer'a borçlanmamak daha iyidir
  • Monte Carlo simülasyonu üzerinden bu stratejinin kazanma/kaybetme dağılımına bakmak daha ilginç olurdu

• Ballmer "düşmanca" dediğinde, sabit bir sayı seçmek zorunda olmadığını hesaba katıyor

  • Her tahmin için, stratejiden bağımsız olarak yenilgiyi garanti edecek şekilde mümkün olan sayıların en fazlasını bırakan cevabı verebilir

• "Rastgele ofsetli ikili arama" adlı bir algoritma öneriliyor

  • 0-100 arasında rastgele bir sayı seçin ve buna "ofset" deyin
  • İkili arama algoritmasını uygulayın, ancak her adımda değere "ofset" ekleyin ve 100 ile mod alın
  • Ballmer bu stratejiyi bilse bile performansı düşürmek için belirli bir sayı seçemez
  • Dolayısıyla beklenen sonuç oyun başına hâlâ $0.20'dir

• Bu, Ballmer'ın yanıldığı pek çok şeyden biri

• "Little Mathematics Library – Elements of Game Theory" kitabı tavsiye ediliyor

  • Karma stratejileri ele alan iyi bir oyun teorisi kitabı
  • Kitap, motive edici örnek olarak iki kartlı bir oyun tanıtıyor
    • A oyuncusu as çekerse rakibinden 1 dolar ister
    • İkili çekerse rakibinden 1 dolar isteyebilir ya da 1 dolar ödeyebilir
    • Rakip gönüllü olarak 1 dolar alabilir ya da as olup olmadığının kontrol edilmesini isteyebilir
    • Gerçekten assa 2 dolar öder, blöfse 2 dolar alır
    • Oyun analiz edilir ve her oyuncunun optimal stratejisi ile beklenen getirisi bulunur

• Nash dengesi üzerine daha kapsamlı analiz ve oyunun tamamına ilişkin sayısal çözüm sunan bir bağlantı paylaşılıyor

• Modern teknoloji mülakat süreci tam anlamıyla deliliğin bir örneği

• "Bunun doğru olduğunu düşünüyorum, iyi iş!" diyen bir yorum arıyordum ama bulamayınca kendim yazdım

  • Bunun doğru olduğunu düşünüyorum, iyi iş

• Steve Ballmer'ın net serveti 120 milyar dolar

  • Her oyunun 30 saniye sürdüğünü varsayarsanız, tüm parasını kazanmak 1,6 milyon yıl sürer