Распределение предметов без зависти (EF) - это проблема справедливого распределения предметов , в которой критерием справедливости является свобода от зависти - каждый агент должен получить комплект, который, по его мнению, по крайней мере не хуже, чем у любого другого агента. [1] : 296–297
Поскольку элементы неделимы, назначение EF может не существовать. Самый простой случай - когда есть один предмет и как минимум два агента: если предмет назначен одному агенту, другой позавидует. Таким образом, процедуры разделения предусматривают различные виды расслабления.
Раздача вещей и денег без зависти
Свобода от зависти достижима, когда помимо неделимых предметов есть еще и делимое благо («деньги»).
Частным случаем такой настройки является разделение комнат в квартире между жильцами. Он характеризуется двумя требованиями: (а) количество агентов равно количеству объектов, (б) общая сумма денег, выплачиваемых агентами, должна равняться общей ренте (которая фиксируется заранее). Это известно как проблема арендной гармонии .
Второй особый случай - продажа объектов покупателям. В этом случае сумма платежей не фиксируется заранее, и цель состоит в том, чтобы максимизировать либо доход продавца, либо социальное благополучие, при условии отсутствия зависти. Кроме того, количество объектов может отличаться от количества агентов, а некоторые объекты могут быть отброшены. Это известно как проблема ценообразования без зависти .
Третий случай - это когда доброжелательная третья сторона желает субсидировать выделение, но хочет минимизировать размер субсидии, при условии отсутствия зависти. Эта проблема называется распределением минимальных субсидий без зависти, и она изучалась в нескольких условиях.
Агенты единичного спроса
Агенты единичного спроса интересуются не более чем одним товаром. В экономической литературе принято считать, что у каждого агента есть функция полезности на связках (связка - это пара объекта и определенной суммы денег). Функция полезности должна быть непрерывной и увеличиваться в деньгах. Он не обязательно должен быть линейным по деньгам, но должен быть «архимедовым», т. Е. Существует некоторое значение V такое, что для каждых двух объектов j и k полезность объекта j плюс V должна быть больше, чем полезность объекта k (альтернативно, полезность получения объекта j бесплатно больше, чем полезность получения объекта k и оплаты V ). Квазилинейная утилита - это частный случай архимедовой утилиты, в которой V - это наибольшая разница значений (для одного и того же агента) между двумя объектами.
Свенссон [2] впервые доказал, что, когда все агенты архимедовы, распределение без зависти существует и является оптимальным по Парето.
Деманж, Гейл и Сотомайор [3] показали естественный восходящий аукцион, который обеспечивает распределение без зависти с использованием денежных выплат для агентов спроса на единицу.
Маскин [4] доказал существование оптимального по Парето распределения без зависти, когда общий запас денег превышает ( n-1 ) V. В доказательствах используется конкурентное равновесие .
Обратите внимание, что может потребоваться субсидия в размере ( n -1) V : если все агенты оценивают один объект в V, а другие объекты в 0, то для защиты от зависти требуется субсидия в V для каждого агента, который не получает объект.
Таденума и Томсон [5] изучают несколько свойств непротиворечивости правил распределения без зависти.
Арагонес [6] характеризует минимальный размер субсидии, необходимый для отсутствия зависти. Распределение, при котором достигается эта минимальная субсидия, почти уникально: есть только один способ объединить объекты с агентами, и все агенты безразличны среди всех распределений минимальных субсидий. Это совпадает с решением Алкана, Деманжа и Гейла, названного «денежно-Ролсианским решением». [7] Его можно найти за полиномиальное время, найдя соответствие максимального веса и затем найдя кратчайшие пути в определенном индуцированном графе.
Клин [8] представляет другой алгоритм с полиномиальным временем для тех же условий. Его алгоритм использует многогранник побочных платежей, которые делают данное распределение свободным от зависти: этот многогранник непуст, если исходное распределение является эффективным по Парето. Связность неориентированного графа зависти характеризует крайние точки этого многогранника. Это подразумевает метод поиска крайних распределений без зависти.
Добавки
Добавки являются более общими и могут содержать несколько наименований.
Алкан, Деманж и Гейл [7] показали, что распределение без зависти всегда существует, когда сумма денег достаточно велика. Это верно, даже когда предметы могут иметь отрицательную оценку.
Meertens, Potters и Reijnierse [9] доказывают существование свободных от зависти и оптимальных по Парето распределений при очень мягких предположениях относительно оценок (не обязательно квазилинейных).
Кавалло [10] обобщает традиционные бинарные критерии свободы от зависти, пропорциональности и эффективности (благосостояния) на меры степени, которые находятся в диапазоне от 0 до 1. В условиях канонического справедливого деления при любом эффективном распределительном механизме благосостояние наихудшего случая. коэффициент равен 0, коэффициент диспропорциональности - 1; Другими словами, результаты наихудшего случая являются как можно более плохими. Он ищет механизм, который обеспечивает высокое благосостояние, низкую зависть и низкую диспропорциональность в ожиданиях во всем спектре условий справедливого разделения. Механизм VCG не является подходящим кандидатом, в отличие от механизма перераспределения Бейли [11] и Кавалло [12] .
Халперн и Шах [13] изучают субсидию в общих условиях распределения предметов. Они рассматривают два случая:
- Выдача оговаривается заранее. В этом случае он «свободен от зависти» тогда и только тогда, когда он максимизирует сумму полезностей при всех переназначениях своих пакетов агентам, тогда и только тогда, когда его граф зависти не имеет циклов. Если стоимость каждого товара для каждого агента не превышает V , то субсидия в размере не более ( n -1) мВ всегда достаточна и может быть необходима. Распределение без зависти с минимальной субсидией может быть найдено за строго полиномиальное время.
- Размещение можно выбрать. В этом случае субсидии в размере ( n -1) V достаточно в следующих случаях:
- Когда оценки агентов бинарные (0 или 1). Тогда любое распределение максимального продукта или лексимин-оптимальное распределение требует не более ( n -1) V субсидии и может быть найдено за полиномиальное время. Вычисление минимальной субсидии, необходимой для достижения EF, эквивалентно по Тьюрингу проверке наличия свободного от зависти распределения, что является NP-трудным, когда ограничивается не расточительным распределением.
- Когда все агенты имеют одинаковую аддитивную оценку. Тогда любое выделение ресурсов не вызывает зависти. Распределение, которое требует не более ( n -1) V субсидии, может быть найдено за полиномиальное время. Распределение минимизирует субсидию, если и только если оно минимизирует максимальную полезность для любого агента. Вычисление такого распределения является NP-трудным и может быть решено с помощью алгоритма максимального произведения.
- Когда есть два агента, при циклическом распределении элементов с определенным порядком агента обнаруживается распределение, которое не вызывает зависти с субсидией не выше V.
Брюстл, Диппель, Нараян, Судзуки и Ветта [14] улучшают верхние границы требуемой субсидии:
- При аддитивной оценке всегда достаточно субсидии в размере не более V на агента и не более ( n -1) V в целом. Более того, существует распределение, достигающее этой границы, которое также является EF1 и сбалансированным (мощности выделенных пакетов различаются не более чем на один товар). Его можно вычислить за полиномиальное время с помощью простого алгоритма: итеративно найти соответствие максимального веса в двудольном графе агентов и объектов.
- При общих монотонных оценках всегда достаточно субсидии в размере не более 2 ( n -1) V на агента и не более O ( n 2 V ). В частности, размер необходимой субсидии не зависит от количества объектов. Распределение, достигающее этой границы, может быть вычислено за полиномиальное время с помощью запросов значений.
Карагианнис и Иоаннидис [15] изучают вычислительную проблему минимизации субсидии:
- Для постоянного числа агентов они представляют алгоритм, который приблизительно определяет минимальную сумму субсидий с любой требуемой точностью. Для любого ε > 0 он находит распределение с субсидией не более, где max ( v ) - максимальное значение, которое агент присваивает всем объектам. Алгоритм использует динамическое программирование и работает во времени..
- Для переменного числа агентов тривиальный алгоритм аппроксимации достигает . Однако получить коэффициент аппроксимации, не зависящий от n , сложно: NP-сложно вычислить распределение с субсидией не более. Доказательство проводится редукцией от ограниченного варианта максимального трехмерного сопоставления , в котором каждая вершина встречается ровно дважды.
Обратите внимание, что распределение без зависти с субсидией остается без зависти, если фиксированная сумма берется с каждого агента. Таким образом, аналогичные методы можно использовать для поиска не субсидируемых ассигнований:
- Начисление среднего платежа каждому агенту дает беспристрастное распределение, которое также является сбалансированным по бюджету . Минимизация субсидии эквивалентна минимизации максимальной суммы, которую должен заплатить любой отдельный агент.
- Также можно использовать отрицательную субсидию (налог), минимизируя при этом общую сумму, которую должны платить все агенты.
Многомерные цели
Часто помимо справедливости необходимо достичь и других целей. Например, при назначении задач агентам требуется как избежать зависти, так и минимизировать время выполнения (- время выполнения последнего агента). Муалем представляет общую основу для задач оптимизации с гарантией свободы от зависти, которая естественным образом расширяет справедливое распределение предметов за счет денежных выплат. [16]
Азиз [17] стремится достичь с помощью денежных переводов беспристрастного и справедливого распределения . Он изучает не только аддитивные положительные полезности, но и любые супераддитивные полезности , как положительные, так и отрицательные:
- Для сверхаддитивных утилит существует алгоритм с полиномиальным временем, который обеспечивает свободу от зависти, справедливость и баланс бюджета (легко заменить баланс бюджета на субсидию).
- Если данное распределение является конвертируемым в EFEQ, то минимальная субсидия, необходимая для превращения его в EF + EQ, может быть найдена за линейное время.
- Найти распределение, конвертируемое в EFEQ с минимальной субсидией, является NP-трудной задачей, и ее нельзя приблизить к какому-либо положительному коэффициенту. Это просто потому, что проверка наличия выделения EF (для которого требуется 0 субсидий) является NP-сложной задачей.
- Субсидия в размере не более ( n -1) мВ всегда достаточна и может быть необходима вне зависимости от того, предоставлено ли выделение или нет.
Нахождение свободного от зависти распределения, когда оно существует
Предпочтительные заказы на связки: без зависти
Процедура подрезки находит полное распределение EF для двух агентов, если и только если такое распределение существует. Он требует от агентов ранжирования связок предметов, но не требует кардинальной полезной информации. Он работает, когда отношения предпочтений агентов строго монотонны, но не обязательно предполагать, что они являются реактивными предпочтениями . В худшем случае агентам, возможно, придется ранжировать все возможные пакеты, поэтому время выполнения может быть экспоненциальным по количеству элементов.
Предпочтительные заказы на товары: необходимо / возможно без зависти
Людям обычно легче ранжировать отдельные предметы, чем наборы. Предполагая, что все агенты имеют отзывчивые предпочтения , можно поднять ранжирование элементов до частичного ранжирования пакетов. Например, если рейтинг элементов равен w> x> y> z, то отзывчивость подразумевает, что {w, x}> {y, z} и {w, y}> {x, z}, но ничего не подразумевает о связи между {w, z} и {x, y}, между {x} и {y, z} и т. д.
Учитывая рейтинг предмета:
- Распределение обязательно без зависти (NEF), если оно не зависит от зависти согласно всем отзывчивым ранжированиям пакетов, согласующимся с ранжированием предметов;
- Распределение возможно без зависти (PEF), если оно не зависит от зависти согласно, по крайней мере, одному адаптивному ранжированию пакетов, совместимому с ранжированием элементов;
- Распределение обязательно является оптимальным по Парето (NPE), если оно является оптимальным по Парето согласно всем отзывчивым ранжированиям пакетов, согласованным с ранжированием элементов;
- Распределение, возможно, является оптимальным по Парето (PPE), если оно является оптимальным по Парето в соответствии с, по крайней мере, одним отзывчивым ранжированием пакетов, согласованным с ранжированием элементов.
Бувере, Эндрисс и Ланг [18] изучают алгоритмические вопросы поиска распределения NEF / PEF с дополнительным условием эффективности, в частности, полнотой или NPE или PPE. В общем, PEF прост с вычислительной точки зрения, тогда как NEF сложен с точки зрения вычислений.
Определение наличия выделения EF
Пустое выделение всегда EF. Но если нам нужна некоторая эффективность в дополнение к EF, тогда проблема решения становится вычислительно сложной: [1] : 300–310
- Решение о том, существует ли EF и полное выделение, завершается NP . Это верно даже тогда, когда есть только два агента, и даже когда их утилиты аддитивны и идентичны, поскольку в этом случае поиск распределения EF эквивалентен решению проблемы разделения . [19]
- Решение о том, существует ли справедливое распределение, требует экспоненциальной связи (по количеству товаров), когда агентов более двух. Когда есть два агента, сложность коммуникации зависит от конкретных комбинаций параметров. [20]
- Решение о том, существует ли распределение, эффективное по EF и Парето, выше NP: это Σ 2 п {\ Displaystyle \ Sigma _ {2} ^ {\ textrm {P}}} -в комплекте даже с дихотомическими утилитами [21] и даже с дополнительными утилитами . [22] ( Σ 2 п {\ Displaystyle \ Sigma _ {2} ^ {\ textrm {P}}} - это класс задач, которые могут быть решены за недетерминированное время с помощью оракула, который может решить любую проблему в NP).
Проблема решения может стать решаемой, если некоторые параметры задачи считаются фиксированными малыми константами: [23]
- Принимая во внимание количество объектов m в качестве параметра, наличие распределения PE + EF может быть решено вовремя.для аддитивных или дихотомических утилит. Когда утилиты являются двоичными и / или идентичными, время выполнения падает до. Здесь обозначение скрывает выражения, полиномиальные по другим параметрам (например, количеству агентов).
- Учитывая количество агентов n в качестве параметра, существование распределения PE + EF остается трудным. С дихотомическими утилитами это NP-сложно даже для n = 2. [21] Однако теперь она находится в NP и может быть эффективно решена с помощью NP-оракула (например, решателя SAT ). С участием агентов, это можно сделать с такие оракулы, и по крайней мере оракулы необходимы, если P = NP. С аддитивными утилитами это NP-сложно даже для n = 2. [21] Более того, он является W [1] -полным по отношению к количеству агентов, даже если все утилиты идентичны и закодированы в унарном формате.
- Принимая во внимание как количество агентов n, так и наибольшую полезность V в качестве параметров, существование распределения PE + EF может быть решено вовремя.для аддитивных утилит с использованием динамического программирования .
- Принимая во внимание как количество агентов n, так и количество уровней полезности z в качестве параметров, существование распределения PE + EF для идентичных аддитивных полезностей может быть решено с использованием целочисленной линейной программы спеременные; Алгоритм Ленстры позволяет решать такие ILP за время.
Поиск распределения с ограниченным уровнем зависти
Многие процедуры находят распределение "почти" без зависти, т. Е. Уровень зависти ограничен. Существуют различные представления о «почти» свободе от зависти:
EF1 - без зависти максимум до одного предмета
Выделение называется EF1, если для каждых двух агентов A и B, если мы удаляем не более одного элемента из связки B, тогда A не завидует B. [24] Распределение EF1 всегда существует и может быть эффективно найдено с помощью различных процедур. , особенно:
- Когда все агенты имеют слабо аддитивные утилиты, протокол циклического перебора находит полное распределение EF1. Требуется слабая аддитивность, поскольку каждый агент должен иметь возможность выбрать в каждой ситуации «лучший элемент».
- В более общем случае, когда все агенты имеют монотонно возрастающие полезности, процедура envy-graph находит полное распределение EF1. Единственное требование - агенты могут ранжировать наборы предметов. Если оценки агентов представлены функцией кардинальной полезности , то гарантия EF1 имеет дополнительную интерпретацию: числовой уровень зависти каждого агента является не более чем максимальной предельной полезностью - наибольшей предельной полезностью одного предмета для этого. агент.
- Когда агенты имеют произвольные утилиты (не обязательно аддитивные или монотонные), механизм A-CEEI возвращает частичное распределение EF1. Единственное требование - агенты могут ранжировать наборы предметов. Небольшое количество элементов может остаться нераспределенным, а небольшое количество элементов может потребоваться добавить. Распределение является эффективным по Парето по отношению к выделенным позициям.
- Maximum Nash Welfare алгоритм выбирает полное распределение , которое максимизирует продукт коммунальных услуг. Он требует, чтобы каждый агент предоставил числовую оценку каждой позиции, и предполагает, что полезности агентов складываются. Результирующее распределение является эффективным как для EF1, так и для Парето . [25]
- Различные другие алгоритмы возвращают распределения EF1, которые также являются эффективными по Парето; см. « Эффективное приблизительно справедливое распределение предметов» .
- Для двух агентов с произвольными монотонными оценками или трех агентов с аддитивными оценками распределение EF1 может быть вычислено с использованием числа запросов, логарифмических по количеству элементов. [26]
- Для двух агентов с произвольными функциями полезности (не обязательно монотонными) распределение EF1 может быть найдено за полиномиальное время. [27]
- Для не более 4 агентов с произвольными монотонными оценками или n агентов с одинаковыми монотонными оценками всегда существует распределение EF1, которое также связано (когда элементы предварительно заказаны в строке, например, дома на улице). В доказательстве используется алгоритм, аналогичный протоколам Симмонса – Су . Когда имеется n > 4 агентов, неизвестно, существует ли связанное выделение EF1, но связанное выделение EF2 существует всегда. [28]
EFx - без зависти к любому предмету
Распределение называется EFx, если для каждых двух агентов A и B, если мы удалим какой-либо элемент из набора B, то A не завидует B. [29] EFx строго сильнее, чем EF1: EF1 позволяет нам устранить зависть, удаляя пункт наиболее ценные (для A) из пучка Б; EFx требует, чтобы мы избавились от зависти, удалив наименее ценный предмет (для A). Известно, что распределение EFx существует в некоторых особых случаях:
- Когда есть два агента или когда есть n агентов с одинаковыми оценками . В этом случае leximin -оптимальным распределение является EFX и Парето-оптимальным. Однако для вычисления требуется экспоненциально много запросов. [30] [27]
- Когда имеется n агентов с аддитивными оценками , но существует не более двух разных значений для товаров. В этом случае любое распределение max-Nash-welfare - EFx. Более того, существует эффективный алгоритм для расчета распределения EFx (хотя и не обязательно max-Nash-welfare). [31]
- I Когда имеется n агентов с аддитивными оценками , но существует не более двух различных типов оценок. [32]
- Когда есть три агента с аддитивными оценками . В этом случае существует алгоритм с полиномиальным временем. [33]
Известны некоторые приближения:
- 1/2-приблизительное распределение EFx (которое также удовлетворяет другому понятию приблизительной справедливости, называемому Maximin Aware ) может быть найдено за полиномиальное время. [34]
- Приблизительное распределение EFx в размере 0,618 (которое также является EF1 и аппроксимирует другие понятия справедливости, называемые групповой максимальной долей и попарной максимальной долей ) можно найти за полиномиальное время. [35]
- Всегда существует частичное распределение EFx, когда благосостояние Нэша составляет не менее половины максимально возможного благосостояния Нэша. Другими словами, после пожертвования некоторых предметов на благотворительность, оставшиеся предметы могут быть распределены способом EFx. Эта оценка является наилучшей из возможных. На крупных рынках, где оценка агента по каждому предмету относительно невелика, алгоритм достигает EFx с почти оптимальным благосостоянием по Нэшу. [36] Достаточно пожертвовать n -1 вещей, и ни один агент не завидует набору подаренных вещей. [37]
Вопрос о том, существует ли вообще выделение EFx, остается открытым. Наименьший открытый случай - 4 агента с аддитивными оценками.
В отличие от EF1, который требует логарифмического количества запросов по количеству элементов, для вычисления распределения EFx может потребоваться линейное количество запросов, даже если есть два агента с идентичными аддитивными оценками. [26]
Еще одно различие между EF1 и EFx заключается в том, что количество выделений EFX может составлять всего 2 (для любого количества элементов), в то время как количество выделений EF1 всегда экспоненциально зависит от количества элементов. [38]
EFm - приблизительный без зависти смесь делимых и неделимых предметов
Некоторые сценарии разделения включают как делимые, так и неделимые объекты, такие как делимые земли и неделимые дома. Выделение называется EFm, если для каждых двух агентов A и B: [39]
- Если набор B содержит некоторые делимые товары, то A не завидует B (как при распределении EF).
- Если набор B содержит только неделимые товары, то A не завидует B после удаления не более одного предмета из набора B (как в распределении EF1).
Распределение EFm существует для любого количества агентов. Однако для его обнаружения требуется оракул для точного разделения торта. Без этого оракула распределение EFm может быть вычислено за полиномиальное время в двух частных случаях: два агента с общими аддитивными оценками или любое количество агентов с кусочно-линейными оценками.
В отличие от EF1, который совместим с оптимальностью по Парето, EFm может быть несовместим с ним.
Сведение к минимуму зависти
Вместо того, чтобы использовать наихудший предел количества зависти, можно попытаться минимизировать количество зависти в каждом конкретном случае. См. Сведения и ссылки в разделе « Минимизация зависти» .
Поиск частичного распределения EF
Процедура AL находит выделение EF для двух агентов. Он может отбросить некоторые элементы, но окончательное распределение является эффективным по Парето в следующем смысле: никакое другое распределение EF не лучше для одного и слабо лучше для другого. Процедура AL требует от агентов только ранжирования отдельных элементов. Предполагается, что агенты имеют адаптивные предпочтения, и возвращает распределение, которое обязательно является свободным от зависти (NEF).
Процедура Скорректированный победитель возвращает полное и эффективное распределение EF для двух агентов, но, возможно, придется вырезать один элемент (в качестве альтернативы, один элемент остается в совместном владении). Он требует, чтобы агенты сообщали числовое значение для каждого элемента, и предполагает, что у них есть дополнительные утилиты .
Когда каждый агент может получить не более одного элемента, а оценки являются двоичными (каждый агент либо любит, либо не любит каждый элемент), существует алгоритм с полиномиальным временем, который находит соответствие максимальной мощности без зависти . [40]
Существование распределений EF со случайными оценками
Если агенты имеют аддитивные функции полезности , полученные из распределений вероятностей, удовлетворяющих некоторым критериям независимости, и количество элементов достаточно велико по сравнению с количеством агентов, то распределение EF существует с высокой вероятностью . В частности: [41]
- Если количество предметов достаточно велико: , то, если существует распределение EF (вероятность стремится к 1, когда m стремится к бесконечности).
- Если количество элементов недостаточно велико, т. Е. , то если выделение EF не существует.
Свобода от зависти против других критериев справедливости
- Каждое распределение EF является минимальным и максимальным . Это следует непосредственно из порядковых определений и не зависит от аддитивности.
- Если все агенты имеют аддитивные функции полезности , то распределение EF также пропорционально и справедливо по максимуму-минимуму . В противном случае распределение EF может быть непропорциональным и даже не максимальным и минимальным.
- Любое распределение конкурентного равновесия из равных доходов также не вызывает зависти. Это верно независимо от аддитивности. [24]
- Каждое оптимальное по Нэшу распределение (распределение, которое максимизирует продукт полезности) - это EF1. [29]
- Свобода от зависти к группе - это усиление свободы от зависти, которое применимо как к делимым, так и к неделимым объектам.
Подробную информацию и ссылки см. В Справедливом распределении предметов .
Таблица результатов
Ниже используются следующие сокращения:
- = количество агентов, участвующих в дивизионе;
- = количество элементов, которые нужно разделить;
- EF = без зависти, EF1 = без зависти, за исключением-1-элемента (слабее, чем EF), MEF1 = без маргинальной-зависти-без-за исключением-1-элемента (слабее, чем EF1).
- PE = Парето-эффективный.
Имя | #partners | Вход | Предпочтения | # запросы | Справедливость | Эффективность | Комментарии |
---|---|---|---|---|---|---|---|
Подрезка | 2 | Пакетный рейтинг | Строго монотонный | EF | Полный | Если и только если существует полное распределение EF | |
AL | 2 | Рейтинг предмета | Слабо добавка | Обязательно-EF | Частично, но не с преобладанием Парето со стороны другого НЭФ | ||
Скорректированный победитель | 2 | Оценка предметов | Добавка | EF и равноправие | PE | Может разделить один предмет. | |
По-круговой | Рейтинг предмета | Слабо добавка | Обязательно-EF1 | Полный | |||
Зависть-граф | Пакетный рейтинг | Монотонный | EF1 | Полный | |||
A-CEEI | Пакетный рейтинг | Любой | ? | EF1 и -maximin-доля | Частично, но PE по выделенным элементам | Также приблизительно стратегически устойчивый, когда агентов много. | |
Максимум-Nash-Welfare [29] | Оценка предметов | Добавка | NP-жесткий (но есть приближения в особых случаях) | EF1, и примерно--maximin-доля | PE | В субмодульных энергосистемах распределение - PE и MEF1. |
Рекомендации
- ^ a b Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. ISBN 9781107060432.( бесплатная онлайн-версия )
- ^ Свенссон, Ларс-Гуннар (1983). «Крупные неделимые: анализ ценового равновесия и справедливости». Econometrica . 51 (4): 939–954. DOI : 10.2307 / 1912044 . ISSN 0012-9682 . JSTOR 1912044 .
- ^ Деманж Г., Гейл Д., Сотомайор М. (1986). «Многопозиционные аукционы». Журнал политической экономии . 94 (4): 863–872. DOI : 10.1086 / 261411 . JSTOR 1833206 . S2CID 154114302 .
- ^ Маскин, Эрик С. (1987), Фейвел, Джордж Р. (редактор), «О справедливом распределении неделимых благ» , Стрелка и основы теории экономической политики , Лондон: Palgrave Macmillan UK, стр. 341– 349, DOI : 10.1007 / 978-1-349-07357-3_12 , ISBN 978-1-349-07357-3, получено 2021-02-16
- ^ Таденума, Коичи; Томсон, Уильям (1991). «Отсутствие зависти и последовательность в экономике с неделимыми благами». Econometrica . 59 (6): 1755–1767. DOI : 10.2307 / 2938288 . ISSN 0012-9682 . JSTOR 2938288 .
- ^ Арагонес, Энрикета (1995). «Вывод раулсианского денежного решения». Социальный выбор и благосостояние . 12 (3): 267–276. DOI : 10.1007 / BF00179981 . ISSN 0176-1714 . JSTOR 41106132 . S2CID 154215964 .
- ^ а б Алкан, Ахмет; Деманж, Габриель; Гейл, Дэвид (1991). «Справедливое распределение неделимых благ и критерии справедливости». Econometrica . 59 (4): 1023–1039. DOI : 10.2307 / 2938172 . ISSN 0012-9682 . JSTOR 2938172 .
- ^ Клин, Флип (2000-03-01). «Алгоритм распределения без зависти в экономике с неделимыми объектами и деньгами» . Социальный выбор и благосостояние . 17 (2): 201–215. DOI : 10.1007 / s003550050015 . ISSN 1432-217X . S2CID 18544150 .
- ^ Меертенс, Марк; Поттерс, Джос; Рейджниерс, Ганс (2002-12-01). «Распределение без зависти и Парето в экономике с неделимыми товарами и деньгами» . Математические социальные науки . 44 (3): 223–233. DOI : 10.1016 / S0165-4896 (02) 00064-1 . ISSN 0165-4896 .
- ^ Руджеро Кавалло (2012). Справедливость и благосостояние через перераспределение при передаче полезности (PDF) . AAAI-12.
- ^ Бейли, Мартин Дж. (1997). «Процесс выявления спроса: распределить излишки». Общественный выбор . 91 (2): 107–126. DOI : 10,1023 / A: 1017949922773 . S2CID 152637454 .
- ^ Кавалло, Руджеро (2006). «Принятие оптимальных решений с минимальными отходами». Материалы пятой международной совместной конференции по автономным агентам и мультиагентным системам - AAMAS '06 . п. 882. DOI : 10,1145 / 1160633,1160790 . ISBN 1595933034.
- ^ Халперн, Дэниел; Шах, Нисарг (2019). Фотакис, Димитрис; Маркакис, Евангелос (ред.). «Честный раздел с субсидией» . Алгоритмическая теория игр . Конспект лекций по информатике. Чам: Издательство Springer International. 11801 : 374–389. DOI : 10.1007 / 978-3-030-30473-7_25 . ISBN 978-3-030-30473-7.
- ^ Брюстл, Йоханнес; Диппель, Джек; Нараян, Вишну В .; Сузуки, Машбат; Ветта, Адриан (13.07.2020). «Один доллар избавляет от зависти» . Материалы 21-й конференции ACM по экономике и вычислениям . EC '20. Виртуальное мероприятие, Венгрия: Ассоциация вычислительной техники: 23–39. arXiv : 1912.02797 . DOI : 10.1145 / 3391403.3399447 . ISBN 978-1-4503-7975-5. S2CID 208637311 .
- ^ Карагианнис, Иоаннис; Иоаннидис, Ставрос (06.02.2020). «Вычисление свободных от зависти ассигнований с ограниченными субсидиями». arXiv : 2002.02789 [ cs.GT ].
- ^ Муалем А (2014). «Ярмарка по замыслу: многомерные механизмы без зависти». Игры и экономическое поведение . 88 : 29–46. DOI : 10.1016 / j.geb.2014.08.001 .
- ^ Азиз, Харис (18.03.2020). «Достижение свободы от зависти и справедливости с помощью денежных переводов». arXiv : 2003.08125 [ cs.GT ].
- ^ Сильвен Бувере, Улле Эндрисс, Жером Ланг (2010). Справедливое разделение при порядковых предпочтениях: вычисление распределения неделимых товаров без зависти . ECAI 2010. С. 387–392.CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Lipton, RJ; Markakis, E .; Mossel, E .; Сабери, А. (2004). «О примерно справедливых размещениях неделимых товаров». Материалы 5-й конференции ACM по электронной коммерции - EC '04 . п. 125. DOI : 10,1145 / 988772,988792 . ISBN 1-58113-771-0.
- ^ Плаут, Бенджамин; Рафгарден, Тим (01.01.2020). «Коммуникационная сложность дискретного выставочного дивизиона» . SIAM Journal on Computing . 49 (1): 206–243. arXiv : 1711.04066 . DOI : 10.1137 / 19M1244305 . ISSN 0097-5397 . S2CID 212667868 .
- ^ а б в Bouveret, S .; Ланг, Дж. (2008). «Эффективность и непринужденность в справедливом разделении неделимых товаров: логическое представление и сложность» . Журнал исследований искусственного интеллекта . 32 : 525–564. DOI : 10.1613 / jair.2467 .
- ^ Де Кейзер, Барт; Бувере, Сильвен; Клос, Томас; Чжан, Инцянь (2009). «О сложности эффективности и непричинения зависти при честном разделении неделимых товаров с добавочными предпочтениями». Теория алгоритмических решений . Конспект лекций по информатике. 5783 . п. 98. DOI : 10.1007 / 978-3-642-04428-1_9 . ISBN 978-3-642-04427-4.
- ^ Блием, Бернхард; Бредерек, Роберт; Нидермайер, Рольф (09.07.2016). «Сложность эффективного распределения ресурсов без зависти: мало агентов, ресурсов или уровней полезности» . Материалы двадцать пятой международной совместной конференции по искусственному интеллекту . IJCAI'16. Нью-Йорк, Нью-Йорк, США: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
- ^ а б Будиш, Эрик (2011). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов». Журнал политической экономии . 119 (6): 1061–1103. CiteSeerX 10.1.1.357.9766 . DOI : 10.1086 / 664613 . S2CID 154703357 .
- ^ Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM по экономике и вычислениям 2016 года - EC '16. п. 305. DOI : 10,1145 / 2940716,2940726 . ISBN 9781450339360.
- ^ а б О, Хун; Procaccia, Ariel D .; Суксомпонг, Варут (17.07.2019). «Справедливое распределение многих товаров с помощью нескольких запросов» . Труды конференции AAAI по искусственному интеллекту . 33 (1): 2141–2148. DOI : 10.1609 / aaai.v33i01.33012141 . ISSN 2374-3468 . S2CID 51867780 .
- ^ а б Берци, Кристоф; Bérczi-Kovács, Erika R .; Борос, Эндре; Гедефа, Фекаду Толесса; Камияма, Наоюки; Кавита, Теликепалли; Кобаяси, Юске; Макино, Кадзухиса (08.06.2020). «Расслабление без зависти для товаров, дел и смешанных вещей». arXiv : 2006.04428 [ econ.TH ].
- ^ Било, Витторио; Карагианнис, Иоаннис; Фламмини, Микеле; Игараси, Аюми; Монако, Джанпьеро; Петерс, Доминик; Винчи, Козимо; Цвикер, Уильям С. (28.08.2018). «Распределение почти без зависти с подключенными пакетами». arXiv : 1808.09406 [ cs.GT ].
- ^ а б в Карагианнис, Иоаннис; Курокава, Дэвид; Мулен, Эрве; Procaccia, Ariel D .; Шах, Нисарг; Ван, Цзюньсин (2016). Необоснованная справедливость максимального благосостояния Нэша (PDF) . Труды конференции ACM по экономике и вычислениям 2016 года - EC '16. п. 305. DOI : 10,1145 / 2940716,2940726 . ISBN 9781450339360.
- ^ Плаут, Бенджамин; Рафгарден, Тим (01.01.2020). «Почти свобода от зависти с общими оценками» . Журнал СИАМ по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . DOI : 10.1137 / 19M124397X . ISSN 0895-4801 .
- ^ Аманатидис, Георгиос; Бирмпас, Георгиос; Филос-Рацикас, Арис; Холлендер, Александрос; Вудурис, Александрос А. (01.06.2020). «Максимальное благосостояние Нэша и другие истории о EFX». arXiv : 2001.09838 [ cs.GT ].
- ^ Махара, Рёга (20.08.2020). «Существование EFX для двух аддитивных оценок». arXiv : 2008.08798 [ cs.GT ].
- ^ Чаудхури, Бхаскар Рэй; Гарг, Джугал; Мельхорн, Курт (30 мая 2020 г.). «EFX существует для трех агентов». arXiv : 2002.05119 [ cs.GT ].
- ^ Чан, Хау; Чен, Цзин; Ли, Бо; У, Сяовэй (2019-10-25). «Максимально ориентированное размещение неделимых товаров». arXiv : 1905.09969 [ cs.GT ].
- ^ Аманатидис, Георгиос; Нтокос, Апостолос; Маркакис, Евангелос (2020). «Несколько зайцев одним выстрелом: избиение 1/2 для EFX и GMMS посредством исключения цикла зависти». Теоретическая информатика . 841 : 94–109. arXiv : 1909.07650 . DOI : 10.1016 / j.tcs.2020.07.006 . S2CID 222070124 .
- ^ Карагианнис, Иоаннис; Гравин, Ник; Хуан, Синь (17.06.2019). «Свобода от зависти к любому предмету с высоким уровнем благосостояния Нэша: достоинство дарения предметов» . Материалы конференции ACM по экономике и вычислениям 2019 . EC '19. Феникс, Аризона, США: Ассоциация вычислительной техники: 527–545. arXiv : 1902.04319 . DOI : 10.1145 / 3328526.3329574 . ISBN 978-1-4503-6792-9. S2CID 60441171 .
- ^ Чаудхури, Бхаскар Рэй; Кавита, Теликепалли; Мельхорн, Курт; Сгурица, Алкмини (2019-12-23), «Небольшая благотворительность гарантирует почти свободу от зависти» , Труды Симпозиума ACM-SIAM 2020 по дискретным алгоритмам , Труды, Общество промышленной и прикладной математики, стр. 2658–2672, arXiv : 1907.04596 , DOI : 10.1137 / 1.9781611975994.162 , ISBN 978-1-61197-599-4, S2CID 195874127 , получено 02.10.2020
- ^ Суксомпонг, Варут (30 сентября 2020 г.). «По количеству почти беспричинных выделений» . Дискретная прикладная математика . 284 : 606–610. arXiv : 2006.00178 . DOI : 10.1016 / j.dam.2020.03.039 . ISSN 0166-218X . S2CID 215715272 .
- ^ Бэй, Сяохуэй; Ли, Цзыхао; Лю, Цзиньянь; Лю, Шэнсинь; Лу, Синьхан (2021 г.). «Справедливое разделение смешанных неделимых и неделимых товаров». Искусственный интеллект . 293 : 103436. arXiv : 1911.07048 . DOI : 10.1016 / j.artint.2020.103436 . S2CID 231719223 .
- ^ Айгнер-Хорев, Элад; Сегал-Халеви, Эрель (22.12.2020). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv : 1901.09527 [ cs.DS ].
- ^ Джон П. Дикерсон; Джонатан Голдман; Джереми Карп; Ариэль Д. Прокачча; Туомас Сандхольм (2014). Вычислительный взлет и падение справедливости . В материалах Двадцать восьмой конференции AAAI по искусственному интеллекту (2014). С. 1405–1411. CiteSeerX 10.1.1.703.8413 . Ссылка ACM