Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:hornsbym:chapter_1 [2018/01/16 01:34] – hornsbym
+++ courses:cs211:winter2018:journals:hornsbym:chapter_1 [2018/01/16 01:40] (current) – hornsbym
@@ Line 1: / Line 1: @@
 ====== Chapter 1 ======
-<Enter overview of chapter 1 here>
+This chapter deals with the Stable Matching Problem. In Chapter 1.1, the authors sketch out the algorithm and prove the following:\\
+(A) The Gale-Shapely algorithm terminates after n<sup>2</sup> iterations\\
+(B) The final matching is a perfect matching\\
+(C) The final matching is stable
 ===== Section 1.1(The Stable Matching Problem) =====
-This section deals with the Stable Matching Problem, which was first posed by David Gale and Lloyd Shapely in 1962. This algorithm seeks to assign job applicants to potential employers in a way such that:\\
+This section deals with the Stable Matching Problem, which was first posed by David Gale and Lloyd Shapely in 1962. This algorithm seeks to assign job applicants to potential employers in a way such that:
     "(i) Employers prefer every one of its accepted applicants to the remaining applicants; or
      (ii)Accepted job applicants prefer their current situation over working for other potential employers."
@@ Line 9: / Line 12: @@
 To simplify this problem, Gale and Shapely made the assumption that every applicant sought a single employer, and every employer sought a single applicant. The latter, of course, would rarely be the case; however, the simplification allowed for the problem to be more easily defined while still maintaining the fundamental issues. Gale and Shapely simulated this problem by substituting employers for men and applicants for women, then designing an algorithm that will ensure the men and women form stable pairs.\\
 \\
-The algorithm follows the following steps:\\
+The algorithm follows the following steps:
-\\
      (1)Each man proposes to each woman in order of his preference, until a woman accepts.
      (2)Each woman accepts any proposal if she's free. If she's already engaged, she will only accept the proposal if she prefers the new man.
      (3)If a woman breaks her current proposal, the man she leaves becomes free again.
      (4)The process continues until there is no more free men.
-\\
 This algorithm keeps everyone as happy as they can expect to be, so no one will feel compelled to leave their current situation. Since each pair will be self motivated to stay together, the matching is stable.