最適配点問題
以下はまたミクシィからの転載のブラッシュアップです。
運動会で考えてもらうとわかりやすいかもしれませんが、例えば棒倒しは、1位をとった組には100点、2位の組には50点、3位の組には30点……というように、順位に応じて獲得点数が変わる競技です(正確な配分は忘れた)。そういう競技がいくつかあって、それらでの得点の総計が最終的な優勝組を決めるわけです。
この仕組みは選挙でも同じことで、1人の有権者が1回の競技に相当します。つまり、有権者は候補を1位、2位……と評価したあとで、1位に1点、2位以下は0点を与えるわけです。逆に言えば、有権者Aさんという競技で1位をとった候補は1点を得て、2位以下の候補は0点を得る、というふうになっています。
さて、選挙であれば(1,0,0,…)というある意味わかりやすい配分ですが、棒倒しの(100,50,30,…)という配分は、そうした理由が明確ではありません。理由があるとすれば、最終得点総計が1位になる組が2つ出ると、最終決戦が即決法(くじびき)かなんかになってしまうので、それを避けるためでしょう。
さあそこで問題です。いったいどういう配分であれば、最終的に1位タイが発生する確率が、もっとも低くなるでしょうか？
いま私が取り組んでいる問題はもう少し込み入っていて、5人が相互に投票しあうのですが、自分にだけは0点をつけなくてはならない、というものです。つまり、有権者は、自分以外の候補者4人について、独自の選好にしたがって1位〜4位の順位をつけ、点数を与えます。
4位の点数は0でいいと思います。これは、たとえば(100,50,30,1)という配分と、(99,49,29,0)という配分では、タイ発生率は等しいだろうからです。また、1位の点もあまり高くしても意味がないでしょう。(5000,3,2,1)と(1000,3,2,1)とで差はなさそうです。では、1位の点をどこまで下げても差はでないのか？ おそらくこのへんが突破口になりそうです。
確率の問題は検算がしにくいので、チェックプログラムを用意しました。C言語で書いたつたないものです。これでも、自分以外の4人に重複しないように1〜4位の投票をする部分で、かなり苦労しました。考え付いてから、トランプのシャッフルと同じだ、と気づいて検索したところ、主流のものとだいたい合っていたようです。何かほかにプログラムミスがあったら教えてください。
このプログラムにかけると、例えば(1,1,1,1)という配分では、タイ発生率は1です。(30,5,1,0)だと0.051909と出ましたが、100万回の試行ではまだ揺らぎが出るようで、またやったら0.052369でした。
以下はチェックプログラム。検算機能などを入れたものを作って、必要な部分だけ抜いたものなので、むだが少しあるかもしれません。配列の名前については、work[]はちょっとへんかもしれません。これは最初に提示された問題が、上記のものともさらに違っていたためです。つまり、5人の人間が、それぞれの持ち寄った作品(work)について評価しあう、という問題だったのです。
続きを読む