مساله ۴۶. رقابت بینگ و گوگل

گوگل و بینگ سر سرچ «کافه ریاضی» با هم رقابت دارن. سه تا پیچ برای این سرچ وجود داره. درصد کاربرایی که دنبال هر پیج میگردن برابر است با ۳۰،۳۰، ۴۰.

هر بار یه کاربر میاد سرچ میکنه «کافه ریاضی» و میبینه کدوم سرچ عنجین پیجشو بالاتر پیشنهاد میده و تا آخر عمر مشتری همون سرچ عنجین میشه. (اگه جفت سرچ عنجین ها در یه جایگاه دادن ریزالتشو، سرچ‌کردن رو تا آخر عمر میذاره کنار)

هدف هر سرچ عنجین بیشینه کردن تعداد کاربرای خودش منهای تعداد کاربرای رقیبشه. بهترین استراتژی در این بازی چیه؟

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1710911075036893518

-

مسئله یک بازی حاصل جمع صفر را توصیف می کند. در این بازی، هر بازیکن دارای 6 استراتژی \(\langle 1, 2, 3 \rangle\), \(\langle 1, 3, 2 \rangle\), \(\langle 2, 1, 3 \rangle\), \(\langle 2, 3, 1 \rangle\), \(\langle 3, 1, 2 \rangle\), و \(\langle 3, 2, 1 \rangle\) هست. جدول زیر امتیاز بازیکنان برای هر جفت استراتژی را نشان می دهد:

\(\langle 1, 2, 3\rangle\) \(\langle 1, 3, 2\rangle\) \(\langle 2, 1, 3\rangle\) \(\langle 2, 3, 1\rangle\) \(\langle 3, 1, 2\rangle\) \(\langle 3, 2, 1\rangle\)
\(\langle 1, 2, 3\rangle\) \((0-0)=0\) \((30-40)=-10\) \((30-30)=0\) \((30-70)=-40\) \((60-40)=20\) \((30-40)=-10\)
\(\langle 1, 3, 2\rangle\) \((40-30)=10\) \((0-0)=0\) \((70-30)=40\) \((30-30)=0\) \((30-40)=-10\) \((30-70)=-40\)
\(\langle 2, 1, 3\rangle\) \((30-30)=0\) \((30-70)=-40\) \((0-0)=0\) \((30-40)=-10\) \((30-40)=-10\) \((60-40)=20\)
\(\langle 2, 3, 1\rangle\) \((70-30)=40\) \((30-30)=0\) \((40-30)=10\) \((0-0)=0\) \((30-70)=-40\) \((30-40)=-10\)
\(\langle 3, 1, 2\rangle\) \((40-60)=-20\) \((40-30)=10\) \((40-30)=10\) \((70-30)=40\) \((0-0)=0\) \((30-30)=0\)
\(\langle 3, 2, 1\rangle\) \((40-30)=10\) \((70-30)=40\) \((40-60)=-20\) \((40-30)=10\) \((30-30)=0\) \((0-0)=0\)

از آنجایی که امتیازها برای صفحات وب 1 و 2 یکسان هستند، می توانیم تعداد استراتژی ها را با فرض اینکه ابتدا صفحه وب سوم را در جایگشت قرار می دهیم و سپس به طور تصادفی صفحات وب اول و دوم را در موقعیت های باقی مانده قرار می دهیم به 3 کاهش دهیم. به دلیل تقارن امتیاز استراتژی بهینه با این کاهش فرقی نخواهد کرد. بنابراین، جدول امتیازها را می توان به صورت زیر خلاصه کرد:

\(\langle 3, *, *\rangle\) \(\langle *, 3, *\rangle\) \(\langle *, *, 3\rangle\)
\(\langle 3, *, *\rangle\) \(0\) \(25\) \(-5\)
\(\langle *, 3, *\rangle\) \(-25\) \(0\) \(25\)
\(\langle *, *, 3\rangle\) \(5\) \(-25\) \(0\)

استراتژی \(\langle 3، *، *\rangle\) را با احتمال \(p\)، استراتژی \(\langle *، 3، *\rangle\) با احتمال \(q\) و استراتژی \(\langle *، *، 3 \rangle\) با احتمال \(1-p-q\) بازی کنیم. ما می‌خواهیم در بدترین حالت، امتیاز خود را بیشینه کنیم و بنابراین امتیاز خود را برابر با کمترین امتیاز در مقایل سه بازی حریف به صورت زیر فرموله می‌کنیم:

\[\min\{-25q + 5 (1-p-q)، 25p - 25 (1-p-q)، -5p+25q \}\]

عبارت فوق به ازای \(p=5/11، q=1/11، (1-p-q) = 5/11\) بیشینه می‌شود. بنابراین در استراتژی بهینه، به صورت زیر بازی می کنیم:

استراتژی احتمال
\(\langle 1, 2, 3\rangle\) \(5/22\)
\(\langle 1, 3, 2\rangle\) \(1/22\)
\(\langle 2, 1, 3\rangle\) \(5/22\)
\(\langle 2, 3, 1\rangle\) \(1/22\)
\(\langle 3, 1, 2\rangle\) \(5/22\)
\(\langle 3, 2, 1\rangle\) \(5/22\)