4

The following problem is from "Algorithm Design" by Jon Kleinberg and Éva Tardos, Chapter 1, Exercise 3. I shortened down the description as much as possible (my annotations in brackets or outside the quote block)

Suppose we have two television networks, whom we'll call A and B. There are n prime-time programming slots, and each network has n TV shows. Each network wants to devise a schedule -- an assignment of each show to a distinct slot -- so as to attract as much market share as possible. [...] Each show has a fixed rating [...]; we'll assume that no two shows have exactly the same rating. A network wins a given time slot if the show that it schedules for the time slot has a larger rating than the show the other network schedules for that time slot. The goal is to win as many time slots as possible.

We get a schedule for one season from each network, so the first network gives us a schedule s, the second network gives us a schedule T.

[...] We'll say that the pair of schedules (S, T) is stable if neither network can unilaterally change its own schedule and win more time slots.

That is, there is no schedule S' that would give the first network more time slots, and neither there is a similar schedule T' for the second network.

[the question is]: For every set of TV shows and ratings, is there always a stable pair of schedules?

My gut feeling tells me NO, because the only instance of the problem of which i can imagine stable schedules is when the best show of the first network is still worse than the worst show of the second network, i.e. when one network can win all schedules. Otherwise i think one network can swap two entries to win more slots, and the other network could change its schedule so that it wins these slots back, all the time.

John
  • 2,015
  • 5
  • 23
  • 37
  • Is a network limited in any way by how it can change its schedule? Ex. Can it only swap the times for two programs? Or can it totally reposition all programs simultaneously? – Kevin Dec 23 '13 at 19:26
  • Going forward please ask such questions at https://cs.stackexchange.com/ – Mahesh Jamdade Mar 12 '23 at 19:26

2 Answers2

5

It's not always possible to arrive to a stable solution, but I suppose there may be a way to guarantee that a stable case exists if the rankings meet a certain criteria.

For example, a (trivially) stable case is when all the shows of one network have average rating and all the shows of the other network have extremely high or low ranking, then there is nothing either network can accomplish by swapping slots in the schedule.
For example:
A = {45, 50, 59, 60}
B = {1, 3, 90, 92}
I think you may be able to generalize this idea to arrive to a characterization of a family of stable cases.

user3076574
  • 161
  • 5
4

Hmm yeah, my gut feeling was right. It's easy to imagine a counterexample when n = 2.

Say, we have two shows for each network. The ratings for the shows of the first network are 10, 20 and the ones for the shows of the second are 15, 25.

So, we have this schedule:

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

Now B wins all slots. A will want to change the schedule to get at least one slot. So the new schedule is:

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

Now B changes its schedule to win back all slots...

John
  • 2,015
  • 5
  • 23
  • 37