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