In tug-of-war, two players compete by moving a counter along edges of a graph, each winning the right to move at a given turn according to the flip of a possibly biased coin. The game ends when the counter reaches the boundary, a fixed subset of the vertices, at which point one player pays the other an amount determined by the boundary vertex. Economists and mathematicians have independently studied tug-of-war for many years, focussing respectively on resource-allocation forms of the game, in which players iteratively spend precious budgets in an effort to influence the bias of the coins that determine the turn victors; and on PDE arising in fine mesh limits of the constant-bias game in a Euclidean setting. In this article, we offer a mathematical treatment of a class of tug-of-war games with allocated budgets: each player is initially given a fixed budget which she draws on throughout the game to offer a stake at the start of each turn, and her probability of winning the turn is the ratio of her stake and the sum of the two stakes. We consider the game played on a tree, with boundary being the set of leaves, and the payment function being the indicator of a single distinguished leaf. We find the game value and the essentially unique Nash equilibrium of a leisurely version of the game, in which the move at any given turn is cancelled with constant probability after stakes have been placed. We show that the ratio of the players' remaining budgets is maintained at its initial value $\lambda$; game value is a biased infinity harmonic function; and the proportion of remaining budget that players stake at a given turn is given in terms of the spatial gradient and the $\lambda$-derivative of game value. We also indicate examples in which the solution takes a different form in the non-leisurely game.
翻译:在拔河游戏中,两个玩家通过沿着图的边移动计数器竞争,每个玩家根据可能偏倚的硬币正反面赢得移动的权利。当计数器到达边界时,即一组固定的顶点时,游戏结束,此时一方向另一方支付一个由固定叶子指定的金额。多年来,经济学家和数学家分别研究了拔河游戏,分别关注资源分配形式的游戏和在欧几里得设置中常数偏差游戏的细网极限中涉及的PDE。在本文中,我们提供了一个分配了预算的拔河游戏类的数学处理:每个玩家最初都有一个固定的预算,她在整个游戏中从中撤资,以努力影响确定胜利方的硬币偏差。我们考虑在树上进行的游戏,边界为叶子的集合,支付功能为单个指定叶子的指标。我们找到了游戏值和游戏的本质唯一纳什平衡的缓慢版本,其中给定回合的移动在放置赌注后以恒定概率被取消。我们证明了玩家剩余预算比例保持在其初始值$\lambda$,游戏值是有偏无限调和函数;玩家在给定回合下注的剩余预算比例以空间梯度和游戏值的$\lambda$-导数表示。我们也提供了在非缓慢游戏中解决方案采用不同形式的示例。