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)
- Kleinberg and Tardos, Chapter 1, Problem 3, page 22-23.
- Kleinberg and Tardos, Chapter 1, Problem 5, pages 24-25.
- 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?)
-
- Kleinberg and Tardos, Chapter 2, Problem 2, page 67.
- Kleinberg and Tardos, Chapter 2, Problem 4, page 67-68.
- Extra credit: Kleinberg and Tardos, Chapter 1, Problem 8, pages 27-28.
- 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.