text: We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2+e)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.
  @cite_18: In any two-sided matching market, a stable matching can be found by a central agency using the deferred acceptance procedure of Gale and Shapley. But if the market is decentralized and information is incomplete then stability of the ensuing matching is not to be expected. Despite the prevalence of such matching situations, and the importance of stability, little theory exists concerning instability. We discuss various measures of instability and analyze how they interact with the structure of the underlying preferences. Our main result is that even the outcome of decentralized matching with incomplete information can be expected to be “almost stable” under reasonable assumptions.
  @cite_22: In this paper a parallel algorithm to solve the stable marriage problem is given. The worst case performance of this algorithm is stated. A theoretical analysis shows that the probability of the occurrence of this worst case is extremely small. For instance, if there are sixteen men and sixteen women involved, then the probability that the worst case occurs is only 10−45. Possible future research is also discussed in this paper.
  @cite_29: Abstract A parallel algorithm for the stable matching problem is presented. The algorithm is based on the primal-dual interior path-following method for linear programming. The main result is that a stable matching can be found in O ∗ ( m ) time by a polynomial number of processors, where m is the total length of preference lists of individuals.
  @cite_32: Abstract We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2 n −1) in any metric space (where n is the number of vertices). This algorithm is optimal - there is no on-line deterministic algorithm that achieves a competitive ratio better than (2 n −1) in all metric spaces. We also study the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple “first come, first served” deterministic algorithm yields on the average O( n log n ) unstable pairs, but in the worst case no deterministic or randomized on-line algorithm can do better than ω( n 2 ) unstable pairs. This appears to be the first on-line problem for which provably one cannot do better with randomization; for most on-line problems studied in the past, randomization has helped in improving the performance.
  @cite_3: 
  @cite_20: In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n) loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).
summary: From a theory perspective, apparently only a few papers address decentralised implementations of the Gale--Shapley algorithm and or stability after early termination of a stable matching algorithm. In a recent paper @cite_18 it is claimed that little theory exists concerning instability.'' @cite_32 give bounds on the performance of a simple online algorithm. Feder al @cite_29 show that a stable matching can be found on a polynomial number of processors in sublinear time; their algorithm is not local. Other work on parallel stable matching include Tseng and Lee @cite_22 , Tseng @cite_20 , and Hull @cite_3 . Eriksson and H " a ggstr " o m @cite_18 prove that a simple heuristic works well for random inputs. Our Theorem shows that the Gale--Shapley algorithm works well for an arbitrary input.