论文标题
计算离散竞标游戏中的阈值预算
Computing Threshold Budgets in Discrete-Bidding Games
论文作者
论文摘要
在两个玩家的零和图形游戏中，玩家在整个图中移动一个令牌，以制作无限的游戏，这决定了游戏的获胜者。投标游戏是图形游戏，在每个回合中，拍卖（投标）决定了哪个玩家移动令牌：玩家有预算，并且在每个回合中，两个玩家同时提交出价，这些投标率不超过其可用的预算，较高的投标人会移动令牌，并向低价竞标者付费（称为Richman bidman bidman bidding）。我们专注于离散的游戏游戏，在这种游戏中，在实际应用中，限制了玩家出价的粒度，例如，必须以美分给出投标。 投标游戏的中心数量是门槛预算：赢得游戏的必要和足够的初始预算。以前，阈值被证明存在于平等游戏中，但它们的结构仅在可及性游戏中被理解。此外，以前已知的算法具有达到达到目标和奇偶元目标的最糟糕的指数运行时间，以及使用指数内存的输出策略。我们描述了两种算法，用于在平等离散游戏中查找阈值预算。第一个是定点算法。它首次揭示了平等离散游戏中阈值预算的结构。基于这种结构，我们开发了第二种算法，该算法表明，找到阈值预算的问题是NP和企图，以达到可达性和奇偶性目标。此外，我们的算法构建了仅使用线性内存的策略。 这是最初于2025年1月22日发布的论文（Arxiv：2210.02773V4）的校正版本。
In a two-player zero-sum graph game, the players move a token throughout a graph to produce an infinite play, which determines the winner of the game. Bidding games are graph games in which in each turn, an auction (bidding) determines which player moves the token: the players have budgets, and in each turn, both players simultaneously submit bids that do not exceed their available budgets, the higher bidder moves the token, and pays the bid to the lower bidder (called Richman bidding). We focus on discrete-bidding games, in which, motivated by practical applications, the granularity of the players' bids is restricted, e.g., bids must be given in cents. A central quantity in bidding games is threshold budgets: a necessary and sufficient initial budget for winning the game. Previously, thresholds were shown to exist in parity games, but their structure was only understood for reachability games. Moreover, the previously-known algorithms have a worst-case exponential running time for both reachability and parity objectives, and output strategies that use exponential memory. We describe two algorithms for finding threshold budgets in parity discrete-bidding games. The first is a fixed-point algorithm. It reveals, for the first time, the structure of threshold budgets in parity discrete-bidding games. Based on this structure, we develop a second algorithm that shows that the problem of finding threshold budgets is in NP and coNP for both reachability and parity objectives. Moreover, our algorithm constructs strategies that use only linear memory. This is a corrected version of the paper (arXiv:2210.02773v4) published originally on Jan 22, 2025.
