stable matching

Question

Hi all,

I'm reading a algorithm book in my lesure time. Here is a question I have my own answer but not quite sure. What's your opinion? Thanks!

Question: There are 2 television network company, let as assume A and B, each are planning the TV progame schedule in n time slots of a day. Each of them are putting their n programs in those slots. While each program have a rate based on the popularity in the past year, and these rate are distinct to each other. The company win a slot when its show have a higher rate then its opponent's. Is there a schedule matching that A made a schedule S and B made a schedule T, and (S, T) is stable that neither network can unilaterally change its own schedule and win more time slots.

Answer 1

My own answer is no stable matching. Supposing there are only 2 time slots. A have program p1(5.0) p2(3.0); B have program p3(4.0) p4(2.0);

The schedule of A includes: S1: p1, p2 S2: p2, p1 The schedule of B includes: T1: p3, p4 T2: p4, p3

So the matching include: (S1, T1)(S1, T2)(S2, T1)(S2, T2)

while the results are (S1, T1) - (p1, p3)(p2, p4) 2:0 - not stable, becuase B can change its schedule to T2 and the result is : (S1, T2) - (p1, p4)(p2, p3) 1:0

Vise versa and so does the other matching.

Answer 2

Solution in Haskell:

hasStable :: Ord a => [a] -> [a] -> Bool
hasStable x y =
  score x y + score y x == 0

-- score is number of slots we win minus number of slots they win
-- in our best possible response schedule
score :: Ord a => [a] -> [a] -> Integer
score others mine =
  scoreSorted (revSort others) (revSort mine)
  where
    -- revSort is sort from biggest to smallest
    revSort = reverse . sort

scoreSorted :: Ord a => [a] -> [a] -> Integer
scoreSorted (o:os) (m:ms)
  | m > o =
    -- our best show is better then theirs
    -- we use it to beat theirs and move on
    1 + score os ms
  | otherwise =
    -- their best show is better then ours
    -- we match it with our worst show
    -- so we could make use of our big guns
    -1 + score os (m : ms)
scoreSorted _ _ = 0 -- there are no shows left

> hasStable [5,3] [4,2]
False
> hasStable [5,2] [3,4]
True

Answer 3

There is no stable matching, unless one station has all its programs contiguous in the ratings (ie. the other station has no program which is rated better than one program on the first station but worse than another on the first station).

Proof

• Suppose a station can improve its score, and the result is a stable matching. But then the other station could improve its own score by reversing the rearrangement. So it wasn't a stable matching. Contradiction.

• Therefore a stable matching can not be reached by a station improving its score.

• Therefore a stable matching can't be made worse (for either station), because then the lower state could be improved to a stable matching (which I just showed was not allowed).

• Therefore every program rearrangement of a stable matching must give equal scores to both stations.

• The only program sets which can't have scores changed by rearrangement are the ones where one of the stations' programs are contiguous in the ratings. (Proof left to reader)