3

私が作成したゲームについて非常に簡単な質問があります (これは宿題ではありません): ペイオフを最大化するには、次のメソッドに何を含める必要がありますか:

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

繰り返しますが、これは宿題ではないことを強調します。ここで何が行われているのかを理解しようとしています。

「戦略」は些細なことです: true または false の 2 つの選択肢しかありません。

「ゲーム」自体は非常にシンプルです。

P1  R1        R2 P2


          R5


P3  R3        R4 P4

  • 4 人のプレーヤー (P1、P2、P3、および P4) と 5 つのリソース (R1、R2、R3、R4 はすべて 1 の価値があり、R5 は 2 の価値がある) があります。

  • 各プレイヤーには、正確に 2 つのオプションがあります: 1 を与える開始位置に近く、プレイヤーが確実に取得できるリソースを探す (他のプレイヤーが最初にそのリソースに到達することはできません)または、プレイヤーは次のリソースを取得しようとすることができます:は 2 の価値があります... しかし、他のプレイヤーもそれを選ぶかもしれません。

  • 2 人以上のプレイヤーがより大きなリソース (2 分の 1) を求めた場合、それらは同時により大きなリソースに到達し、ランダムに 1 人のプレイヤーだけがそれを手に入れ、他のプレイヤーはそれを手に入れます。そのリソースは 0 になります (1 のリソースに戻ることはできません)。

  • 各プレイヤーは同じ戦略をプレイします (メソッドgoForBiggerResource () で定義されたもの)

  • プレイヤーは戦略に同意するために互いに「話す」ことはできません

  • ゲームは100万回実行されます

したがって、基本的には、利益を最大化する方法で、true または false を返すメソッド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;
};

その後、4 人のプレイヤー全員がより大きなリソースを求めます。そのうちの1つだけがランダムに取得されます。100 万回以上の反復では、プレーヤーごとの平均ペイオフは 2/4 になり、0.5 となり、プログラムは次のように出力します。

プレイヤーあたりのペイオフ: 0.5

私の質問は非常に単純です。平均利益を最大化するには、メソッドgoForBiggerResource() (true または false を返す) に何を入れるべきですか? またその理由は何ですか?

4

4 に答える 4

5

各プレーヤーはあなたのgoForBiggerResource方法で説明されている同じ戦略を使用し、全体的な利益を最大化しようとするため、最良の戦略は、3 人のプレーヤーがローカル リソースに固執し、1 人のプレーヤーが大きなゲームに参加することです。残念ながら、彼らは戦略に同意できず、ビッグ ゲーム ハンターとして区別できないプレーヤーはいないと思います。

プレーヤーがビッグ ゲームに参加するかどうかをランダム化する必要があります。p が彼がそれを選ぶ確率であると仮定します。次に、ビッグ ゲーム ハンターの数に応じてケースを分けて、ケースの数、確率、ペイオフを計算し、これに基づいて、期待されるペイオフを計算できます。

  • 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 確率、2 ペイオフ、期待 2(p^4)

次に、期待されるペイオフの合計を最大化する必要があります。私が正しく計算した場合、これは -2p^4+8p^3-12p^2+4p+4 です。最初の項は -2 < 0 であるため、これは凹関数であり、うまくいけばその導関数の根の 1 つ -8p^3+24p^2-24p+4 が期待される利得を最大化します。これをオンラインの多項式ソルバーにプラグインすると、3 つの根が返されます。そのうちの 2 つは複素数で、3 つ目は p ~ 0.2062994740159 です。2 番目の導関数は -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

基本的に、私が間違っていなければ、「ナッシュ均衡」に関するウィキペディアのページ、特にこれを読みたいと思います。

「ナッシュ均衡は、プレイヤーが可能なアクションよりも確率分布を選択する、混合戦略の観点から定義されます」

私が間違っていなければ、あなたの質問/簡単な例は、共謀しているプレイヤーがより良い平均報酬を得ることができる理由を示すためにも使用できます。

また、私の回答には近似エラーが含まれており（0から99までの乱数のみをチェックしています）、ランダムPRNGに少し依存していることにも注意してください。

于 2011-10-10T17:09:14.647 に答える
2

プレイヤーが協力できず、記憶がない場合、実装する方法は 1 つしかありませんgoForBiggerResource。値をランダムに選択します。ここで問題は、どのレートを使用するのが最適かということです。

簡単な数学 (実際にはプログラミングとは関係ありません):

  • レートxは、小さなリソースにとどまる確率を表すと仮定します。
  • したがって、ビッグ 1 を狙うプレーヤーがいない可能性はx^4;
  • したがって、少なくとも 1 人のプレーヤーがビッグ プレーヤーに行く可能性は1-x^4;
  • 総利益はx + ( 1 - x^4 ) / 2
  • x0% <= <= 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 に答える