Bounded discrepancies between tie-breaking conventions

Claim. For every nonempty finite subtraction set $S\subseteq\mathbb N$, every heap size $h\geq 0$, every pair of deterministic tie-breaking conventions, and either player $i$, the corresponding self-interest equilibrium utilities satisfy

$$\left|u_i^{\tau}(h)-u_i^{\tau'}(h)\right| \leq \left\lfloor\frac{3\max S-2}{2}\right\rfloor. \tag{1}$$

In particular, the discrepancies are bounded independently of the heap size. This proves Conjecture 17 of Anjali Bhagat, Tanmay Kulkarni, Urban Larsson, and Divya Murali, Tie-breaking in self interest cumulative subtraction games, arXiv:2510.24280v2, and also gives an explicit linear upper bound for the immediately following Problem 1.

The finite-subtraction-set assumption is the setting in which the source poses its quantitative questions: Problems 1–3 use $\max S$, and its experimental subtraction sets are finite. No assertion is made here about unbounded infinite subtraction sets.

Write

$$M=\max S. \tag{2}$$

Each move removes some $s\in S$ from the common heap, with $s$ credited to the mover. The game stops when the remaining heap admits no legal subtraction. Thus, if its final utilities are $a$ and $b$, then

$$a\geq 0, \qquad b\geq 0, \qquad a+b\leq h. \tag{3}$$

The possible strict inequality accounts for pebbles left in a terminal heap.

Step 1: A security guarantee for the second player. Consider any heap of size $x$, and suppose $K\geq\min S$ bounds every subtraction that can occur now or anywhere in the continuation. The second player uses the following strategy: whenever the first player removes $s$, respond by removing the same $s$ if that response is legal.

Suppose the strategy first fails when the heap size immediately before the first player's move is $R$. Every preceding pair of moves removed equal amounts, so each player has already collected

$$\frac{x-R}{2}. \tag{4}$$

The first player now removes $s\leq K$. Failure of the matching response means that the remaining heap is smaller than $s$, and therefore

$$R-s<s, \qquad R\leq 2s-1\leq 2K-1. \tag{5}$$

Whatever happens afterwards can only increase the second player's accumulated utility. Consequently, that player can guarantee at least

$$\left\lceil\frac{x-2K+1}{2}\right\rceil. \tag{6}$$

If the game ends immediately after a completed matching pair, its remaining heap is smaller than the smallest legal subtraction and hence is at most $K-1$. The same bound follows. The bound is also valid when the initial heap itself has no legal move, provided $K\geq\min S$, as in both applications below: its right-hand side is then nonpositive.

Applying (6) to the original game gives the second player's security level

$$L_2(h) = \left\lceil\frac{h-2M+1}{2}\right\rceil. \tag{7}$$

Step 2: A stronger security guarantee for the first player. Suppose first that the initial heap has a legal move, and let

$$s=\max\bigl(S\cap\{1,\ldots,h\}\bigr). \tag{8}$$

The first player removes $s$ immediately. Every subtraction that can occur anywhere in the remaining game is at most $s$: a larger subtraction would already have been legal at the original heap, contradicting the definition of $s$.

In the residual heap of size $h-s$, the original first player now has the role of second player. Applying (6) with $x=h-s$ and $K=s$, while retaining the already collected $s$, gives the security guarantee

$$\begin{aligned} s+\left\lceil\frac{h-s-2s+1}{2}\right\rceil &= \left\lceil\frac{h-s+1}{2}\right\rceil \\ &\geq \left\lceil\frac{h-M+1}{2}\right\rceil. \end{aligned} \tag{9}$$

Accordingly, set

$$L_1(h) = \left\lceil\frac{h-M+1}{2}\right\rceil. \tag{10}$$

If the initial heap has no legal move, then $h<\min S\leq M$, so both utilities are zero and both proposed lower bounds $L_1(h)$ and $L_2(h)$ are nonpositive. Hence (7) and (10) apply in this case as well.

Step 3: Security guarantees apply to every tie-breaking equilibrium. A pure subgame-perfect equilibrium is, in particular, a Nash equilibrium of the underlying extensive-form game. Consequently, neither player can earn strictly more by unilaterally replacing their equilibrium strategy with any other legal strategy against the other player's fixed equilibrium strategy.

The deterministic conventions in the source only choose among actions yielding the same personal continuation utility. They do not remove actions or permit a player to select a strictly inferior personal continuation. Therefore, the selected profile remains a Nash equilibrium for the original personal utilities.

The copying strategy used in Steps 1–2 may depend on the preceding move and need not itself be a Markovian tie-breaking convention. This is harmless: it is used only as a legal unilateral security strategy in the underlying game, not as a proposed equilibrium convention.

Hence every selected equilibrium outcome $(a,b)$ satisfies

$$a\geq L_1(h), \qquad b\geq L_2(h). \tag{11}$$

Together with (3), this gives the role-specific intervals

$$\begin{aligned} L_1(h)&\leq a\leq h-L_2(h),\\ L_2(h)&\leq b\leq h-L_1(h). \end{aligned} \tag{12}$$

These intervals are independent of the tie-breaking conventions.

Step 4: Compare any two conventions. Let $(a,b)$ and $(a',b')$ be the equilibrium outcomes for any two convention profiles at the same initial heap. Equation (12) implies

$$\max\bigl\{|a-a'|,|b-b'|\bigr\} \leq h-L_1(h)-L_2(h). \tag{13}$$

Finally, the elementary inequality $\lceil x\rceil+\lceil y\rceil\geq\lceil x+y\rceil$ yields

$$\begin{aligned} L_1(h)+L_2(h) &\geq \left\lceil \frac{h-M+1}{2}+\frac{h-2M+1}{2} \right\rceil \\ &= h- \left\lfloor\frac{3M-2}{2}\right\rfloor. \end{aligned} \tag{14}$$

Substitution into (13) proves (1). Thus, for every fixed nonempty finite $S$, the discrepancy is uniformly bounded over all heaps, all deterministic tie-breaking profiles, and both players. In fact, the same argument applies to every Nash equilibrium, since only unilateral security and conservation of the heap were used.