stable matching

Question

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

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)