1
$\begingroup$

I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite quickly for larger sets. Here's the problem

Let's say you want to take n bets each with odds k. We want to optimize the amount we should bet for each value of k denoted as x(k) such that in the worst case we loose the least amount of money. All the bets are mutually exclusive, so if one outcome happens all the rest are lost.

So far our bets would look something like

a . x(a)
b . b(a)
c . c(a)
... up to n bets

The bet amounts can only be made in discrete multiples of 10. We have a maximum total betting amount of total_bet_max and a maximum amount per bet of bet_max. So essentially we are trying to optimize the following

worst_outcome = Min(a . x(a) - b - c - [...], b . x(b) - a - c - [...], c . x(c) - a - b - [...], [...])
a + b + c + [...] <= total_bet_max
a , b , c, [...] <= bet_max

--> optimize a, b, c, ... for the highest value of worst_outcome

I tried a greedy algorithm approach by iterating over and incrementing values and checking if the worst_outcome is improved, however, this doesn't actually work. Because sometimes it makes sense to increment two variables e.g. a and b together but not by themselves. Also I think some cases you would need to look ahead to see you need to increment by 3 units for a, 2 units for b and 1 unit of c, so greedy doesn't really work.

Any suggestion or solution on how to solve this? An approximation may also be suitable if the problem is not solvable.

$\endgroup$
4

1 Answer 1

2
$\begingroup$

Notice that the equation $o = \min(a_1 x(a_1) - a_2 - a_3 - ..., a_2 x(a_2) - a_1 - a_3 - ..., ...)$ (I'm using $a_1 , a_2 , ...$ instead of $a, b, c, ...$) can be rewritten as $$o = \min(a_1 (x(a_1)+1) - \sum a_i, a_2 (x(a_2)+1) - \sum a_i, ...) = \min(a_1 (x(a_1)+1), a_2 (x(a_2)+1), ...) - \sum a_i$$ We will use $b_i = x(a_i) + 1 $. Set $c = \min(a_i b_i)$, and notice that in the optimal solution $a_i = 10 \lceil \frac{c}{10 b_i} \rceil $, since if $a_i \leq 10 (\lceil \frac{c}{10 b_i} \rceil - 1)$ (remember that it must be divisable by 10) then $a_i b_i < c$ and $c$ isn't the minimum, and if $a_i \geq 10 (\lceil \frac{c}{10 b_i} \rceil + 1)$ then $a_i$ could be decreased by 10 without hurting the minimum but decreasing the sum.

Both requirements $\sum 10 \lceil \frac{c}{10 b_i} \rceil = \sum a_i \leq s_{\max}$ and $10 \lceil \frac{c}{10 b_i} \rceil = a_i \leq a_{\max}$ are monotone in $c$, so using binary searching we can find a value $c_{\max}$ such that a solution is valid iff $c \leq c_{\max} $.

We reduced the problem to maximizing $ c - \sum 10 \lceil \frac{c}{10 b_i} \rceil $ subject to $0 \leq c \leq c_{\max} $. If $c_{\max}$ is small enough then we can search the entire range (note that we can reduce the time from $O(n c_{\max})$ to $\tilde O(\sum \lceil \frac{c_{\max}}{10 b_i} \rceil)$, by marking points where $\sum \lceil \frac{c}{10 b_i} \rceil$ increases).

Otherwise, while not a precise solution, we can argue that if $\sum \frac1{b_i} > 1$ then the general trend of the function is to decrease, so it is likely the optimal value of $c$ will be fairly small and we can check values of $c$ in the order $0, 1, 2, ...$ until we run out of time. In the same way, if $\sum \frac1{b_i} < 1$ then the general trend of the function is to increase, it is likely the optimal value will be fairly big, and we can check values in the order $c_{\max} , c_{\max} - 1, c_{\max} - 2, ...$ until we run out of time. Here as well we can mark the points where $\sum \lceil \frac{c}{10 b_i} \rceil$ increases to get a time of $\tilde O(\sum \lceil \frac{R}{10 b_i} \rceil)$, with $R$ being the size of the range we are testing.

For example, suppose there are three bets with odds 1, 2 and 23 (so $b = 2, 3, 24$), with a maximum bet of 200, and a maximum total bet of 260. Then, with binary search, we can find that $c_\max = 280$, which will produce the bets $140, 100, 20$, which are valid, while $281$ will give the bets $150, 100, 20$ which have too big of a sum. Now, we need to find the maximum value of $ c - \sum 10 \lceil \frac{c}{10 b_i} \rceil $ for integer $0 \leq c \leq 280$. An exhaustive search gives $c = 240$, for which it is equal to 30, and the optimal bets will be $120, 80, 10$

$\endgroup$
4
  • $\begingroup$ Wow great answer! Thanks! Will take me some time to digest it $\endgroup$ Feb 3, 2023 at 5:21
  • $\begingroup$ Sorry noob question, what is the m in Cm and Tm? $\endgroup$ Feb 3, 2023 at 5:26
  • $\begingroup$ Would be super helpful if you could add an explanation with an example with numbers because it's quite abstract. Really appreciate the help! $\endgroup$ Feb 3, 2023 at 5:32
  • $\begingroup$ @AntersBear I added an example. $\endgroup$ Feb 3, 2023 at 8:28

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.