1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ You might be interested in March Madness and the Office Pool. $\endgroup$
    – RobPratt
    Commented Apr 1, 2021 at 16:28
  • $\begingroup$ @RobPratt This seems to be behind a paywall $\endgroup$
    – user620842
    Commented Apr 1, 2021 at 19:24
  • $\begingroup$ You have the cost part, but how are payoffs calculated? $\endgroup$
    – prubin ♦
    Commented Apr 1, 2021 at 19:36
  • $\begingroup$ @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. $\endgroup$
    – user620842
    Commented Apr 1, 2021 at 19:44
  • $\begingroup$ Try this link instead. $\endgroup$
    – RobPratt
    Commented Apr 1, 2021 at 19:46

1 Answer 1

Reset to default
5
$\begingroup$

You have an instance of the 0-1 knapsack problem where you want to determine which teams to select to maximize the number of wins, subject to a budget. The linked page provides a DP recurrence, which is obtained by conditioning on whether or not you select the next team.

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}

Your code incorrectly yields 29 because your budget check should instead be:

if s + seed_costs[teams[j][0]] <= budget:
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.