CSE 421 Assignment #1
Autumn 2008

Due: Friday, October 3, 2008.

Reading Assignment: Kleinberg and Tardos Chapters 1 and 2.

Problems: (see the Grading Guidelines before answering)

  1. Kleinberg and Tardos, Chapter 1, Problem 3, page 22-23.

  2. Kleinberg and Tardos, Chapter 1, Problem 5, pages 24-25.

  3. Kleinberg and Tardos, Chapter 1, Problem 7, pages 26-27.
    (HINT: Try to set up a stable matching problem that will solve this problem. How should the preferences be determined? Why will that work?)

    1. Kleinberg and Tardos, Chapter 2, Problem 2, page 67.

    2. Kleinberg and Tardos, Chapter 2, Problem 4, page 67-68.

  5. Extra credit: Kleinberg and Tardos, Chapter 1, Problem 8, pages 27-28.

  6. Extra credit: The previous problem considered whether or not a woman with knowledge of everyone else's preferences could improve her outcome by lying about her preference list. This is exactly the same problem except for the men. Can a man improve his match by proposing to women in a different order from his true preference list? If so, give an example; if not, argue why not.