Проблема стабільних шлюбів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Проблема стабільних шлюбів (англ. Stable Matching Problem або SMP) — математична задача знаходження стабільної відповідності між членами двох множин елементів згідно з їхніми перевагами для кожного елемента. Відповідності — це поєднання елементів однієї множини з елементами іншої. Відповідності є стабільним, коли не існує жодної альтернативи спаровування (A, B). Тобто, нема інших елементів, які б краще підійшли до елементів А і В.

Формулювання[ред. | ред. код]

Проблема стабільного шлюбу зазвичай сформулюється так: Уявимо, що існує n чоловіків та n жінок, і кожна людина ранжує всіх членів протилежної статі унікальним номером від 1 до N в порядку надання переваг. Якщо одружуються чоловіки і жінки разом так, що немає двох людей протилежної статі, які б були кращі одне для одного, ніж їхні нинішні партнери, то всі шлюби «стабільний». Стабільне одруження називається оптимальним по відношенню до чоловіків, якщо не існує іншого такого стабільного одруження, в якому якомусь чоловікові відповідала жінка, якій він надавав би більше переваг, ніж та, яка присвоєна йому на початку. Алгоритми пошуку вирішення проблеми стабільного шлюбу застосовується в різних реальних ситуаціях, мабуть, найвідомішим з яких є в розподіл випускників медичних закладів та їхніх перших лікарень.[1]

Розв'язання[ред. | ред. код]

У 1962 році Девід Гейл і Ллойда Шеплі довели, що для будь-якої рівної кількості чоловіків і жінок завжди можна вирішити задачу SMP і зробити всі шлюби стабільними. Вони представили алгоритм для цього.[2][3]

Алгоритм Гейл-Шеплі включає в себе ряд «раундів» (або «ітерацій»), де кожний чоловік не пов'язаний зобов'язанням «робити пропозицію» найбільш привабливій жінці, якій він ще не пропонував. Кожна жінка після обмірковування пропозицій всіх її женихів говорить одному, кому найбільше віддає перевагу «Може бути», а всім іншим — «Ні». У цей час вона віддає перевагу одному найкращому на її погляд нареченому, а наречений у цей час найбільше віддає перевагу нареченій.

У першому раунді:

a) не пов'язаний зобов'язанням чоловік робить пропозицію жінці, якій він найбільше віддає перевагу: b) кожна жінка відповідає: «може бути» одному найкращому, і «ні» всім іншим.

У наступному раунді:

a) не пов'язаний зобов'язанням чоловік робить пропозицію жінці, якій він найбільше віддає перевагу та якій ще не робив пропозицію (незалежно від того, чи зайнята вже жінка).
b) кожна жінка відповідає: «може бути» одному, хто найбільше сподобається (незалежно від того, чи існує в неї вже партнер) і відхиляє решту.

Тимчасовий характер зобов'язань зберігає право вже зайнятій жінці шукати кращого партнера. Цей алгоритм гарантує, що:

  • Кожен виходить заміж
  • Після того, як жінка стає зайнятою, вона завжди зайнята кимось. Так що, врешті-решт, не може бути чоловіка і жінки, які були незадіяним, так як чоловік, мабуть, зробив би пропозицію жінці, і будучи задіяною, але не зайнятою, вона повинна була б сказали «так».
  • Шлюби є стабільними
  • Усі чоловіки роблять пропозиції жінкам, які найбільше подобаються, а жінки з цих пропозицій обирають найкращих для себе чоловіків.

Алгоритм[ред. | ред. код]

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}

Оптимальність рішення[ред. | ред. код]

У той час як рішення стійке, воно не обов'язково оптимальне з точки зору всіх осіб. Традиційна форма алгоритму є оптимальною для ініціатора пропозиції. Оптимальне рішення ініціатора може бути або може не бути оптимальним для рецензента пропозиції. Як приклад можна розглянути наступну ситуацію:
Є три наречені чоловіки (A, B, C) і три наречені жінки (X, Y, Z), які мають переваги: 

 A: YXZ  B: ZYX  C: XZY  X: BAC  Y: CBA  Z: ACB

Існує 3 стабільні рішення для цієї ситуації:

  • Ініціатори пропозиції отримати свій найкращій вибір, а рецензенти - найгірший (AY, BZ, CX)
  • Всі учасники отримують другий найкращий вибір (AX, BY, CZ)
  • Ініціатори отримали найгірший свій вибір, у той час як рецензенти обрали найкраще для себе (AZ, BX, CY)

Всі три поєднання є стабільними, оскільки нестабільність вимагає, щоб учасники були щасливішими з альтернативними партнерами. Обрання ініціаторами найкращих на їхній погляд альтернатив гарантує, що поєднання є стабільними, тому що вони були б незадоволені будь-якою іншою пропонованою альтернативою. Якщо надається перевага другій найкращій альтернативі, це гарантує, що будь-яке інше поєднання не буде подобатись одній зі сторін. Алгоритм сходиться в єдиному раунді, тому що кожен рецензент отримує рівно одну пропозицію, і тому обирає, що пропозиція є його найкращим вибором. Ця асиметрія оптимальності спричиняється тим фактом, що у ініціаторів є весь набір, щоб вибрати, а рецензенти пропозиції вибирають з обмеженого набору женихів в будь-який момент часу.

Реалізація алгоритму[ред. | ред. код]

Реалізація мовою Scala: 

 /**
  * Problem description
  *
  * Given an equal number of men and women to be paired for marriage,
  * each man ranks all the women in order of his preference and each women ranks all the men in order of her preference.
  *
  * A stable set of engagements for marriage is one where no man prefers a women over the one he is engaged to,
  * where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages,
  * there would be no reason for the engagements between the people to change.
  * 
  * @author Oleksandr KOL Kucher
  */
 object Marriage {
 
   /**
    * solves Marriage problem
    * @param boyPrefers - map of all Boys and their prefers
    * @param girlPrefers - map of all Girls and their prefers
    * @return list of couples
    */
   def solve(boyPrefers: Map[String, Array[String]], girlPrefers: Map[String, Array[String]]): List[Couple] = {
     val (boys, girls) = mapsToPersons(boyPrefers, girlPrefers)
     searchCouples(boys, girls)
   }
 
   /**
    * verifies if created couples stable
    * @param boyPrefers - map of all Boys and their prefers
    * @param girlPrefers - map of all Girls and their prefers
    * @param couples - list of created couples
    * @return true or false
    */
   def isStable(boyPrefers: Map[String, Array[String]], girlPrefers: Map[String, Array[String]], couples: List[Couple]): Boolean = {
     val (boys, girls) = mapsToPersons(boyPrefers, girlPrefers)
     val boyCouple: Map[String, Girl] = couples.map(c => c.boy.name -> c.girl).toMap
     val girlCouple: Map[String, Boy] = couples.map(c => c.girl.name -> c.boy).toMap
 
     boys.foreach(b => b.fiance = boyCouple(b.name))
     girls.foreach(g => g.fiance = girlCouple(g.name))
 
     for(boy <- boys){
       for(girl <- girls){
         if(boy.isPrefers(girl) && girl.isPrefers(boy)){
           return false
         }
       }
     }
     true
   }
 
   /**
    * gets two maps with names and prefers (one for boys and one for girls) 
    * and create for each person his/her own object with his/her own prefers
    * 
    * @param boyPrefers - map with all boys' prefers
    * @param girlPrefers - map with all girls' prefers
    * @return tuple with list of Boy and list of Girl that have all their prefers
    */
   private def mapsToPersons(boyPrefers: Map[String, Array[String]], girlPrefers: Map[String, Array[String]]): (List[Boy], List[Girl]) = {
     val (boyNames, girlNames) = (boyPrefers.keySet.toList, girlPrefers.keySet.toList)
     val (boysMap, girlsMap) = (boyNames.map(name=> name -> new Boy(name)).toMap, girlNames.map(name => name -> new Girl(name)).toMap)
 
     boyNames.foreach(name => boysMap(name).prefers = boyPrefers(name).map(gName => girlsMap(gName)))
     girlNames.foreach(name => girlsMap(name).prefers = girlPrefers(name).map(gName => boysMap(gName)))

     (boysMap.values.toList, girlsMap.values.toList)
   }
 
   /**
    * Searches all couples and return list of them
    * @param boys - list of all Boys
    * @param girls - list of all Girls
    */
   private def searchCouples(boys: List[Boy], girls: List[Girl]): List[Couple] = {
     /**
      * makes couples from Boys and Girls with using Girls' boyfriends
      * @param girls - list of Girls
      * @param couples - list of created couples
      */
     def toCouples(girls: List[Girl], couples: List[Couple]): List[Couple] = {
       if(girls.isEmpty) couples
       else toCouples(girls.tail, couples ::: List(new Couple(girls.head.fiance, girls.head)))
     }
     iterateBoys(boys)
     toCouples(girls, List())
   }
 
   /**
    * gets all free boys and runs for each of them function `@link project.marriageProblem.Marriage.iterateBoyPrefers`
    * @param freeBoys - list of Boys which has not a couple yet
    */
   private def iterateBoys(freeBoys: List[Boy]): Unit = {
     if(freeBoys.nonEmpty) iterateBoys(iterateBoyPrefers(freeBoys.head, freeBoys.head.prefers, freeBoys.tail))
   }
 
   /**
     *
     * @param boy - current free Boy
     * @param girls - prefers of current free Boy
     * @param freeBoys - rest free Boys
     * @return new list of free boys
    *         it can be:
    *         1. empty
    *         2. contains rest free boys
    *         3. contains rest free boys with one boy which has couple and was replaced by current boy
     */
   private def iterateBoyPrefers(boy: Boy, girls: Array[Girl], freeBoys: List[Boy]): List[Boy] = {
     if(girls.isEmpty) freeBoys
     else if(null == girls.head.fiance){
       girls.head.fiance = boy
       boy.fiance = girls.head
       boy.prefers = girls.tail
       freeBoys
     } else if(girls.head.prefers.indexOf(girls.head.fiance) > girls.head.prefers.indexOf(boy)){
       val boyfriend: Boy = girls.head.fiance
       girls.head.fiance = boy
       boy.fiance = girls.head
       boy.prefers = girls.tail
       freeBoys ::: List(boyfriend)
     } else {
       boy.prefers = girls.tail
       iterateBoyPrefers(boy, girls.tail, freeBoys)
     }
   }
 } 

 /**
  * Class represents Girl
  * @param name - name of Girl
  * @param fiance - Girl's boyfriend
  * @param prefers - Girl's prefers
  */
 class Girl(val name: String, var fiance: Boy, var prefers: Array[Boy]) {
 
   def this(name: String, prefers: Array[Boy]) = this(name, null, prefers)
 
   def this(name: String) = this(name, null, null)
 
   override def toString: String = name
 
   def isPrefers(other: Boy): Boolean =
     prefers.indexWhere(p => p.name == other.name) < prefers.indexWhere(p => p.name == fiance.name)
 }
 
 /**
  * Class represents Boy
  * @param name - name of Boy
  * @param fiance - Boy's girlfriend
  * @param prefers - Boy's prefers
  */
 class Boy(val name: String, var fiance: Girl, var prefers: Array[Girl]) {
 
   def this(name: String, prefers: Array[Girl]) = this(name, null, prefers)
 
   def this(name: String) = this(name, null)
 
   override def toString: String = name
 
   def isPrefers(other: Girl): Boolean =
     prefers.indexWhere(p => p.name == other.name) < prefers.indexWhere(p => p.name == fiance.name)
 }
 
 class Couple(val boy: Boy, val girl: Girl){
   override def toString: String = boy.name + " -> " + girl.name
 }

 object Test extends App {
   val boyPrefers: Map[String, Array[String]] = Map(
     "abe" -> Array("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
     "bob" -> Array("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
     "col" -> Array("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
     "dan" -> Array("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
     "ed" -> Array("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
     "fred" -> Array("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
     "gav" -> Array("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
     "hal" -> Array("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
     "ian" -> Array("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
     "jon" -> Array("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope")
   )
   val girlPrefers: Map[String, Array[String]] = Map(
     "abi" -> Array("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
     "bea" -> Array("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
     "cath" -> Array("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
     "dee" -> Array("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
     "eve" -> Array("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
     "fay" -> Array("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
     "gay" -> Array("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
     "hope" -> Array("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
     "ivy" -> Array("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
     "jan" -> Array("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan")
   )
 
   println("Test Solving Marriage Problem:")
   val couples: List[Couple] = Marriage.solve(boyPrefers, girlPrefers).sortBy(_.boy.name)
   couples.foreach(println)
   println("Stable = " + Marriage.isStable(boyPrefers, girlPrefers, couples) + "\n")
 
   println("Switching fred & jon's partners")
   val (fred, jon) = (couples(5), couples(9))
   val switchedCouples: List[Couple] = couples.updated(5, new Couple(fred.boy, jon.girl)).updated(9, new Couple(jon.boy, fred.girl))
   switchedCouples.foreach(println)
   println("Stable = " + Marriage.isStable(boyPrefers, girlPrefers, switchedCouples))
 }

Результат: 

Solving Marriage Problem:
abe -> ivy
bob -> cath
col -> dee
dan -> fay
ed -> jan
fred -> bea
gav -> gay
hal -> eve
ian -> hope
jon -> abi
Stable = true

Switching fred & jon's partners
abe -> ivy
bob -> cath
col -> dee
dan -> fay
ed -> jan
fred -> abi
gav -> gay
hal -> eve
ian -> hope
jon -> bea
Stable = false

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

  1. ↑ Stable Matching Algorithms
  2. ↑ D. Gale and L. S. Shapley: «College Admissions and the Stability of Marriage», American Mathematical Monthly 69, 9-14, 1962.
  3. ↑ Harry Mairson: «The Stable Marriage Problem», The Brandeis Review 12, 1992 (online).

Джерела[ред. | ред. код]

  • Dubins, L., and Freedman, D. (1981). Machiavelli and the Gale–Shapley algorithm. The American Mathematical Monthly, 88(7), 485—494.
  • Kleinberg, J., and Tardos, E. (2005) Algorithm Design, Chapter 1, pp 1–12. See companion website for the Text [1].
  • Knuth, D. E. (1976). Marriages stables. Montreal: Les Presses de I'Universite de Montreal.
  • Roth, A. E. (1984). The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92, 991—1016.
  • Roth, A. E., and Sotomayor, M. A. O. (1990). Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press.
  • Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. See Section 10.6.4; downloadable free online.
  • Schummer, J., and Vohra, R. V. (2007). Mechanism design without money. In Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V. (Eds.). (2007). Algorithmic game theory. Cambridge, UK: Cambridge University Press, chapter 10, 243—265.

Посилання[ред. | ред. код]


На цю статтю не посилаються інші статті Вікіпедії.
Будь ласка розставте посилання відповідно до прийнятих рекомендацій.
Отримано з https://uk.wikipedia.org/w/index.php?title=Проблема_стабільних_шлюбів&oldid=39926179