论文标题
无限全付竞标游戏
Infinite-Duration All-Pay Bidding Games
论文作者
论文摘要
在两个玩家的零和图游戏中，玩家在整个图中移动一个令牌，以产生无限的路径，这决定了游戏的获胜者或回报。传统上，玩家交替扭转转移令牌。但是，在{\ em Bidding Games}中，玩家都有预算，在每个回合中，我们都举行“拍卖”（竞标）来确定哪个球员移动令牌：两个球员都同时提交出价，而高价竞标者则可以移动令牌。投标机制的付款计划有所不同。竞标游戏的研究很大程度上是研究了{\ em优先价值}竞标的变体，其中只有更高的竞标者才能支付他的出价。我们专注于{\ em all-Pay}竞标，两位球员都支付了他们的投标。研究了有限的全付竞标游戏，并且在技术上比其第一名的竞标更具挑战性。我们首次学习无限持续的全付竞标游戏。我们最有趣的结果是针对{\ em Mean-payoff}目标：我们描绘了在强烈连接图上玩的游戏的完整图片。我们研究纯净（确定性）和混合（概率）策略，并完全表征玩家可以分别可以保证的最佳确保和几乎是差不多的（概率$ 1 $）的收益。我们表明，在全付竞标下的平均付款游戏展示了其首位同行的有趣数学属性。也就是说，与{\ em随机转变游戏}的等效性在每个转弯中，移动的玩家根据（偏见）硬币折腾选择。与先价竞标相比，全付竞标的等效性更复杂和出乎意料。
In a two-player zero-sum graph game the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In {\em bidding games}, however, the players have budgets, and in each turn, we hold an "auction" (bidding) to determine which player moves the token: both players simultaneously submit bids and the higher bidder moves the token. The bidding mechanisms differ in their payment schemes. Bidding games were largely studied with variants of {\em first-price} bidding in which only the higher bidder pays his bid. We focus on {\em all-pay} bidding, where both players pay their bids. Finite-duration all-pay bidding games were studied and shown to be technically more challenging than their first-price counterparts. We study for the first time, infinite-duration all-pay bidding games. Our most interesting results are for {\em mean-payoff} objectives: we portray a complete picture for games played on strongly-connected graphs. We study both pure (deterministic) and mixed (probabilistic) strategies and completely characterize the optimal sure and almost-sure (with probability $1$) payoffs that the players can respectively guarantee. We show that mean-payoff games under all-pay bidding exhibit the intriguing mathematical properties of their first-price counterparts; namely, an equivalence with {\em random-turn games} in which in each turn, the player who moves is selected according to a (biased) coin toss. The equivalences for all-pay bidding are more intricate and unexpected than for first-price bidding.
