Арендная гармония

Арендная гармония Это своего рода задача справедливого дележа , в которой неделимые предметы и фиксированная денежная стоимость должны быть разделены одновременно. Проблема с соседями по дому и разделение аренды помещений это альтернативные названия одной и той же проблемы.

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

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

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

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

Отсутствие зависти предполагает эффективность по Парето. Доказательство: предположим от противного, что существует альтернативное задание с тем же вектором цен, которое строго лучше по крайней мере для одного партнера. Затем, при текущем распределении, этот партнер завидует.

Проблема гармонии аренды изучалась при двух различных предположениях о предпочтениях партнеров:

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

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

Порядковая версия

Вс: один человек в номере

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

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

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

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

Протокол Су «Rental Harmony» был популяризирован в нескольких новостных статьях. и имеет несколько онлайн-реализаций.

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

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

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

1. Хороший дом : каждому партнеру нравится хотя бы одна комната с учетом каждого вектора цен.
2. Никаких внешних эффектов : всем партнерам нравятся бесплатные комнаты.
3. Скупые партнеры : Преференции постоянны в ценах.

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

• Теорема ККМС — обобщение теоремы Ккм .
• Теорема Холла о браке .

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

Общие свойства порядковых протоколов

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

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

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

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

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

Сегал-Халеви показывает, что это предположение можно еще больше ослабить. Предположим, что цена T слишком высока для некоторого агента i , если всякий раз, когда какая-то комната стоит T, а какая-то другая комната свободна, ни одна комната не предпочитает комнату, которая стоит T . Гармония аренды существует всякий раз, когда существует цена, которая слишком высока для всех агентов. Это предположение слабее, чем предположение о скупых арендаторах, и слабее, чем квазилинейность. Остается открытым вопрос, существует ли еще более слабое предположение, гарантирующее существование рентной гармонии.

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

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

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

Несовместимость EF и NN

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

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

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

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

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

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

Брэмс и Килгур: NN, но не EF

Брэмс и Килгур предложите процедуру пробелов :

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

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

Процедура разрыва всегда назначает неотрицательные цены. Поскольку присваивание является максимальной суммой, оно, очевидно, также эффективно по Парето. Однако некоторые партнеры могут позавидовать. Т.е. процедура Gap удовлетворяет требованиям NN и PE, но не EF.

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

Хааке, Райт и Су: EF, но не NN

Хааке, Райт и Су представить Порядок компенсации. Проблема, которую он решает, является более общей, чем проблема гармонии арендной платы, в некоторых аспектах:

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

К партнеру существует «квалификационное требование»: сумма его ставок должна быть не ниже общей стоимости.

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

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

При наличии большого количества элементов и сложных ограничений первый шаг — поиск распределения максимальной суммы — может оказаться затруднительным для расчета без компьютера. В этом случае Процедура компенсации может начаться с произвольного распределения. В этом случае процедура может завершиться распределением, содержащим элементы envy-cycles . Эти циклы можно удалить, перемещая пакеты по циклу. Это строго увеличивает общую сумму коммунальных услуг. Следовательно, после ограниченного числа итераций будет найдено распределение максимальной суммы, и процедура может продолжаться, как указано выше, для создания распределения без зависти.

Процедура компенсации может взимать с некоторых партнеров отрицательный платеж (т. е. давать партнерам положительную сумму денег). Это означает, что Процедура компенсации — это EF (следовательно, также PE), а не NN. Авторы говорят:

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

Однако другие авторы утверждают, что в обычном сценарии соседей по дому:

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

Абдулкадироглу, Сонмез и Унвер: ЕС и NN, если возможно

Абдулкадироглу и др. предложить рыночный подход. Это комбинация восходящего и нисходящего аукционов . Проще всего описать это как аукцион с непрерывной ценой:

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

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

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

Сунг и Влах: EF и NN, если возможно.

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

1. Свобода от зависти подразумевает максимальную сумму: при распределении x , если существует вектор цен p, при котором x свободен от зависти, то x является максимальной суммой.
2. Максимальная сумма подразумевает отсутствие зависти: при заданном векторе цен p , если существует распределение x, при котором p не вызывает зависти, то p является свободным от зависти для любого распределения максимальной суммы.

На основании этих свойств они предлагают следующий алгоритм:

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

Сложность выполнения как определения максимальной суммы, так и определения минимальных цен равна $O(n^{3})$.

Решение Суна и Влаха, похоже, обладает всеми желательными свойствами предыдущих протоколов, а именно: PE, EF и NN (если возможно) и полиномиальным временем выполнения, а кроме того, оно гарантирует, что каждый завистливый партнер получит свободное место. обеспечивает реализацию аналогичного решения, также основанного на решении задачи линейного программирования, но со ссылкой на другую статью.

Арагонес: EF и деньги – Ролсиан

Арагонес представил политаймовый алгоритм поиска решения EF, которое среди всех решений EF максимизирует наименьший платеж агента (это называется решением Money Rawlsian).

Маш, Галь, Прокачча и Зик: EF и эгалитаризм

Галь, Маш, Прокачча и Зик, Основываясь на своем опыте работы с приложением разделения арендной платы на веб-сайте Spliddit , отметим, что одной только свободы от зависти недостаточно, чтобы гарантировать удовлетворение участников. Поэтому они создают алгоритмическую основу, основанную на линейном программировании, для расчета распределений, которые не вызывают зависти и оптимизируют некоторые критерии. Основываясь на теоретических и экспериментальных тестах, они приходят к выводу, что эгалитарное правило – максимизирующее минимальную полезность агента, не подверженного зависти, – достигает оптимальных результатов.

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

Решение maximin реализовано на сайте spliddit.org и на сайте pref.tools .

Петерс, Прокачча и Чжу: надежный EF

Петерс, Прокачча и Чжу изучите практические условия, в которых агенты могут быть не уверены в своих оценках.

Агенты с ограниченным бюджетом

Жесткие бюджетные ограничения

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

В этом случае может не существовать ценового вектора, который был бы одновременно EF и доступным. Например, предположим, что общая арендная плата равна 1000, имеются две комнаты и два агента с одинаковыми оценками: 800 и 200 и одинаковым бюджетом: 600. Существует единый вектор цен, в котором оба агента имеют одинаковую квазилинейную полезность: (800 200); но у агента в комнате 1 недостаточно средств для оплаты. Напротив, существуют доступные ценовые векторы, например (600 400), но они не свободны от зависти.

Обратите внимание, что условие «слишком высокая цена» в этом случае все еще сохраняется, но предпочтения не являются непрерывными (агенты предпочитают только комнату 2, когда p1>600, и только комнату 1, когда p1<=600).

Прокачча, Велес и Ю представить эффективный алгоритм для определения того, существует ли распределение, которое является одновременно EF и доступным. Если да, то он находит такое распределение, которое среди всех доступных распределений EF максимизирует наименьшую полезность (как при эгалитарном распределении предметов ).

Айрио, Гилберт, Гранди, Ланг и Вильчински предложить два решения для преодоления проблемы несуществования при бюджетных ограничениях:

• Снижение EF до бюджетного EF , что означает, что агент i может завидовать агенту j, если j платит больше, чем . бюджет i Распределение BF-EF существует с большей вероятностью, чем распределение EF, но его существование еще не гарантировано. Они показывают MILP для расчета распределения BF-EF, если оно существует. Они также демонстрируют политаймовый алгоритм для фиксированного ценового вектора и псевдополитеймовый алгоритм для фиксированного распределения номеров.
• Разрешение дробного распределения , т. е. распределить (1,2) с ценой между агентами (1,2) на полгода и отменить распределение для другой половины и взимать с каждого агента 500. Они показывают линейную программу для нахождения дробного EF. распределение, если оно существует. Они показывают, что найти распределение EF с наименьшим общим количеством переключателей NP-трудно (путем сокращения из проблемы разделения Хэмминга или из проблемы продавца ), но может быть решено за время O*(2 ^к ) методом динамического программирования , где k — размер разложения Биркгофа ( к ≤ n ² ). Они предполагают, что минимизация максимального количества переключений на одного агента также является NP-сложной задачей.

Оба эти послабления значительно расширяют набор распределений EF. Однако даже при каждом из этих послаблений распределение EF может не существовать.

Мягкие бюджетные ограничения

Велес изучает разделение арендной платы EF в условиях мягких бюджетных ограничений . Каждый агент сообщает о своей стоимости комнат, своем бюджете и предельной бесполезности, связанной с необходимостью платить больше, чем предусмотрено бюджетом (например, процентная ставка ). Он представляет алгоритм, который находит разделение ренты EF, которое, кроме того, является эгалитарным (максимум-минимальная полезность), или денежно-роулсовским (минимальная-максимальная рента), или удовлетворяет одному из других подобных условий. Время выполнения находится в O( n ^{к + с} ), где n — количество агентов, k — количество различных значений бесполезности (например, разных процентных ставок), а c >2 — некоторая константа.

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

Кусочно-линейные утилиты

Аруначалешваран, Барман и Рати изучите ситуацию, существенно более общую, чем квазилинейная, в которой полезность каждого агента из каждой комнаты может быть любой кусочно-линейной функцией ренты. Этот параметр обобщает мягкое бюджетное ограничение. Поскольку цена слишком высока, распределение EF всегда существует. Они показывают FPTAS - алгоритм, который находит распределение, которое является EF до (1+ ε ), за полиномиальное время от 1/ ε и n. ^{к + с} , где n — количество агентов, k — количество различных значений бесполезности (например, разных процентных ставок), а c >2 — некоторая константа. Они также показывают, что проблемные линии находятся на пересечении классов сложности PPAD и PLS .

Стратегические соображения

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

	Комната 1	Комната 2
Партнер 1	100	х
Партнер 2	100	и

Единственное распределение максимальной суммы — это предоставление комнаты 1 партнеру 1 и комнаты 2 партнеру 2. Пусть $p_{2}$ быть ценой комнаты 2 (так что цена комнаты 1 равна $100-p_{2}$). Чтобы партнер 1 не завидовал, мы должны иметь $p_{2}\geq x/2$. Чтобы партнер 2 не завидовал, мы должны иметь $p_{2}\leq 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. Гарантированная вероятность отсутствия зависти (GPEF) означает, что существует определенная вероятность $p$ такая, что независимо от оценок партнеров с вероятностью не менее $p$, окончательный результат не будет вызывать зависти. Можно достичь GPEF $1/n$ следующим образом: найдите задание без зависти; выберите целое число $i\in \{0,\dots ,n-1\}$ наугад; и перемещать каждого партнера циклически $i$ комнаты направо. Этот рандомизированный механизм является правдивым в ожидании, поскольку каждый партнер имеет равную вероятность попасть в каждую комнату, а ожидаемый платеж равен $1/n$ от общей стоимости, независимо от ставки партнера. Вероятность распределения EF – это вероятность того, что $i=0$, что именно $1/n$. Это не обнадеживает, поскольку вероятность отсутствия зависти стремится к 0 при росте числа партнеров. Но добиться большего невозможно: в любом механизме, основанном на правдивых ожиданиях, GPEF не более чем $1/n$.

3. Ожидаемое количество партнеров без зависти (ENEF) означает, что существует определенное целое число. $N$ так что если усреднить число партнеров, не завидующих всем возможным результатам механизма, то независимо от оценок партнеров ожидание будет как минимум $N$. Критерий ENEF кажется более подходящим, чем критерий GPEF, поскольку он измеряет не только вероятность полного отсутствия зависти, но и качество случаев, в которых распределение не является полностью свободным от зависти. Максимальный ENEF механизма правдивых ожиданий не превышает $n-1+1/n$. Эту границу можно достичь за $n=2$. Для $n>2$, существует механизм правдивого ожидания, который почти достигает этой границы: ENEF $n-1$. Общая идея заключается в следующем. Используйте механизм VCG для расчета максимальной суммы и платежей. Случайным образом выберите одного партнера. Игнорируйте этого партнера и снова используйте VCG. Объедините результаты таким образом, чтобы гарантировать, что общая сумма платежей равна общей стоимости (подробности см. в документе). Можно показать, что: (а) механизм истинен в ожидании; (б) все партнеры, кроме игнорируемого партнера, не завидуют. Следовательно, ENEF $n-1$. Моделирование показывает, что примерно в 80% случаев GPEF этого механизма также находится на максимуме. $1/n$.

Андерссон, Элерс и Свенссон: достижение частичной стратегической устойчивости

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

См. также

Существует несколько проблем, в которых можно разделить только неделимые предметы без денежных переводов:

• Справедливое случайное назначение — каждому агенту должен достаться один объект; справедливость достигается с помощью рандомизации.
• Проблема распределения дома – каждому агенту должен достаться один объект (дом); рандомизация не допускается. Целью является эффективность и/или справедливость.
• Сопоставление без зависти — каждый агент должен получить не более одного объекта; цель состоит в том, чтобы максимизировать количество заданий, подлежащих свободе от зависти.
• Справедливое распределение предметов — каждый агент может получить произвольное количество предметов.
• Проблема назначения — каждому агенту должен достаться один объект; цель состоит в том, чтобы максимизировать общую ценность или минимизировать общие затраты.