3

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

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

我们从每个网络得到一个赛季的时间表，所以第一个网络给我们一个时间表s，第二个网络给我们一个时间表T。

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

也就是说，没有S'可以给第一个网络更多时隙的时间表，也没有T'用于第二个网络的类似时间表。

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

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

4

2 回答 2

4

并非总是有可能得出一个稳定的解决方案，但我想如果排名符合特定标准，可能有一种方法可以保证存在一个稳定的案例。

例如，一个（微不足道的）稳定的情况是，当一个网络的所有节目都具有平均收视率，而另一个网络的所有节目的排名都非常高或极低时，那么任何一个网络都无法通过交换时间表中的时段来完成任何事情。
例如：
A = {45, 50, 59, 60}
B = {1, 3, 90, 92}
我认为您可以将这个想法推广到对一系列稳定案例的表征。

于 2013-12-23T19:49:42.020 回答
3

嗯，是的，我的直觉是对的。当 时很容易想象一个反例n = 2。

比如说，我们每个网络有两个节目。第一个网络的节目收视率为，第二个网络的节目收视10, 20率为15, 25。

所以，我们有这个时间表：

slot 1: A: 10, B: 15  # B wins
slot 2: A: 20, B: 25  # B wins

现在B赢得所有插槽。A将想要更改时间表以至少获得一个插槽。所以新的时间表是：

slot 1: A: 20, B: 15  # A wins
slot 2: A: 10, B: 25  # B wins

现在B更改其时间表以赢回所有插槽...

于 2013-12-23T19:27:36.820 回答