Gale and Shapley have an algorithm for finding a stable marriage in a system of preferences. Recently, Dubins and Freedman have extended this result by showing the theorem that honest is the best policy, that is, no coalition of boys can simultaneously improve their fates by lying about their preferences. Their algorithm is quite complicated and therefore the main object here is to give a short proof of this #x201C;Honest Theorem#x201D;.
展开▼