3

我有一个关于我创建的游戏的非常简单的问题（这不是家庭作业）：以下方法应该包含什么来最大化收益：

private static boolean goForBiggerResource() {
    return ... // I must fill this
};

我再次强调这不是功课：我试图了解这里的工作。

“策略”是微不足道的：只有两种选择：真或假。

“游戏”本身很简单：

P1  R1        R2 P2


          R5


P3  R3        R4 P4

  • 有四个玩家（P1、P2、P3 和 P4）和五个资源（R1、R2、R3、R4 都值 1 和 R5，值 2）

  • 每个玩家都有两个选择：要么去靠近它的起始位置的资源，它给出 1 并且玩家肯定会得到（没有其他玩家可以先得到那个资源），或者玩家可以尝试去寻找一个资源值得 2... 但其他玩家也可能会去。

  • 如果两个或更多玩家去争取更大的资源（价值 2 的那个），那么他们将同时到达更大的资源，并且随机只有一名玩家会得到它，而其他玩家则去该资源将得到 0（他们不能回到价值 1 的资源）。

  • 每个玩家都玩相同的策略（在goForBiggerResource () 方法中定义的那个）

  • 玩家不能互相“交谈”以就策略达成一致

  • 游戏运行 100 万次

所以基本上我想填充方法goForBiggerResource()，它返回真或假，以最大化回报。

这是允许测试解决方案的代码：

private static final int NB_PLAYERS = 4;
private static final int NB_ITERATIONS = 1000000;

public static void main(String[] args) {
    double totalProfit = 0.0d;
    for (int i = 0; i < NB_ITERATIONS; i++) {
        int nbGoingForExpensive = 0;
        for (int j = 0; j < NB_PLAYERS; j++) {
            if ( goForBiggerResource() ) {
                nbGoingForExpensive++;
            } else {
                totalProfit++;
            }
        }
        totalProfit += nbGoingForExpensive > 0 ? 2 : 0;
    }
    double payoff = totalProfit / (NB_ITERATIONS * NB_PLAYERS);
    System.out.println( "Payoff per player: " + payoff );
}

例如，如果我建议以下解决方案：

private static boolean goForBiggerResource() {
    return true;
};

然后所有四个玩家都将寻求更大的资源。他们中只有一个会随机得到它。超过一百万次迭代，每个玩家的平均收益将是 2/4，即 0.5，程序将输出：

每位玩家的收益：0.5

我的问题很简单：goForBiggerResource()方法（返回 true 或 false）应该使用什么来最大化平均收益，为什么？

4

4 回答 4

5

由于每个玩家都使用您方法中描述的相同策略goForBiggerResource，并且您尝试最大化整体收益，因此最佳策略是三个玩家坚持使用本地资源，一个玩家参与大型游戏。不幸的是，由于他们无法就策略达成一致，而且我认为没有玩家不能被区分为大游戏猎人，事情变得棘手。

我们需要随机化玩家是否参加大型比赛。假设 p 是他坚持下去的概率。然后根据 Big Game Hunters 的数量来划分案例，我们可以计算案例的数量、概率、收益，并据此计算预期收益。

  • 0 BGH：（4个选择0）个案例，（1-p）^4个概率，4个回报，预期4（p^4-4p^3+6p^2-4p+1）
  • 1 BGH：（4选1）个案例，（1-p）^3*p概率，5个回报，预期20（-p^4+3p^3-3p^2+p）
  • 2 BGH：（4 选择 2）个案例，(1-p)^2*p^2 概率，4 回报，预期 24(p^4-2p^3+p^2)
  • 3 BGH：（4选3）个案例，（1-p）*p^3概率，3个回报，预期12（-p^4+p^3）
  • 4 BGH：（4 选择 4）个案例，p^4 prob，2 payoff，预期 2(p^4)

然后我们需要最大化预期收益的总和。如果我计算正确，则为 -2p^4+8p^3-12p^2+4p+4。由于第一项是 -2 < 0，因此它是一个凹函数，希望它的导数 -8p^3+24p^2-24p+4 的一个根将最大化预期收益。将其插入在线多项式求解器，它会返回三个根，其中两个是复数，第三个是 p ~ 0.2062994740159。第二个导数是 -24p^2+48p-24 = 24(-p^2+2p-1) = -24(p-1)^2，对于所有 p != 1，它 < 0，所以我们确实找到了一个最大值。（总体）预期收益是在此最大值下评估的多项式，约为 4.3811015779523，即每位玩家的收益为 1.095275394488075。

因此获胜的方法是这样的

private static boolean goForBiggerResource ()
{
    return Math.random() < 0.2062994740159;
}

当然，如果玩家可以使用不同的策略和/或互相对抗，那就完全不同了。

编辑：另外，你可以作弊；）

private static int cheat = 0;

private static boolean goForBiggerResource ()
{
    cheat = (cheat + 1) % 4;
    return cheat == 0;
}
于 2011-10-10T18:42:06.180 回答
3

我认为您尝试了以下操作：

private static boolean goForBiggerResource() {
    return false;
};

没有一个玩家试图去寻找价值 2 的资源。因此，他们保证每个人每次都能获得价值 1 的资源，因此：

每位玩家的收益：1.0

我还想，如果你问这个好问题是因为你猜有更好的答案。

诀窍是您需要所谓的“混合策略”。

编辑：好的，我在这里采用了混合策略...我不明白帕特里克如何快速找到 20%（当他发表评论时，仅在您发布问题后几分钟）但是，是的，我发现基本相同价值太：

private static final Random r = new Random( System.nanoTime() );

private static boolean goForBiggerResource() {
    return r.nextInt(100) < 21;
}

例如，这给出了：

每位玩家的收益：1.0951035

基本上，如果我没记错的话，你想阅读关于“纳什均衡”的维基百科页面，尤其是这个：

“纳什均衡是根据混合策略定义的，其中玩家选择可能行动的概率分布”

如果我没记错的话，您的问题/简单示例也可以用来说明为什么串通的玩家可以获得更好的平均收益：如果玩家可以串通，他们平均会得到 1.25，这超过了我得到的 1.095。

另请注意，我的答案包含近似错误（我只检查从 0 到 99 的随机数）并且有点取决于 Random PRNG，但您应该明白这一点。

于 2011-10-10T17:09:14.647 回答
2

如果玩家不能合作并且没有记忆，那么只有一种可能的实现方式goForBiggerResource：随机选择一个值。现在的问题是什么是最好的使用率。

现在简单的数学（不是真正的编程相关）：

  • 假设比率x代表保留小资源的概率；
  • 因此，没有球员选择大牌的机会是x^4；
  • 所以至少一名球员去大的机会是1-x^4；
  • 总利润是x + ( 1 - x^4 ) / 2
  • 找到该公式的最大值 0% <= x<= 100%

结果约为 79.4%（用于返回 false）

于 2011-10-10T18:57:36.077 回答
-1

嗯，我认为你的基本问题是所描述的游戏是微不足道的。在所有情况下，最佳策略是坚持使用本地资源，因为使用 R5 的预期收益仅为 0.5 (1/4 * 2)。将 R5 的奖励提高到 4，变得均匀；没有更好的策略。奖励（R5） > 4，拿 R5 总是值得的。

于 2011-10-10T17:10:01.803 回答