The Marriage Problem
https://web.stanford.edu/~niederle/Palgrave%20Matching.Approved.pdf
The paper linked above addresses, amongst others, the issue of the marriage problem, which is a two-sided matching problem. This is where agents on both sides have preferences for a matching. According to the Deferred Acceptance Algorithm developed by Gale and Shapely (1962), there exists a stable matching in every marriage market where men propose if men continue to propose to women starting from their first preference and working down their rank ordering, and only stopping when a woman accepts the most preferred proposal. It is here that the question of stating true preferences comes into play, which is the central question our class dealt with during the topic. According to Roth and Sotomayor, the Impossibility Theorem states that it is not possible that a stable matching exists where both agents’s dominant strategy is stating their true preferences, or bidding truthfully. The Deferred Acceptance Algorithm, however, makes it the dominant strategy to bid truthfully for a man in the case of the marriage problem. This finding is similar to other matching models, such as a many-to-one matching (the example in the paper is of an individual seeking 1 job, and firms seeking multiple employees), where firms do not have a dominant strategy but it is a dominant strategy for job seekers to bid truthfully. This is because in the real world, it is difficult to form strict preferences over options, and so firms often hire based on qualifications but also interest in the firm (i.e guessing the job seeker’s strict preference).
In class, we only discussed one-sided matching problems, where often buyers and items could be matched any which way, even if it was not efficient. There is only one active participant in the market- the buyer/seller. The marriage problem above, stemming from two-sided matching markets opens a whole new area of exploration, where matching markets, auctions and preferences all intertwine.