穩定婚姻的變化 - 總會有穩定的「解決方案」嗎？

下面的問題是由「算法設計」由喬恩·克萊因伯格和伊娃·塔爾多斯，第1章，練習3.我縮短下來的說明儘可能（我的括號或外面的引號塊註釋）穩定婚姻的變化 - 總會有穩定的「解決方案」嗎？

假設我們有兩個電視網絡，我們將其稱爲A和B。黃金時段編程插槽有n，每個網絡都有n電視節目。每個網絡都想制定一個時間表 - 將每個節目分配到一個不同的時段 - 以吸引儘可能多的市場份額。 [...]每場演出都有固定的評級[...];我們假設沒有兩個節目具有完全相同的評分。網絡在給定的時隙中獲勝，如果其爲時隙調度的節目具有比顯示該時隙的其他網絡調度更大的評級。目標是爭取儘可能多的時間段。

我們得到一個時間表，從每一個網絡的一個賽季，所以第一個網絡給了我們一個時間表s，第二網絡爲我們提供了一個時間表T。

[...]我們會說，對日程（S，T）是穩定如果沒有網絡可以單方面改變自己的計劃和贏得更多的時隙。

也就是說，沒有時間表S'，將給予與第一網絡更多時隙，也不存在對所述第二網絡的類似時間表T'。

[問題是]：對於每一套的電視節目和收視率，是總有一個穩定的對時間表？

我的直覺告訴我，NO，因爲這個問題的，而我可以想像穩定時間表的唯一實例是當第一個網絡的最好的表演仍比第二網絡的最爛節目更糟即一個網絡可以贏得所有的時間表。否則，我認爲一個網絡可以交換兩個條目贏得更多的插槽，另一個網絡可以改變它的時間表，以便它一直贏回這些插槽。

來源

2013-12-23 John

網絡是如何改變其時間安排的？防爆。它只能交換兩個程序的時間嗎？或者它可以同時重新定位所有程序？ – Kevin

到達穩定的解決方案並不總是可能的，但我想如果排名滿足一定的標準，可能有辦法保證存在穩定的情況。

例如，（平凡）穩定的情況是當一個網絡的所有節目有平均等級和其它網絡的所有節目有非常高或低的排名，那麼就沒有任何網絡可以通過在交換時隙完成日程安排。
例如：
A = {45，50，59，60}
B = {1，3，90，92}
我想你可能能夠概括這個想法到達一個家庭的穩定箱子表徵。

來源

2013-12-23 19:49:42 user3076574

嗯，是的，我的直覺是對的。當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-23 19:27:36 John

穩定婚姻的變化 - 總會有穩定的「解決方案」嗎？

回答

相關問題