  This thesis was submitted as partial fulfillment of the requirements for the
Masters Degree in the Department of Computer Science, Bar-Ilan University.
  The final step in getting an Israeli M.D. is performing a year-long
internship in one of the hospitals in Israel. Internships are decided upon by a
lottery, which is known as "The Internship Lottery". In 2014 we redesigned the
lottery, replacing it with a more efficient one. The new method is based on
calculating a tentative lottery, in which each student has some probability of
getting to each hospital. Then a computer program "trades" between the
students, where trade is performed only if it is beneficial to both sides. This
trade creates surplus, which translates to more students getting one of their
top choices. The average student improved his place by $0.91$ seats. The new
method can improve the welfare of medical graduates, by giving them more
probability to get to one of their top choices. It can be applied in internship
markets in other countries as well.
  This thesis presents the market, the redesign process and the new mechanism
which is now in use. There are two main lessons that we have learned from this
market. The first is the "Do No Harm" principle, which states that (almost) all
participants should prefer the new mechanism to the old one. The second is that
new approaches need to be used when dealing with two-body problems in object
assignment. We focus on the second lesson, and study two-body problems in the
context of the assignment problem. We show that decomposing stochastic
assignment matrices to deterministic allocations is NP-hard in the presence of
couples, and present a polynomial time algorithm with the optimal worst case
guarantee. We also study the performance of our algorithm on real-world and on
simulated data.
