#

#
Venture Bets

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

You are given a set of investment opportunities.
Each one has a payoff expressed as a multiple of your investment
(e.g., 10 times return) and an unknown probability of obtaining that payoff
expressed as a bounded range (e.g., between 0.7 and 0.8).
For simplicity, assume that half the time the real probability will
be at the low end of the range and half the time, the real probability
will be at the high end of the range, but your adversary chooses which
after you have made your investments.
If you make an odd number of investments 2n+1, your adversary chooses
the lower value n+1 times.
You have a budget of 100 million dollars
and you want to allocate your money so that you
can obtain 800 million dollars with probability 0.9 (higher
than any individual investment).
Determine whether this is possible.
If so, what is the minimum amount you need to invest
to achieve this goal.
If not, what number can you obtain with probability 0.9?

investment(id, payoff, lowprob, highprob)

1,20,0.4,0.6
2,10,0.6,0.7
3,15,0.5,0.7
4,15,0.45,0.6
5,15,0.5,0.7
6,25,0.5,0.6
7,10,0.6,0.8
8,10,0.6,0.8
9,22,0.3,0.6
10,12,0.5,0.8
11,12,0.6,0.6
12,13,0.5,0.8
13,13,0.45,0.8
14,17,0.4,0.7
15,20,0.4,0.6
16,12,0.7,0.75