Optimal Strategy - Survival

Question

There are $n$ players playing the following game:

• There is a $\$1$ entry fee for each of the $n$ players.
• There are $m$ teams in a Sports League (say NFL for example). Each week, each of the $n$ players chooses one of the $m$ teams in the league. Different players can choose the same team if they wish.
• A player gets through to the next round if their team wins, otherwise, they're out.
• A player can't choose a team who they have already chosen previously.
• This process continues until there is either one player left or there are no players left and the process repeats itself from the start.

What is the optimal strategy for this game? What strategy maximises your return? To make things easier, we can assume we possess the probabilities of each team $j$ winning in week $i$ and that they are independent for all $i, j$.

Intuitively, I feel like the following are important:

• Choosing a team whose future expected value is poor. As in, if a "bad" team is playing "one of the worst" teams, then it may be a good idea to choose this team this week while they have a decent chance of winning.
• Going against the grain. A lot of players will likely pick the same teams (with good chance of progressing), but it may be good to go against the grain. If you have a unique pick, then there is a chance (probably slim) of scooping the pot that week. Even if you don't scoop it, you now have the team remaining that the majority of people chose that week, which will give you a low owned pick in the future.
• The strategy will depend on $n$ a fair bit, as this will likely dictate how long the process continues for, and if we'll ever "need" to take a big gamble and choose the bad teams

Answer 1

For one entry, you can maximize the overall survival probability by solving a minimum sum linear assignment problem in a bipartite graph with a left node for each team $i$, a right node for each week $j$, and an arc $(i,j)$ if team $i$ plays in week $j$. The overall survival probability to be maximized is a product of win probabilities, but you can transform to minimization of a linear function by taking each arc weight to be the negative log of the win probability. Explicitly, the problem is to minimize $$-\sum_{i,j} \log(p_{ij}) x_{ij}$$ subject to \begin{align} \sum_j x_{ij} &\le 1 &&\text{for all $i$} \\ \sum_i x_{ij} &= 1 &&\text{for all $j$} \\ x_{ij} &\in \{0,1\} &&\text{for all $i$ and $j$} \end{align}

For an optimal strategy with multiple entries, see Surviving a National Football League Survivor Pool (2017) by David Bergman and Jason Imbrogno.

Answer 2

In this situation you want primarily a strategy that makes it most likely that you win overall. It’s not important how long you survive. Say there are ten players, and there is one team A that wins their game with probability 0.8 and one team B that wins with probability 0.6. If everyone bets on A and you bet on B, chances are 0.12 that you are the only winner! (Instead of 0.1 if everyone plays randomly. And 0.12 is just the probability for an immediate win in the first round. Even if you are the only loser with p = 0.32 the other nine players may still draw and you start all over).

This is incredibly difficult. Even if you started with 10 players, and after a while only two are left with one choice of teams left. If you both win or both lose the game is restarted and you win with probability 0.1. If only you win you won. If only you lose then you lost. If your team wins with probability p and the other one wins with probability q, your total probability of winning is p(1-q) + 0.1 (pq + (1-p)(1-q)).

Now if two players have two teams left it gets more difficult. You both have a good chance of winning overall and you absolutely don’t want a draw. So a good method would be to agree with your opponent to throw a coin, and agree beforehand what teams will be chosen depending on the winner of the coin throw. You will make a choice that minimises the chances of a draw, while giving the winner of the coin throw a better chance to win. (Remember it is in the interest of both players that there is no draw). I think that tiny sub problem is hard enough :-( It’s a non-zero sum game requiring negotiating.

With two players and three teams left, you will again do one coin throw, and possibly another coin throw when you are both down to two teams. Three players with two teams would be really hard to solve optimally.