Задача о совместном съёме квартиры

Протокол Франсиса Су делает следующие предположения на предпочтения партнёров:

1. Хороший дом: В любом разбиении арендной платы каждое лицо находит по меньшей мере один пакет комната+плата приемлемым.
2. Минимум внешнего воздействия: Отношение предпочтения зависят от комнаты и платежа, но не от выбора других партнёров.
3. Скупые партнёры: всем партнёрам нравятся бесплатные комнаты (с нулевой оплатой) по сравнению с любой другой комнатой.
4. Топологически замкнутое множество предпочтений: Партнёр, предпочитающий комнату для последовательности цен, предпочитает эту комнату и за предельную цену.

Нормализуем полную оплату помещения до 1. Тогда любая схема цен является точкой в ${\displaystyle (n-1)}$-мерном симплексе с ${\displaystyle n}$ вершинами в ${\displaystyle \mathbb {R} ^{n}}$. Протокол Су работает с двойственной версией этого симплекса аналогично протоколам Симмонса — Су для разрезания торта — для любой вершины триангуляции двойственного симплекса, который соответствует определённой схеме цен, алгоритм спрашивает партнёра «какую комнату ты предпочитаешь в этой схеме цен?». Это приводит к раскраске Шпернера двойственного симплекса, а тогда существует небольшой подсимплекс, который соответствует приближённому распределению комнат и выплат без зависти.

Протокол Су возвращает последовательность распределений, которые сходятся к распределению без зависти. Цены всегда неотрицательны. Следовательно, результат удовлетворяет требованиям неотрицательности и ОЗ.

Сан[10] и Прокачча[11] дали популярное объяснение протокола Су совместного съёма квартиры.

На страницах Francis Su’s Fair Division Page[12] и Divide Your Rent Fairly[13] есть онлайновые реализации.

Азриэли и Шмайя[2] обобщили решение Су для ситуации, в которой вместимость каждой комнаты может быть больше единицы (то есть некоторые партнёры могут жить в одной комнате).

Они доказали существование распределения без зависти при следующих условиях:

1. Хороший дом: Каждому партнёру нравится по меньшей мере одно помещение согласно каждому вектору цен.
2. Минимум внешнего воздействия: Все партнёры предпочитают бесплатные комнаты.
3. Скупые партнёры: Предпочтения непрерывны по цене.

Основные средства, использованные в доказательстве:

• лемма Кнастера — Куравтоского — Мазуркевича — Шепли — обобщение леммы Кнастера — Куравтоского — Мазуркевича.
• теорема о свадьбах.

Их решение конструктивно в том же смысле, что и решение Су — существует процедура, которая аппроксимирует решения до любой заданной точности.

A. Как в протоколе Су, так и в протоколе Азриэли и Шмайя отношениям предпочтения каждого партнёра позволено (но не обязано) зависеть от полного вектора цен. То есть, партнёр может сказать: «если комната A стоит 1000, то я предпочту комнату B комнате C, но если комната A будет стоить только 700, то я предпочту комнату C комнате B».

Имеется несколько причин, по которым такая общность может быть полезна[2].

1. Планирование будущего. Предположим, что партнёр считает, что лучшей комнатой является A, затем B, затем C. Если A чересчур дорога, участник занимает B. Но если A дешевле, партнёр может купить C (самую дешёвую), а затем скопить денег и перейти в A.
2. Неполная информация. Вектор цен может дать партнёру информацию о качестве комнат.
3. Соседи. Вектор цен может партнёру предсказать, до некоторой степени, какие люди будут жить в соседних комнатах.
4. Нелогичные эффекты, например, эффекты воздействия рамок восприятия. Если комнаты B и C имеют одно качество и ту же цену, то партнёр выбирает A. Но если комната B становится более дорогой, партнёр может выбрать C, думая «она такая же как и B, но дешевле..».

B. Решение Су и решение Азриэли и Шмайя делают предположение о «скупых арендаторах» — они предполагают, что арендатор всегда предпочитает бесплатную комнату любой комнате с положительной ценой. Это предположение сильное и не всегда реалистично. Если одна комната очень плохая, может случиться, что некоторые арендаторы не захотят жить в такой комнате даже если оплата будет нулевой. Это легко видеть в кардинальной версии — если вы считаете, что комната A стоит 0, а комната B стоит 100, при этом комната A бесплатна, а комната B стоит 50, вы определённо предпочтёте комнату B.

Су[1] предложил ослабление этого предположения следующим образом: каждый партнёр никогда не выбирает наиболее дорогую комнату, если имеется бесплатная комната. Это не требует от лица выбора бесплатной комнаты. В частности, это будет выполняться, если лицо всегда предпочитает бесплатную комнату комнате, стоящей по меньшей мере ${\displaystyle 1/(n-1)}$ полной цены. Однако даже это ослабленное предположение может оказаться нереальным как в примере выше[14].

Два требования, отсутствие зависти и неотрицательность платежей, не всегда совместимы. Например, предположим, что полная цена равна 100, а оценки следующие:

Здесь только maxsum распределение отдаёт комнату 1 партнёру 1, а комнату 2 партнёру 2. Чтобы партнёр 2 не завидовал, партнёр 1 должен платить 115, а партнёр 2 должен платить −15.

В этом примере сумма оценок больше полной стоимости. Если сумма оценок равна полной стоимости и есть два или три партнёра, то всегда существует ОЗ и НО распределение[15]. Но в случае четырёх и более партнёров опять ОЗ и НО могут оказаться несовместимыми, как в следующем примере (см. статью Брамса[16] для доказательства):

Заметим, что этот пример не возникает в ординальной версии, поскольку ординальный протокол делает предположение «скупых партнёров», когда партнёры всегда предпочитают бесплатные комнаты. Если это предположение выполняется, всегда существует ОЗ+НО распределение. Однако в вышеприведённом примере предположение не выполняется, и ОЗ+НО распределение не существует. Поэтому протоколы в кардинальной версии должны искать компромисс между ОЗ и НО. Каждый протокол делает различные компромиссы.

Брамс и Килгур[8][17] предложили процедуру разрыва:

1. Вычисляем maxsum распределение.
2. Если max-sum меньше полной цены, то проблема неразрешима, поскольку партнёры не хотят платить полную стоимость, назначенную владельцем дома.
3. Если maxsum в точности равен полной цене, то комнаты распределены и партнёры платят их заявленные цены.
4. Если maxsum больше полной цены, то цены понижаются на основе разрыва между этими ценами и следующими (минимальными) оценками (см. книгу для более детального обсуждения).

Идея последнего шага заключается в том, что следующая (минимальная) оценка представляет «конкуренцию» за комнату. Если комнату больше хочет партнёр со следующей по величине заявкой, то она должна стоить больше. Это похоже по духу аукциону Викри. Однако в аукционе Викри платёж полностью зависит от заявленных цен, а в процедуре разрыва платежи только частично независимы. Поэтому процедура разрыва не является неуязвимой.

Процедура разрыва всегда назначает неотрицательные цены. Поскольку назначение является maxsum, очевидно, что оно также эффективно по Парето. Однако некоторые партнёры могут завидовать. То есть, процедура разрыва удовлетворяет НО и ЭП, но не ОЗ.

Более того, процедура разрыва может возвратить распределение с присутствием зависти даже когда ОЗ распределение существует. Брамс относительно этой проблемы говорил: «Цены разрыва принимают во внимание конкуренцию при заявке цен, которые делают механизм ценообразования рыночным. Хотя отсутствие зависти является желаемым свойством, я предпочитаю механизм, подобный рыночному, когда имеется конфликт между этими двумя свойствами; партнёры должны платить больше, если их заявки конкурируют, даже если это приводит к зависти»[18].

Хааке, Рэйт и Су[7] представили компенсационную процедуру. Задача, которую решает эта процедура, является в некоторых аспектах более общей, чем задача о совместном съёме квартиры:

• Число неделимых объектов для дележа (m) может отличаться от числа партнёров (n).
• Могут быть произвольные ограничения на комплекты объектов, если они не различаются партнёрами. Например, может не быть ограничений вообще, или ограничения, такие как «каждый партнёр должен получить по меньшей мере некоторое определённое число объектов» или «некоторые объекты должны быть вместе» (например это могут быть земельные участки, которые должны прилегать друг к другу), и так далее.
• Полная «цена» может быть положительной, то есть имеется часть денег для общего владения. Это характерно для сценария дележа наследства. Аналогично «объекты» могут иметь отрицательную полезность (например, они могут представлять неделимые рутинные работы).

Имеется «квалификационное требование» к партнёрам — сумма заявок должна быть не меньше полной стоимости.

Процедура делает следующие шаги.

1. Находим maxsum (прагматичное) распределение, распределение с наивысшей суммой полезности, удовлетворяющее ограничениям на пакеты объектов. Если ограничений нет, то распределение, которое даёт каждый объект партнёру с наивысшей оценкой, является maxsum. Если имеются ограничения (такие как «по меньшей мере по объекту на партнёра»), то может оказаться, что maxsum распределение трудно найти.
2. Назначаем каждому партнёру значение пакета, ему распределённого. Это создаёт начальную кассу.
3. Выплачиваем цену из начальной кассы. Если все партнёры выполнили квалификационные требования, то денег в кассе достаточно и может появиться некоторая остаточная сумма.
4. Исключаем зависть путём компенсационных выплат завидующим партнёрам. Имеется не более ${\displaystyle n-1}$ раундов выплат. Процедура полностью наглядна и говорит явно какую компенсацию следует платить и в каком порядке. Более того, эту процедуру легко выполнить без компьютера.
5. Сумма сделанных компенсаций во всех раундах является наименьшей суммой, которая требуется для исключения зависти, и она никогда не превосходит остаточной суммы. Если что-то останется, этот остаток можно поделить любым способом, не создающим зависти, например путём выплат равной суммы каждому партнёру (статьи обсуждают другие варианты, которые могут считаться более «справедливыми»).

Если имеется много объектов и сложные ограничения, начальный шаг нахождения maxsum распределения может быть сложным для вычисления без компьютера. В этом случае «компенсационная процедура» может начать с произвольного распределения. В этом случае процедура может завершиться распределением, содержащим циклы зависти. Эти циклы можно удалить путём переноса пакетов по циклу. Такой перенос строго увеличивает полную сумму полезности. Следовательно, после ограниченного числа итераций будет найдено maxsum распределение и процедура может продолжить как выше для получения распределения без зависти.

Компенсационная процедура может назначить некоторым партнёрам отрицательные выплаты (то есть даёт партнёрам положительные величины денег). Это означает, что компенсационная процедура является ОЗ, но не НО. Авторы говорят:

«мы не исключаем ситуации, когда одной личности будут платить другие. В контексте справедливого дележа мы вообще не видим в этом проблемы. Более того, если группа не хочет избавиться от какого-либо из членов, нет никаких причин, чтобы группа не субсидировала члена группы, который получает нежелательный (для других) пакет объектов. Более того, квалификационное требование гарантирует, что субсидии не являются следствием недооценки полного набора объектов игроками»[19].

Однако другие авторы утверждают, что в обычном сценарии съёма жилья

«съёмщик, которому назначена комната с отрицательной стоимостью проживания субсидируется несколькими из остальных съёмщиков. В такой ситуации они могут предпочитать оставить эту комнату пустой и избавиться от занимающего комнату соседа, поскольку они получают при этом скидку на проживание. Чтобы избежать таких ситуаций, отрицательная плата за помещение должна быть исключена»[4].

Абдулкадироглу, Сёнмез и Унвер[5] предложили подход, основанный на рыночном механизме. Он является комбинацией английского аукциона и голландского аукциона. Его проще всего описать как аукцион с непрерывными ценами:

1. Присваиваем цену каждой комнаты в ${\displaystyle 1/n}$ полной стоимости дома.
2. Вычисляем множество требований каждого партнёра — комната или множество комнат, которые наиболее желает получить партнёр за текущую цену.
3. Отбираем комнаты, пользующиеся повышенным спросом (комнаты, которые желают получить больше пользователей, чем количество комнат; см. статью с точным определением).
4. Повышаем цену комнат с повышенным спросом с одинаковым коэффициентом;
5. Одновременно уменьшаем цену других комнат на одинаковую величину, так чтобы сумма цен всех комнат оставалась равной полной цене.
6. Сразу же обновляем требования партнёров и множество комнат с повышенным спросом.
7. Когда множество комнат с повышенным спросом будет пусто, останавливаемся и применяем теорему Холла о свадьбах, чтобы распределить каждому партнёру комнату согласно его требованию.

На практике не обязательно менять цену непрерывно, поскольку интересны только цены, при которых набор требований одного и более партнёров меняется. Можно определить множество интересующих нас цен заранее и превратить аукцион с непрерывными ценами в аукцион с дискретными ценами. Такой аукцион с дискретными ценами останавливается за конечное число шагов[20].

Получаемое распределение всегда свободно от зависти. Цены могут быть отрицательными как в процедуре Хааке, Рэйта и Су. Однако, в отличие от этой процедуры, цены неотрицательны, если существует ОЗ распределение с неотрицательными ценаси.

Сон и Влах[4] доказали следующее общее свойство распределений:

1. Из отсутствия зависти следует maxsum: при данном распределении x, если существует вектор цен p, при котором в распределении x отсутствует зависть, то x является maxsum.
2. Из maxsum вытекает отсутствие зависти: при заданном векторе цен p, если существует распределение x, при котором вектор цен p не создаёт зависть, при этом векторе цен p в любом maxsum распределении зависти не будет.

Опираясь на эти свойства авторы предложили следующий алгоритм:

1. Находим maxsum распределение.
2. Находим minsum вектор цен (вектор, на котором сумма цен минимальна) с учётом условия отсутствия зависти. Такой вектор цен является решением линейного программирования и может быть найден с помощью алгоритма Беллмана — Форда.
3. Если минимальная цена равна полной цене, реализуем maxsum распределение с minsum ценами и завершаем работу.
4. Если minsum меньше полной цены, увеличиваем все цены так, чтобы сумма стала равной полной цене (то есть, добавляем к каждой цене величину ${\displaystyle (cost-minsum)/n}$). Изменение цен на одинаковую величину обеспечивает сохранение отсутствия зависти.
5. Если minsum больше полной цены, то нет решения, одновременно удовлетворяющего требованиям НО и ОЗ. Есть несколько возможных путей продолжать процедуру
   • Уменьшаем все цены на одинаковую величину, пока сумма не станет равной полной цене (то есть вычитаем из каждой цены величину ${\displaystyle (minsum-cost)/n}$). Некоторые цены обязательно станут отрицательными, как в решении Хааке, Рэйта и Су.
   • Уменьшаем только положительные цены на одинаковую величину, пока сумма цен не станет равной полной цене. Здесь цены не меняются одинаково, что приведёт обязательно к зависти как в решении Брамса и Килгура. Однако в этом решении завидующие партнёры получат свои комнаты бесплатно.

Сложность выполнения maxsum распределения и minsum цен равна ${\displaystyle O(n^{3})}$.

Решение Сона и Влаха представляется имеющим все желаемые свойства предыдущих протоколов, то есть ОЗ, НО (если возможно), полиномиальное время работы и, кроме того, оно гарантирует, что любой завидущий партнёр получает бесплатную комнату. Статья «Assign Rooms and Share Rent»[21] предоставляет реализацию похожего решения, также основывающегося на решении задачи линейного программирования, но статья цитирует другую работу.

Галь, Мэш, Прокачча и Зик[22], основываясь на опыте с приложением распределения аренды на сайте www.spliddit.org, заметили, что одного отсутствия зависти недостаточно для удовлетворения чаяний участников. Поэтому они построили алгоритмический аппарат, основанный на линейном программировании, для вычисления распределения в котором отсутствует зависть и которое оптимизирует некоторые критерии. Опираясь на теоретические и экспериментальные тесты, они заключили, что критерий maximin — максимизации минимальной полезности агента с учётом отсутствия зависти — даёт оптимальные результаты.

Заметим, что поскольку их решение всегда ОЗ, оно может вернуть отрицательные цены.

Большинство статей с кардинальной моделью предполагают, что агенты имеют квазилинейные функции полезности — полезность для них равна значению комнаты минус цена. Но в реальности агенты имеют ограничения на бюджет — если цена комнаты выше их бюджета, полезность падает много быстрее линейности. Прокачча, Велес и Ю[23] изучали эту модель и представили алгоритм для определения, существует ли ОЗ распределение, удовлетворяющее ограничениям бюджета, и если есть, алгоритм находит распределение, которое удовлетворяет дополнительному критерию справедливости.

Есть вариант задачи, в которой вместо предположения, что полная стоимость дома фиксирована, мы предполагаем, что имеется максимальная стоимость каждой комнаты. В этом варианте существует механизм неуязвимой стратегии — детерминированное правило распределения, выбирающее минимальную в сумме цену, является стратегией неуязвимости[24].

Этот результат можно обобщить для большей гибкости на неделимые объекты и доказательство устойчивости коалиционной стратегии[25][26].

Возвращаясь к исходной задаче справедливого дележа жилья, можно рассматривать механизм случайности. Механизм случайности возвращает распределение вероятности по распределению комнат и распределению оплаты. Механизм случайности честен в ожидании, если никакой партнёр не увеличивает математическое ожидание своей полезности путём неверного указания своей оценки комнат. Справедливость механизма случайности можно измерить разными путями[6]:

1. Заблаговременное отсутствие зависти означает, что нет партнёров, которые завидуют выпавшей по жеребьёвке комнате любого другого партнёра. Это условие тривиально удовлетворить: делаем выбор всех распределений с равной вероятностью и назначаем каждому партнёру плату ${\displaystyle 1/n}$ общей стоимости. Но это условие мало пригодно, поскольку велик шанс, что в конечном распределении многие партнёры будут завидовать. Их может не удовлетворить факт, что лотерея была справедливой.

2. Гарантированная вероятность отсутствия зависти (ГВОЗ, англ. Guaranteed Probability of Envy-Freeness, GPEF) означает, что существует определённая вероятность ${\displaystyle p}$ при которой, независимо от оценок участников с вероятностью по меньшей мере ${\displaystyle p}$ в конечном решении будет отсутствовать зависть. Можно получить ГВОЗ в ${\displaystyle 1/n}$ следующим образом: находим распределение без зависти; выбираем целое число ${\displaystyle i\in \{0,\dots ,n-1\}}$ случайным образом и передвигаем партнёров по циклу в ${\displaystyle i}$ комнату правее. Этот случайный механизм честен-в-ожидании, поскольку любой партнёр имеет равную вероятность оказаться в каждой комнате и ожидаемой ценой в ${\displaystyle 1/n}$ от полной стоимости независимо от заявленных цен партнёра. Вероятность получить ОЗ распределения равна вероятности, что ${\displaystyle i=0}$, что в точности равно ${\displaystyle 1/n}$. Это не особенно воодушевляет, поскольку вероятность отсутствия зависти стремится к 0 по мере роста числа партнёров, однако сделать её лучше возможности нет, поскольку в любом честном-в-ожидании механизме ГВОЗ не превосходит ${\displaystyle 1/n}$.

3. Ожидаемое число партнёров без зависти (ОЧБЗ, англ. Expected Number of Envy-Free partners, ENEF) означает, что имеется некоторое целое ${\displaystyle N}$, такое, что если мы определяем число партнёров, которые не завидуют всем возможным результатам механизма, вне зависимости от оценок партнёров ожидание не превосходит ${\displaystyle N}$. Критерий ОЧБЗ кажется более пригодным, чем критерий ГВОЗ, поскольку он измеряет не только вероятность полного отсутствия зависти, но также и качество случаев, в которых распределение не полностью свободно от зависти. Максимум ОЧБЗ честного в ожидании механизма не превосходит ${\displaystyle n-1+1/n}$. Есть возможность получить эту границу для ${\displaystyle n=2}$. Для ${\displaystyle n>2}$ существует честный в ожидании механизм, который почти достигает этой границы — ОЧБЗ равен ${\displaystyle n-1}$. Главная идея следующая. Используем механизм Викри — Кларка — Гроувса для вычисления назначения с максимальной суммой и его суммы оплат. Случайно выбираем партнёра. Игнорируем данного партнёра и используем механизм Викри — Кларка — Гроувса опять. Комбинируем результаты так, чтобы гарантировать равенство полного платежа полной стоимости (см. статью для деталей). Можно показать, что

(a) механизм честен в ожидании

(b) все партнёры, за исключением игнорируемого не будут завидовать

Следовательно, ОЧБЗ равно ${\displaystyle n-1}$. Моделирование показывает, что около в 80 % случаев ГВОЗ этого механизма не превосходит ${\displaystyle 1/n}$.

Возможное ослабление требования неуязвимости является попыткой минимизировать «степени манипулируемости»[27]. Она определяется подсчётом для каждого случая числа агентов, которые могут манипулировать правилами. Максимально предпочитаемые справедливые правила распределения являются минимально манипулируемыми (как индивидуально, так и в коалиции) как в смысле справедливости, так и в смысле баланса бюджета. Такие правила выбирают распределение с максимальным числом агентов, для которых полезность максимальна среди всех справедливых и сбалансированных распределений.