ℜ \mathfrak{R} obin Hood Reachability Bidding Games Full Version

Shaull Almagor, Guy Avni, Neta Dafni · 2024

Read ℜ \mathfrak{R} obin Hood Reachability Bidding Games Full Version by Shaull Almagor, Guy Avni, Neta Dafni (2024) 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-2412-17718.txt.

Introduction

Shaull Almagor, Guy Avni, and Neta Dafni present a 2024 paper on a new kind of bidding game played on a graph. Two players move a token along the graph's edges. At each step they bid from their budgets for the right to move it, and the winner pays the loser.

In this variant, named for Robin Hood, the richer player first pays the poorer a fixed share of the wealth gap at each step. A regulator thus keeps wealth from piling up. The authors show the core trait of bidding games survives: a threshold rule still decides who wins. They also show the threshold can be found with a mixed whole number program, though the games are not always settled.

Catalog record

CREATORShaull Almagor, Guy Avni, Neta Dafni
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17718

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ℜ \mathfrak{R} obin Hood Reachability Bidding Games Full Version Shaull Almagor, Guy Avni, Neta Dafni Abstract . Two-player graph games are a fundamental model for reasoning about the interaction of agents. These games are played between two players who move a token along a graph. In bidding games, the players have some monetary budget, and at each step they bid for the privilege of moving the token. Typically, the winner of the bid either pays the loser or the bank, or a combination thereof. We introduce Robin Hood bidding games, where at the beginning of every step the richer player pays the poorer a fixed fraction of the difference of their wealth. After the bid, the winner pays the loser. Intuitively, this captures the setting where a regulating entity prevents the accumulation of wealth to some degree. We show that the central property of bidding games, namely the existence of a threshold function, is retained in Robin Hood bidding games. We show that finding the threshold can be formulated as a Mixed-Integer Linear Program. Surprisingly, we show that the games are not always determined exactly at the threshold, unlike their standard counterpart. A. El Fallah Seghrouchni, Y. Vorobeychik, S. Das, A. Nowe (eds.) Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA 1. Introduction A reachability game is a 2-player game played on a graph, by placing a token on one of the vertices and moving it along the edges according to some predefined rules, where the goal of Player 1 (denoted 🚺 1 ) is to reach a set of target vertices, and the goal of Player 2 (denoted 🚹 2 ) is to prevent that. Reachability games are fundamental in automated synthesis of systems ( Pnueli and Rosner, 1989 ) , where a system plays against an environment (e.g., controller synthesis ( Girard, 2012 ) , robotic planning ( Fainekos et al., 2006 ) , network routing ( Brihaye et al., 2019 ) , etc.). In bidding games ( Lazarus et al., 1996 ; Lazarus et al., 1999 ; Avni et al., 2019 ; Avni and Henzinger, 2020 ) , each player has a budget (a real value in [0,1] , where the sum of the budgets is assumed to be normalized to 1 ) at any given moment, and the movement of the token in each step is determined by an auction , resulting in the higher bidder moving the token. We focus on Richman games ( Lazarus et al., 1996 ) , where the winner of the auction pays their bid to the loser (see e.g., ( Avni et al., 2021 ) for other bidding mechanisms). Bidding games are useful for modelling settings where agents compete for some resource (e.g., money, computational resources, etc.) and use these resources to direct the interaction. A common phenomenon in bidding games is that if one of the players accumulates a high-enough portion of the budget, that player can force the game to reach any desired location. In loose terms, “the rich can do whatever they want”. In some settings this phenomenon is desirable, e.g., when modelling the interaction between an attacker and defender of a security system, and the budget is computational resources – nothing prevents either party from hogging resources in order to win. In many other settings, however, the players operate under some regulating entity (e.g., a scheduler in an operating system, or monetary regulation), which prevents the accumulation of excessive wealth in order to achieve some fairness, or to inspire active participation in the game. A standard means to regulate wealth is to redistribute some of the wealth of the rich to the poor, à la Robin Hood’s steal from the rich and give to the poor ( Poddar et al., 2012 ; Franko et al., 2013 ) . Note that this is not the same as taxation in that in standard taxation it is not at all clear that taxes go to the poor, nor is it the case that the poor are not taxed. In this work, we introduce a variant of bidding games called Robin Hood bidding games which incorporates wealth regulations. In a Robin Hood bidding game, each auction is preceded by a wealth redistribution phase: the richer player pays the poorer player a constant fraction (denoted \lambda ) of the difference between their budgets. The classical model of bidding games then corresponds to \lambda=0 . We only consider 0\leq\lambda<\frac{1}{2} , as \lambda\geq\frac{1}{2} would mean that the richer player becomes the poorer (or equal, for \lambda=\frac{1}{2} ), which is of little motivation. Example 1.1. Consider the game depicted in Figure 1 , starting in v_{\mathrm{left}} , where the target for 🚺 1 is v_{1} . The wealth redistribution factor is \lambda=\frac{1}{8} . v_{\mathrm{left}} v_{2} v_{\mathrm{right}} v_{1} Figure 1 . A Robin Hood game. The target for 🚺 1 is v_{1} . Figure 2 . Threshold of v_{\textrm{left}} in Figure 1 as a function of \lambda . Observe that 🚺 1 wins if the play reaches v_{1} , and loses if it reaches v_{2} or oscillates indefinitely between v_{\mathrm{left}} and v_{\mathrm{right}} . Recall that we assume the sum of budgets of the players is 1 . As we show in Section 3 , 🚺 1 needs a starting budget of at least 0.7 in order to win. We demonstrate why 🚺 1 loses when starting with 0.6 . At a glance, the optimal strategies for the players induce the play in Figure 3 . Starting with budgets \left(\begin{smallmatrix}0.6\\ 0.4\end{smallmatrix}\right) , the first step is to apply wealth redistribution (WR, for short). Since \lambda=\frac{1}{8} and 0.6-0.4=0.2 , then 🚺 1 pays 0.025 , so the new budgets are \left(\begin{smallmatrix}0.575\\ 0.425\end{smallmatrix}\right) . Note that if 🚺 1 loses the bidding at v_{\mathrm{left}} , she loses the game. Therefore, she must bid at least 0.425 (we use the common assumption that ties are broken in favor of 🚺 1 ). Fortunately, she has sufficient budget for this bid. She moves the token to v_{\mathrm{right}} and the new budgets are \left(\begin{smallmatrix}0.15\\ 0.85\end{smallmatrix}\right) (see (1) in Figure 3 ). Next, WR is applied (with 🚹 2 paying). In v_{\mathrm{right}} 🚹 2 must win the bidding, or he loses the game. To do so, he must bid strictly more than 🚺 1 . He bids 0.2375+0.001=0.2385 , wins the bid and moves the token to v_{\mathrm{left}} (see (2)). Then, WR leaves 🚹 2 as the richer, and he wins the game (3) by out-bidding 🚺 1 and moving to v_{2} . \underbrace{\left(\begin{smallmatrix}0.6\\ 0.4\end{smallmatrix}\right)}_{v_{\mathrm{left}}}\overset{\text{WR}}{\longrightarrow}\underbrace{\left(\begin{smallmatrix}0.575\\ 0.425\end{smallmatrix}\right)}_{v_{\mathrm{left}}}\overset{(1)}{\longrightarrow}\underbrace{\left(\begin{smallmatrix}0.15\\ 0.85\end{smallmatrix}\right)}_{v_{\mathrm{right}}}\overset{\text{WR}}{\longrightarrow}\underbrace{\left(\begin{smallmatrix}0.2375\\ 0.7625\end{smallmatrix}\right)}_{v_{\mathrm{right}}}\overset{(2)}{\longrightarrow}\underbrace{\left(\begin{smallmatrix}0.476\\ 0.524\end{smallmatrix}\right)}_{v_{\mathrm{left}}}\overset{\text{WR}}{\longrightarrow}\underbrace{\left(\begin{smallmatrix}0.4805\\ 0.5195\end{smallmatrix}\right)}_{v_{\mathrm{left}}}\overset{(3)}{\longrightarrow}v_{2} Figure 3. A losing play for 🚺 1 . The central question in the study of bidding games is the existence of a threshold function for the game: a function that assigns for each vertex v a value \mathsf{Th}(v) , such that if 🚺 1 starts with budget more than \mathsf{Th}(v) then she wins, and if she starts with less than \mathsf{Th}(v) , she loses. It is shown in ( Avni et al., 2021 ) that every reachability bidding game has a threshold, and finding its value is in \mathrm{NP}\cap\mathrm{coNP} . We extend the known results regarding

Read the complete text