Problem 46. Competition Between Bing and Google
Google and Bing are competing against each other over the search result of query “Math Cafe". There are three relevant results for this search. The percentage of users looking for the results are equal to 30%, 30%, and 40%, respectively. Upon querying “Math Cafe" in each of the search engines, they show a permutation of the three webpages.
Every time a user searches for query “Math Cafe" in both search engines and finds out which search engine shows the result he is looking for first. Based on this he will stick to that search engine for the rest of his life. (If both search engines show the corresponding result in the same position, the user will never again use Bing or Google in his life)
Each search engine wishes to design an algorithm for showing the results in a way that maximizes the number of its own users minus the number of its competitor’s users. What is the best strategy in this game?
Link to the problem on Twitter: https://twitter.com/Riazi_Cafe/status/1710911075036893518
. The problem describes a zero-sum game. In this game, each player has 6 strategies \(\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\), and \(\langle 3, 2, 1 \rangle\). The table below shows the utility of the players for playing each pair of strategies:
| \(\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 |
Since webpages 1 and 2 are identical, we can reduce the number of strategies to 3 by assuming that we first place the third webpage in the permutation and then randomly put the first and the second webpages in the remaining positions. It follows from symmetry that the utility of the optimal strategy remains the same with this reduction. Therefore, the payoff table can be summarized as:
| \(\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 |
Now, let us play strategy \(\langle 3, *, *\rangle\) with probability \(p\), strategy \(\langle *, 3, *\rangle\) with probability \(q\) and strategy \(\langle *, *, 3\rangle\) with probability \(1-p-q\). We wish to maximize our utility in the worst case and therefore we formulate this values as the minimum payoff we obtain for each of the three strategies of the opponent as follows: \[\min\{-25q + 5(1-p-q), 25p - 25(1-p-q), -5p+25q \}\] The above expression is maximized for \(p=5/11, q=1/11, (1-p-q) = 5/11\). Thus in the optimal strategy, we play as follows:
| strategy | probability |
|---|---|
| \(\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 |