Advanced Search
MyIDEAS: Login to save this paper or follow this series

Manipulationsanreize im Gale-Shapley-Algorithmus: Ein Literaturüberblick


Author Info

  • Hüber, Frank
Registered author(s):


    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. -- 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.

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL:
    Download Restriction: no

    Bibliographic Info

    Paper provided by Social Science Research Center Berlin (WZB) in its series Discussion Papers, Research Unit: Market Behavior with number SP II 2011-203.

    as in new window
    Date of creation: 2011
    Date of revision:
    Handle: RePEc:zbw:wzbmbh:spii2011203

    Contact details of provider:
    Postal: Reichpietschufer 50, 10785 Berlin, Germany
    Phone: ++49 - 30 - 25491 - 0
    Fax: ++49 - 30 - 25491 - 684
    Web page:
    More information through EDIRC

    Related research

    Keywords: Matching; university admission; manipulation; strategic behavior;

    Find related papers by JEL classification:

    This paper has been announced in the following NEP Reports:


    References listed on IDEAS
    Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
    as in new window
    1. Sebastian Braun & Nadja Dwenger & Dorothea Kübler, 2007. "Telling the Truth May Not Pay Off: An Empirical Study of Centralised University Admissions in Germany," SFB 649 Discussion Papers SFB649DP2007-070, Sonderforschungsbereich 649, Humboldt University, Berlin, Germany.
    2. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, The MIT Press, edition 1, volume 1, number 0262650401, December.
    3. Sertel, Murat R. & Ozkal-Sanver, Ipek, 2002. "Manipulability of the men- (women-) optimal matching rule via endowments," Mathematical Social Sciences, Elsevier, Elsevier, vol. 44(1), pages 65-83, September.
    4. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, American Economic Association, vol. 99(3), pages 608-27, June.
    5. Sebastian Braun & Nadja Dwenger & Dorothea Kübler, 2008. "Studienplatzvergabe: die cleversten Bewerber kommen zum Zug," DIW Wochenbericht, DIW Berlin, German Institute for Economic Research, vol. 75(16), pages 198-202.
    Full references (including those not matched with items on IDEAS)



    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.


    Access and download statistics


    When requesting a correction, please mention this item's handle: RePEc:zbw:wzbmbh:spii2011203. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (ZBW - German National Library of Economics).

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.