1

私が作成しているゲームの値でランク付けしたい ~ 1000 の異なるアセットのリストがあります。

プレーヤーには、2 つのアセット バスケットのいずれかを選択する機会が与えられます。たとえば、A + B または C のどちらを希望するかを尋ねられる場合があります。

バスケットの好みの膨大なリストから、認識された価値によって資産をランク付けしたいと考えています。

以下は入力の例で、それに応じてプレイヤーは次のように言っています。

A > B
A + A > B + C
C > B

つまり、彼らは B よりも A を好む。B と C よりも 2 つの As を好む。

この入力から、最も可能性の高い値のランキングは次のようになると思います。

A > C > B

この問題を解決するには、どのクラスのアルゴリズムを使用する必要がありますか?

場合によっては、好みのリストが矛盾することがあります (A > B と考えるプレイヤーもいれば、B > A と考えるプレイヤーもいます)。プレーヤーのスキル レベルの別の測定値がある場合、これをどのように活用してより正確なランキングを取得できますか?

また、バスケット間の関係に「島」がある場合も処理できる必要があります。例えば：

A > B
C > D

つまり、A <> C かどうかはわかりません。

これは、さまざまなパッキング アルゴリズムに似た最適化問題のように思えます。このランキング問題は NP 困難ですか?

4

2 に答える 2

1

実際には、グラフ理論のように聞こえます。

A < Bを示すA -> Bの有向グラフがあるとします。その後、あなたができる

問題は、そのようなグラフをどのように作成するかです。重要な多変数ルールは次の形式だけであるという予感があります (残念ながらまだそれ以上ではありません)。

A_1 + A1 + ... + A_i < A_{i + 1}

そして、それらは次のように単純化する必要があります

A_j < A_{i + 1}、j = 1、..、i .

(それとは別に、RHS 多値ルールの唯一の使用は、(私の勘によると) 推移的演繹のためです。つまり、

A < B + CおよびB + C < Dは、 A < D を意味します。ただし、これは合計にダミー変数を使用して処理できます。)

おそらく、これを検証または反論できるかどうかを確認する必要があります。

于 2015-05-19T22:18:34.203 に答える
1

あなたがやろうとしていることは、アローの定理による合理的な仮定の下では一般的に不可能です。

より良いアプローチは、プレーヤーにランクではなくスコアを求めることです。たとえば、「A に何ズウォティを支払うか? B に? C に?」と尋ねてから、回答したプレイヤーによる各アイテムのスコアを平均します。したがって、プレーヤー 2、5、および 11 のみがアイテム A の価値の見積もりについて回答した場合、それらの回答を足して 3 で割ります。また、より経験豊富なプレーヤーの回答に重みを付けることもできます。

それでも資産のバスケットを使用したい場合は、おそらく線形代数を使用して、A+B と AB のスコアに基づいて A と B のスコアを解きほぐすことができます。

ランキング データでやりくりしたい場合 (たとえば、それしかなく、これ以上質問できない場合) は、おそらく Ami のアプローチが最適です。

于 2015-05-19T23:25:52.270 に答える