Sharing Problem

A problem also known as the Points Problem or Unfinished Game. Consider a tournament involving $k$ players playing the same game repetitively. Each game has a single winner, and denote the number of games won by player $i$ at some juncture $w_i$. The games are independent, and the probability of the $i$th player winning a game is $p_i$. The tournament is specified to continue until one player has won $n$ games. If the tournament is discontinued before any player has won $n$ games so that $w_i<n$ for $i=1$, ..., $k$, how should the prize money be shared in order to distribute it proportionally to the players' chances of winning?

For player $i$, call the number of games left to win $r_i\equiv n-w_i>0$ the ``quota.'' For two players, let $p\equiv p_1$ and $q\equiv p_2=1-p$ be the probabilities of winning a single game, and $a\equiv r_1=n-w_1$ and $b\equiv r_2=n-w_2$ be the number of games needed for each player to win the tournament. Then the stakes should be divided in the ratio $m:n$, where

$$m = p^a\left[{1+{a\over 1}q+{a(a+1)\over 2!}q^2+\ldots+{a(a+1)\cdots(a+b-2)\over(b-1)!}q^{b-1}}\right]$$ (1)

$$n = q^b\left[{1+{b\over 1}p+{b(b+1)\over 2!}p^2+\ldots+{b(b+1)\cdots(b+a-2)\over(a-1)!}p^{a-1}}\right]$$ (2)

(Kraitchik 1942).

If $i$ players have equal probability of winning (``cell probability''), then the chance of player $i$ winning for quotas $r_1$, ..., $r_k$ is

$$W_i = D_1^{k-1}(r_1, \dots, r_{i-1}, r_{i+1}, \ldots, r_k; r_i),$$ (3)

where $D$ is the Dirichlet Integral of type 2D. Similarly, the chance of player $i$ losing is

$$L_i = C_1^{k-1}(r_1, \dots, r_{i-1}, r_{i+1}, \ldots, r_k; r_i),$$ (4)

where $C$ is the Dirichlet Integral of type 2C. If the cell quotas are not equal, the general Dirichlet integral $D_{\bf a}$ must be used, where

$$a_i={p_i\over 1-\sum_{i=1}^{k-1} p_i}.$$ (5)

If $r_i=r$ and $a_i=1$, then $W_i$ and $L_i$ reduce to $1/k$ as they must. Let $P(r_1, \ldots, r_k)$ be the joint probability that the players would be Ranked in the order of the $r_i$s in the argument list if the contest were completed. For $k=3$,

$$P(r_1,r_2,r_3) =CD_1^{(1,1)}(r_1, r_2, r_3).$$ (6)

For $k=4$ with quota vector ${\bf r}=(r_1, r_2, r_3, r_4)$ and $\Delta=p_2+p_3+p_4$,

$$P({\bf r}) = \sum_{i=0}^{r_3-1} \sum_{j=0}^{r_4-1} {r_2-1+i+j\choose r_2-1, i,... ...a}\right)^{r_2} \left({p_3\over\Delta}\right)^i \left({p_4\over\Delta}\right)^j$$

$$\phantom{=} \times C^{(1)}_{p_1/\Delta}(r_1, r_2+i+j)D^{(1)}_{p_4/p_3}(r_4-j, r_3-i).$$ (7)

An expression for $k=5$ is given by Sobel and Frankowski (1994, p. 838).

See also Dirichlet Integrals

References

Kraitchik, M. ``The Unfinished Game.'' §6.1 in Mathematical Recreations. New York: W. W. Norton, pp. 117-118, 1942.

Sobel, M. and Frankowski, K. ``The 500th Anniversary of the Sharing Problem (The Oldest Problem in the Theory of Probability).'' Amer. Math. Monthly 101, 833-847, 1994.