Giá trị kỳ vọng dương của trò chơi bất kể chiến lược của Ballmer

Steve Ballmer đã sai

Vài ngày trước, John Graham-Cumming đã đăng một bài viết về “câu hỏi phỏng vấn tìm kiếm nhị phân sai lầm của Steve Ballmer”, và bài đó đã thu hút rất nhiều sự chú ý trên HackerNews. Câu đố trí tuệ yêu thích của Ballmer như sau:

Tôi đang nghĩ về một số từ 1 đến 100. Bạn có thể đoán, và sau mỗi lần đoán tôi sẽ nói là cao hơn hay thấp hơn. Nếu bạn đoán đúng ngay lần đầu, tôi sẽ đưa bạn 5 đô la. 4 đô la, 3 đô la, 2 đô la, 1 đô la, 0 đô la, rồi bạn sẽ phải trả cho tôi 1 đô la, 2 đô la, 3 đô la.

Bạn có chơi trò này không?

Trong cuộc phỏng vấn trên YouTube này, Steve Ballmer đưa ra hai lý do vì sao bạn không nên chơi trò này:

1. Trong các số từ 1 đến 100, có nhiều số sẽ dẫn đến thua lỗ, nên ngay cả khi ông ấy chọn số ngẫu nhiên thì kỳ vọng vẫn là âm.
2. Ông ấy có thể chọn số một cách chiến lược sao cho mất nhiều bước nhất để tìm ra bằng tìm kiếm nhị phân.

Tuy nhiên, John đã bác bỏ luận điểm thứ nhất khi chỉ ra rằng nếu Ballmer chọn số ngẫu nhiên, giá trị kỳ vọng của trò chơi thực ra là $0.20 dương.

Tôi sẽ bác bỏ luận điểm thứ hai và chứng minh rằng giá trị kỳ vọng của trò chơi là dương bất kể chiến lược của Ballmer.

Ballmer có thể chọn số một cách đối kháng như thế nào

Hãy giả sử bạn luôn dùng chiến lược tìm kiếm nhị phân để tìm số. Trong 100 số, có 37 số cần tới 6 câu hỏi để đoán ra. Nếu Ballmer biết chiến lược của bạn, ông ấy luôn có thể chọn một trong những số “thua” này để khiến bạn lỗ ở mọi ván chơi. Điều này luôn đúng với bất kỳ mẫu tìm kiếm cố định nào. Sẽ luôn có ít nhất 37 số gây thua lỗ, và Ballmer có thể chọn một trong số đó.

Có thể đối phó thế nào?

Đây là lúc ta bước vào lĩnh vực lý thuyết trò chơi. Thay vì một mẫu tìm kiếm cố định duy nhất, bạn có thể chuẩn bị nhiều mẫu tìm kiếm khác nhau. Sau đó khi trò chơi bắt đầu, bạn chọn một trong các mẫu đó theo xác suất và bám theo nó trong suốt ván chơi.

Trong lý thuyết trò chơi, điều này được gọi là chiến lược hỗn hợp, dựa trên một tập chiến lược gồm nhiều chiến lược thuần.

Vì cùng một số có thể là “thắng” trong một mẫu tìm kiếm nhưng là “thua” trong mẫu khác, chiến lược hỗn hợp như vậy có thể “cân bằng” lợi nhuận kỳ vọng của từng số. Về mặt tiềm năng, một chiến lược hỗn hợp có thể biến mọi số thành “thắng”, tức là có lợi nhuận kỳ vọng dương với từng số. Đó chính là điều chúng ta đang tìm.

Cách tìm một chiến lược hỗn hợp chiến thắng

Lưu ý: mục tiêu của chúng ta là tìm một chiến lược thắng với mọi số, chứ không phải tìm chiến lược thắng tốt nhất (Nash equilibrium) có giá trị kỳ vọng lớn nhất trong trường hợp xấu nhất.

Nếu bạn tò mò về Nash equilibrium, Arthur O’Dwyer đã khảo sát nghiệm dạng khép kín cho trò chơi với tối đa 5 số, còn Bo Waggoner đã xấp xỉ giá trị equilibrium của trò chơi 100 số bằng học trực tuyến không hối tiếc.

Việc tìm một chiến lược hỗn hợp thắng với mọi số có thể được xem như một bài toán tối ưu hóa toán học. Mỗi chiến lược có thể được mô tả bằng một vector “thắng” V=(v1,..,v100), trong đó vk là mức thắng kỳ vọng khi Ballmer chọn số k. Ví dụ, tìm kiếm nhị phân có thể tương ứng với vector có v50=5, v25=4, v0=−1.

Giả sử ta có các chiến lược thuần V1, V2, ..., Vn, và chiến lược hỗn hợp chọn chiến lược Vk với xác suất pk. Khi đó vector “thắng” tương ứng của chiến lược hỗn hợp chỉ đơn giản là tổ hợp tuyến tính: Vmixed=∑i=1npiVi.

Theo cách diễn giải này, việc tìm một chiến lược thắng tương đương với tìm một tổ hợp tuyến tính thỏa hai ràng buộc:

• Mọi phần tử của tổ hợp tuyến tính đều dương (bạn kiếm được tiền trung bình với mọi số).
• Các hệ số của tổ hợp tuyến tính không âm (vì chúng tương ứng với xác suất).

Đây là một bài toán quy hoạch tuyến tính điển hình, và scipy có một lời giải hiệu quả cho việc này. Tôi đã nghĩ ra một số chiến lược thuần (nhiều kiểu tìm kiếm nhị phân khác nhau) để tìm chiến lược hỗn hợp, rồi đưa chúng vào scipy.linprog(), và voilà - lời giải đã cho ra một chiến lược chiến thắng!

Ví dụ về chiến lược chiến thắng

Toàn bộ mã nguồn có trong gukoff/ballmer_puzzle. Lưu ý: kết quả ban đầu là $0.07 đã được Arthur O’Dwyer cải thiện đáng kể bằng cách thêm các chiến lược thuần mới.

• Mức thắng trung bình nếu Ballmer chọn ngẫu nhiên: $0.16
• Mức thắng tệ nhất nếu Ballmer chọn đối kháng: $0.14

Chiến lược hỗn hợp thu được như sau:

• Xác suất 0.4714%: tìm kiếm nhị phân, lần đoán đầu là 29. Ở mỗi bước, đoán phần tử giữa của khoảng. Nếu hòa, chọn phần tử bên trái
• Xác suất 0.1691%: tìm kiếm nhị phân, lần đoán đầu là 33. Ở mỗi bước, đoán phần tử giữa của khoảng. Nếu hòa, chọn phần tử bên trái
• Xác suất 0.1299%: tìm kiếm nhị phân, lần đoán đầu là 36. Ở mỗi bước, đoán phần tử giữa của khoảng. Nếu hòa, chọn phần tử bên phải
• Xác suất 3.3341%: tìm kiếm nhị phân, lần đoán đầu là 37. Ở mỗi bước, đoán phần tử giữa của khoảng. Nếu hòa, chọn phần tử bên phải
• Xác suất 1.7818%: tìm kiếm nhị phân, lần đoán đầu là 43. Ở mỗi bước, đoán phần tử ngoài cùng bên phải của khoảng mà không làm tăng độ phức tạp trong trường hợp xấu nhất
• Xác suất 1.1608%: tìm kiếm nhị phân, lần đoán đầu là 44. Ở mỗi bước, đoán phần tử ngoài cùng bên trái của khoảng mà không làm tăng độ phức tạp trong trường hợp xấu nhất
• Xác suất 2.1310%: tìm kiếm nhị phân, lần đoán đầu là 42. Ở mỗi bước, đoán phần tử ở một đầu của khoảng mà không làm tăng độ phức tạp trong trường hợp xấu nhất

...

Toàn bộ chiến lược gồm 74 dòng và được lược bỏ cho ngắn gọn. Nếu quan tâm, bạn có thể xem trên GitHub.

Kết luận

Nếu bạn có thể kiếm trung bình 14 xu mỗi ván, thì lần tới khi Steve Ballmer đề nghị chơi trò này, bạn nhất định nên tham gia.

Tóm tắt của GN⁺

• Bài viết này bàn về tranh luận xoay quanh trò chơi tìm kiếm nhị phân của Steve Ballmer.
• Bài viết giải thích cách dùng lý thuyết trò chơi để tìm một chiến lược hỗn hợp có thể thắng bất kể chiến lược của Ballmer.
• Bài viết này có thể hữu ích với những ai quan tâm tới lý thuyết trò chơi và các bài toán tối ưu hóa.
• Những dự án khác có chức năng tương tự gồm nhiều nghiên cứu và bài báo liên quan đến lý thuyết trò chơi.

[GN⁺]

Ý kiến Hacker News

• Lập luận của Ballmer là về rủi ro đuôi

  • Nếu coi trọng việc sống sót, giá trị kỳ vọng không phải là cách đặt cược tốt
  • Cũng giống như trong poker, dù giá trị kỳ vọng cao cũng không phải lúc nào bạn cũng all-in
  • Trung bình có thể có khả năng thắng cao hơn, nhưng bạn chỉ nhận được một kết quả duy nhất
  • Nếu mục tiêu là chiến thắng, tốt hơn là đừng nợ tiền Ballmer
  • Sẽ thú vị hơn nếu dùng mô phỏng Monte Carlo để xem phân phối thắng thua của chiến lược này

• Khi Ballmer nói là "thù địch", ông ấy đã tính đến việc không cần chọn một con số cố định

  • Với mỗi lần đoán, ông ấy có thể đưa ra câu trả lời để giữ lại số lượng con số khả dĩ tối đa, từ đó bảo đảm đối thủ thua bất kể chiến lược nào

• Đề xuất một thuật toán gọi là "tìm kiếm nhị phân với độ lệch ngẫu nhiên"

  • Chọn một số ngẫu nhiên từ 0-100 và gọi đó là "độ lệch"
  • Thực hiện thuật toán tìm kiếm nhị phân, nhưng ở mỗi bước cộng thêm "độ lệch" vào giá trị rồi lấy modulo 100
  • Ngay cả khi Ballmer biết chiến lược này, ông ấy cũng không thể chọn một con số cụ thể để làm giảm hiệu năng
  • Vì vậy kết quả kỳ vọng vẫn là $0.20 mỗi ván

• Đây là một trong rất nhiều điều Ballmer đã sai

• Giới thiệu cuốn "Little Mathematics Library – Elements of Game Theory"

  • Đây là một cuốn sách hay nói về chiến lược hỗn hợp trong lý thuyết trò chơi
  • Sách dùng ví dụ tạo động lực là một trò chơi hai lá bài
    • Nếu người chơi A rút được át, họ đòi đối thủ trả 1 đô la
    • Nếu rút được quân 2, họ có thể đòi đối thủ trả 1 đô la hoặc tự trả 1 đô la
    • Đối thủ có thể tự nguyện nhận 1 đô la, hoặc yêu cầu xác minh xem có phải át hay không
    • Nếu đúng là át thì họ trả 2 đô la, còn nếu là bluff thì họ nhận 2 đô la
    • Phân tích trò chơi và tìm chiến lược tối ưu cùng phần thưởng kỳ vọng cho mỗi người chơi

• Chia sẻ một liên kết cung cấp phân tích rộng hơn về cân bằng Nash và lời giải số cho toàn bộ trò chơi

• Quy trình phỏng vấn kỹ thuật hiện đại đúng là một ví dụ hoàn toàn điên rồ

• Tôi đã tìm một bình luận kiểu "cái này có vẻ đúng đấy, làm tốt lắm!", nhưng không thấy nên tự để lại

  • Cái này có vẻ đúng đấy, làm tốt lắm

• Tài sản ròng của Steve Ballmer là 120 tỷ đô la

  • Giả sử mỗi ván mất 30 giây, sẽ mất 1,6 triệu năm để thắng hết toàn bộ số tiền đó