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

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

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

В математиці і комп’ютерній науці, проблема стабільних шлюбів (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
    whilefree 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) 

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

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

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

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

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

Зовнішні посилання[ред.ред. код]