Nilai harapan positif dari permainan yang tidak bergantung pada strategi Ballmer

Steve Ballmer salah

Beberapa hari lalu, tulisan John Graham-Cumming tentang "pertanyaan wawancara pencarian biner Steve Ballmer yang keliru" mendapat banyak perhatian di HackerNews. Teka-teki favorit Ballmer adalah sebagai berikut:

Saya sedang memikirkan sebuah angka antara 1 dan 100. Anda boleh menebak, dan setelah setiap tebakan saya akan memberi tahu apakah angkanya lebih tinggi atau lebih rendah.

Jika Anda benar pada tebakan pertama, saya akan memberi Anda $5. $4, $3, $2, $1, $0, lalu Anda harus membayar saya $1, $2, $3.

Apakah Anda mau memainkan permainan ini?

Dalam wawancara YouTube ini, Steve Ballmer memberikan dua alasan mengapa kita seharusnya tidak memainkan permainan ini:

1. Di antara angka 1 sampai 100, ada banyak angka yang akan menimbulkan kerugian, sehingga bahkan jika Anda memilih angka secara acak, nilai harapannya negatif.
2. Ia bisa secara strategis memilih angka yang membutuhkan waktu paling lama untuk ditemukan dengan menggunakan pencarian biner.

Namun, John membantah poin pertama dengan menunjukkan bahwa jika Ballmer memilih angka secara acak, nilai harapan permainan ini sebenarnya positif, yaitu $0.20.

Saya akan membantah poin kedua dan membuktikan bahwa nilai harapan permainan ini tetap positif, terlepas dari strategi Ballmer.

Bagaimana Ballmer bisa memilih angka secara adversarial

Mari kita asumsikan Anda selalu menggunakan strategi pencarian biner untuk menemukan angka. Dari 100 angka, 37 di antaranya memerlukan 6 pertanyaan untuk ditemukan. Jika Ballmer mengetahui strategi Anda, ia selalu bisa memilih salah satu dari angka-angka "kalah" ini dan menyebabkan kerugian di setiap permainan. Ini selalu berlaku untuk pola pencarian yang tetap. Setidaknya akan ada 37 angka yang menyebabkan kerugian, dan Ballmer dapat memilih salah satunya.

Bagaimana cara melawannya?

Di sinilah kita masuk ke ranah teori permainan. Alih-alih satu pola pencarian tetap, kita bisa menyiapkan sekumpulan pola pencarian. Lalu, saat permainan dimulai, kita memilih salah satu pola tersebut secara probabilistik dan tetap menggunakannya sepanjang permainan.

Dalam teori permainan, ini disebut strategi campuran, yang dibangun dari kumpulan strategi berupa beberapa strategi murni.

Karena angka yang sama bisa "menang" dalam satu pola pencarian dan "kalah" dalam pola lainnya, strategi campuran seperti ini dapat "meratakan" hasil yang diharapkan untuk setiap angka. Secara potensial, strategi campuran bisa membuat semua angka menjadi "menang", yaitu memiliki hasil harapan positif untuk setiap angka. Itulah yang kita cari.

Cara menemukan strategi campuran yang menang

Catatan: Kita ingin menemukan suatu strategi yang menang untuk semua angka, bukan mencari strategi menang terbaik (Nash equilibrium) yang memiliki nilai harapan maksimum dalam kasus terburuk.

Jika Anda penasaran tentang Nash equilibrium, Arthur O’Dwyer telah mengeksplorasi solusi bentuk tertutup untuk permainan hingga 5 angka, dan Bo Waggoner mengaproksimasi nilai equilibrium untuk permainan 100 angka dengan menggunakan pembelajaran online tanpa penyesalan.

Menemukan strategi campuran yang menang untuk semua angka bisa dipandang sebagai masalah optimisasi matematis. Setiap strategi dapat dijelaskan dengan vektor "kemenangan" V=(v1,..,v100), di mana vk adalah kemenangan yang diharapkan saat Ballmer memilih angka k. Sebagai contoh, pencarian biner bisa bersesuaian dengan vektor dengan v50=5, v25=4, v0=−1.

Misalkan kita memiliki strategi murni V1, V2, ..., Vn, dan strategi campuran memilih strategi Vk dengan probabilitas pk. Maka vektor "kemenangan" yang sesuai untuk strategi campuran hanyalah kombinasi linear: Vmixed=∑i=1npiVi.

Dalam interpretasi ini, mencari strategi yang menang berarti mencari kombinasi linear dengan dua kendala:

• Setiap elemen dalam kombinasi linear tersebut bernilai positif (kita bisa menghasilkan uang rata-rata untuk setiap angka).
• Koefisien kombinasi linear tersebut tidak negatif (karena mewakili probabilitas).

Ini adalah masalah pemrograman linear yang khas, dan scipy memiliki solusi efisien untuk itu. Untuk menemukan strategi campuran, saya memikirkan berbagai strategi murni (berbagai variasi pencarian biner) dan memasukkannya ke scipy.linprog(), lalu voilà — solusinya menghasilkan strategi yang menang!

Contoh strategi yang menang

Kode lengkap tersedia di gukoff/ballmer_puzzle. Catatan: hasil awal sebesar $0.07 kemudian meningkat secara signifikan setelah Arthur O’Dwyer menambahkan strategi murni baru.

• Kemenangan rata-rata jika Ballmer memilih secara acak: $0.16
• Kemenangan terburuk jika Ballmer memilih secara adversarial: $0.14

Strategi campuran yang dihasilkan adalah sebagai berikut:

• Probabilitas 0.4714%: pencarian biner, tebakan pertama 29. Pada setiap langkah, tebak elemen tengah dari interval. Jika seri, tebak elemen kiri
• Probabilitas 0.1691%: pencarian biner, tebakan pertama 33. Pada setiap langkah, tebak elemen tengah dari interval. Jika seri, tebak elemen kiri
• Probabilitas 0.1299%: pencarian biner, tebakan pertama 36. Pada setiap langkah, tebak elemen tengah dari interval. Jika seri, tebak elemen kanan
• Probabilitas 3.3341%: pencarian biner, tebakan pertama 37. Pada setiap langkah, tebak elemen tengah dari interval. Jika seri, tebak elemen kanan
• Probabilitas 1.7818%: pencarian biner, tebakan pertama 43. Pada setiap langkah, tebak elemen paling kanan dari interval yang tidak meningkatkan kompleksitas kasus terburuk
• Probabilitas 1.1608%: pencarian biner, tebakan pertama 44. Pada setiap langkah, tebak elemen paling kiri dari interval yang tidak meningkatkan kompleksitas kasus terburuk
• Probabilitas 2.1310%: pencarian biner, tebakan pertama 42. Pada setiap langkah, tebak elemen ujung dari interval yang tidak meningkatkan kompleksitas kasus terburuk

...

Strategi lengkap terdiri dari 74 baris dan dihilangkan demi keringkasan. Jika tertarik, Anda bisa melihatnya di GitHub.

Kesimpulan

Jika Anda bisa memperoleh rata-rata 14 sen per permainan, maka saat Steve Ballmer berikutnya menawarkan permainan ini, Anda pasti harus ikut.

Ringkasan GN⁺

• Artikel ini membahas perdebatan tentang permainan pencarian biner Steve Ballmer.
• Dijelaskan cara menggunakan teori permainan untuk menemukan strategi campuran yang bisa menang terlepas dari strategi Ballmer.
• Artikel ini dapat bermanfaat bagi orang-orang yang tertarik pada teori permainan dan masalah optimisasi.
• Proyek lain dengan fungsi serupa mencakup berbagai riset dan makalah terkait teori permainan.

[GN⁺]

Komentar Hacker News

• Argumen Ballmer berkaitan dengan risiko ekor

  • Jika yang diprioritaskan adalah bertahan hidup, nilai harapan bukan cara bertaruh yang baik
  • Sama seperti alasan orang tidak selalu all-in di poker hanya karena nilai harapannya tinggi
  • Rata-rata peluang menang mungkin lebih tinggi, tetapi hasil yang didapat hanya satu kali
  • Jika tujuannya adalah menang, sebaiknya tidak berutang uang kepada Ballmer
  • Akan lebih menarik melihat distribusi menang-kalah strategi ini melalui simulasi Monte Carlo

• Saat Ballmer mengatakan ia "bersifat adversarial", ia mempertimbangkan bahwa ia tidak perlu memilih satu angka tetap

  • Untuk setiap tebakan, ia bisa memberi jawaban yang menyisakan jumlah angka yang mungkin semaksimal mungkin, sehingga kekalahan bisa dijamin apa pun strateginya

• Mengusulkan algoritme bernama "random offset binary search"

  • Pilih angka acak antara 0-100 dan sebut itu sebagai "offset"
  • Jalankan algoritme binary search, tetapi pada setiap langkah tambahkan "offset" ke nilainya lalu lakukan operasi modulo 100
  • Bahkan jika Ballmer mengetahui strategi ini, ia tidak bisa memilih angka tertentu untuk menurunkan performanya
  • Karena itu, hasil harapannya tetap $0.20 per permainan

• Ini adalah salah satu dari sekian banyak hal yang keliru dari Ballmer

• Merekomendasikan buku "Little Mathematics Library – Elements of Game Theory"

  • Ini buku yang bagus tentang strategi campuran dalam teori permainan
  • Buku itu memperkenalkan permainan dua kartu sebagai contoh motivasi
    • Jika pemain A menarik ace, ia meminta lawannya membayar 1 dolar
    • Jika menarik deuce, ia bisa meminta lawannya membayar 1 dolar atau justru membayar 1 dolar
    • Lawan bisa secara sukarela menerima 1 dolar, atau meminta verifikasi apakah itu ace
    • Jika benar ace, lawan membayar 2 dolar; jika itu gertakan, lawan menerima 2 dolar
    • Permainan itu dianalisis untuk menemukan strategi optimal dan imbal hasil harapan masing-masing pemain

• Membagikan tautan yang memberikan analisis Nash equilibrium yang lebih luas serta solusi numerik untuk keseluruhan permainan

• Proses wawancara kerja teknologi modern benar-benar contoh kegilaan murni

• Sedang mencari komentar yang berbunyi, "Sepertinya ini benar, kerja bagus!", tetapi tidak menemukannya, jadi menuliskannya sendiri

  • Sepertinya ini benar, kerja bagus

• Kekayaan bersih Steve Ballmer adalah 120 miliar dolar

  • Jika diasumsikan tiap permainan memakan waktu 30 detik, diperlukan 1,6 juta tahun untuk memenangkan seluruh uangnya