Задача о совместном найме квартиры — это вид задачи справедливого дележа, в которой неделимые объекты и фиксированная денежная цена должны быть разделены одновременно. В английской литературе данная задача имеет разные названия, такие как Rental harmony (гармония съёма), housemates problem (задача о соседях) и room-assignment-rent-division (назначение комнат / распределение оплаты).
В типичных условиях имеется партнёров, желающих снять совместно -комнатный дом за запрошенную домовладельцем цену. Каждый из партнёров имеет свои собственные предпочтения — один предпочитает большую комнату, другой может предпочитать комнату с видом на главную дорогу и так далее. Следующие две проблемы следует решить одновременно:
(a) Назначить каждому партнёру комнату, (b) Определить, какую долю будет платить партнёр, чтобы сумма всех платежей составила фиксированную цену.
Есть несколько свойств, которые мы будем требовать выполненными. Неотрицательность (НО): все цены должны быть 0 или больше: никакому участнику не следует платить за то, что он снимет комнату. Отсутствие зависти (ОЗ, , EF): Если дана схема цен (назначение оплат за комнаты), мы говорим, что партнёр предпочитает данную комнату, если он верит, что пакет комната+оплата слабоЗдесь слово слабо означает, что партнёр может не отличать другой пакет комната+оплата по предпочтению от указанного. Если же партнёр не считает пакеты равными, употребляется термин строго лучше. лучше, чем другие пакеты. ОЗ означает, что любой партнёр предпочитает выделенную ему комнату. То есть, никакой партнёр не предпочёл бы занять комнату другого партнёра за цену, назначенную этой комнате. Pareto-efficiency (ЭП, , PE): Никакое другое назначение партнёров слабо лучше для всех партнёров и строго лучше по меньшей мере для одного партнёра (если дан вектор цен).
Из отсутствия зависти следует эффективность по Парето. Доказательство: (от противного) предположим, что существует альтернативное назначение с тем же самым вектором цен, которое строго лучше по меньшей мере для одного партнёра. Тогда при текущем распределении этот партнёр будет завидовать.
Задача о совместном съёме квартиры изучалась при двух различных предположениях на предпочтениях партнёров: В версии ординалистской теории полезности каждый партнёр имеет отношение предпочтения на наборы [комната, цена]. Если дан вектор цен, партнёр должен сказать, какую комнату (или комнаты) он предпочитает получить за эту цену. В версии кардиналистской теории полезности каждый партнёр имеет вектор денежных оценок. Партнёр должен сказать для каждой комнаты сколько точно денег он готов платить за эту комнату. Предполагается, что партнёр имеет квазилинейную полезность, то есть он оценивает комнату как и платит , суммарная полезность комнаты равна .
Кардинальность подразумевает ординальность, поскольку по вектору оценок всегда можно выстроить отношение предпочтения. Ординальность является более общим предположением и возлагает меньшие ментальные нагрузки на партнёров.
Ординальная версия
Су: по человеку на комнату Протокол делает следующие предположения на предпочтения партнёров: Хороший дом: В любом разбиении арендной платы каждое лицо находит по меньшей мере один пакет комната+плата приемлемым. Минимум внешнего воздействия: Отношение предпочтения зависят от комнаты и платежа, но не от выбора других партнёров. Скупые партнёры: всем партнёрам нравятся бесплатные комнаты (с нулевой оплатой) по сравнению с любой другой комнатой. Топологически замкнутое множество предпочтений: Партнёр, предпочитающий комнату для последовательности цен, предпочитает эту комнату и за предельную цену.
Нормализуем полную оплату помещения до 1. Тогда любая схема цен является точкой в -мерном симплексе с вершинами в . Протокол Су работает с двойственной версией этого симплекса аналогично протоколам Симмонса — Су для разрезания торта — для любой вершины триангуляции двойственного симплекса, который соответствует определённой схеме цен, алгоритм спрашивает партнёра «какую комнату ты предпочитаешь в этой схеме цен?». Это приводит к раскраске Шпернера двойственного симплекса, а тогда существует небольшой подсимплекс, который соответствует приближённому распределению комнат и выплат без зависти.
Протокол Су возвращает последовательность распределений, которые сходятся к распределению без зависти. Цены всегда неотрицательны. Следовательно, результат удовлетворяет требованиям неотрицательности и ОЗ.
Сан и Прокачча дали популярное объяснение протокола Су совместного съёма квартиры.
На страницах Francis Su’s Fair Division Page и Divide Your Rent Fairly есть онлайновые реализации.
Азриэли и Шмайя: совместное проживание в комнате Азриэли и Шмайя обобщили решение Су для ситуации, в которой вместимость каждой комнаты может быть больше единицы (то есть некоторые партнёры могут жить в одной комнате).
Они доказали существование распределения без зависти при следующих условиях: Хороший дом: Каждому партнёру нравится по меньшей мере одно помещение согласно каждому вектору цен. Минимум внешнего воздействия: Все партнёры предпочитают бесплатные комнаты. Скупые партнёры: Предпочтения непрерывны по цене.
Основные средства, использованные в доказательстве: — обобщение . теорема о свадьбах.
Их решение конструктивно в том же смысле, что и решение Су — существует процедура, которая аппроксимирует решения до любой заданной точности.
Основные свойства ординальных протоколов A. Как в протоколе Су, так и в протоколе Азриэли и Шмайя отношениям предпочтения каждого партнёра позволено (но не обязано) зависеть от полного вектора цен. То есть, партнёр может сказать: «если комната A стоит 1000, то я предпочту комнату B комнате C, но если комната A будет стоить только 700, то я предпочту комнату C комнате B».
Имеется несколько причин, по которым такая общность может быть полезна. Планирование будущего. Предположим, что партнёр считает, что лучшей комнатой является A, затем B, затем C. Если A чересчур дорога, участник занимает B. Но если A дешевле, партнёр может купить C (самую дешёвую), а затем скопить денег и перейти в A. Неполная информация. Вектор цен может дать партнёру информацию о качестве комнат. Соседи. Вектор цен может партнёру предсказать, до некоторой степени, какие люди будут жить в соседних комнатах. Нелогичные эффекты, например, эффекты воздействия рамок восприятия. Если комнаты B и C имеют одно качество и ту же цену, то партнёр выбирает A. Но если комната B становится более дорогой, партнёр может выбрать C, думая «она такая же как и B, но дешевле..».
B. Решение Су и решение Азриэли и Шмайя делают предположение о «скупых арендаторах» — они предполагают, что арендатор всегда предпочитает бесплатную комнату любой комнате с положительной ценой. Это предположение сильное и не всегда реалистично. Если одна комната очень плохая, может случиться, что некоторые арендаторы не захотят жить в такой комнате даже если оплата будет нулевой. Это легко видеть в кардинальной версии — если вы считаете, что комната A стоит 0, а комната B стоит 100, при этом комната A бесплатна, а комната B стоит 50, вы определённо предпочтёте комнату B.
Су предложил ослабление этого предположения следующим образом: каждый партнёр никогда не выбирает наиболее дорогую комнату, если имеется бесплатная комната. Это не требует от лица выбора бесплатной комнаты. В частности, это будет выполняться, если лицо всегда предпочитает бесплатную комнату комнате, стоящей по меньшей мере полной цены. Однако даже это ослабленное предположение может оказаться нереальным как в примере выше.
Кардинальная версия Как объяснено выше, входом кардинальной версии является матрица заявочных цен — каждый партнёр должен предложить цену для каждой комнаты, указывая, во сколько он оценивает эту комнату (скажем, в рублях или долларах).
Ключевым понятием в кардинальных решениях является maxsum распределение. Это распределение партнёров по комнатам, при котором максимизируется сумма заявочных цен. Задача нахождения распределения с maxsum известна как задача о назначениях и может быть решена венгерским алгоритмом за время (где — число партнёров). Любое ОЗ распределение является maxsum и любое maxsum распределение является ЭП.
Несовместимость ОЗ и неотрицательности Два требования, отсутствие зависти и неотрицательность платежей, не всегда совместимы. Например, предположим, что полная цена равна 100, а оценки следующие: Комната 1 Комната 2Партнёр 11500Партнёр 214010 Здесь только maxsum распределение отдаёт комнату 1 партнёру 1, а комнату 2 партнёру 2. Чтобы партнёр 2 не завидовал, партнёр 1 должен платить 115, а партнёр 2 должен платить −15.
В этом примере сумма оценок больше полной стоимости. Если сумма оценок равна полной стоимости и есть два или три партнёра, то всегда существует ОЗ и НО распределение. Но в случае четырёх и более партнёров опять ОЗ и НО могут оказаться несовместимыми, как в следующем примере (см. статью Брамса для доказательства): Комната 1 Комната 2 Комната 3 Комната 4 Партнёр 13634300 Партнёр 23136330 Партнёр 33430360 Партнёр 43233350
Заметим, что этот пример не возникает в ординальной версии, поскольку ординальный протокол делает предположение «скупых партнёров», когда партнёры всегда предпочитают бесплатные комнаты. Если это предположение выполняется, всегда существует ОЗ+НО распределение. Однако в вышеприведённом примере предположение не выполняется, и ОЗ+НО распределение не существует. Поэтому протоколы в кардинальной версии должны искать компромисс между ОЗ и НО. Каждый протокол делает различные компромиссы.
Брамс и Килгур: НО, но не ОЗ Брамс и Килгур предложили процедуру разрыва: Вычисляем maxsum распределение. Если max-sum меньше полной цены, то проблема неразрешима, поскольку партнёры не хотят платить полную стоимость, назначенную владельцем дома. Если maxsum в точности равен полной цене, то комнаты распределены и партнёры платят их заявленные цены. Если maxsum больше полной цены, то цены понижаются на основе разрыва между этими ценами и следующими (минимальными) оценками (см. книгу для более детального обсуждения). Идея последнего шага заключается в том, что следующая (минимальная) оценка представляет «конкуренцию» за комнату. Если комнату больше хочет партнёр со следующей по величине заявкой, то она должна стоить больше. Это похоже по духу аукциону Викри. Однако в аукционе Викри платёж полностью зависит от заявленных цен, а в процедуре разрыва платежи только частично независимы. Поэтому процедура разрыва не является .
Процедура разрыва всегда назначает неотрицательные цены. Поскольку назначение является maxsum, очевидно, что оно также эффективно по Парето. Однако некоторые партнёры могут завидовать. То есть, процедура разрыва удовлетворяет НО и ЭП, но не ОЗ.
Более того, процедура разрыва может возвратить распределение с присутствием зависти даже когда ОЗ распределение существует. Брамс относительно этой проблемы говорил: «Цены разрыва принимают во внимание конкуренцию при заявке цен, которые делают механизм ценообразования рыночным. Хотя отсутствие зависти является желаемым свойством, я предпочитаю механизм, подобный рыночному, когда имеется конфликт между этими двумя свойствами; партнёры должны платить больше, если их заявки конкурируют, даже если это приводит к зависти».
Хааке, Рэйт и Су: ОЗ, но не НО Хааке, Рэйт и Су представили компенсационную процедуру. Задача, которую решает эта процедура, является в некоторых аспектах более общей, чем задача о совместном съёме квартиры: Число неделимых объектов для дележа (m) может отличаться от числа партнёров (n). Могут быть произвольные ограничения на комплекты объектов, если они не различаются партнёрами. Например, может не быть ограничений вообще, или ограничения, такие как «каждый партнёр должен получить по меньшей мере некоторое определённое число объектов» или «некоторые объекты должны быть вместе» (например это могут быть земельные участки, которые должны прилегать друг к другу), и так далее.