Search code examples
pythonalgorithmmathstatisticsgame-engine

Prize distribution algorithm to handle ties

I'm trying to come up with a prize distribution algorithm that can scalably handle different number of players and factor in ties i.e in case the contestants fall in the same position.

This is what I have so far:

Distribution Formula        
P=((1-d)/1-d^n)*d^(p-1))*A      

Where:      
P   Prize   
n   Number of winners   
A   Total amout of money to share   
d   Distribution constant >0<1  
p   Position or rank of the user

Modeling it in Excel I get the following results:

Constants

A   50000
d   0.4
n   15

Sample data

Distribution without ties

Position (p)    Player  Prize (P)
1   A   30000.03221
2   B   12000.01288
3   C   4800.005154
4   D   1920.002062
5   E   768.0008246
6   F   307.2003299
7   C   122.8801319
8   D   49.15205278
9   E   19.66082111
10  F   7.864328444
11  C   3.145731378
12  D   1.258292551
13  E   0.5033170204
14  F   0.2013268082
15  C   0.08053072327
**Total     50000**

Distribution with ties

Position (p)    Player  Prize (P)
1   A   30000.03221
1   B   30000.03221
2   C   12000.01288
3   D   4800.005154
4   E   1920.002062
4   F   1920.002062
5   C   768.0008246
6   D   307.2003299
7   E   122.8801319
8   F   49.15205278
9   C   19.66082111
10  D   7.864328444
11  E   3.145731378
12  F   1.258292551
13  C   0.5033170204
**Total 81919.75242**

Problem

Not my second data with ties the total distributed prizes is more than 50000 which is what I wanted to share

Desired results

Users falling in the same position should get an equal amount and have the prizes well distributed to the other users. The total amount paid out should not be more than what was intended.

How can I improve the above function to achieve the above results.

Solution
    1. Let MaxT (default value 1) is maximum of all ties for various tied positions

    2. Choose d <= 1/MaxT

      UPDATE: For example:

      1   A   30000.03221 |
1   B   30000.03221 |  Tie count T1 = 2
2   C   12000.01288
3   D   4800.005154
4   E   1920.002062 | 
4   F   1920.002062 |  Tie count T2 = 2

      maxT = max of {T1, T2, .. Tn} = max {2, 2} = 2

    3. Calculate prize money once for each unique position

    4. For tied positions, just divide the prize money calculated in step #2 by no. of ties for the position (Tn) (Example: For position 1: 30000/2.0)

    This scheme makes sure that total is A and prize value of a position is less than prize value of upper position, independent of ties.