IDEAS home Printed from https://ideas.repec.org/a/spr/jogath/v25y1996i2p161-76.html
   My bibliography  Save this article

Canonical Monotone Decompositions of Fractional Stable Matchings

Author

Listed:
  • Abeledo, Hernan G
  • Blum, Yosef
  • Rothblum, Uriel G

Abstract

The paper continues recent work that introduced algebraic methods for studying the stable marriage problem of Gale and Shapley (1962). Vande Vate (1989) and Rothblum (1992) identified a set of linear inequalities which define a polytope whose extreme points correspond to the stable matchings. Points in the polytope are called fractional stable matchings. Here we identify a unique representation of fractional stable matchings as a convex combination of stable matchings that are arrangeable in a man-decreasing order. We refer to this representation and to a dual one, in terms of woman-decreasing order, as the canonical monotone representations. These representations can be interpreted as time-sharing stable matchings where particular stable matchings are used at each time-instance but the scheduled stable matchings are (occasionally) switched over time. The new representations allow us to extend, in a natural way, the lattice structure of the set of stable matchings to the set of all fractional stable matchings.

Suggested Citation

  • Abeledo, Hernan G & Blum, Yosef & Rothblum, Uriel G, 1996. "Canonical Monotone Decompositions of Fractional Stable Matchings," International Journal of Game Theory, Springer;Game Theory Society, vol. 25(2), pages 161-176.
    • Handle: RePEc:spr:jogath:v:25:y:1996:i:2:p:161-76
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Neme, Pablo & Oviedo, Jorge, 2021. "On the set of many-to-one strongly stable fractional matchings," Mathematical Social Sciences, Elsevier, vol. 110(C), pages 1-13.
    2. Pavlos Eirinakis & Dimitrios Magos & Ioannis Mourtos & Panayiotis Miliotis, 2014. "Polyhedral Aspects of Stable Marriage," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 656-671, August.
    3. Fleiner, Tamas, 2003. "On the stable b-matching polytope," Mathematical Social Sciences, Elsevier, vol. 46(2), pages 149-158, October.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jogath:v:25:y:1996:i:2:p:161-76. See general information about how to correct material in RePEc.

    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.

    We have no bibliographic references for this item. You can help adding them by using 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.