{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:44Z","timestamp":1759063544456},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5674,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1993,3]]},"abstract":"<jats:p>In a set of even cardinality<jats:italic>n<\/jats:italic>, each member ranks all the others in order of preference. A stable matching is a partition of the set into<jats:italic>n<\/jats:italic>\/2 pairs, with the property that no two unpaired members both prefer each other to their partners under matching. It is known that for some problem instances no stable matching exists. In 1985, Irving found an<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) two-phase algorithm that would determine, for any instance, whether a stable matching exists, and if so, would find such a matching. Recently, Tan proved that Irving's algorithm, with a modified second phase, always finds a stable cyclic partition of the members set, which is a stable matching when each cycle has length two. In this paper we study a likely behavior of the algorithm under the assumption that an instance of the ranking system is chosen uniformly at random. We prove that the likely number of basic steps,<jats:italic>i.e.<\/jats:italic>the individual proposals in the first phase and the rotation eliminations, involving subsets of members in the second phase, is<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>), and that the likely size of a rotation is<jats:italic>O<\/jats:italic>((<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>)<jats:sup>1\/2<\/jats:sup>). We establish a \u2018hyperbola law\u2019 analogous to our past result on stable marriages. It states that at every step of the second phase, the product of the rank of proposers and the rank of proposal holders is asymptotic, in probability, to<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>. We show that every stable cyclic partition is likely to be almost a stable matching, in the sense that at most<jats:italic>O<\/jats:italic>((<jats:italic>n<\/jats:italic>log<jats:italic>n<\/jats:italic>)<jats:sup>1\/2<\/jats:sup>) members can be involved in the cycles of length three or more.<\/jats:p>","DOI":"10.1017\/s0963548300000481","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:18:20Z","timestamp":1221218300000},"page":"53-92","source":"Crossref","is-referenced-by-count":9,"title":["On a Random Instance of a \u2018Stable Roommates\u2019 Problem: Likely Behavior of the Proposal Algorithm"],"prefix":"10.1017","volume":"2","author":[{"given":"Boris","family":"Pittel","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000481_ref025","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL052139015X"},{"key":"S0963548300000481_ref024","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005708"},{"key":"S0963548300000481_ref020","first-page":"147","article-title":"Sur la division d'un segment par des points choisis au hasard","volume":"208","author":"Levy","year":"1939","journal-title":"Comptes Rendus Acad. Sci."},{"key":"S0963548300000481_ref019","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010102"},{"key":"S0963548300000481_ref018","volume-title":"Marriages Stables et leurs relations avec d'autres probl\u00e9mes combinatoires","author":"Knuth","year":"1976"},{"key":"S0963548300000481_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-058470-3.50016-1"},{"key":"S0963548300000481_ref015","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1093\/genetics\/97.2.457","article-title":"Some natural viability systems for a multiallelic locus: a theoretical study","volume":"97","author":"Karlin","year":"1981","journal-title":"Genetics"},{"key":"S0963548300000481_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90033-1"},{"key":"S0963548300000481_ref010","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"S0963548300000481_ref016","doi-asserted-by":"publisher","DOI":"10.2307\/3214150"},{"key":"S0963548300000481_ref009","volume-title":"The Stable Marriage Problem, (Structure and Algorithms)","author":"Gusfield","year":"1989"},{"key":"S0963548300000481_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"},{"key":"S0963548300000481_ref014","unstructured":"[14] Irving R. W. (1991) Personal communication."},{"key":"S0963548300000481_ref006","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993799"},{"key":"S0963548300000481_ref003","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"S0963548300000481_ref001","volume-title":"Random Graphs","author":"Bollob\u00e1as","year":"1985"},{"key":"S0963548300000481_ref028","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932966"},{"key":"S0963548300000481_ref004","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729030"},{"key":"S0963548300000481_ref026","volume-title":"Game Theory in the Social Sciences: Concepts and Solutions","author":"Shubik","year":"1982"},{"key":"S0963548300000481_ref021","doi-asserted-by":"publisher","DOI":"10.1145\/362619.362631"},{"key":"S0963548300000481_ref023","doi-asserted-by":"publisher","DOI":"10.1137\/0402048"},{"key":"S0963548300000481_ref007","volume-title":"Probability: Theory and Examples","author":"Durrett","year":"1991"},{"key":"S0963548300000481_ref011","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548300000481_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90028-W"},{"key":"S0963548300000481_ref005","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994313"},{"key":"S0963548300000481_ref002","volume-title":"Probability","author":"Breiman","year":"1968"},{"key":"S0963548300000481_ref013","first-page":"1","volume-title":"On the stable room-mates problem","author":"Irving","year":"1986"},{"key":"S0963548300000481_ref022","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989126"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,16]],"date-time":"2021-09-16T09:51:20Z","timestamp":1631785880000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000481\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,3]]}},"alternative-id":["S0963548300000481"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000481","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,3]]}}}