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

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

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

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

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

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

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

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

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

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

Порядковый номер [ править ]

Вс: по одному человеку в комнате [ править ]

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

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

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

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

^[9] и ^[10] предоставляют популяризированные объяснения протокола Harmony аренды Су.

^[11] и ^[12] предоставляют интерактивные реализации.

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

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

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

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

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

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

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

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

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

Такая универсальность может быть полезной по нескольким причинам. ^[2]

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

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

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

Кардинальная версия [ править ]

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

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

Несовместимость EF и NN [ править ]

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

Здесь единственная максимальная сумма распределения дает комнату 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 [13]} предлагают процедуру разрыва :

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

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

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

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

Хааке, Райт и Су: EF, но не NN [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сун и Влах: EF и NN, если возможно [ править ]

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

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

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

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

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

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

Маш, Гал, Прокачча и Зик: EF и maximin [ править ]

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

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

Соображения по поводу бюджета [ править ]

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

Стратегические соображения [ править ]

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

Единственная максимальная сумма распределения - это предоставление комнаты 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}$

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

Сунь и Ян: изменение проблемы [ править ]

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]