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
AandB. There arenprime-time programming slots, and each network hasnTV 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.
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.