Решетка стабильных соответствий - Lattice of stable matchings

В математика, экономика, и Информатика, то решетка устойчивых паросочетаний это распределительная решетка чьи элементы стабильные совпадения. Для данного экземпляра задачи устойчивого согласования эта решетка обеспечивает алгебраический описание семейства всех решений проблемы. Первоначально он был описан в 1970-х годах Джон Хортон Конвей и Дональд Кнут.^[1][2]

К Теорема Биркгофа о представлении, эту решетку можно представить в виде нижние наборы лежащего в основе частично заказанный набор, а элементам этого набора можно придать конкретную структуру в виде вращений, графики цикла описание изменений между соседними устойчивыми согласованиями в решетке. Семейство всех вращений и их частичный порядок можно построить в полиномиальное время, что приводит к полиномиальному времени для других задач стабильного сопоставления, включая стабильное сопоставление с минимальным или максимальным весом. В Алгоритм Гейла – Шепли можно использовать для построения двух специальных элементов решетки, ее верхнего и нижнего элемента.

Каждую конечную дистрибутивную решетку можно представить в виде решетки устойчивых паросочетаний. Число элементов в решетке может варьироваться от среднего случая ${ Displaystyle е ^ {- 1} п пер п}$ до наихудшего экспоненциального случая. # P-complete.

Фон

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

В общем, может быть много разных стабильных соответствий. Например, предположим, что есть три врача (A, B, C) и три больницы (X, Y, Z), которые имеют следующие предпочтения:

А: YXZ B: ZYX C: XZY

X: BAC Y: CBA Z: ACB

Есть три стабильных решения этого согласования:

1. Доктора получают свой первый выбор, а больницы - третий: AY, BZ, CX.
2. Всем участникам предоставляется второй выбор: AX, BY, CZ.
3. Больницы получают первый выбор, а врачи - третий: AZ, BX, CY.

Решетка стабильных сопоставлений организует этот набор решений для любого случая устойчивого сопоставления, придавая ему структуру распределительная решетка.^[1]

Структура

Частичный заказ на совпадения

Решетка стабильных паросочетаний основана на следующей более слабой структуре: частично заказанный набор элементы которого являются устойчивыми сопоставлениями. Определите операцию сравнения ${ displaystyle leq}$ на стабильных сопоставлениях, где ${ Displaystyle P leq Q}$ тогда и только тогда, когда все врачи предпочитают соответствие ${ displaystyle Q}$ к соответствию ${ displaystyle P}$: либо им назначена одна и та же больница в обоих матчах, либо им назначают лучшую больницу в ${ displaystyle Q}$ чем они в ${ displaystyle P}$. Если врачи не согласны с тем, какое соответствие они предпочитают, тогда ${ displaystyle P}$ и ${ displaystyle Q}$ несравнимы: ни один не ${ displaystyle leq}$ другой. Одна и та же операция сравнения может быть определена таким же образом для любых двух наборов элементов, а не только для врачей и больниц. Выбор того, какой из двух наборов элементов использовать в роли врачей, произвольный. Обмен ролями врачей и больниц меняет порядок каждой пары элементов на противоположный, но не меняет структуру частичного порядка.^[1]

Затем этот порядок придает сопоставлениям структуру частично упорядоченного множества. Для этого он должен подчиняться следующим трем свойствам:

• Для каждого совпадения ${ displaystyle P}$, ${ Displaystyle P leq P}$
• Для каждых двух разных совпадений ${ displaystyle P}$ и ${ displaystyle Q}$, не может быть, чтобы оба ${ Displaystyle P leq Q}$ и ${ Displaystyle Q leq P}$ верны.
• Для каждых трех разных совпадений ${ displaystyle P}$, ${ displaystyle Q}$, и ${ displaystyle R}$, если ${ Displaystyle P leq Q}$ и ${ Displaystyle Q leq R}$, тогда ${ Displaystyle P leq R}$.

Для стабильных сопоставлений все три свойства следуют непосредственно из определения операции сравнения.

Верхний и нижний элементы

Определите наилучшее соответствие элемента ${ displaystyle x}$ стабильного совпадающего экземпляра быть элементом ${ displaystyle y}$ который ${ displaystyle x}$ большинство предпочитает среди всех элементов, которые могут быть сопоставлены ${ displaystyle x}$ в стабильном сопоставлении и аналогичным образом определите наихудшее совпадение. Тогда никакие два элемента не могут иметь одинаковое наилучшее совпадение. Предположим противное. ${ displaystyle x}$ и ${ displaystyle x '}$ как есть ${ displaystyle y}$ как их лучший матч, и это ${ displaystyle y}$ предпочитает ${ displaystyle x}$ к ${ displaystyle x '}$. Затем в стабильном сопоставлении, которое соответствует ${ displaystyle x '}$ к ${ displaystyle y}$ (который должен существовать по определению наилучшего соответствия ${ displaystyle x '}$), ${ displaystyle x}$ и ${ displaystyle y}$ будет нестабильной парой, потому что ${ displaystyle y}$ предпочитает ${ displaystyle x}$ к ${ displaystyle x '}$ и ${ displaystyle x}$ предпочитает ${ displaystyle y}$ любому другому партнеру в любом стабильном матче. Это противоречие показывает, что назначение всех врачей их лучшим совпадениям дает совпадение. Это стабильное соответствие, потому что любая нестабильная пара также будет нестабильной для одного из сопоставлений, используемых для определения наилучших совпадений. Помимо назначения всех врачей на их лучшие матчи, он назначает все больницы на их худшие матчи. При частичном упорядочивании сопоставлений он больше, чем все другие стабильные сопоставления.^[1]

Симметрично, распределение всех врачей с их худшими совпадениями и назначение всех больниц с их лучшими совпадениями дает еще одно стабильное совпадение. В частичном порядке сопоставлений он меньше, чем все другие стабильные сопоставления.^[1]

В Алгоритм Гейла – Шепли дает процесс построения стабильных сопоставлений, который можно описать следующим образом: пока сопоставление не будет достигнуто, алгоритм выбирает произвольную больницу с незаполненной вакансией, и эта больница делает предложение о работе доктору, которого она предпочитает, среди тех, которые у нее есть еще не сделал предложения. Если врач не работает или у него менее предпочтительное назначение, он принимает предложение (и увольняется с другого назначения, если оно существует). Процесс всегда завершается, потому что каждый врач и больница взаимодействуют только один раз. Когда он завершается, результатом является стабильное сопоставление, при котором каждой больнице назначается наилучшее соответствие, а для всех врачей - наихудшие совпадения. Алгоритм, который меняет роли врачей и больниц (в котором безработные врачи отправляют заявки о приеме на работу по своему следующему предпочтению среди больниц, а больницы принимают заявки либо когда у них есть незаполненная должность, либо они предпочитают нового кандидата, увольняя врача, которого они ранее был принят) вместо этого производит стабильное сопоставление, которое назначает всех врачей их лучшим совпадениям и каждой больнице - их худшим совпадениям.^[1]

Решетчатые операции

Учитывая любые два стабильных соответствия ${ displaystyle P}$ и ${ displaystyle Q}$ для того же входа можно сформировать еще два сопоставления ${ displaystyle P vee Q}$ и ${ displaystyle P wedge Q}$ следующим образом:

В ${ displaystyle P vee Q}$, каждый врач получает лучший выбор среди двух больниц, в которых он находится. ${ displaystyle P}$ и ${ displaystyle Q}$ (если они отличаются), и каждая больница получает свой худший выбор.

В ${ displaystyle P wedge Q}$, каждый врач получает худший выбор среди двух больниц, в которые они попадают. ${ displaystyle P}$ и ${ displaystyle Q}$ (если они отличаются), и каждая больница получает свой лучший выбор.

(Одни и те же операции могут быть определены одинаково для любых двух наборов элементов, а не только для врачей и больниц.)^[1]

Тогда оба ${ displaystyle P vee Q}$ и ${ displaystyle P wedge Q}$ Например, невозможно, чтобы два врача имели один и тот же лучший выбор и находились в одной и той же больнице в ${ displaystyle P vee Q}$, поскольку независимо от того, какого из двух врачей предпочитает больница, этот врач и больница составят нестабильную пару в зависимости от того, ${ displaystyle P}$ и ${ displaystyle Q}$ они еще не сопоставлены. Поскольку врачи сопоставлены в ${ displaystyle P vee Q}$, больницы также должны быть сопоставлены. Те же рассуждения симметрично применимы к ${ displaystyle P wedge Q}$.^[1]

Кроме того, оба ${ displaystyle P vee Q}$ и ${ displaystyle P wedge Q}$ Не может быть пары, состоящей из врача и больницы, которые предпочли бы друг друга своему совпадению, потому что одна и та же пара обязательно также будет нестабильной парой по крайней мере для одного из ${ displaystyle P}$ и ${ displaystyle Q}$.^[1]

Свойства решетки

Две операции ${ displaystyle P vee Q}$ и ${ displaystyle P wedge Q}$ сформировать присоединяйся и встречайся операции конечного распределительная решетка.В этом контексте конечная решетка определяется как частично упорядоченный конечный набор в котором существует уникальный минимальный элемент и уникальный максимальный элемент, в котором каждые два элемента имеют уникальный наименьший элемент, больший или равный им обоим (их соединение), и каждые два элемента имеют уникальный наибольший элемент, меньший или равный они оба (их встречаются).^[1]

В случае операций ${ displaystyle P vee Q}$ и ${ displaystyle P wedge Q}$ определено выше, соединение ${ displaystyle P vee Q}$ больше или равно обоим ${ displaystyle P}$ и ${ displaystyle Q}$ потому что он был определен, чтобы дать каждому врачу его предпочтительный выбор, и потому что эти предпочтения врачей определяют порядок сопоставления. Это ниже любого другого соответствия, которое также выше обоих ${ displaystyle P}$ и ${ displaystyle Q}$, потому что любое такое сопоставление должно дать каждому врачу назначенное сопоставление, которое, по крайней мере, не хуже. Таким образом, он соответствует требованиям для операции соединения решетки. Симметрично операция ${ displaystyle P wedge Q}$ соответствует требованиям для выполнения операции.^[1]

Поскольку они определены с использованием поэлементного минимума или поэлементного максимума в порядке предпочтений, эти две операции подчиняются одному и тому же законы распределения подчиняются минимальным и максимальным операциям по линейному порядку: для каждых трех различных сопоставлений ${ displaystyle P}$, ${ displaystyle Q}$, и ${ displaystyle R}$,

${ Displaystyle P клин (Q vee R) = (P клин Q) vee (P клин R)}$

и

${ Displaystyle P vee (Q клин R) = (P vee Q) клин (P vee R)}$

Следовательно, решетка стабильных паросочетаний является распределительная решетка.^[1]

Представление вращениями

Теорема Биркгофа о представлении утверждает, что любая конечная дистрибутивная решетка может быть представлена ​​семейством конечные множества, с пересечением и объединением в качестве операций встречи и соединения и с отношением принадлежности к подмножеству в качестве операции сравнения для связанного частичного порядка. Более конкретно, эти наборы можно рассматривать как нижние наборы В общей форме теоремы Биркгофа этот частичный порядок можно рассматривать как индуцированный порядок на подмножестве элементов решетки, неприводимых к соединению элементов (элементов, которые не могут быть образованы как соединения двух других элементы).^[4] Для решетки стабильных согласований элементы частичного порядка вместо этого могут быть описаны в терминах структур, называемых вращения, описанный Ирвинг и кожа (1986).^[5]

Предположим, что два разных стабильных соответствия ${ displaystyle P}$ и ${ displaystyle Q}$ сопоставимы и не имеют третьего устойчивого соответствия между собой в частичном порядке. (То есть, ${ displaystyle P}$ и ${ displaystyle Q}$ сформировать пару покрывающее отношение частичного порядка стабильных сопоставлений.) Тогда набор пар элементов, которые сопоставляются в одном, но не в обоих, ${ displaystyle P}$ и ${ displaystyle Q}$ (в симметричная разница их наборов согласованных пар) называется вращением. Он образует график цикла чьи края чередуются между двумя совпадениями. Эквивалентно вращение можно описать как набор изменений, которые необходимо будет выполнить, чтобы изменить более низкое из двух сопоставлений на более высокое (при этом более низкие и высокие значения определяются с использованием частичного порядка). Если два разных стабильных соответствия по отдельности являются более высоким соответствием для одного и того же вращения, то их соответствие также является их совпадением. Отсюда следует, что для любого вращения набор устойчивых соответствий, которые могут быть высшими из пары, соединенной вращением, имеет уникальный наименьший элемент. Это наименьшее сопоставление является неприводимым по объединению, и это дает взаимно однозначное соответствие между поворотами и устойчивыми сопоставлениями, неприводимыми по объединению.^[5]

Если вращениям задан такой же частичный порядок, как и их соответствующие неразложимые по соединению стабильные паросочетания, то теорема Биркгофа о представлении дает взаимно однозначное соответствие между нижними наборами вращений и всеми стабильными паросочетаниями. Набор поворотов, связанных с любым заданным стабильным соответствием, может быть получен путем изменения данного соответствия вращениями вниз в частичном порядке, произвольным выбором вращения для каждого шага до достижения нижнего элемента и перечислением поворотов, используемых в этой последовательности. изменений. Устойчивое согласование, связанное с любым нижним набором поворотов, может быть получено путем применения поворотов к нижнему элементу решетки стабильных сопоставлений, произвольно выбирая, какое вращение применять, когда может применяться более одного.^[5]

Каждая пара ${ Displaystyle (х, у)}$ элементов данного стабильного экземпляра сопоставления принадлежит не более чем двум поворотам: одно вращение, применяемое к более низкому из двух сопоставлений, удаляет другие назначения ${ displaystyle x}$ и ${ displaystyle y}$ и вместо этого назначает их друг другу, и второе вращение, которое, когда применяется к более низкому из двух соответствий, удаляет пару ${ Displaystyle (х, у)}$ из сопоставления и находит другие назначения для этих двух элементов. Потому что есть ${ Displaystyle п ^ {2}}$ пары элементов, есть ${ Displaystyle О (п ^ {2})}$ вращения.^[5]

Математические свойства

Универсальность

Помимо конечной дистрибутивной решетки, нет никаких других ограничений на решеточную структуру стабильных паросочетаний. Это потому, что для любой конечной дистрибутивной решетки ${ displaystyle L}$, существует устойчивый экземпляр паросочетания, решётка стабильных паросочетаний изоморфна ${ displaystyle L}$.^[6]Более того, если конечная дистрибутивная решетка имеет ${ displaystyle k}$ элементов, то это может быть реализовано с использованием стабильного совпадающего экземпляра с не более чем ${ displaystyle k ^ {2} -k + 4}$ врачи и больницы.^[7]

Количество элементов решетки

Решетку устойчивых паросочетаний можно использовать для изучения вычислительная сложность подсчета количества стабильных совпадений данного экземпляра. Из эквивалентности решеток стабильных паросочетаний и произвольных конечных дистрибутивных решеток следует, что эта задача имеет эквивалентную вычислительную сложность подсчету числа элементов в произвольной конечной дистрибутивной решетке или подсчету числа элементов в произвольной конечной дистрибутивной решетке. антицепи в произвольном частично упорядоченном множестве. Вычисление количества стабильных совпадений # P-complete.^[5]

В равномерно-случайном примере проблемы стабильного брака с ${ displaystyle n}$ врачи и ${ displaystyle n}$ больниц, среднее количество стабильных сопоставлений асимптотически ${ Displaystyle е ^ {- 1} п пер п}$.^[8] В случае стабильного брака, выбранного для максимального увеличения числа различных стабильных совпадений, это число может быть не менее ${ Displaystyle 2 ^ {п-1}}$,^[5]и мы тоже ограниченный сверху по экспоненциальная функция из п (значительно меньше, чем наивный факториал ограничение на количество совпадений).^[9]

Алгоритмические последствия

Семейство вращений и их частичное упорядочение можно построить в полиномиальное время из данного экземпляра стабильного сопоставления и обеспечивает краткое представление семейства всех стабильных сопоставлений, которое для некоторых экземпляров может быть экспоненциально больше, если указано явно. Это позволяет эффективно выполнять несколько других вычислений на стабильных совпадающих экземплярах.^[10]

Взвешенное стабильное соответствие и закрытие

Если каждой паре элементов в устойчивом экземпляре сопоставления присвоен действительный вес, можно найти стабильное сопоставление с минимальным или максимальным весом в полиномиальное время. Один из возможных методов для этого - применить линейное программирование к порядковый многогранник частичного порядка поворотов или устойчивый согласующий многогранник.^[11] Возможен альтернативный комбинаторный алгоритм, основанный на том же частичном порядке.^[12]

Из весов на парах элементов можно присвоить веса каждому вращению, где вращению, которое изменяет данное стабильное соответствие на другое более высокое в частичном порядке стабильных соответствий, назначается изменение веса, которое оно вызывает: общий вес более высокое соответствие минус общий вес более низкого соответствия. По соответствию между стабильными сопоставлениями и нижними наборами поворотов общий вес любого сопоставления равен общему весу его соответствующего нижнего набора плюс вес нижнего элемента решетки сопоставлений. Таким образом, проблема поиска стабильного согласования с минимальным или максимальным весом становится эквивалентной проблеме поиска нижнего набора минимального или максимального веса в частично упорядоченном наборе полиномиального размера, частично упорядоченном множестве поворотов.^[12]

Эта задача оптимального нижнего множества эквивалентна экземпляру проблема закрытия, задача о вершинно-взвешенных ориентированные графы в котором цель - найти подмножество вершин оптимального веса без выходящих ребер. Оптимальный нижний набор - это оптимальное закрытие ориентированный ациклический граф вершинами которого являются элементы частичного порядка с ребром из ${ displaystyle alpha}$ к ${ displaystyle beta}$ в любое время ${ Displaystyle альфа leq beta}$ в частичном порядке. Проблема замыкания, в свою очередь, может быть решена за полиномиальное время путем преобразования ее в экземпляр проблема максимального расхода.^[12]

Минимум сожалений

Гасфилд (1987) Определяет сожаление участника стабильного сопоставления как расстояние от назначенного ему совпадения до вершины его списка предпочтений. Он определяет сожаление о стабильном совпадении как максимальное сожаление для любого участника. Затем можно найти стабильное сопоставление с минимальным сожалением с помощью простого жадного алгоритма, который начинается с нижнего элемента решетки сопоставлений, а затем многократно применяет любое вращение, которое уменьшает сожаление участника с максимальным сожалением, пока это не вызовет у другого участника иметь большее сожаление.^[10]

Среднее стабильное соответствие

Элементы любой дистрибутивной решетки образуют медианный график, структура, в которой любые три элемента ${ displaystyle P}$, ${ displaystyle Q}$, и ${ displaystyle R}$ (здесь стабильные сопоставления) имеют уникальный медианный элемент ${ displaystyle m (P, Q, R)}$ который лежит на кратчайшем пути между любыми двумя из них. Его можно определить как:^[13]

${ Displaystyle м (п, Q, R) = (п клин Q) vee (P клин R) vee (Q клин R) = (P vee Q) клин (P vee R) клин (Q vee R).}$

Для решетки стабильных сопоставлений эту медиану можно взять поэлементно, назначив каждому врачу медианное значение в предпочтениях врача из трех больниц, сопоставленных с этим врачом в ${ displaystyle P}$, ${ displaystyle Q}$, и ${ displaystyle R}$ и аналогичным образом назначив каждой больнице медианное значение из трех соответствующих ей врачей. В более общем смысле, любой набор из нечетного числа элементов любой распределительной решетки (или медианного графа) имеет медиану, уникальный элемент, минимизирующий его сумму расстояний до данного набора.^[14] Для медианы нечетного числа стабильных сопоставлений каждому участнику сопоставляется медианный элемент мультимножества их совпадений из данных сопоставлений. Для равномерного набора стабильных сопоставлений это можно устранить, выбрав назначение, которое сопоставляет каждого врача с высшим из двух средних элементов, а каждой больнице - с более низким из двух средних элементов. В частности, это приводит к определению медианного сопоставления во множестве всех стабильных сопоставлений.^[15] Однако для некоторых примеров проблемы стабильного сопоставления нахождение этой медианы всех стабильных сопоставлений NP-жесткий.^[16]

Рекомендации