Efficient Mechanism Design

• Theorem: in any VCG mechanism it is weakly dominant to tell the truth. hence the outcome is efficient, as long as we ignore the sum of net transfers
• Vickrey Auction: each agent submits K bids, highest K bids win, each player pays the sum of the bids submitted by others that would have won had they not participated in the auction
• Gale-Shapley deferred acceptance algorithm: each tutor names his or her favourite college. Colleges demanded by multiple tutors provisionally pick a tutor. Tutors not picked by a college choose again, except they cannot choose a college that already rejected them. The loop is repeated until each tutor is allocated to a college
• if every participant behaves truthfully, then the Gale-Shapley algorithm leads to the stable matching optimal for the side that makes the initial demands
• It is a dominant strategy for the side that makes the initial demands to tell the truth in the Gale-Shapley algorithm
• If there are multiple stable matchings then the receiving side can manipulate to obtain their favourite pairing
• If there are multiple stable matchings, then there is no stable matching algorithm that is impossible to manipulate
• Top trading cycle algorithm: each tutor points to their 'top' most-preferred college (could be their default assigned one) and each college points to their default tutor. Identify cycles; carry out the suggested trades and remove the participants. Repeat until complete.
• in the TTC mechanism truth-telling is dominant, the outcome is stable