stable matching

Tag: algorithm Author: p1021 Date: 2009-08-07

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.

Go post your answer - I'd like to see it.
I don't object to this question at all, but I wonder whether it opens the door to a series of questions which are "programming related", but are not "computer programming related" ;-)
solve with some programming, and you've made it computer programming related. :)

Best Answer

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)

Other Answer1

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

Other Answer2

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.

comments:

The answer actually depends on the input. Say A has programs rated [1, 2, 3] and B has programs rated [4, 5, 6], there actually is a stable matching. The problem is to find out the condition.
Really, I don't think there is any stable matching in the situation you states. Can you give me the show case? Thanks! And the question in the book is: "Is there always a stable pair of schedules?". So my answer is also:"No, it depends on the situation." And is there any people can work out the condition whether stable matching always exists? Thanks!
My situation is very trivial - no matter who changes its own schedule, B always wins all the time slots. So any schedule pair (S, T) is stable. I'm also wondering the necessary and sufficient condition though. :)
Sorry, I saw it. I thought your example is[1, 3, 5] and [2, 4, 6]. Sorry about that.
Actually, in mixed strategies, a stable equilibrium always exists (in Roy's example both companies play each schedule permutation with equal probability = 0.5); but it sounds like the question only allows pure strategies.

Other Answer3

Let each TV channel having 2 shows. TV-1:

Show1 has a rating of 20 pts. show2 has a rating of 40 pts.

TV-2:

Show1 has a rating of 30 pts. Show2 has a rating of 50 pts.

Then it clearly shows the matching is unstable.