Алгоритм Гейла-Шеплі
Алгоритм Гейла-Шеплі розв'язує проблему стабільного шлюбу: як зіставити дві групи (наприклад, лікарів-інтернів до лікарень, учнів до шкіл) таким чином, щоб жодна пара не віддавала перевагу одне одному над призначеними партнерами. Запропонований Девідом Гейлом та Ллойдом Шеплі у 1962 році, алгоритм гарантує стабільне зіставлення за поліноміальний час за допомогою процесу відкладеного прийняття, де одна сторона послідовно робить пропозиції, а інша сторона відповідає, переглядаючи вибір у міру надходження кращих варіантів.
Читати метод повністю
Увійдіть із безкоштовним обліковим записом, щоб прочитати цей розділ.
Карта методів
Околиця споріднених методів — виберіть вузол, щоб дослідити.
Джерела
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. DOI: 10.1080/00029890.1962.11989827 ↗
- Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628. DOI: 10.1287/moor.7.4.617 ↗
Як цитувати цю сторінку
ScholarGate. (2026, June 3). Gale-Shapley Stable Marriage Algorithm. ScholarGate. https://scholargate.app/uk/game-theory/gale-shapley-algorithm
Який метод?
Поставте цей метод поруч із його найближчими спорідненими й читайте їх пліч-о-пліч — бібліотека викладає книги на стіл; вибір за вами.
- Байєсів рівноваги НешаТеорія ігор↔ порівняти
- Модель «Принципал-Агент»Теорія ігор↔ порівняти
- Найкращі торгові циклиТеорія ігор↔ порівняти
- Механізм ВікріТеорія ігор↔ порівняти
Згадується в
Помітили помилку на цій сторінці? Повідомте про неї або запропонуйте виправлення →