A liability allocation game

Abstract

The following problem is considered. Two players are each required to allocate a quota of $n$ counters among $k$ boxes labelled 1, 2, $\ldots$ , $k$ . At times $t=$ 1, 2, 3, $\ldots$ a random box is identified; the probability of choosing box $i$ is $p_{i}$ . If a player has at least one counter in the chosen box, she removes one counter from it; otherwise she takes no action. The winner is the first player to remove all her counters. The game so described may be modified so that each player simultaneously, but independently, identifies a box at random.

This paper analyses this deceptively simple game, which has apparently not been studied in the literature. Some analytical and numerical results are then presented, followed by some challenges for further work.

Keywords

Zero-sum game liability allocation game allocation game colonel Blotto coupon collector’s problem

1. Introduction

Two players are each required to allocate a quota of $n$ counters among $k$ boxes labelled $1,2,\ldots,k$ . At times $t=1,2,3,\ldots$ a random box is identified; the probability of choosing box $i$ is $p_{i}$ and these probabilities are common knowledge. If a player has $\geqslant 1$ counters in the chosen box, she removes one counter from it; otherwise she takes no action. The winner is the first player to remove all her counters, except that if both players remove their respective last counters simultaneously then the game is a draw. As such the problem may be considered to be a two-person zero-sum game.

Further to the above, in which the same box is identified for each player (the “common throw” régime), the game may be modified so that each player simultaneously, but independently, identifies a box at random (the “separate throw” régime). In this case the two players may both use the same set of probabilities $p_{1},p_{2},\ldots,p_{k}$ , or each player may use her own probabilities; however, unless otherwise stated in what follows, the two sets of probabilities will be identical.

Observe that, in contrast to allocation games such as Colonel Blotto [13] in which the units to be allocated are beneficial, here the units are detrimental. The game described here bears the same relation to resource allocation as chore division [12] does to cake division [5]: we call it “Alice’s game”.

The box probabilities will be arranged in a nonincreasing order, so that $p_{1}\geqslant p_{2}\geqslant\ldots\geqslant p_{k}$ . The initial allocation of counters $n_{1},n_{2},\ldots,n_{k}$ , with $\sum n_{i}=n$ , is termed a strategy, written $\left<n_{1},n_{2},\ldots,n_{k}\right>$ ; strategies thus comprise compositions in the language of Hankin [7]. Players may be identified with their strategies when this does not cause confusion.

Writing $t_{S}$ for the time at which the final counter is removed under strategy $S$ , and observing that this cannot be less than $n$ , it is convenient to consider the random variable $X_{S}=t_{S}-n$ , taking non-negative integer values, here denoted the number of “excess [die] throws to removal”.

This game is natural and easily specified, and may be played with nothing more than some plastic counters, a piece of paper, and a pair of dice. Applications might include inventory control (for example, allocating slow-selling goods amongst shops with different sales rates) and perhaps allocation of multiple indistinguishable tasks among workers of different efficiencies.

The game is equivalent to a weighted coupon collector’s problem [4], with removing a counter corresponding to collecting a coupon. However, in this paper, the allocation of counters amongst boxes is adjustable by the player at will subject to the overall sum (quota) being fixed. The game reduces to that considered by Myers [11] if each player allocates the same number of counters to each box.

2. The two-box game

Much of the flavour of the general game is visible in the simplest non-trivial case: that of two boxes with probabilities $(p,1-p)$ respectively. Then the probability mass function of $X_{<a,b>}$ , the number of excess throws to removal for the strategy of placing $a$ counters in box 1 and $b$ counters in box 2, is

$\displaystyle\operatorname{Pr}(X_{\left<{a,b}\right>}=r)=$

(1) $\displaystyle\quad p^{a}(1-p)^{b}\left[{a+b+r-1\choose a-1,b+r}(1-p)^{r}+{a+b+% r-1\choose a+r,b-1}p^{r}\right],\ r=0,1,2,\ldots.$

where ${x+y\choose x,y}=\frac{(x+y)!}{x!y!}$ is the choose function. The two terms correspond to the final counter being removed from box 1 or box 2 respectively. Expectations may be calculated by observing that

$\displaystyle\sum_{r=0}^{\infty}r{a+b+r-1\choose a+r,b-1}p^{r}=p\sum_{s=0}^{% \infty}\left(s+1\right)p^{s}{a+b+s\choose a+s+1,b-1}=p\sum_{s=0}^{\infty}{p^{s% }}\frac{\left(s+1\right)!}{s!}\frac{\left(a+b+s\right)!}{\left(a+s+1\right)!% \left(b-1\right)!}=p{a+b\choose a+1,b-1}\sum_{s=0}^{\infty}\frac{\Gamma\left(a% +b+1+s\right)}{\Gamma\left(a+b+1\right)}\frac{\Gamma\left(2+s\right)}{\Gamma% \left(2\right)}\frac{\Gamma\left(a+2\right)}{\Gamma\left(a+2+s\right)}\frac{p^% {s}}{s!}=p{a+b\choose a+1,b-1}{}_{2}F_{1}\left(a+b+1,2;a+2;p\right).$ (2)

Thus the PMF in Eq. (2) has expectation

$\displaystyle\mathbb{E}\left(X_{\left<{a,b}\right>}\right)=p^{a}(1-p)^{b}\left% [(1-p){a+b\choose a-1,b+1}\,{}_{2}F_{1}\left(a+b+1,2;b+2;1-p\right)+\right.% \left.p{a+b\choose a+1,b-1}\,{}_{2}F_{1}\left(a+b+1,2;a+2;p\right)\right]$ (3)

where ${}_{2}F_{1}(a,b;c;z)=\sum_{n=0}^{\infty}\frac{(a)_{n}(b)_{n}}{(c)_{n}}\frac{z^% {n}}{n!}$ is the hypergeometric function [1]. Here $(a)_{n}=a(a+1)\ldots(a+n-1)$ is the rising factorial function. No analytical continuation is needed here because the primary argument does not intersect the function’s branch cut, conventionally defined as the interval $[1,\infty$ .

Figure 1.
Expected number of excess throws as a function of $p$ for different allocations of 9 counters in a two-box game; note log scale.

Figure 2.
The two-box game: optimal strategies in expectation for $n=$ 1(1)9 counters (horizontal axis) as a function of probability of box 1 (vertical axis).

The strategy $a,b>$ which minimizes expected time to removal is

$\operatorname*{arg\,min}_{a,b|a,b\geqslant 0,a+b=n}\mathbb{E}X_{\left<{a,b}% \right>}.$

Conversely, the cut-off point of $p$ , at which strategy $\left<a,b\right>$ yields to strategy $\left<a-1,b+1\right>$ (assuming all integers non-negative) is given by solving the equation $\mathbb{E}X_{\left<{a,b}\right>}=\mathbb{E}X_{\left<{a-1,b+1}\right>}$ which may be solved numerically using the hypergeo package [9]. Figures 1 and 2 show some numerical results.
2.1 Game theoretic analysis

The counter removal process is now considered as a standard two-person zero sum game with payoff $+1$ for a victory – that is, removing all one’s counters before the opponent, $-$ 1 for a loss and 0 for a draw. The situation is complicated by the fact that play stops when either player removes her last counter.

There are two natural interpretations: at each time, the players each randomly choose a box independently from the other players (“separate [dice] throw”); or alternatively, a random box is chosen for all the players simultaneously (a “common throw”). In the separate throw case, it is possible to allow the box probabilities to differ between the players but unless otherwise stated the probabilities will be identical.

Figure 3.

Diagram showing $\left<1,0\right>$ vs $\left<0,1\right>$ game, separate throw game; expected payoff to player I is $\mathbb{V}$ . Here $\mathbb{V}=1\cdot p^{2}+0\cdot p(1-p)+\mathbb{V}\cdot(1-p)p+(-1)\cdot(1-p)^{2}$ , giving $\mathbb{V}=\frac{2p-1}{1-p(1-p)}$ .

Figure 4.

Diagram showing $\left<2,0\right>$ vs $\left<0,1\right>$ game, separate throw game; the $p^{2}$ term is derived in Fig. 3. The expected payoff to $\left<2,0\right>$ is $\frac{p^{2}\cdot\frac{2p-1}{1-p(1-p)}+p(1-p)\cdot(-1)+(1-p)^{2}\cdot(-1)}{1-p(% 1-p)}=\frac{3p^{3}-3p^{2}+2p-1}{(1-p(1-p))^{2}}$ .

2.2 Separate throws

Writing $\mathbb{V}\left(\left<a_{1},b_{1}\right>,\left<a_{2},b_{2}\right>\right)$ for the game-theoretic payoff to a $\left<a_{1},b_{1}\right>$ player versus a $\left<a_{2},b_{2}\right>$ player, Figs 3 and 4 show that $\mathbb{V}\left(\left<1,0\right>,\left<0,1\right>\right)=\frac{2p-1}{p^{2}-p+1}$ and $\mathbb{V}\left(\left<2,0\right>,\left<0,1\right>\right)=\frac{3p^{3}-3p^{2}+2% p-1}{(1-p(1-p))^{2}}$ . The simplest non-trivial case with the players possessing an equal number of counters is $\left<2,0\right>$ versus $\left<1,1\right>$ for which the payoff to the $\left<2,0\right>$ player may be calculated by extending the methodology of Figs 3 and 4. Explicitly, the payoff to the $\left<2,0\right>$ player is given as

$\displaystyle\mathbb{V}\left(\left<2,0\right>,\left<1,1\right>\right)=p^{2}% \mathbb{V}\left(\left<1,0\right>,\left<0,1\right>\right)+p(1-p)\mathbb{V}\left% (\left<1,0\right>,\left<1,0\right>\right)+(1-p)p\mathbb{V}\left(\left<2,0% \right>,\left<0,1\right>\right)+(1-p)^{2}\mathbb{V}\left(\left<2,0\right>,% \left<1,0\right>\right)$ (4)

The first term is given in Fig. 3, the second is clearly zero, the third given in Fig. 4, and the fourth (in a different format) is given in Fig. 5 as $1/(p-2)$ . Combining these gives $\frac{p^{5}-4p^{3}+3p^{2}-2p+1}{p^{5}-4p^{4}+7p^{3}-8p^{2}+5p-2}$ . Thus $\left<2,0\right>$ has a positive expected payoff against $\left<1,1\right>$ if and only if $p$ exceeds the unique real root of the numerator, about 0.643. Figure 6 shows the expected payoff to $\left<2,0\right>$ as a function of $p$ and exhibits an unexpected feature: a nontrivial local minimum near $p=$ 0.225 of about $\mathbb{V}=$ $-$ 0.543. This observation is not useful in the general context of this paper in which a specified number of counters must be allocated, but might be relevant if a player is constrained to play $\left<1,1\right>$ against $\left<2,0\right>$ (and may vary $p$ at will).

Figure 5.

Markov chain for $\left<2,0\right>$ vs $\left<1,0\right>$ ; separate calls. Absorbing states shown in gray. Players I and II have box probabilities $(p,1-p)$ . Using the fact that $\mathbb{V}\left(\left<1,0\right>,\left<1,0\right>\right)=$ 0, it can be shown that the game value is $1/(p-2)$ .

Figure 6.

Expected payoff to a $\left<2,0\right>$ player against a $\left<1,1\right>$ player as a function of (common) box 1 probability; separate calls.

It is possible to relax the requirement that the players’ probabilities are identical, although the algebra becomes complicated quickly. Figure 7 shows the expected payoff to I as a function of the players’ probabilities of choosing the first box. If viewed as a game on the unit square in the sense of Heuer [10], the expected payoff has a saddle point at $p=$ 1, $q=$ 1/2 at which the payoff to I is 0.5.

Figure 7.

Expected payoff to $\left<2,0\right>$ (box probablities $p,1-p$ ) against $\left<1,1\right>$ (box probablities $q,1-q$ ).

2.3 Two boxes, common throw

The case where the throw is common to both players is qualitatively different, see Fig. 8. In the following, we suppose that $a, b, m, n$ are strictly positive integers.

Figure 8.

Two box, common thow game with player I playing $\left<8,3\right>$ and player II playing $\left<4,5\right>$ . A game is represented by a coloured line in the form of a random walk from the origin; axes indicate total number of box 1 and box 2 throws. Line colours show the winner: red for player I winning and blue for player II winning, and line type shows the winning box: solid for winning by box 1 and dotted for winning by box 2. Shaded regions indicate a player clearing both boxes: red for player I and blue for player II.

Suppose player I plays $\left<a+n,b\right>$ and player II plays $\left<a,b+m\right>$ . Then player I may win in one of two ways: the final counter to be removed may be from box 1 (written “winning by box 1”), or from box 2.

The successive throws constitute an iid sequence of 1’s and 2’s. At any time, denote the total number of box 1 throws as $r_{1}$ and number of box 2 throws as $r_{2}$ . Player I wins by box 2 if, when $r_{2}=b$ , we have $r_{1}\geqslant a+n$ , and this occurs with probability $\operatorname{Pr}(r_{1}\geqslant a+n|r_{2}=b)$ , a negative binomial distribution. Similarly, player I wins by box 1 with probability $\operatorname{Pr}(b\leqslant r_{2}<b+m|r_{1}=a+n)$ .

Because the complementary cumulative distribution function of the negative binomial with parameters $r, p$ is given by the regularized incomplete beta function1

This is a standard function defined as $I_{x}(\alpha,\beta)=\frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}% \int_{p=0}^{x}p^{\alpha-1}(1-p)^{\beta-1}\,dp$ . Here it is evaluated using the GSL library [8] or the hypergeo library [9].

I_{p}(k+1,r)

, the probabilities of player I beating player II by box 1 is

1-I_{p}(a+n,b+m)-(1-I_{1-p}(b,a+n))

and by box 2 is

I_{p}(a+n,b)

Thus the total probability of player I winning is $I_{p}(a+n,b+m)$ and, observing that a draw is impossible, the expected payoff to player I is thus $2I_{1-p}(b+m,a+n)-1$ . Note that these probabilities are functions only of the larger number of counters in each of the two boxes.

Table 1

Expected game value for the two-box, five-counter game, $p=0.4$ , common throw. Saddle point at $\left<2,3\right>$

I $\backslash$ II	$\left<0,5\right>$	$\left<1,4\right>$	$\left<2,3\right>$	$\left<3,2\right>$	$\left<4,1\right>$	$\left<5,0\right>$
$\left<0,5\right>$	0.00	$-$ 0.84	$-$ 0.53	$-$ 0.16	0.19	0.47
$\left<1,4\right>$	0.84	0.00	$-$ 0.33	0.09	0.42	0.65
$\left<2,3\right>$	0.53	0.33	0.00	0.37	0.64	0.81
$\left<3,2\right>$	0.16	$-$ 0.09	$-$ 0.37	0.00	0.83	0.92
$\left<4,1\right>$	$-$ 0.19	$-$ 0.42	$-$ 0.64	$-$ 0.83	0.00	0.98
$\left<5,0\right>$	$-$ 0.47	$-$ 0.65	$-$ 0.81	$-$ 0.92	$-$ 0.98	0.00

Figure 9.

All 6 $\times$ 6 $=$ 36 possible games played between two players with five counters each. For each game, the two rectangles represent the allocation of counters by player I (left) and player II (right); green indicates that that box’s counters are “active” in the sense that the number appears in the expression for the payoff to player I, viz $2I_{1-p}(b+m,a+n)-1$ .

Similar considerations apply if player I plays $\left<a,b\right>$ and II plays $\left<a+m,b\right>$ ; now player II cannot win but draws with probability $I_{1-p}(b+m,a)$ (both players removing their final counter from box 2 simultaneously).

For completeness, we observe that $\left<a,b\right>$ certainly beats $\left<a+m,b+n\right>$ , and further that $\left<a,b\right>$ certainly draws against $\left<a,b\right>$ , even if one or both of $a$ and $b$ is zero.

The minimax strategy for the common-call two-category game is pure, except possibly at boundaries. This follows from the facts that: the payoff matrix is antisymmetric (see Fig. 9 and Table 1); each row is decreasing with column number on the left of the diagonal, and increasing to the right (because $I_{p}(a-1,b)>I_{p}(a,b)$ for $a\geqslant 1$ ); and, for any $p\in\left[0,1\right]$ one has $I_{p}(a+1,b)>I_{p}(a,b+1)$ .

Critical points for $p$ are found by solving $I_{p}(r,n+1-r)=1/2$ for $r=$ 0, 1, $\ldots$ , $n$ . For example, the range of $p$ for which $\left<1,4\right>$ is the dominant strategy $(p_{L},p_{U})$ is given by $I_{p_{L}}(4,2)=I_{p_{U}}(5,1)=1/2$ ; numerically this is about (0.686, 0.871).

3. Three boxes

The three box case is now considered, partly motivated by the fact that the space of probabilities is easily visualized on a ternary plot.

The simplest nontrivial case for three boxes is with three counters, in which case there are are 10 strategies, from $<$ 3, 0, 0 $>$ through $<$ 1, 1, 1 $>$ to $<$ 0, 0, 3 $>$ . The optimal strategy for any box probabilities is shown in Fig. 10.

Figure 10.

Triangular plot showing optimal strategies in expectation as a function of the three box probabilities $p_{1},p_{2},p_{3}$ , where $p_{1}+p_{2}+p_{3}\leqslant 1$ . Different coloured regions show the extent of the different strategies.

Figure 11.

Diagram showing mapping used for the ternary diagrams.

It is possible to streamline graphical results by taking advantage of the fact that we may assumet, without loss of generality, that $p_{1}\geqslant p_{2}\geqslant p_{3}$ (Fig. 11). In what follows, we will consider only strategies for which $n_{1}\geqslant\ n_{2}\geqslant n_{3}$ – restricted partitions in the language of Hankin [7] – as strategies not satisfying this constraint may be improved in expectation.2

To see this, consider the general case of $p_{1}\geqslant\ldots\geqslant p_{k}$ and a strategy that violates the constraint, that is, there exist $i, j$ with $1\leqslant i<j\leqslant k$ and $n_{i}<n_{j}$ . Then split the boxes into two sets: $S=\{i,j\}$ and its complement $\overline{S}$ . Then removal of a counter from either set may be embedded into two independent Poisson processes, following [4]. Then consider transferring a counter from box $i$ to box $j$ . The $\overline{S}$ process is unaffected, but the $S$ process has lower expected time to completion. Proof: consider the common throw game with player I playing $\left<a+1,b\right>$ and player II $\left<a,b+1\right>$ ; here $a>b$ and $p>\frac{1}{2}$ . We shall show that player I’s expected throws is strictly less than player II’s. First, define I’s margin of victory $M$ as the number of throws needed for II to clear her counters after I clears her counters ( $M<0$ means she lost; note that $M\neq 0$ ). Then $\mathbb{E}(M)$ may be calculated as $\mathbb{E}(M|M>0)\cdot\operatorname{Pr}(M>0)+\mathbb{E}(M|M<0)\cdot% \operatorname{Pr}(M<0)$ . From Fig. 8, we see that the two conditional distributions are geometric and so $\mathbb{E}(M)=\frac{I_{p}(a+1,b+1)}{1-p}-\frac{1-I_{p}(a+1,b+1)}{p}$ . This is strictly positive because $1-p<\frac{1}{2}<I_{1/2}(a+1,b+1)<I_{p}(a+1,b+1)$ . Thus a player may increase her game value by transferring a counter from box $i$ to box $j$ .

and game value3

Proof: for the common throw case, we observe that $p>\frac{1}{2}$ and $a>b$ imply $I_{p}(a+1,b+1)>\frac{1}{2}$ . For the separate throw case we observe that the existence of $a,m,n>0$ with $p>\frac{1}{2}$ and $\mathbb{V}\left(\left<a+n,a\right>,\left<a,a+m\right>\right)<$ 0 implies that $\exists a^{\prime}<a$ and $m^{\prime},n^{\prime}>$ 0 with $\mathbb{V}\left(\left<a^{\prime}+n^{\prime},a\right>,\left<a^{\prime},a^{% \prime}+m^{\prime}\right>\right)<$ 0. The result follows from the fact thatthat $\mathbb{V}\left(\left<0,0\right>,\left<0,0\right>\right)=$ 0.

3.1 Expectation

The probability mass function for $X_{<n_{1},n_{2},n_{3}>}$ (that is, the time to removal of the final counter, minus $n=n_{1}+n_{2}+n_{3}$ ) is given by

$\displaystyle\operatorname{Pr}(X_{\left<n_{1},n_{2},n_{3}\right>}=r)=\sum_{r_{% 2}+r_{3}=r}{n+r_{2}+r_{3}-1\choose n_{1}-1,n_{2}+r_{2},n_{3}+r_{3}}p_{1}^{n_{1% }}p_{2}^{n_{2}+r_{2}}p_{3}^{n_{3}+r_{3}}+\sum_{r_{1}+r_{3}=r}{n+r_{1}+r_{3}-1% \choose n_{1}+r_{1},n_{2}-1,n_{3}+r_{3}}p_{1}^{n_{1}+r_{1}}p_{2}^{n_{2}}p_{3}^% {n_{3}+r_{3}}+\sum_{r_{1}+r_{2}=r}{n+r_{1}+r_{2}-1\choose n_{1}+n_{1},n_{2}+r_% {2},n_{3}-1}p_{1}^{n_{1}+r_{1}}p_{2}^{n_{2}+r_{2}}p_{3}^{n_{3}}.$ (5)

Here, the three terms correspond to the final counter being removed from boxes 1, 2, 3 respectively; and $r_{i}$ corresponds to the number of “wasted” box $i$ throws (that is, the number of times box $i$ is called when box $i$ is empty). This equation is analytically challenging; the first term is algebraically equal to

$\displaystyle p_{1}^{n_{1}}p_{2}^{n_{3}}p_{3}^{n_{3}}\left[{p_{3}}^{r}{n+r-1% \choose n_{1}-1,n_{2},n_{3}+r}{}_{2}F_{1}\left(1,-n_{3}-r;n_{2}+1;-\frac{p_{2}% }{p_{3}}\right)\right.-$ (6) $\displaystyle\quad\left.{p_{2}}^{r}\frac{p_{2}}{p_{3}}{n+r-1\choose n_{1}-1,n_% {2}+r+1,n_{3}-1}{}_{2}F_{1}\left(1,1-n_{3};n_{2}+r+2;-\frac{p_{2}}{p_{3}}% \right)\right].$

Figure 12.

Triangular plot showing optimal strategy in expectation for allocating 3 counters among 3 boxes, as a function of $p_{1},p_{2},p_{3};p_{1}\geqslant p_{2}\geqslant p_{3}$ . The three points of the triangle correspond to $(1,0,0)$ , $(\frac{1}{2},\frac{1}{2},0)$ , and $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ . The line common to the $<$ 3, 0, 0 $>$ and $<$ 2, 1, 0 $>$ regions is straight, but the line common to $<$ 2, 1, 0 $>$ and $<$ 1, 1, 1 $>$ is not.

Figure 13.

Triangular plot showing optimal strategy in expectation for allocating 7 counters among 3 boxes, as a function of $p_{1},p_{2},p_{3},p_{1}\geqslant p_{2}\geqslant p_{3}$ .

However, because the hypergeometric functions each have an upper argument of a strictly negative integer, the expressions are a polynomial in $p_{2}/p_{3}$ . However, Eq. (3.1) is the preferred form for numerical evaluation [9]. The other terms are analogous, unless one of the $n_{i}=$ 0, in which case that term is omitted. These results may be used to show that the expected times to removal for the three consistent strategies are:

$\displaystyle\mathbb{E}X_{\left<3,0,0\right>}=\frac{3(1-p_{1})}{p_{1}}$ (7) $\displaystyle\mathbb{E}X_{\left<2,1,0\right>}=-3+\frac{1}{p_{2}}+\frac{p_{2}(3% p_{1}+2p_{2})}{p_{1}(p_{1}+p_{2})^{2}}$ (8) $\displaystyle\mathbb{E}X_{\left<1,1,1\right>}=-2+\frac{1}{p_{1}}+\frac{1}{p_{2% }}+\frac{1}{p_{3}}-\frac{1}{1-p_{1}}-\frac{1}{1-p_{2}}-\frac{1}{1-p_{3}}$ (9)

(the first result is more easily determined as the expectation of an inverse binomial distribution with parameters 2 and $p_{1}$ , and the third is a special case of the Coupon Collector’s problem with $n=$ 3 [2]).

To find the boundaries of the regions in which the three strategies are optimal in expectation, solve $\mathbb{E}X_{<3,0,0>}=\mathbb{E}X_{<2,1,0>}$ and $\mathbb{E}X_{<2,1,0>}=\mathbb{E}X_{<1,1,1>}$ . These yield relationships showing that while the boundary of the $<$ 3, 0, 0 $>$ region is linear, the boundary of $<$ 1, 1, 1 $>$ is not; thus not all the regions in Fig. 12 are polygonal, despite appearances.

3.1.1 More than three counters

For the three-box case with an arbitrary number of counters, one natural strategy would be to allocate one’s quota in proportion to $p_{1},p_{2},p_{3}$ (or at least as close as this as possible). However, this is not necessarily optimal in expectation. Consider the game with probabilities (0.7, 0.2, 0.1) and ten counters; one might think strategy $<$ 7, 2, 1 $>$ to be superior to, say, $<$ 9, 1, 0 $>$ . However, numerical methods show that the former strategy has expected time to removal of 6.09 (to 2dp), compared with the latter which has 3.37.

Figure 13 shows a triplot of the best strategy in expectation for distributing seven counters among three boxes over the region $p_{1}>p_{2}>p_{3}$ .

3.2 Game theoretic analysis

For both the common throw game and the separate throw game, natural extensions of the methods of Figs 3 and 4 may be applied. Here the simplest non trivial case, that of three counters, is considered. For the common throw game, Table 2 shows the payoff matrix as a function of the probabilities; but the equivalent calculation for the separate case is algebraically more involved. To illustrate of this, if Table 3 is written in exact, rational form with fractions in their lowest terms, one of the entries has denominator exceeding 5 $\times$ 10 ${}^{27}$ . In the absence of intelligible algebraic formulas, Table 3 shows the payoff matrix for the three counters, three box case, written to three decimal places, for both the common throw and separate throw games. The tables show perhaps unexpected differences; for example, the sign of the payoff to $<$ 3, 0, 0 $>$ when playing against $<$ 2, 1, 0 $>$ changes; also note that the common throw game has a saddle point at $<$ 2, 1, 0 $>$ , the separate throw game at $<$ 3, 0, 0 $>$ .

Table 2
Expected game value for the three-box, three counter common throw game with probabilities $(p_{1},p_{2},p_{3})$

I $\backslash$ II	$<$ 300 $>$	$<$ 210 $>$	$<$ 111 $>$
$<$ 300 $>$	0	$\frac{2p_{1}^{3}}{(1-p_{3})^{3}}-1$	$2p_{1}^{3}\left(\frac{1}{(1-p_{2})^{3}}+\frac{1}{(1-p_{3})^{3}}-1\right)-1$
$<$ 210 $>$	$1-\frac{2p_{1}^{3}}{(1-p_{3})^{3}}$	0	$p_{2}^{2}\left(\frac{2}{(1-p_{2})^{2}}+\frac{1}{(1-p_{3})^{2}}+\frac{p_{2}}{1-% p_{1}}-2\right)-1$
$<$ 111 $>$	$1-2p_{1}^{3}\left(\frac{1}{(1-p_{2})^{3}}+\frac{1}{(1-p_{3})^{3}}-1\right)$	$1-p_{2}^{2}\left(\frac{2}{(1-p_{2})^{2}}+\frac{1}{(1-p_{3})^{2}}\right.$
		$\left.+\frac{p_{2}}{1-p_{1}}-2\right)$	0

Table 3

Expected game value, to three decimal places, for the three-box, three counter game with probabilities $\left(\frac{6}{10},\frac{3}{10},\frac{1}{10}\right)$ . Left, common throw game; right, separate throw game

$\backslash$ II	$<$ 300 $>$	$<$ 210 $>$	$<$ 111 $>$
$<$ 300 $>$	0	$-$ 0.059	$+$ 0.595
$<$ 210 $>$	$+$ 0.059	0	$+$ 0.483
$<$ 111 $>$	$-$ 0.595	$-$ 0.483	0

$\backslash$ II	$<$ 300 $>$	$<$ 210 $>$	$<$ 111 $>$
$<$ 300 $>$	0	$+$ 0.200	$+$ 0.707
$<$ 210 $>$	$-$ 0.200	0	$+$ 0.519
$<$ 111 $>$	$-$ 0.707	$-$ 0.519	0

It is possible to conduct numerical experiments for larger numbers of counters. Figure 14 shows the appropriate strategy for the case with three boxes and seven counters.

Figure 14.

Triangular plot showing regions which are game-theoretic optimal for the 7 counter, 3 box case (separate throws).

Figure 15 illustrates the optimal strategy in a game-theoretic sense for the case of 7 counters and shows that, for some probabilities, the minimax strategy is not pure. Thus if, for example, $(p_{1},p_{2},p_{3})=(\frac{3}{4},\frac{1}{8},\frac{1}{8})$ , a minimax strategy is to play $<$ 7, 0, 0 $>$ with probability 0.156, $<$ 6, 1, 0 $>$ with probability 0.189, and $<$ 5, 1, 1 $>$ with probability 0.655.

Figure 15.

Triangular plot showing regions in which the minimax strategy is pure, marked in eight different colours for the eight different strategies $<$ 7, 0, 0 $>$ through $<$ 3, 2, 2 $>$ . White signifies regions in which the minimax strategy is mixed.

4. The game with an arbitrary number of boxes

The PMF for the exact number of throws required to remove the final counter in the general case is considerably more complicated. We have that $\operatorname{Pr}(X=r)$ is

$\sum_{i=1}^{k}\sum_{\sum_{j}r_{j}=r\atop r_{i}=0}{n+r-1\choose n_{1}+r_{1},% \ldots,n_{i-1}+r_{i-1},n_{i}-1,n_{i+1}+r_{i+1},\ldots,n_{k}+r_{k}}\prod_{s=1}^% {k}p_{s}^{n_{s}+r_{s}}$ (10)

Here the $r_{i}$ are the number of “wasted” throws in box $i$ . The outer summation is over the number of the box whose counter is removed last; the inner summation is over all distributions of $r$ wasted throws among the other boxes.

Table 4

Expected time to removal for the three box, ten-counter game with probabilities $(0.7,0.2,0.1)$ as calculated numerically; figures accurate to 4 decimal places

Strategy	$\mathbb{E}X$
$<$ 10, 0, 0 $>$	4.2840
$<$ 9, 1, 0 $>$	3.3731
$<$ 8, 2, 0 $>$	3.9637
$<$ 8, 1, 1 $>$	5.4261
$<$ 7, 3, 0 $>$	6.3922
$<$ 7, 2, 1 $>$	6.0878
$<$ 6, 4, 0 $>$	10.4550
$<$ 6, 3, 1 $>$	8.6927
$<$ 6, 2, 2 $>$	12.2692
$<$ 5, 5, 0 $>$	15.0561
$<$ 5, 4, 1 $>$	12.2627
$<$ 5, 3, 2 $>$	13.7832
$<$ 4, 4, 2 $>$	16.6344
$<$ 4, 3, 3 $>$	21.8522

The original case [6] was to place 11 counters on boxes corresponding to the total of two independent six-sided dice, that is, with probabilities $\min[i,13-i]/36,i=2,\ldots,12$ . There are 56 ways in which the counters may be arranged if $p_{i}\geqslant p_{j}\rightarrow a_{i}\geqslant a_{j}$ is required. Of these, $<$ 0, 0, 1, 1, 2, 3, 2, 1, 1, 0, 0 $>$ is optimal in expectation and game-theoretic value. There does not seem to be any way of ascertaining this fact other than direct numerical evaluation of all 56 expectations.

A more interesting example would arise from Zipf’s law [14]. If there are 4 boxes then probabilities proportional to $\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4}$ would be indicated; with seven counters, there are 11 distinct strategies from $<$ 7, 0, 0, 0 $>$ through $<$ 2, 2, 2, 1 $>$ .

Expected time to removal is minimized by $<$ 5, 1, 1, 0 $>$ , while the separate throw game has minimax strategy of $<$ 4, 2, 1, 0 $>$ . With a common throw, the minimax strategy is mixed; specifically, play $<$ 4, 1, 1, 1 $>$ with probability 0.26 and $<$ 3, 2, 1, 1 $>$ with probability 0.73.

5. Conclusions and further work

The liability allocation problem described here bears the same relation to Blotto-type resource allocation as chore division does to cake division. The games discussed here do not appear to have been discussed in the literature, even though they are simple to state, and potentially rich in applications. They are unusual in that the simplest non-trivial cases are algebraically involved; numerical methods have to be used for even small numbers of counters and boxes.

Further work might include relaxing the assumption that the box probabilities are common knowledge; perhaps one or both players have to infer the box probabilities from previous calls, as in multi-armed bandit problems [3].

The three-box case shows a variety of results using the triplot device; it would be interesting to understand why the boundary lines are so close to perfect straight lines.

Footnotes

Acknowledgments

The author thanks S. Marshall for valuable discussions; and also A. M. Hankin (“Alice”) for bringing this problem to his attention, making the (then) unintuitive observation that placing all one’s counters on the maximal probability box is suboptimal in expectation and game value.

References

Abramowitz

and Stegun

I.A.

, Handbook of mathematical functions with formulas, graphs and mathematical tables (AMS-55), National Bureau of Standards, 1965.

Berenbrink

and Sauerwald

, Computing and Combinatorics, 15 annual international conference, COCOON 2009, Niagara Falls NY, USA, July 2009, chapter The weighted coupon collector’s problem and applications, Springer, 2009, pp. 449–458.

Berry

D.A.

and Fristedt

, Bandit problems: sequential allocation of experiments, Springer Netherlands, 1985.

Boneh

and Hofri

, The coupon collector problem revisited – a survey of engineering problems and computational methods, Communications in Statistics – Stochastic Models 13(1) (1997), 39–66.

Brams

S.J.

and Taylor

A.D.

, On envy-free cake division, Journal of Combinatorial Theory, Series A 70 (1995), 170–173.

Hankin

A.M.

, Personal communication, 2014.

Hankin

R.K.S.

, Additive integer partitions in R, Journal of Statistical Software, Code Snippets 16(1) (2006).

Hankin

R.K.S.

, Special functions in R: introducing the gsl package, R News 6 (October 2006).

Hankin

R.K.S.

, Hypergeo: the hypergeometric function for complex R package number 1.2–5, URL http://CRAN.R-project.org/package=hypergeo, 2013.

10.

Heuer

G.A.

, Three-part partition games on rectangles, Theoretical Computer Science 259 (2001), 639–661.

11.

Myers

A.N.

and Wilf

H.S.

, Some new aspects of the coupon collector’s problem, SIAM Review 48(3) (2006).

12.

Peterson

and Su

F.E.

, Four-person envy-free chore division, Mathematics Magazine 75(2) (2002), 117–122.

13.

Roberson

, The Colonel Blotto game, Economic Theory 29 (2006), 1–24.

14.

Zipf

G.K.

, The psychology of language, Houghton-Mifflin, 1935.

A liability allocation game

Abstract

Keywords

1. Introduction

2. The two-box game

3.2 Game theoretic analysis

Table 2 Expected game value for the three-box, three counter common throw game with probabilities ( p 1 , p 2 , p 3 )

Footnotes

Acknowledgments

References

Table 2
Expected game value for the three-box, three counter common throw game with probabilities $(p_{1},p_{2},p_{3})$