稳定婚姻的变异——总有一个稳定的“解决方案”吗？

Question

以下问题来自 Jon Kleinberg 和 \xc3\x89va Tardos 的“算法设计”，第 1 章，练习 3。我尽可能缩短了描述（我的注释在括号中或引用块之外）

\n\n

\n

假设我们有两个电视网络，我们将其称为A和B。有n黄金时段的节目时段，每个网络都有n电视节目。每个电视网都希望制定一个时间表——将每个节目分配到一个不同的时段——以便吸引尽可能多的市场份额。\n [...] 每个节目都有固定的收视率[...]；我们假设没有两个节目具有完全相同的评级。如果一个网络在给定的时间段安排的节目比其他网络在该时间段安排的节目具有更高的收视率，则该网络赢得该时间段。目标是赢得尽可能多的时间段。

\n

\n\n

我们从每个网络获得一个赛季的时间表，因此第一个网络给我们一个时间表s，第二个网络给我们一个时间表T。

\n\n

\n

[...]如果两个网络都不能单方面改变自己的时间表并赢得更多的时隙，我们就说这对时间表（S，T）是稳定的。

\n

\n\n

也就是说，不存在S\'给予第一网络更多时隙的调度，并且也不存在用于T\'第二网络的类似调度。

\n\n

---

\n\n

\n

【问题是】：每一套电视剧和收视率，是否总有一对稳定的档期？

\n

\n\n

我的直觉告诉我不，因为我可以想象稳定时间表的问题的唯一实例是当第一个网络的最佳节目仍然比第二个网络的最差节目差时，即当一个网络可以赢得所有时间表时。否则，我认为一个网络可以交换两个条目以赢得更多插槽，而另一个网络可以更改其时间表，以便始终赢回这些插槽。

\n

Answer 1

并不总是能够得出稳定的解决方案，但我想如果排名满足一定的标准，可能有一种方法可以保证稳定的情况存在。

例如，一种（普通）稳定的情况是，当一个网络的所有节目具有平均收视率，而另一个网络的所有节目具有极高或极低的排名时，则任一网络都无法通过交换时间表中的时段来完成任何事情。
例如：
A = {45, 50, 59, 60}
B = {1, 3, 90, 92}
我认为您也许能够概括这个想法，以得出一系列稳定案例的特征。