论文标题
通过随机玩最佳地达到目标
Reaching Your Goal Optimally by Playing at Random
论文作者
论文摘要
最短的路径游戏是在配备整数重量的图表上玩的两人零和游戏。一个我们称为最小的球员想达到目标状态，同时最大程度地减少总重量，而另一个则具有对立目标。定性可及性目标和定量总计目标的这种组合是最简单的设置之一，其中最小需求记忆（重量中的伪多项式）可以最佳地发挥作用。在本文中，我们旨在研究一个权衡，允许最小的人随机玩，但没有记忆。我们表明，在两种情况下，最小值都可以达到相同的最佳价值。特别是，我们计算出一个随机的无内存$ \ varepsilon $ - 最佳策略，其中概率是由$ \ varepsilon $参数参数的。然后，我们表征并在多项式时间内确定游戏类别的游戏类别，即最佳的随机无内存策略。
Shortest-path games are two-player zero-sum games played on a graph equipped with integer weights. One player, that we call Min, wants to reach a target set of states while minimising the total weight, and the other one has an antagonistic objective. This combination of a qualitative reachability objective and a quantitative total-payoff objective is one of the simplest setting where Min needs memory (pseudo-polynomial in the weights) to play optimally. In this article, we aim at studying a tradeoff allowing Min to play at random, but using no memory. We show that Min can achieve the same optimal value in both cases. In particular, we compute a randomised memoryless $\varepsilon$-optimal strategy when it exists, where probabilities are parametrised by $\varepsilon$. We then characterise, and decide in polynomial time, the class of games admitting an optimal randomised memoryless strategy.
