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

Задача о совместном съёме квартиры — это вид задачи справедливого дележа, в которой неделимые объекты и фиксированная денежная цена должны быть разделены одновременно. В английской литературе данная задача имеет разные названия, такие как Rental harmony (гармония съёма), housemates problem (задача о соседях) и room-assignment-rent-division (назначение комнат / распределение оплаты).

В типичных условиях имеется $n$ партнёров, желающих снять совместно $n$-комнатный дом за запрошенную домовладельцем цену. Каждый из партнёров имеет свои собственные предпочтения — один предпочитает большую комнату, другой может предпочитать комнату с видом на главную дорогу и так далее. Следующие две проблемы следует решить одновременно:

• (a) Назначить каждому партнёру комнату,
• (b) Определить, какую долю будет платить партнёр, чтобы сумма всех платежей составила фиксированную цену.

Есть несколько свойств, которые мы будем требовать выполненными.

• Неотрицательность (НО): все цены должны быть 0 или больше: никакому участнику не следует платить за то, что он снимет комнату.
• Отсутствие зависти (ОЗ, англ. Envy-freeness, EF): Если дана схема цен (назначение оплат за комнаты), мы говорим, что партнёр предпочитает данную комнату, если он верит, что пакет комната+оплата слабо лучше, чем другие пакеты. ОЗ означает, что любой партнёр предпочитает выделенную ему комнату. То есть, никакой партнёр не предпочёл бы занять комнату другого партнёра за цену, назначенную этой комнате.
• Pareto-efficiency (ЭП, англ. Pareto-efficiency, PE): Никакое другое назначение партнёров слабо лучше для всех партнёров и строго лучше по меньшей мере для одного партнёра (если дан вектор цен).

Из отсутствия зависти следует эффективность по Парето. Доказательство: (от противного) предположим, что существует альтернативное назначение с тем же самым вектором цен, которое строго лучше по меньшей мере для одного партнёра. Тогда при текущем распределении этот партнёр будет завидовать.

Задача о совместном съёме квартиры изучалась при двух различных предположениях на предпочтениях партнёров:

• В версии ординалистской теории полезности каждый партнёр имеет отношение предпочтения на наборы [комната, цена]. Если дан вектор цен, партнёр должен сказать, какую комнату (или комнаты) он предпочитает получить за эту цену.
• В версии кардиналистской теории полезности каждый партнёр имеет вектор денежных оценок. Партнёр должен сказать для каждой комнаты сколько точно денег он готов платить за эту комнату. Предполагается, что партнёр имеет квазилинейную полезность, то есть он оценивает комнату как $v$ и платит $p$, суммарная полезность комнаты равна $v-p$.

Кардинальность подразумевает ординальность, поскольку по вектору оценок всегда можно выстроить отношение предпочтения. Ординальность является более общим предположением и возлагает меньшие ментальные нагрузки на партнёров.

Ординальная версия

Су: по человеку на комнату

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

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

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

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

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

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

Азриэли и Шмайя: совместное проживание в комнате

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

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

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

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

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

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

Основные свойства ординальных протоколов

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

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

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/(n-1)$ полной цены. Однако даже это ослабленное предположение может оказаться нереальным как в примере выше.

Кардинальная версия

Как объяснено выше, входом кардинальной версии является матрица заявочных цен — каждый партнёр должен предложить цену для каждой комнаты, указывая, во сколько он оценивает эту комнату (скажем, в рублях или долларах).

Ключевым понятием в кардинальных решениях является maxsum распределение. Это распределение партнёров по комнатам, при котором максимизируется сумма заявочных цен. Задача нахождения распределения с maxsum известна как задача о назначениях и может быть решена венгерским алгоритмом за время $O(n^{3})$ (где $n$ — число партнёров). Любое ОЗ распределение является maxsum и любое maxsum распределение является ЭП.

Несовместимость ОЗ и неотрицательности

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

	Комната 1	Комната 2
Партнёр 1	150	0
Партнёр 2	140	10

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

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

	Комната 1	Комната 2	Комната 3	Комната 4
Партнёр 1	36	34	30	0
Партнёр 2	31	36	33	0
Партнёр 3	34	30	36	0
Партнёр 4	32	33	35	0

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

Брамс и Килгур: НО, но не ОЗ

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

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

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

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

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

Хааке, Рэйт и Су: ОЗ, но не НО

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

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

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

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

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

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

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

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

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

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

Абдулкадироглу, Сёнмез и Унвер: ОЗ и НО, если возможно

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

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

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

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

Сон и Влах: ОЗ и НО, если возможно

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

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

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

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

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

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

Мэш, Галь, Прокачча и Зик: ОЗ и maximin

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

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

Соглашения о бюджете

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

Стратегические соглашения

Все рассмотренные протоколы предполагают, что партнёры честно указывают свои оценки. Стратегии не являются неуязвимыми — партнёр может получить выигрыш путём указания неверного значения. Более того, неуязвимость стратегии несовместима с отсутствием зависти — не существует протокола детерминированной неуязвимой стратегии, который всегда даёт распределение без зависти. Это верно даже в случае, когда есть только два партнёра и цены могут быть отрицательными. Доказательство: Предположим, что полная цена равна 100, а оценки партнёров следующие (где $x,y$ являются параметрами и $0<x<y<100$):

	Комната 1	Комната 2
Партнёр 1	100	x
Партнёр 2	100	y

Только максимальное по сумме распределение даёт комнату 1 партнёру 1 и комнату 2 партнёру 2. Пусть $p_{2}$ будет ценой за комнату 2 (так что цена комнаты 1 равна $100-p_{2}$). Чтобы партнёр 1 не завидовал, должно выполняться $p_{2}\geqslant x/2$. Чтобы не завидовал партнёр 2, должно выполняться $p_{2}\leqslant y/2$.

Предположим, что детерминированный протокол устанавливает цену $p_{2}$ в некоторое значение из интервала $[x/2,y/2]$. Если цена больше $x/2$, то партнёр 2 имеет мотивы указать меньшее значение $y$, которое остаётся больше, чем $x$, чтобы уменьшить свои платежи ближе к $x/2$. Аналогично, если цена меньше $y/2$, то партнёр 1 имеет причины указать более высокую цену для $x$, которая остаётся ниже $y$, чтобы увеличить платежи партнёра 2 в сторону $y/2$ (и тем самым уменьшить собственные платежи). Следовательно, механизм не может быть неуязвимой стратегией.

Исследователи справляются с этой невозможностью двумя путями.

Сан и Янг: Замена задачи

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

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

Дафтон и Ларсон: Используем случайность

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

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

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

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

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

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

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

Андерссон и Свенссон: Получение частичной неуязвимости

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

См. также

• Задача справедливого распределения объектов — задача справедливого дележа, где есть только неделимые предметы для обмена без денежных переводов.

Литература

• Su F. E. Rental Harmony: Sperner's Lemma in Fair Division // The American Mathematical Monthly. — 1999. — Т. 106, вып. 10. — doi:10.2307/2589747. — .
• Yaron Azrieli, Eran Shmaya. Rental harmony with roommates // Journal of Economic Theory. — 2014. — Т. 153. — doi:10.1016/j.jet.2014.06.006. — arXiv:1406.6672.
• Richard F. Potthoff. Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem // Group Decision and Negotiation. — 2002. — Т. 11, вып. 5. — doi:10.1023/A:1020485018300.
• Shao Chin Sung, Milan Vlach. Competitive envy-free division // Social Choice and Welfare. — 2004. — Т. 23. — doi:10.1007/s00355-003-0240-z.
• Atila Abdulkadiroğlu, Tayfun Sönmez, M. Utku Ünver. Room assignment-rent division: A market approach // Social Choice and Welfare. — 2004. — Т. 22, вып. 3. — doi:10.1007/s00355-003-0231-0.
• Lachlan Dufton, Kate Larson. Randomised Room Assignment-Rent Division // Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence. — 2011.
• Claus-Jochen Haake, Matthias G. Raith, Francis Edward Su. Bidding for envy-freeness: A procedural approach to n-player fair-division problems // Social Choice and Welfare. — 2002. — Т. 19, вып. 4. — doi:10.1007/s003550100149.
• Steven J. Brams. Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. — Princeton, NJ: Princeton University Press, 2008. — ISBN 9780691133218.
• Steven J. Brams, D. Marc Kilgour. Competitive Fair Division // Journal of Political Economy. — 2001. — Т. 109, вып. 2. — doi:10.1086/319550.
• Ya'akov Gal, Moshe Mash, Ariel D. Procaccia, Yair Zick. Which Is the Fairest (Rent Division) of Them All?. — ACM, 2016. — ISBN 9781450339360. — doi:10.1145/2940716.2940724.
• Ariel D. Procaccia, Rodrigo A. Velez, Dingli Yu. Fair Rent Division on a Budget // AAAI. — 2018.
• Ning Sun, Zaifu Yang. A general strategy proof fair allocation mechanism // Economics Letters. — 2003. — Т. 81. — doi:10.1016/s0165-1765(03)00151-4.
• Tommy Andersson, Lars-Gunnar Svensson. Non-manipulable assignment of individuals to positions revisited // Mathematical Social Sciences. — 2008. — Т. 56, вып. 3. — doi:10.1016/j.mathsocsci.2008.05.004.
• Tommy Andersson. A general strategy-proof fair allocation mechanism revisited // Economics Bulletin. — 2009. — Т. 29, вып. 3.
• Tommy Andersson, Lars Ehlers, Lars-Gunnar Svensson. Budget balance, fairness, and minimal manipulability // Theoretical Economics. — 2014. — Т. 9, вып. 3. — doi:10.3982/te1346.