The speed of convergence in greedy Galois games

2026/04/30 by Jeffrey Shallit · 1 voice
Computer Science · Mathematics · #cs.DM #cs.FL #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.2605.00194

Abstract

In 2013 Cooper and Dutle invented a dueling scenario where Alice and Bob shoot at each other until one is hit. Each shot is successful with some fixed probability p, 0 < p < 1. The shooting order is given by a greedy algorithm, where at each step a shot is assigned to the player whose current probability of success is smaller. Cooper and Dutle observed that as p → 0, the resulting sequence of shots (by Alice or Bob) converges to the infinite Thue-Morse sequence t, but left the speed of convergence as an open problem. In this note we determine the speed of this convergence.

Citations

• TOURNAMENTS, FAIRNESS AND THE PROUHET‐THUE‐MORSE SEQUENCE
• Greedy Galois Games
• Greedy Galois Games
• Rowing and the same-sum problem have their moments

Discussions

• Jeffrey Shallit: The speed of convergence in greedy Galois games https://arxiv.org/abs/2605.00194 https://arxiv.org/pdf/2605.00194 https://arxiv.org/html/2605.00194 [bsky, 0 points, 0 comments]

Related

• Greedy Galois Games
• Greedy Galois Games
• From First-Order to Second-Order Rationality: Advancing Game Convergence with Dynamic Weighted Fictitious Play
• Games played by Exponential Weights Algorithms
• On the Exponential Rate of Convergence of Fictitious Play in Potential Games