Note on an Auction Procedure for a Matching Game in Polynomial Time

Hochstättler, Winfried and Nickel, Robert (2005) Note on an Auction Procedure for a Matching Game in Polynomial Time.
Technical Report , 7 p.

Abstract

We derive a polynomial time algorithm to compute a stable solution in a mixed matching market from an auction procedure as presented by Eriksson and Karlander. As a special case we derive an O(nm) algorithm for bipartite matching that does not seem to have appeared in the literature yet.


Actions:
Download: [img] Postscript
Download (233kB) | Preview
Download: [img] PDF
Download (134kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 5 (Google Scholar) |
Uncontrolled Keywords: assignment game core auction algorithms stable matching
Subjects:
  • 91-XX Game theory, economic, social and behavioral sciences > 91Bxx Mathematical economics > 91B68 Matching models

  • 91-XX Game theory, economic, social and behavioral sciences > 91Axx Game theory > 91A12 Cooperative games

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
    Mathematical Institute > Prof. Dr. Faigle
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2005-491
    Depositing User: Winfried Hochstättler
    Date Deposited: 27 Oct 2005 00:00
    Last Modified: 19 Dec 2011 09:44
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/491