2
$\begingroup$

Here are the results of $1,000,000$ games between $7$ players

        1       2       7       10      16      17      47      

1       1.00    1.99    7.03    9.98    16.00   16.99   47.01   
2       1.48    2.99    9.92    13.88   20.89   22.05   28.78   
3       2.20    4.33    13.72   18.00   23.11   23.26   15.38   
4       3.56    6.86    19.24   22.72   20.83   20.20   6.58    
5       6.69    12.72   28.67   22.99   14.04   12.94   1.94    
6       22.18   41.03   17.35   10.54   4.56    4.06    0.29    
7       62.88   30.08   4.07    1.89    0.57    0.48    0.02

The first row represents the player power, the rows after it represents how many times that player won. For example, the player with the power of $47$ won the first place $47.01$ percent of the total games, he won the second place $28.78$ percent of the total games and so on.

The game is selecting a ball from a jar where each ball has a unique number between $0$ to $2^{256}$, during each game the players draw number of balls equal to their power, and never return it to the jar, then they keep the ball with the lowest number and throw away all the other balls, so each player only have one ball. The player with the lowest ball wins the first place, the player with the seconds lowest ball wins the second place an so on.

I have a reward of 100 coins and I would like to equally share it among the players based on their power. My first strategy was to only reward the first place, and it worked perfectly. However, it upset the rest of the players who didn't win.

Therefore I would like to come up with a new rewarding idea that will reward all the players after each game solely based on the game results. But still, after all the games are over, the total reward will be equally distributed among the players based on their power.

$\endgroup$
  • $\begingroup$ Are the balls drawn with replacement? Also, I don't understand how power works. You say that each player draws a number of balls equal to his power, but power is defined as the percentage of games won. How is power computed during the course of the game? $\endgroup$ – saulspatz Jul 27 '18 at 12:49
  • $\begingroup$ @saulspatz I don't understand your question. After the ball is drawn, it's never returning to the jar, not even in the future games. $\endgroup$ – Ilya Gazman Jul 27 '18 at 12:58
  • $\begingroup$ Sorry, I missed that. How is the power computed during the course of the game? $\endgroup$ – saulspatz Jul 27 '18 at 13:01
  • $\begingroup$ Power is not defined as the percentage of games won, I just ran this simulation, and those were the results. Power is defined as the number of balls the player picks during each game $\endgroup$ – Ilya Gazman Jul 27 '18 at 13:01
  • 1
    $\begingroup$ Sorry for all the questions; you explained it well in your question. Good problem. I'll think about it. $\endgroup$ – saulspatz Jul 27 '18 at 13:17
2
$\begingroup$

Sorry, but I think you've already found the only possible solution. Let $a_{ij}$ be the probability that player $i$ finishes in position $j$ on a given round. You want to award some fraction $f_j$ to the player who finishes in position $j$ on each round, and we may take $f_1+f_2+\dots+f_7=1.$ You also want the prizes to awarded in proportion to power, so the expectation of the players should be in proportion to their power. The expectation of player $i$ is $a_{i1}f_1+a_{i2}f_2+\dots+a_{i7}f_7$.

We can rescale the powers by dividing by the total power without changing the problem. In your example, we can make the powers $.01,.02, .07, .10, .16,.17,.47,$ and say that the players draw balls in proportion to their power; the problem doesn't change. Then the power of a player is simply the probability that he finishes in first place. We have $$ \mathbf{A}f = a,$$ where $\mathbf{A}$ is the matrix $(a_{ij})_{7\times 7},\ f=(f_1,\dots,f_7)^T,\ a=(a_{11},a_{21},\dots,a_{71})^T.$ Note that the right-hand side is the first column of $\mathbf{A}$ so that $$f=(1,0,0,0,0,0,0)^T$$ is a solution. Unless $\mathbf{A}$ is nonsingular, which seems highly unlikely (the set of singular matrices has measure zero) this is the only solution, and it's precisely what you are doing already.

Of course, there's nothing magic about $7$. The same result holds for any number of players.

$\endgroup$
  • $\begingroup$ It proves that the new reward system cannot be linear to the power. But what about a polynomial solution? $\endgroup$ – Ilya Gazman Jul 27 '18 at 15:23
  • 1
    $\begingroup$ @IlyaGazman: There's no assumption here that the rewards are linear in the power; in fact, there's no assumption about the rewards at all. The linearity here is just the linearity of expectation. You said you wanted the rewards to be awarded "after each game solely based on the game results". I don't understand what you mean by "linear to the power" in that context. Aren't the rewards to be distributed solely based on the results, without using knowledge about the players' power? $\endgroup$ – joriki Jul 27 '18 at 15:26
  • $\begingroup$ I second joriki's comment. There's no assumptions about the rewards. They are whatever they are. $\endgroup$ – saulspatz Jul 27 '18 at 15:36
  • $\begingroup$ Your argument can be strenghtened somewhat. That $\mathbf A$ is "highly likely" nonsingular is on slightly shaky ground, since there might theoretically be systematic reasons for it to be singular. But if the rewards are to be positive, we'd actually need a convex combination of the other columns to be equal to the first column; and this is not possible, since the gradient in the probabilities is strongest for the first-place probability and is reduced and then reversed as we go to the probabilities for lower places. $\endgroup$ – joriki Jul 27 '18 at 15:44
  • 1
    $\begingroup$ @IlyaGazman: I think you're misunderstanding the answer. The $f_i$ are arbitrary variables that stand for the rewards awarded in each game to the player who's in $i$-th place in that game. No relationship between these variables and the players' power is being assumed. $\endgroup$ – joriki Jul 27 '18 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.