机构名称：
¥ 2.0
摘要 混合策略通常根据其保证的预期收益进行评估。这并不总是可取的。在本文中，我们考虑最大化预期收益与玩家实际目标相偏离的游戏。为了解决这个问题，我们引入了 ( u, p )- 最大最小策略的概念，该策略确保以至少 p 的概率获得 u 的最小效用。然后，我们给出了寻找这些游戏的 ( u, p )- 最大最小策略问题的近似算法。我们考虑的第一个游戏是 1921 年推出的、经过深入研究的游戏“布洛托上校”。在布洛托上校游戏中，两位上校将他们的军队分配到一组战场上。每个战场都由投入更多军队的上校赢得。每个上校的收益是她赢得的战场的加权数量。我们表明，对于 Colonel Blotto 的某些应用，最大化玩家的预期收益并不一定能最大化其获胜概率。例如，在总统选举中，玩家的目标是最大化赢得超过一半选票的概率，而不是最大化他们获得的预期票数。我们为该游戏的连续版本的自然变体提供了一个精确算法。更一般地，我们提供了常数和对数近似算法来查找 ( u, p )- 最大最小策略。我们还引入了 Colonel Blotto 的安全游戏版本，我们称之为审计游戏。它在两个玩家之间进行，一个是防守者，一个是攻击者。防守者的目标是防止攻击者更改 Colonel Blotto 实例的结果。同样，最大化防守者的预期收益不一定是最佳的。因此，我们为 ( u, p )- 最大最小策略提供了一个常数近似值。
Blotto 和审计游戏的获胜策略
主要关键词
相关文件推荐
