EconStor >
Wissenschaftszentrum Berlin für Sozialforschung (WZB) >
Discussion Papers, Abteilung Verhalten auf Märkten, WZB >

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10419/54566
  
Title:Manipulationsanreize im Gale-Shapley-Algorithmus: Ein Literaturüberblick PDF Logo
Authors:Hüber, Frank
Issue Date:2011
Series/Report no.:Discussion papers // Wissenschaftszentrum Berlin für Sozialforschung, Schwerpunkt Märkte und Politik: Abteilung Verhalten auf Märkten SP II 2011-203
Abstract:Die von Gale und Shapley in ihrem 1962 veröffentlichten Artikel College Admissions and the Stability of Marriage vorgestellte deferred acceptance procedure hat in der Literatur zu einer umfassenden Diskussion über Zuordnungsverfahren auf zweiseitigen Märkten geführt, die sich mit der Fragestellung beschäftigen, wie die Agenten zweier disjunkter Mengen anhand gegenseitiger Präferenzlisten einander zugeordnet werden können. Dem von Gale und Shapley vorgestellten Algorithmus kam dabei in den letzten Jahren nicht nur in der Theorie eine große Bedeutung zu, sondern auch in der Praxis wird dem Versagen zahlreicher Märkte mit solchen Mechanismen entgegengetreten. Diese Arbeit geht ausführlich auf die von Gale und Shapley entwickelte deferred acceptance procedure und die sich hieraus ergebenden Manipulationsanreize auf zweiseitigen Märkten anhand des Hochzeits- und college admissions-Problems ein. Die im jeweiligen Modell resultierenden Manipulationsanreize werden in vier Arten von Manipulationen gegliedert - die Manipulation anhand von Präferenzen, anhand vorzeitiger bilateraler Vereinbarungen, anhand von endowments und anhand der Quote - und jeweils miteinander verglichen. Dabei wird deutlich, dass weder die deferred acceptance procedure noch irgendein anderes Zuordnungsverfahren, das stabile Zuordnungen ergibt, vollständig immun gegen Manipulationen ist. Anhand zahlreicher Theoreme und Überlegungen kann jedoch gezeigt werden, dass die Anreize oft nur für eine Seite des Marktes existieren und bei größer werdenden Märkten in der Praxis sogar abnehmen.
Abstract (Translated):The deferred acceptance procedure introduced by Gale and Shapley in their article College Admissions and the Stability of Marriage (1962) led to a huge and still growing discussion in the literature on two-sided matching markets. The algorithm didn't only become important in theory but is also often used in practice by policymakers to confront market failure. This paper explains the deferred acceptance procedure in detail and presents a survey on the resulting manipulability on twosided matching markets, e.g., within the marriage and college admissions problem. The incentives to manipulate are categorized in four groups of manipulations - manipulation via preferences, via pre-arranged matches, via endowments and via capacities - and are then compared for both problems. It is shown that there exists no stable matching procedure that is strategy-proof for all agents. But in practice many incentives to manipulate only apply to one side of the market and decrease with the size of the market.
Subjects:Matching
university admission
manipulation
strategic behavior
JEL:C78
D78
I29
Document Type:Working Paper
Appears in Collections:Publikationen von Forscherinnen und Forschern des WZB
Discussion Papers, Abteilung Verhalten auf Märkten, WZB

Files in This Item:
File Description SizeFormat
682517984.pdf333.9 kBAdobe PDF
No. of Downloads: Counter Stats
Download bibliographical data as: BibTeX
Share on:http://hdl.handle.net/10419/54566

Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.