GN⁺: Ballmer 전략과 무관한 게임의 긍정적 기대값

Steve Ballmer가 틀렸음

며칠 전 John Graham-Cumming이 "Steve Ballmer의 잘못된 이진 검색 인터뷰 질문"에 대해 게시한 글이 HackerNews에서 많은 주목을 받았음. Ballmer의 좋아하는 두뇌 티저는 다음과 같음:

나는 1에서 100 사이의 숫자를 생각하고 있음. 당신은 추측할 수 있으며, 각 추측 후 내가 높거나 낮다고 말해줄 것임. 첫 번째 추측에서 맞추면 5달러를 줄 것임. 4달러, 3달러, 2달러, 1달러, 0달러, 당신은 나에게 1달러, 2달러, 3달러를 지불해야 함.

이 게임을 할 것인가?

Steve Ballmer는 이 YouTube 인터뷰에서 이 게임을 하지 말아야 하는 두 가지 이유를 제시함:

1. 1에서 100 사이의 숫자 중 많은 숫자가 손실을 초래하여, 무작위로 숫자를 선택하더라도 기대값이 음수임.
2. 그는 이진 검색을 사용하여 찾는 데 가장 오랜 시간이 걸리는 숫자를 전략적으로 선택할 수 있음.

그러나 John은 Ballmer가 숫자를 무작위로 선택하면 게임의 기대값이 실제로 $0.20로 양수임을 보여주며 첫 번째 점을 반박함.

나는 두 번째 점을 반박하고 Ballmer의 전략에 관계없이 게임의 기대값이 양수임을 증명할 것임.

Ballmer가 적대적으로 숫자를 선택할 수 있는 방법

항상 이진 검색 전략을 사용하여 숫자를 찾는다고 가정해보자. 100개의 숫자 중 37개는 추측을 하기 위해 6번의 질문이 필요함. Ballmer가 당신의 전략을 알고 있다면 항상 이러한 "패배" 숫자 중 하나를 선택하여 매 게임에서 손실을 초래할 수 있음. 이는 고정된 검색 패턴에 대해 항상 성립함. 최소한 37개의 숫자가 손실을 초래할 것이며, Ballmer는 그 중 하나를 선택할 수 있음.

어떻게 대응할 수 있는가?

여기서 우리는 게임 이론 영역으로 들어감. 단일 고정 검색 패턴 대신 여러 검색 패턴 세트를 준비할 수 있음. 그런 다음 게임 시작 시 이러한 패턴 중 하나를 확률적으로 선택하고 게임 동안 이를 고수함.

게임 이론에서는 이를 혼합 전략이라고 하며, 여러 순수 전략의 전략 세트를 기반으로 함.

같은 숫자가 한 검색 패턴에서는 "승리"하고 다른 검색 패턴에서는 "패배"할 수 있기 때문에, 이러한 혼합 전략은 각 숫자의 기대 수익을 "평준화"할 수 있음. 잠재적으로 혼합 전략은 모든 숫자를 "승리"로 만들 수 있음, 즉 각 숫자에 대해 양수의 기대 수익을 가질 수 있음. 이것이 우리가 찾고 있는 것임.

승리하는 혼합 전략을 찾는 방법

참고: 우리는 모든 숫자에서 승리하는 어떤 전략을 찾고자 하며, 최악의 경우 최대 기대값을 가지는 최고의 승리 전략(Nash equilibrium)을 찾고자 하는 것이 아님.

Nash equilibrium에 대해 궁금하다면, Arthur O’Dwyer가 5개의 숫자까지의 게임에 대한 폐쇄형 해를 탐구했으며, Bo Waggoner가 100개의 숫자 게임에 대한 equilibrium 값을 무후회 온라인 학습을 사용하여 근사함.

모든 숫자에서 승리하는 혼합 전략을 찾는 것은 수학적 최적화 문제로 볼 수 있음. 각 전략은 "승리" 벡터 V=(v1,..,v100)로 설명될 수 있으며, 여기서 vk는 Ballmer가 숫자 k를 선택했을 때의 기대 승리임. 예를 들어, 이진 검색은 v50=5, v25=4, v0=−1인 벡터에 해당할 수 있음.

순수 전략 V1, V2, ..., Vn이 있다고 가정하고, 혼합 전략이 확률 pk로 전략 Vk를 선택한다고 가정하자. 그러면 혼합 전략의 해당 "승리" 벡터는 단순히 선형 결합임: Vmixed=∑i=1npiVi.

이 해석에서 승리 전략을 찾는 것은 두 가지 제약 조건을 가진 선형 결합을 찾는 것임:

• 선형 결합의 각 요소가 양수임 (각 숫자에 대해 평균적으로 돈을 벌 수 있음).
• 이 선형 결합의 계수가 음수가 아님 (확률에 해당함).

이는 전형적인 선형 프로그래밍 문제이며, scipy에는 이를 위한 효율적인 해결책이 있음. 혼합 전략을 찾기 위해 여러 순수 전략(다양한 이진 검색)을 생각해내고 이를 scipy.linprog()에 입력했으며, voilà - 해결책이 승리 전략을 제시함!

예시 승리 전략

전체 코드는 gukoff/ballmer_puzzle에 있음. 참고: 초기 결과인 $0.07는 Arthur O’Dwyer가 새로운 순수 전략을 추가하여 크게 개선됨.

• Ballmer가 무작위로 선택할 경우 평균 승리: $0.16
• Ballmer가 적대적으로 선택할 경우 최악의 승리: $0.14

결과 혼합 전략은 다음과 같음:

• 확률 0.4714%: 이진 검색, 첫 추측 29. 각 단계에서 구간의 중간 요소를 추측함. 동점일 경우 왼쪽 요소를 추측함
• 확률 0.1691%: 이진 검색, 첫 추측 33. 각 단계에서 구간의 중간 요소를 추측함. 동점일 경우 왼쪽 요소를 추측함
• 확률 0.1299%: 이진 검색, 첫 추측 36. 각 단계에서 구간의 중간 요소를 추측함. 동점일 경우 오른쪽 요소를 추측함
• 확률 3.3341%: 이진 검색, 첫 추측 37. 각 단계에서 구간의 중간 요소를 추측함. 동점일 경우 오른쪽 요소를 추측함
• 확률 1.7818%: 이진 검색, 첫 추측 43. 각 단계에서 최악의 경우 복잡성을 증가시키지 않는 구간의 가장 오른쪽 요소를 추측함
• 확률 1.1608%: 이진 검색, 첫 추측 44. 각 단계에서 최악의 경우 복잡성을 증가시키지 않는 구간의 가장 왼쪽 요소를 추측함
• 확률 2.1310%: 이진 검색, 첫 추측 42. 각 단계에서 최악의 경우 복잡성을 증가시키지 않는 구간의 가장 끝 요소를 추측함

...

전체 전략은 74줄로 구성되어 있으며, 간결성을 위해 생략함. 관심이 있다면 GitHub에서 확인할 수 있음.

결론

게임당 평균적으로 14센트를 벌 수 있다면, 다음에 Steve Ballmer가 이 게임을 제안할 때 반드시 참여해야 함.

GN⁺의 정리

• 이 기사는 Steve Ballmer의 이진 검색 게임에 대한 논쟁을 다루고 있음.
• 게임 이론을 사용하여 Ballmer의 전략에 관계없이 승리할 수 있는 혼합 전략을 찾는 방법을 설명함.
• 이 기사는 게임 이론과 최적화 문제에 관심이 있는 사람들에게 유익할 수 있음.
• 유사한 기능을 가진 다른 프로젝트로는 다양한 게임 이론 관련 연구와 논문이 있음.

[neo]

Hacker News 의견

• Ballmer의 주장은 꼬리 위험에 대한 것임

  • 생존을 중시한다면 기대값은 좋은 베팅 방법이 아님
  • 포커에서 기대값이 높다고 매번 올인하지 않는 이유와 같음
  • 평균적으로 이길 가능성이 더 높을 수 있지만, 한 번의 결과만 얻을 수 있음
  • 목표가 승리라면, Ballmer에게 돈을 빚지 않는 것이 좋음
  • 몬테카를로 시뮬레이션을 통해 이 전략의 승패 분포를 보는 것이 더 흥미로울 것임

• Ballmer가 '적대적'이라고 말했을 때, 그는 고정된 숫자를 선택할 필요가 없음을 고려함

  • 각 추측에 대해 가능한 숫자의 최대 수를 남기는 답을 주어 전략에 상관없이 패배를 보장할 수 있음

• "랜덤 오프셋 이진 탐색"이라는 알고리즘을 제안함

  • 0-100 사이의 랜덤 숫자를 선택하고 이를 '오프셋'이라 부름
  • 이진 탐색 알고리즘을 수행하되, 각 단계에서 값에 '오프셋'을 추가하고 100으로 모듈러 연산을 함
  • Ballmer가 이 전략을 알고 있어도 특정 숫자를 선택해 성능을 떨어뜨릴 수 없음
  • 따라서 기대 결과는 여전히 게임당 $0.20임

• Ballmer가 틀린 많은 것들 중 하나임

• "Little Mathematics Library – Elements of Game Theory" 책을 추천함

  • 게임 이론의 혼합 전략을 다루는 좋은 책임
  • 책에서 동기 부여 예제로 두 장의 카드 게임을 소개함
    • A 플레이어가 에이스를 뽑으면 상대에게 1달러를 요구함
    • 듀스를 뽑으면 상대에게 1달러를 요구하거나 1달러를 지불함
    • 상대는 자발적으로 1달러를 받거나, 에이스인지 확인을 요구할 수 있음
    • 에이스가 맞으면 2달러를 지불하고, 블러핑이면 2달러를 받음
    • 게임을 분석하고 각 플레이어의 최적 전략과 기대 보상을 찾음

• Nash 균형의 더 광범위한 분석과 전체 게임에 대한 수치적 해결책을 제공하는 링크를 공유함

• 현대 기술 면접 과정이 순전히 미친 예시임

• "이것이 맞는 것 같음, 잘했음!"이라는 댓글을 찾고 있었는데, 없어서 직접 남김

  • 이것이 맞는 것 같음, 잘했음

• Steve Ballmer의 순자산이 1200억 달러임

  • 각 게임이 30초 걸린다고 가정하면, 모든 돈을 이기는데 160만 년이 걸림