Презентация на тему Задача о поиске устойчивых паросочетаний. (Лекция 11)

году, когда два экономиста-математика,
Дэвид Гейл и Ллойд Шепли, задались

вопросом:

Можно ли спланировать процесс поступления в колледж (или приема на работу), который был бы саморегулируемым (self-enforcing)?

American Mathematical Monthly в статье под названием «Поступление в

колледж и стабильность браков».
Элвин Рот разработал очень много практических механизмов, основанных на алгоритме Гейла-Шелли.
Ллойд Шепли и Элвин Рот в 2012 году получили Нобелевскую премию по экономике «За теорию стабильного распределения и практики устройства рынков».

интернов по больницам
Набор спортсменов в команды
Набор стажеров в компании
Наем

клерков в суды
Подбор школ для детей
Доноры и реципиенты

на летнюю практику.
В процессе обработки заявок важно взаимодействие двух

разных сторон: компаний (нанимателей) и студентов (кандидатов).
Каждый кандидат упорядочивает список компаний в порядке своих предпочтений.
Каждая компания - после поступления заявок - формирует свой порядок предпочтений для кандидатов, подавших заявки.
На основании этих предпочтений компании обращаются с предложениями к некоторым из своих кандидатов.
Кандидаты решают, какое из полученных предложений стоит принять.

телекоммуникационной компании CluNet. Через несколько дней начинающая компания WebExodus,

которая тянула с принятием нескольких окончательных решений, связывается с Раджем и тоже предлагает ему летнюю практику. Вообще-то, с точки зрения Раджа, вариант с WebExodus предпочтительнее CluNet - скажем, из-за непринужденной атмосферы и творческого азарта. Этот поворот заставляет Раджа отказаться от предложения CluNet и пойти в WebExodus. Лишившись практиканта, CluNet предлагает работу одному из запасных кандидатов, который мгновенно отменяет свое предыдущее согласие на предложение мегакорпорации Babelsoft.

отправиться в Babelsoft. Но услышав историю Раджа, она звонит

в WebExodus и говорит: «Знаете, я бы предпочла провести это лето в вашей фирме, а не в Babelsoft». Отдел кадров WebExodus охотно верит; более того, заглянув в заявку Челси, они понимают, что она перспективнее другого студента, у которого уже запланирована летняя практика. И если компания WebExodus не отличается особой деловой принципиальностью, она найдет способ отозвать свое предложение другому студенту и возьмет Челси на его место.

действовать, исходя из их собственных интересов, весь процесс может

быть нарушен.
Многие участники - как кандидаты, так и наниматели - могут оказаться недовольны как самим процессом, так и его результатом.

набора предпочтений по кандидатам и нанимателям распределить кандидатов по

нанимателям так, чтобы для каждого нанимателя E и каждого кандидата A, который не был принят на работу к E, выполнялось по крайней мере одно из следующих двух условий?
Каждый из кандидатов, принятых E на работу, с его точки зрения, предпочтительнее A.
С точки зрения A, его текущая ситуация предпочтительнее работы на нанимателя E.

очень похожая задача использовалась Национальной программой распределения студентов-медиков по

больницам.
Более того, эта система с относительно незначительными изменениями продолжает применяться и в наши дни.

Другие источники происхождения задачи

из n компаний, а каждая компания хочет принять на

работу одного кандидата.

Упрощенная постановка задачи

n мужчин и множество W = {w1, ..., wn

} из n женщин.
Паросочетание (марьяж) S представляет собой множество пар из M × W, обладающее тем свойством, что каждый элемент M и каждый элемент W встречается не более чем в одной паре в S.
Идеальным паросочетанием S' называется паросочетание, при котором каждый элемент M и каждый элемент W встречается ровно в одной паре из S'

Частный случай задачи

женщин; мы говорим, что m предпочитает w женщине w',

если m присваивает w более высокую оценку, чем w'.
Мы будем называть упорядоченную систему оценок m его списком предпочтений.
«Ничьи» в оценках запрещены.
Аналогичным образом каждая женщина назначает оценки всем мужчинам.

Понятие предпочтений

устойчивым, если оно (1) идеально и (2) не содержит

неустойчивости в отношении S.
Вопросы:
Существует ли устойчивое паросочетание для каждого набора списков предпочтений?
Можно ли эффективно построить устойчивое паросочетание для имеющегося списка предпочтений (если оно существует)?

c, d, e}
Предпочтения:


Мужчины:



Женщины:


Пример 3

предложения. Мужчины делают предложения (первый столбец матрицы предпочтений), женщины

в соответствии с приоритетом выбирают.

столбец матрицы предпочтений).

женщине a и отвергнут ею.

женщиной e принято, а мужчина 4 ею отвергнут.

устойчивое паросочетание:

1 → e, 2 → a, 3 →

b, 4 → d, 5 → c

Начальные предложения женщин.

паросочетание, причем оно совпадает с тем, когда предложения делали

мужчины, а женщины выбирали.

[1..n, 1..n] Of Integer; {Матрицы предпочтений}
indexMan : Array

[1.. n] Of Integer; {Номер предложения i-го мужчины}
married : Array [1.. n] Of Integer; {Результат, married[i] определяет номер мужчины, с которым женщина i сочетается законным браком}
freeman : Array [1..n] Of Boolean; {Признак занятости мужчин. Если freeman[i]=True, то мужчина с номером i свободен}

Do Begin
married[i] := -1; {Женщины не заняты}
indexMan[i]

:= 1; {Каждый мужчина делает предложение первой женщине из своего списка предпочтений}
freeMan[i] := True; {Мужчины свободны}
End;

- № мужчины, cw - № женщины}
Begin
While

Not Result Do {Пока не найдено паросочетание}
For i := 1 To n Do
If freeMan[i] Then Begin {i-ый мужчина свободен}
cw := man[i, indexMan[i]];
WriteLn('мужчина ', i, ' делает предложение ', cw, ' женщине');
If (married[cw] = -1) Then Begin {Женщина свободна}
married[cw] := i;
freeMan[i] := False;
End
Else SelectW(i,cw); {Женщина занята и вынуждена делать выбор}
End;
End;

структурах данных осуществляется подсчетом количества сформировавшихся пар. Если оно

равно значению n, то паросочетание найдено.
Function Result : Boolean;
Var i, k : Integer;
Begin
k := 0;
For i := 1 To n Do
If (married[i] <> -1) Then k := k+1;
If k = n Then Result := True
Else Result := False;
End;

и ищем, кто встретится раньше: ее жених на данный

момент или сделавший только что предложение i-ый мужчина.
Procedure SelectW(i, cw: Integer);
{i - № мужчины, cw - № женщины}
Var j : Integer;{№ приоритета у женщины cw}
pp : Boolean;{женщина cw сделала выбор}
Begin
j := 1;
pp := False;


End;

Цикл по j

Begin
If (women[cw, j] = married[cw]) Then Begin

{жених в приоритете}
indexMan[i] := indexMan[i] + 1; {i-му мужчине надо выбирать следующую женщину по его приоритету}
pp := True;
end
Else If (women[cw, j] = i) Then Begin {Женщина отдает предпочтение мужчине с номером i}
indexMan[married[cw]] := indexMan[married[cw]] + 1; {жениху женщины cw надо выбирать следующую женщину по его приоритету}
freeMan[married[cw]] := True; {жених становится свободным}
freeMan[i] := False; {i-ый мужчина становится занятым}
married[cw] := i;{i становится женихом для cw}
pp := True;
End;
j :=j + 1;
End;

Женщины:


Задача 1