Optimal Online Bookmaking for Any Number of Outcomes
Hadar Tal, Oron Sabag · 2025
Read Optimal Online Bookmaking for Any Number of Outcomes by Hadar Tal, Oron Sabag (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16253.txt.
Introduction
Hadar Tal and Oron Sabag solve the online bookmaking problem for events with any number of outcomes. A bookmaker updates odds round by round as gamblers bet, trying to profit while limiting worst-case loss. They work in a worst-case setting over all gambler behaviors and outcome realizations.
The bookmaker's optimal loss turns out to be the largest root of a simple polynomial. Curiously, the analysis connects the bookmaker's regret to Hermite polynomials. Their efficient algorithm achieves the optimal loss against an optimal gambler and exploits suboptimal play when it occurs. The key tool is an explicit characterization of the Bellman-Pareto frontier from dynamic programming and multi-criteria optimization.
Catalog record
| CREATOR | Hadar Tal, Oron Sabag |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 140 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16253
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Online Bookmaking for Any Number of Outcomes Hadar Tal, Oron Sabag Abstract We study the Online Bookmaking problem, where a bookmaker dynamically updates betting odds on the possible outcomes of an event. In each betting round, the bookmaker can adjust the odds based on the cumulative betting behavior of gamblers, aiming to maximize profit while mitigating potential loss. We show that for any event and any number of betting rounds, in a worst-case setting over all possible gamblers and outcome realizations, the bookmaker’s optimal loss is the largest root of a simple polynomial. Our solution shows that bookmakers can be as fair as desired while avoiding financial risk, and the explicit characterization reveals an intriguing relation between the bookmaker’s regret and Hermite polynomials. We develop an efficient algorithm that computes the optimal bookmaking strategy: when facing an optimal gambler, the algorithm achieves the optimal loss, and in rounds where the gambler is suboptimal, it reduces the achieved loss to the optimal opportunistic loss, a notion that is related to subgame perfect Nash equilibrium. The key technical contribution to achieve these results is an explicit characterization of the Bellman-Pareto frontier , which unifies the dynamic programming updates for Bellman’s value function with the multi-criteria optimization framework of the Pareto frontier in the context of vector repeated games. \coltauthor and School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel \SetCommentSty mycommfont keywords Online decision making, regret analysis, game theory 1 Introduction The online betting industry, particularly in the realm of sports betting, has experienced remarkable growth in recent years ( Zion Market Research 2024 ) . Central to this market is the role of bookmakers, who set odds for uncertain events and accept wagers, while managing their exposure to risk. In online bookmaking, odds are dynamically adjusted based on incoming bets and evolving information, making it an intricate algorithmic task. The challenge is to dynamically calibrate the odds such that the bookmaker guarantees a profit regardless of the event’s outcome. In real-world settings, betting markets exhibit a wide range in the number of possible outcomes K . For instance, in a National Football League (NFL) game, K=2 , as gamblers can bet on either of the two competing teams, while the Eurovision Song Contest presents about K=40 possible outcomes, each indicating a possible winner of the contest. As K increases, the bookmaker faces greater uncertainty and must balance risk across a broader set of outcomes. We consider online bookmaking as a sequential game between a bookmaker and a gambler ( Bhatt et al. 2025 ) , noting that the behavior of multiple gamblers can be unified as a single gambler from the bookmaker’s perspective. The game unfolds over a horizon T and involves an event with K possible outcomes, where exactly one outcome k\in[K] materializes. At time t , the bookmaker assigns the odds \gamma_{t}(k) for each possible outcome k , and the gambler distributes a betting unit as a probability vector q_{t} , where q_{t}(k) is the bet placed on outcome k . Following T rounds of this procedure, the event’s outcome is disclosed. If k is indeed the outcome of the event, the gambler receives a payout of \gamma_{t}(k)\cdot q_{t}(k) , and otherwise the gambler loses their placed bet q_{t}(k) . The bookmaker’s fairness is often measured using the overround parameter, also known as the bookmaker margin or vigorish ( Cortis 2015 ) , \Gamma=\sum_{k\in[K]}\frac{1}{\gamma_{t}(k)}, (1) assumed here to be time-independent. The bookmaker’s odds are considered fair when \Gamma=1 , but in practice, \Gamma>1 . For instance, in UK football betting, the overround typically 1 1 1 According to Football-Data.co.uk remains below 1.1 for K=2 markets. As the number of possible outcomes K increases, the overround also tends to rise: reaching \Gamma\approx 1.15 for K=3 markets (e.g., football match winner), and potentially up to 1.6 for K=24 markets (e.g., final score predictions). The overround also serves to define the bookmaker’s offered odds as a probability vector r_{t}(k)=\frac{1}{\Gamma\gamma_{t}(k)} . In each round, the bookmaker collects a betting unit from the gambler, resulting in a total of T units collected over the game. The return to the gambler upon collecting the bets q_{1},\dots,q_{T} is \frac{1}{\Gamma}\sum_{k=1}^{K}\mathds{1}\{I=k\}\sum_{t=1}^{T}\frac{q_{t}(k)}{r_{t}(k)}, where \mathds{1}\{I=k\} is the indicator function of the materialized outcome. In this paper, we consider the bookmaker’s worst-case scenario: (i) the gambler aims to maximize the bookmaker’s loss, and (ii) the event’s outcome results in the largest possible return. The optimal bookmaking loss is then defined as L^{\star}_{{T},{K}}=\inf_{r_{1},\ldots r_{T}}\;\max_{q_{1},\ldots,q_{T}}\;\max_{k\in\left[K\right]}\;\sum_{t=1}^{T}\frac{{q}_{t}(k)}{{r}_{t}(k)}, (2) where r_{t},q_{t} depend on past offered bets and wagers (formally defined in 2.2 ). Note that the overround is omitted from ( 2 ), but the optimal loss still directly characterizes the fundamental limits of the overround. In particular, after collecting T money units and paying the worst-case loss to the gambler, the bookmaker is left with T-\frac{1}{\Gamma}L^{\star}_{{T},{K}} money units. Thus, to guarantee a positive gain, the bookmaker must choose the overround to be \Gamma>\frac{L^{\star}_{{T},{K}}}{T} . We will show the convergence of \frac{L^{\star}_{{T},{K}}}{T} to 1 as T grows for all K . This implies that, even when facing events with many possible outcomes, bookmakers can choose the overround to be arbitrarily close to 1 , given a sufficiently large T . The online bookmaking problem is a repeated zero-sum game falling under the broader framework of game theory pioneered by Von Neumann’s Minimax Theorem ( v. Neumann 1928 ) . Blackwell’s approachability theorem ( Blackwell 1956 ) and Hannan’s no-regret algorithm for competing with the best fixed action ( Hannan 1957 ) gave rise to online learning algorithms with provable regret bounds. Unlike the classical experts problem ( Cover 1965 ; Vovk 1990 ; Littlestone and Warmuth 1994 ) where the optimal adversarial strategy for more than 4 experts is unknown ( Gravin et al. 2016 ) , our setting benefits from a fully characterized optimal adversarial strategy ( Bhatt et al. 2025 , detailed below) . Sequential prediction and adversarial decision-making are central to online learning, and incorporate concepts such as potential-based strategies ( Cesa-Bianchi and Lugosi 2003 ) and approachability ( Abernethy et al. 2011 ) . These settings have also been examined from an information-theoretic perspective ( Merhav and Feder 2002 ; Shtar’kov 1987 ) , where the minimax log-loss plays a key role, corresponding to the optimal code length in lossless compression ( Cesa-Bianchi and Lugosi 2006 , Ch. 9) . The optimal bookmaking loss in ( 2 ) is difficult to compute for several reasons. First, the bookmaker’s strategy is a sequence of mappings that depend on the entire history of placed bets, resulting in a domain that grows exponentially with time. Second, the event’s outcome becomes apparent only after the final betting round. In particular, the maximization over k implies that the bookmaker does not know the true objective function during the game, turning it into a vector-valued game in which the bookmaker must balance the losses across outcomes throughout the betting process. Lastly, each possible objective function is unbounded and non-Lipschitz. While many online learning problems can be cast as instances of online convex optimization (OCO) ( Hazan 2016 , see) , the regret analyses in OCO hinge on losses being bounded and Lipschitz. In our