# Dynamic Programming - Formulating recurrence relation

We wish to apply dynamic programming techniques to find the optimal betting strategy for a pool to wager on the outcome of the NCAA men's basketball tournament

64 teams compete in a single elimination bracket that lasts for 6 rounds. For each game, the winner will advance and the loser is to be eliminated. The victor is whoever wins 6 games in a row.

Each bracket is split into four regions with 16 teams each. Each team is assigned a seed from 1 to 16 (best to worst).

Before the tournament begins, each player (i.e. the better) who enters the pool is allowed to purchase up to one dollar's worth of teams. We know the outcome of the tournament. This is not a stochastic process. We wish to determine what WOULD have been the optimal betting strategy.

Let $$c_k$$ denote the cost of seed $$k$$. Let $$p_i$$ denote the number of wins team $$i$$ received. Let $$q_i$$ denote the seed of team $$i$$.

Here is my work so far:

• The stages will be the number of teams we have selected thus far, denote this by $$j$$, $$0 \leq j \leq 64$$

• The state will be $$s$$ amount of money used in the budget as well as a vector $$v$$ where each entry is a binary indicating whether we have selected team $$i$$ or not ($$1$$ = selected)

• Let $$f_j(s,v)$$ denote the maximum amount of wins to gain, given we have chosen $$j$$ teams and have used up $$s$$ dollars and have selected $$v$$ teams, where $$v[i]=1$$ if team $$i$$ was chosen.

I now need to construct a recurrence relation for the dynamic program. This is why my trouble lies. So far I have: $$f_j(s,v) = \max_{i, s + \text{extra cost} \leq 1}\{\sum_{i = 0}^{63} p_iv_i + f_{j+1}(s+\text{additional cost}, \text{appropriately update v vector})\}$$

The recurrence function is intended to maximize the amount of wins at a given stage (choosing a team) while not going over budget as well as not betting on team already selected. I am struggling to capture the additional cost at each stage of selecting a cohort of teams given the parameters I have to work with. Furthermore, I am not sure how to update my vector $$v$$ using mathematical notation. In practice, I would set a $$64\times 1$$ array and initialize all entries to be zero. Then, I'd check which entries would provide the greatest net gain by flipping the value to $$1$$ as well as being within budget. However, again, I am struggling to properly model this action.

• You might be interested in March Madness and the Office Pool. – RobPratt Apr 1 at 16:28
• @RobPratt This seems to be behind a paywall – user620842 Apr 1 at 19:24
• You have the cost part, but how are payoffs calculated? – prubin Apr 1 at 19:36
• @prubin If I understand correctly, payoffs are the number of wins you get based your team selection. So if I chose teams 1, 3, 4, 5 which are all top seeds and cost .25 ea, then my pay off would be $p_1+p_3+p_4+p_5$. I don't know if that answers your question. – user620842 Apr 1 at 19:44
The optimal objective value for your instance is 28: $$\begin{matrix} \text{team} & \text{wins} & \text{seed} & \text{cost} \\ \hline 1 & 6 & 1 & 25 \\ 2 & 5 & 3 & 18 \\ 4 & 4 & 5 & 12 \\ 15 & 2 & 12 & 2 \\ 17 & 1 & 9 & 5 \\ 18 & 1 & 12 & 2 \\ 20 & 1 & 10 & 4 \\ 21 & 1 & 9 & 5 \\ 22 & 1 & 12 & 2 \\ 24 & 1 & 10 & 4 \\ 25 & 1 & 9 & 5 \\ 27 & 1 & 11 & 3 \\ 29 & 1 & 9 & 5 \\ 30 & 1 & 13 & 1 \\ 32 & 1 & 10 & 4 \\ \hline & 28 & & 97 \\ \end{matrix}$$
if s + seed_costs[teams[j][0]] <= budget: