Chapter 1: Introduction

• Summary:

This section discusses the stable matching problem. This problem was introduced in 1962 to solve/think about the matching process of students to schools in the college admissions process. It can also help solve other matching problems like patients to hospitals, and applicants to jobs or internships. According to our text book, an unstable matching means two people/groups (ex. a university and a student) could agree to make switches that both of them prefer (ex. W&L wants Suzy more than Ben and Suzy wants W&L more than Lynchburg so they agree to drop Ben and Lynchburg respectively and Suzy goes to W&L), but these switches mess up all of the matchings (ex. what do Ben and Lynchburg do now? Lynchburg might want David, and David might want Lynchburg more than his school and that just leaves more people/schools without matches if David leaves his school for Lynchburg). A stable matching doesn't necessarily mean that everyone has their top choice but that no two groups/people could come to an agreement that would improve both of their situations. The rest of the section discusses solving the problem. The problem/the language of the problem is simplified so that it's easier to solve (ex. we want a one-to-one matching so we use the example of matching up women and men for marriage instead of applicants to colleges). The Gale-Shapley Algorithm is presented, analyzed (run time), and proven to work for this problem. We discussed, analyzed and proved it in class as well so I won't go into the actual algorithm.

• Insights and Questions:

Obviously this is a simplified version of the problem, but I am curious how/if this algorithm is actually used in the college admissions process, because there are so many other factors that I can't imagine incorporating into this model (ex. students don't apply to every university, students don't necessarily have preference lists in advance - it often depends on other factors, applications come in at different times, etc.). Also, this algorithm would not necessarily be favorable to the colleges, so why would they agree to this? For example, if a college can get admissions letters/contracts sent out to their top applicants before other colleges send out their admissions letters, then applicants who prefer other schools might go ahead and accept rather than take the chance that they'll be admitted to another school. And in real life, unlike in the book's scenario, I doubt many applicants would back out and switch schools if they've already accepted to another school. Colleges certainly wouldn't take back an admission. Wouldn't an objective third party need to know all of the colleges' applicants and preferences and all of the applicants' preferences in order to do a matching like this? That's what has to happen for our sorority matchings (I think), but that's a lot easier than this. Anyway, it's interesting that this whole set of problems originated from such a complex problem that it seems impossible to solve in this way.

• Readability:

I found this section very readable. I used the presentation, analysis and proof of the G-S Algorithm as a review rather than trying to understand it based soley on what's written in the book and it worked well for that (I'm not sure how I would have felt about the book's presentation of the algorithm without the priming of our class, though). For me, the most useful part of this section was the more detailed real-life examples of situations in which this algorithm applies and, particularly, how unstable pairings could create problems.

• Sara Says:

A difference with graduate school admissions (and maybe this is true in undergraduate admissions) is that there is a date that is the earliest that schools can ask for a response/acceptance. I think it's April 15. This date protects students and colleges.

I think this works with medical school because, like you said, there is centralized knowledge, e.g., it's known which schools the applicants are most interested in.

• Summary:

This section goes over problems that are representative of different types of problems that can (maybe) be solved using (efficient) algorithms. (1) Interval Scheduling - ex. booking a meeting room, trying to let as many people as possible book the room. (2) Weighted interval scheduling - ex. booking a meeting room, but the people booking the room will pay for it, so you're trying to make as much money as possible. (3) Bipartite Matching - like our stable matching problem with men and women, but “preference lists” don't include every other man/woman (i.e. there are some men that a women would not accept at all, and vice-versa). In this case the goal would be to have a stable situation with maximum pairings (which might not mean that everyone has a partner). (4) Independent set - given a 'graph' with nodes and edges, pick a set of nodes that have no directly connecting edges (of maximum size). This problem is (probably) not able to be solved efficiently with an algorithm! This one's particularly cool, though, because it can be used to model (1), (2), and (3) (so those are special cases of this problem). Solutions may be hard to find for these problems using algorithms, but it's pretty easy to check solutions once you have them. (5) Competitive Facility Location - ex. 2-player game with 2 coffee companies trying to build franchises and make the most money. This one is even harder than (4). It's not even easy to check that a solution exists, much less come up with it using an algorithm.

• Insights and Questions:

Since (1), (2), and (3) are special cases of (4), is it possible to find an efficient solution for every (or almost every) particular example of this type of problem, just not a general solution that works in every instance? Similarly, for (5), are there efficient algorithms to solve any particular cases of this problem? I'm also not sure that I understand how the graphs in Figure 1.13 are (necessarily) bipartite graphs.

• Readability:

This section was also very readable. I am glad that they didn't go any farther into the algorithms that could solve these problems (yet) because I would have been lost. The description of the graph math is the only part I found really confusing/difficult to read. It was too symbol-heavy without enough explanation of what the symbols meant. More labels on Figure 1.13 that explained those symbols would have made it a lot easier to read.

• Sara Says:

“I'm also not sure that I understand how the graphs in Figure 1.13 are (necessarily) bipartite graphs.” –> We'll be talking more about bipartite graphs soon.

Yeah, the Five Representative Problems section was hard to read–getting into more than we need to right now. It'll be a good review closer to the end of the semester.