论文标题
最困难重复协调游戏的最佳协议
Optimal protocols for the most difficult repeated coordination games
论文作者
论文摘要
本文调查了重复的获胜协调游戏（WLC游戏）。我们分析了哪些协议对于这些游戏是最佳的，涵盖了最坏情况和平均情况，即i，e。，优化了保证和预期的协调时间。我们首先分析选择匹配游戏（CM游戏），这是WLC游戏的简单但基本类型的类型，在其中，玩家的目标是从有限的一组最初无法区分的选择中选择相同的选择。我们在两人CM游戏中对最佳预期和保证协调时间进行完整的分类，并表明相应的最佳协议在每种情况下都是唯一的 - 除了在具有四个选择的CM游戏中，我们将分别分析。 我们在CM游戏上的结果对于证明所有WLC游戏的难度更高的结果也至关重要：我们对所有两人WLC游戏中最佳的预期协调时间进行完整的分析，以作为游戏大小的函数。我们还表明，CM游戏可以看作是所有两名玩家WLC游戏中最困难的游戏，因为它们是最佳的预期协调时间。
This paper investigates repeated win-lose coordination games (WLC-games). We analyse which protocols are optimal for these games covering both the worst case and average case scenarios, i,e., optimizing the guaranteed and expected coordination times. We begin by analysing Choice Matching Games (CM-games) which are a simple yet fundamental type of WLC-games, where the goal of the players is to pick the same choice from a finite set of initially indistinguishable choices. We give a complete classification of optimal expected and guaranteed coordination times in two-player CM-games and show that the corresponding optimal protocols are unique in every case - except in the CM-game with four choices, which we analyse separately. Our results on CM-games are also essential for proving a more general result on the difficulty of all WLC-games: we provide a complete analysis of least upper bounds for optimal expected coordination times in all two-player WLC-games as a function of game size. We also show that CM-games can be seen as the most difficult games among all two-player WLC-games, as they turn out to have the greatest optimal expected coordination times.
