次の問題は、Jon Kleinberg と Éva Tardos による「アルゴリズム設計」、第 1 章、演習 3 からのものです。説明をできるだけ短くしました (括弧内または引用ブロックの外側の注釈)。
2 つのテレビ ネットワークがあると
AしますB。nゴールデンタイムの番組枠があり、各ネットワークにはテレビn番組があります。各ネットワークは、できるだけ多くの市場シェアを獲得するために、スケジュール (各ショーを個別のスロットに割り当てる) を考案したいと考えています。[...] 各番組には固定の評価があります [...]。まったく同じ評価の番組は 2 つないと仮定します。ネットワークがそのタイムスロットにスケジュールする番組の評価が、他のネットワークがそのタイムスロットにスケジュールする番組よりも高い場合、そのネットワークはそのタイムスロットを獲得します。目標は、できるだけ多くのタイムスロットを獲得することです。
各ネットワークから 1 シーズンのスケジュールを取得するため、最初のネットワークはスケジュールsを提供し、2 番目のネットワークはスケジュールを提供しTます。
[...]どちらのネットワークも自分のスケジュールを一方的に変更できず、より多くのタイムスロットを獲得できない場合、スケジュールのペア (S、T) は安定していると言えます。
つまりS'、最初のネットワークにより多くのタイムスロットを与えるスケジュールはなくT'、2 番目のネットワークにも同様のスケジュールはありません。
[質問です]:テレビ番組と視聴率のすべてのセットについて、常に安定したスケジュールのペアがありますか?
私の直感では NO です。安定したスケジュールを想像できる問題の唯一の例は、最初のネットワークの最高のショーが 2 番目のネットワークの最悪のショーよりもさらに悪い場合です。つまり、1 つのネットワークがすべてのスケジュールに勝つことができる場合です。 . それ以外の場合、1 つのネットワークが 2 つのエントリを交換してより多くのスロットを獲得し、他のネットワークがスケジュールを変更して、常にこれらのスロットを獲得できると思います。