From CSULA CS Wiki
Jump to: navigation, search

Contents

Jan 5 (week 1)

Jan 12 (week 2)

Jan 19 (week 3)

I was originally introduced to the "Stable Matching/Marriage Problem" in an advanced algorithm course I took a year ago in Cal Poly Pomona. I have decided to explore this a little bit further.

Jan 26 (week 4)

According to my discussion with Dr. Abbott last week, I talked to Dr. Crespi to find out what he thought about Stable Matching Problem. He informed my that he could not take me yet, since I had not taken any graduate level course with him.

I am going to continue doing more research on this problem and will decide what to do after I talk to Dr. Abbott.

Feb 2 (week 5)

I am currently working on the problem of honesty and stable matching. I have found some interesting articles about this and will present the matter next week. I am also writing a small program for stable matching problem.

Feb 9 (week 6)

During the past 2 weeks I worked on my program. I have also tried to do more research to find papers that are related to the "Stable Matching Problem", especially the ones that are related to honesty and incentives to prevent cheating in the agents preference lists as well as during the matching process itself.

The basic idea is whether it is possible for a group of persons (of either sex) to somehow falsify their lists to get better partners.

I found the following papers that address this issue:

- The Economics Of Matching: Stability And Incentives (Roth Alvin)
- Machiavelli and the Gale-Shapley algorithm (L. E. Dubins and D. A. Freedman)
  
- Ms. Machiavelli and the Stable Matching Problem (David Gale and Marilda Sotomayor)
   
- How Hard is it to Cheat in the Gale-Shapley Stable Matching Algorithm (Chien-Chung Huang et. al)

The first paper is one the most important ones on this topic and is still being referenced in most recent research papers. "The main focus of this paper will be on determining the extent to which matching procedures can be designed which give agents the incentive lo honestly reveal their preferences, and which produce stable matches." The author states two main principles in this paper:

- No matching procedure exists that always generates a stable outcome and also gives incentive to agents to be truthful about their preference list.
  
- Matching procedures exist that yield a stable outcome however they only give incentive to agents in one of the two disjoint sets (i.e Men or Women)
  to reveal their true preference lists.

The second paper proves that "students cannot improve their fate by lying about their preferences." I am still in the process of trying to understand the proves in this paper.

Feb 16 (week 7)

Feb 23 (week 8)

Mar 1 (week 9)

Mar 8 (week 10)