Гармония аренды

Гармония аренды ^{[1] [2]} — это своего рода проблема справедливого деления , в которой неделимые предметы и фиксированная денежная стоимость должны быть разделены одновременно. Проблема соседей по дому ^{[3] [4]} и проблема распределения-аренды-комнаты ^{[5] [6]} — это альтернативные названия одной и той же проблемы. ^{[7] [8] : 305–328}

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

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

Мы хотели бы, чтобы задание отвечало нескольким свойствам.

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

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

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

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

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

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

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

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

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

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

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

Протокол Rental Harmony Су был популяризирован в нескольких новостных статьях ^{[9] [10]} и имеет несколько онлайн-реализаций. ^{[11] [12]}

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

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

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

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

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

• Теорема KKMS — обобщение теоремы Kkm .
• Теорема Холла о браке .

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

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

A. В обоих решениях, Su и Azrieli&Shmaya, отношение предпочтений каждого партнера может (но не обязано) зависеть от всего вектора цен. То есть партнер может сказать: «Если комната 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. Оба решения, Su и Azrieli&Shmaya, предполагают «скупых арендаторов» — они предполагают, что арендатор всегда предпочитает бесплатную комнату несвободной. Это предположение сильное и не всегда реалистичное. Если одна из комнат очень плохая, возможно, что некоторые арендаторы не захотят жить в этой комнате даже бесплатно. Это легко увидеть в кардинальной версии: если вы считаете, что комната A стоит 0, а комната B стоит 100, и комната A бесплатна, а комната B стоит 50, то вы, безусловно, предпочитаете комнату B.

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

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

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

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

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

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

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

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

В этом примере сумма оценок больше общей стоимости. Если сумма оценок равна общей стоимости, и есть два или три партнера, то всегда существует распределение EF и NN. ^{[4] : 110–111} Но если есть четыре или более партнеров, то снова EF и NN могут быть несовместимы, как в следующем примере (см. ^{[8] : 318–319} для доказательства):

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

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

Брамс и Килгур ^{[8] : 305–328  [14]} предлагают процедуру зазора :

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

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

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

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

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

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

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

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

Процедура выполняется следующим образом.

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

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

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

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

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

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

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

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

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

На практике нет необходимости изменять цену непрерывно, поскольку единственными интересными ценами являются цены, в которых изменяются наборы спроса одного или нескольких партнеров. Можно заранее рассчитать набор интересных цен и преобразовать аукцион с непрерывной ценой в аукцион с дискретной ценой. Этот аукцион с дискретной ценой останавливается после конечного числа шагов. ^{[5] : 525–528}

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

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

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

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

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

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

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

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

Арагонес: EF и деньги-Rawlsian

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

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

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

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

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

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

Питерс, Прокачча и Чжу ^[18] изучают практическую ситуацию, в которой агенты могут быть не уверены в своих оценках.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Единственное распределение maxsum — отдать комнату 1 партнеру 1, а комнату 2 партнеру 2. Пусть будет ценой комнаты 2 (так что цена комнаты 1 будет ). Чтобы партнер 1 не завидовал, мы должны иметь . Чтобы партнер 2 не завидовал, мы должны иметь . ${\displaystyle p_{2}}$ ${\displaystyle 100-p_{2}}$ ${\displaystyle p_{2}\geq x/2}$ ${\displaystyle p_{2}\leq y/2}$

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

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

Сунь и Ян: изменение проблемы

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

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

Дафтон и Ларсон: использование рандомизации

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

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

2. Гарантированная вероятность отсутствия зависти (GPEF) означает, что существует определенная вероятность того, что независимо от оценок партнеров с вероятностью не менее , конечный результат будет свободен от зависти. Можно достичь GPEF следующим образом: найти назначение без зависти; выбрать целое число случайным образом; и циклически перемещать каждого партнера по комнатам вправо. Этот рандомизированный механизм является ожидаемо правдивым, поскольку каждый партнер имеет равную вероятность оказаться в каждой комнате, а ожидаемая выплата составляет общую стоимость, независимо от ставки партнера. Вероятность наличия распределения EF равна вероятности того, что , что в точности равно . Это не обнадеживает, поскольку вероятность отсутствия зависти стремится к 0, когда число партнеров растет. Но сделать лучше невозможно: в каждом ожидаемо правдивом механизме 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}$ ${\displaystyle 1/n}$

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

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

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

Смотрите также

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

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

Ссылки

1. Su, FE (1999). «Rental Harmony: лемма Спернера в справедливом дележе». The American Mathematical Monthly . 106 (10): 930–942. doi :10.2307/2589747. JSTOR  2589747.
2. Азриэли, Ярон; Шмая, Эран (2014). «Арендная гармония с соседями по комнате». Журнал экономической теории . 153 : 128. arXiv : 1406.6672 . doi : 10.1016/j.jet.2014.06.006. S2CID  12129179.
3. Поттхофф, Ричард Ф. (2002). «Использование линейного программирования для поиска решения без зависти, наиболее близкого к решению проблемы разрыва Брэмса–Килгура для проблемы соседей по дому». Групповые решения и переговоры . 11 (5): 405. doi :10.1023/A:1020485018300. S2CID  122452727.
4. ^Sung, Shao Chin; Vlach, Milan (2004). "Конкурентное разделение без зависти". Социальный выбор и благосостояние . 23. doi :10.1007/s00355-003-0240-z. S2CID  11638306.
5. Абдулкадироглу, Атила; Сёнмез, Тайфун; Утку Юнвер, М. (2004). «Подразделение предоставления помещений-аренда: рыночный подход». Социальный выбор и благосостояние . 22 (3): 515. CiteSeerX 10.1.1.198.186 . дои : 10.1007/s00355-003-0231-0. 
6. Лаклан Дафтон и Кейт Ларсон (2011). "Randomised Room Assignment-Rent Division" (PDF) . Труды семинара IJCAI-2011 по социальному выбору и искусственному интеллекту . IJCAI. стр. 34–39 . Получено 5 марта 2016 г. .
7. Хааке, Клаус-Йохен; Райт, Маттиас Г.; Су, Фрэнсис Эдвард (2002). «Ставки на свободу от зависти: процедурный подход к проблемам справедливого разделения для n игроков». Social Choice and Welfare . 19 (4): 723. CiteSeerX 10.1.1.26.8883 . doi :10.1007/s003550100149. S2CID  2784141. 
8. Стивен Дж. Брамс (2008). Математика и демократия: разработка лучших процедур голосования и справедливого разделения . Принстон, Нью-Джерси: Princeton University Press. ISBN 9780691133218.
9. Sun, Albert (28 апреля 2014 г.). «Чтобы разделить ренту, начните с треугольника». The New York Times . Получено 26 августа 2014 г.
10. Прокачча, Ариэль (2012-08-15). "Справедливое деление и проблема нытиков-философов". Невидимая рука Тьюринга . Получено 26 августа 2014 г.
11. "Страница справедливого деления Фрэнсиса Су". Math.hmc.edu . Получено 05.01.2017 .
12. "Divide Your Rent Fairly". The New York Times . 28 апреля 2014 г. Получено 05.01.2017 .
13. Segal-Halevi, Erel (2022-05-28). «Обобщенная арендная гармония». The American Mathematical Monthly . 129 (5): 403–414. arXiv : 1912.13249 . doi : 10.1080/00029890.2022.2037988. ISSN  0002-9890.
14. Брамс, Стивен Дж.; Килгур, Д. Марк (2001). «Конкурсно-ярмарочный отдел». Журнал политической экономии . 109 (2): 418. дои : 10.1086/319550. S2CID  154200252.
15. "Assign Rooms and Share Rent - Spliddit". Архивировано из оригинала 2016-03-05 . Получено 2016-03-05 .
16. Арагонес, Энрикета (1995-06-01). "Вывод денежного решения Роулза". Социальный выбор и благосостояние . 12 (3): 267–276. doi :10.1007/BF00179981. ISSN  1432-217X.
17. Гал, Яаков (Коби); Маш, Моше; Прокачча, Ариэль Д.; Зик, Яир (2016-07-21). Который из них всех самый справедливый (раздел ренты)? . ACM. стр. 67–84. doi :10.1145/2940716.2940724. ISBN 9781450339360. S2CID  53223944.
18. Питерс, Доминик; Прокачча, Ариэль Д.; Чжу, Дэвид (2022-12-06). «Надежное арендное подразделение». Достижения в области нейронных систем обработки информации . 35 : 13864–13876.
19. Ариэль Д. Прокачча, Родриго А. Велес и Дингли Ю. «Раздел справедливой арендной платы по бюджету». АААИ 2018.
20. Айрио, Стефан; Гилберт, Хьюго; Гранди, Умберто; Ланг, Же Ро я; Вильчински, Анаэль (2023), «Пересмотр вопроса о справедливой арендной плате в бюджете», ECAI 2023 , Frontiers in Artificial Intelligence and Applications, IOS Press, стр. 52–59, doi : 10.3233/FAIA230253, ISBN 978-1-64368-436-9, получено 2024-07-28{{citation}}: CS1 maint: числовые имена: список авторов ( ссылка )
21. Велес, Родриго А. (2022-07-01). «Полиномиальный алгоритм для максминного и минмаксного разделения ренты без зависти при мягком бюджете». Социальный выбор и благосостояние . 59 (1): 93–118. doi :10.1007/s00355-021-01386-z. ISSN  1432-217X.
22. Велес, Родриго А. (2023). «Справедливое распределение арендной платы при мягком бюджете». Игры и экономическое поведение . 139 (C): 1–14. doi :10.1016/j.geb.2023.01.008.
23. Аруначалешваран, Эшвар Рам; Барман, Сиддхарт; Рати, Нидхи (август 2022 г.). «Полностью полиномиальные схемы аппроксимации для справедливого разделения ренты». Математика исследования операций . 47 (3): 1970–1998. arXiv : 1807.04163 . doi : 10.1287/moor.2021.1196. ISSN  0364-765X.
24. Сан, Нин; Ян, Заифу (2003). "Общая стратегия доказательства справедливого механизма распределения" (PDF) . Economics Letters . 81 : 73. doi :10.1016/s0165-1765(03)00151-4.
25. Андерссон, Томми; Свенссон, Ларс-Гуннар (2008). «Повторное рассмотрение неманипулятивного назначения индивидуумов на должности». Математические социальные науки . 56 (3): 350. doi :10.1016/j.mathsocsci.2008.05.004.
26. Андерссон, Томми (2009). «Повторный взгляд на механизм справедливого распределения, защищенный от общей стратегии». Economics Bulletin . 29 (3): 1719–1724.
27. Андерссон, Томми; Элерс, Ларс; Свенссон, Ларс-Гуннар (2014). «Бюджетный баланс, справедливость и минимальная манипулируемость». Теоретическая экономика . 9 (3): 753. doi : 10.3982/te1346 . hdl : 10419/150236 .