You are invited to Log in or Register a free Frihost Account!

Project LCTER - Calculations with Generalisability

We consider a drop-out tournament of the following kind:

We restrict the number of participants n such that it works out nicely, i.e. we set n = 2^k for some natural number k.
This means that there are going to be r = log(base 2) n number of rounds in total.

Here are the specifications:

So before we begin, let
p = chance of winning a round
c = cost of entry
w1, w2, wS = prize winning for the 1st, 2nd, and the 2 semi-finalists respectively
(the 2 semi-finalists each get wS amount of gold as a reward in this case)

Then it is quite natural to ask:

1. If we have a 50% chance of winning each round, what would be the expected return?

First let E = expected return. Then E is a function of w1, w2, wS, c, p and r (or n). One may need to adjust or add these accordingly for different settings.
If p = 0, then we will always lose in the first round and there won't be any prize winnings, thus we would expect to gain -c gold per tournament.
If p = 1, then we will always get the first place, so we would expect w1 - c gold per tournament.
So it is natural to ask if p = 0.5, would it be profitable to enter one such tournament?

We observe that E = (expected winning) - c.

Now the probability that we win in 1st place is just p^r. Each time this occurs, we win w1 gold, so the expected winning from the 1st place prize is w1 p^r per tournament.

The probability that we win in 2nd place is p^(r-1) (1-p)^1 because we won 1 less round and lose 1 more round than the above. Again, each time this occurs, we win w2 gold, giving the expected winning from the 2nd place prize of w2 (1-p) p^(r-1) per tournament.

Similarly, we would expect wS (1-p) p^(r-2) per tournament. We note here that once we get (1-p), we get dropped out of the tournament, thus this is not (1-p)^2 p^(r-2).

Since winning ith and winning jth place are mutually exclusive (for i =/= j), the total expected winning is just the sum of the expected winning from each individual places.
E = w1 p^r + w2 (1-p) p^(r-1) + wS (1-p) p^(r-2) - c

Expanding this out gives us a polynomial of degree r:
E = (w1 - w2) p^r + (w2 - wS) p^(r-1) + wS p^(r-2) - c

This is a general equation for any p, so we can essentially stop here because all we have left is just plugging in the numbers.
Let us consider just one example here:
p = 0.5
c = 1,000
n = 32
r = 5
w1 = 18,000
w2 = 6,000
wS = 3,000

Then, using a calculator of your preference, we get E = -62.5.
Which is what one would expect, E < 0 for p = 0.5 just means that the tournament organiser would be earning at least some money in the long run. But this just can't be too low because that wouldn't attract any participants.

But given this knowledge, it is further natural to ask:

2. If E = 0, what's p?

In other words, what's the minimum chance of winning each round needed such that we break-even? Knowing this means knowing the threshold in which greater p means we would start earning some gold from the tournament and that lower p means we would start losing.

But we already have the equation of E and p and it's a polynomial of degree r!
Unfortunately, we just don't have a general equation for a polynomial of an arbitrary degree.
Fortunately, we can just write a simple program for this. I use a bisection search for p on [0,1], here's a pseudo-code:
class Tournament {
     * relevant variables
    float expectedReturn (p) {
        //see question 1
    float breakEven () {
        lowerBound = 0;
        upperBound = 1;
        p = 0.5; //the first instance of (lowerBound + upperBound)/2
        calculatedReturn = this.expectedReturn(p);
        while ( not(0 <= calculatedReturn < 0.005)) {
            //reduce search interval and update variables
            if (calculatedReturn < 0) {
                lowerBound = p;
            } else {
                upperBound = p;
            p = (lowerBound + upperBound)/2.;
            calculatedReturn = this.expectedReturn(p);
        return p;

Rounded to 2 decimal places, the above gives us (using the same example I used in question 1.) 50.82% for p. This gives an expected return of approximately 0.64 gold (p rounded to 2 decimal places so the expected return is not numerically 0.

Answering these 2 questions basically solves everything I need for the project LCTER, all I have to worry about now is the implementation, which also happens to be what I am not quite so good at.

0 blog comments below

© 2005-2011 Frihost, forums powered by phpBB.