Задача справедливого распределения объектов

Справедли́вое распределе́ние объе́ктов — вид задачи справедливого дележа, в котором объекты, которые требуется распределить среди участников, являются неделимыми. Объекты следует распределить среди партнёров, которые оценивают объекты по-разному, и каждый предмет должен быть передан как единое целое одному участнику. Эта ситуация возникает в нескольких сценариях реальной жизни: несколько наследников хотят поделить наследство, в которое входит, например, дом, автомобиль, рояль и несколько картин; несколько лекторов решают поделить курсы, которые даются на их факультете. Каждый лектор может читать один или несколько курсов, но только полный курс; один курс несколько лекторов читать не могут.

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

Задача распределения объектов имеет несколько составляющих: Участники должны выразить свои предпочтения для различных наборов объектов. Группа должна решить, каков будет критерий справедливости. На основании предпочтений и критерия справедливости должен быть реализован алгоритм справедливого распределения для определения наиболее справедливого варианта решения проблемы. Эти составляющие объяснены в деталях ниже.

Предпочтения

Комбинаторные предпочтения Естественный путь определения предпочтений — попросить каждого участника сопоставить число каждому возможному набору предметов, то есть указать его ценность в числовом выражении. Например, если объектами, которые следует распределить, будут автомобиль и мотоцикл, участники могут оценить автомобиль в 800, а мотоцикл в 200, а набор {автомобиль, мотоцикл} в 900 (см. статью Функции полезности на неделимых товарах для дополнительных примеров). Имеется две проблемы с этими подходами: Участнику может быть сложно вычислить точную численную ценность набора предметов. Число возможных наборов может быть огромным — если имеется предметов, то имеется возможных наборов. Например, если имеется 16 предметов, то каждый участник должен будет представить свои предпочтения, указав 65536 чисел.

Первая проблема побуждает использовать порядковую полезность, а не количественную. В порядковой модели каждый участник должен показать лишь ранжирование по различным наборам, то есть сказать, какой набор объектов лучший, какой стоит на втором месте и т. д. Это может быть проще вычисления точных чисел, но остаётся сложным делом, если число объектов велико.

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

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

Аддитивные предпочтения Чтобы сделать задачу распределения объектов проще часто предполагается, что все объекты являются независимыми (таким образом, они не являются ни взаимозаменяемыми, ни комплементарными). Тогда При численном подходе каждый участник имеет аддитивную функцию полезности (называемую также модулярной функцией полезности). Когда агент сообщает значение каждого индивидуального объекта, легко вычислить значение набора путём суммирования значений входящих в него объектов. При порядковом подходе аддитивность позволяет нам делать некоторое ранжирование наборов. Например, если участник предпочитает объекты в порядке w > x > y > z, то он предпочтёт обязательно {w, x} набору {w, y} или наборы {x, y} и {w, y} набору {x}. Эти выводы только частичные, например, мы не можем знать, предпочтёт ли агент набор {w} набору {x, y} или даже набор {w, z} набору {x, y}.

Из аддитивности следует, что каждый участник может всегда выбрать «предпочтительный объект» из набора объектов на столе и этот выбор не зависит других объектов, которые участник может уже иметь. Это свойство используется в некоторых алгоритмах справедливого дележа, которые будут описаны ниже.

Компактные языки представления предпочтений Компактные языки представления предпочтений разрабатывались как компромисс между полной выразительностью комбинаторных предпочтений и простотой аддитивных предпочтений. Они обеспечивают сжатое представление некоторых естественных классов функций полезности, которые более общие, чем аддитивная полезность (но не настолько общие, как комбинаторная полезность). Некоторыми примерами служат 2-аддитивные предпочтения — каждый участник сообщает ценность для каждого набора размером 1 или 2. Значение набора вычисляется как сумма значений индивидуальных объектов в наборе и добавления значений пар в наборе. Обычно, когда имеются заменяемые объекты, значения пар будут отрицательными, а когда имеются дополняющие объекты, значения пар будут положительными. Эта идея может быть обобщена до k-аддитивных предпочтений для любого положительного целого k. Графические модели — для каждого участника имеется граф, который представляет зависимости между различными объектами. При численном подходе обычным средством является GAI net (обобщённая аддитивная независимость, ). При порядковом подходе обычным средством является CP net (условные предпочтения, ) и его расширения TCP net, UCP net, CP theory, CI net (условная важность, ) и SCI net (упрощение CI net ). Основанные на логике языки — каждый участник описывает некоторые наборы с помощью формул логики первого порядка и может назначить значение для каждой формулы. Например, участник может сказать: «Для (x или (y и z)) моё значение будет 5». Это означает, что агент назначает ценность 5 для любого набора из: x, xy, xz, yz, xyz. Языки торгов — изучались многие языки для представления комбинаторных предпочтений в контексте . Некоторые из этих языков могут быть приспособлены для условий распределения объектов.

Критерий справедливости

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

1. Max-min справедливая доля (, MFS): Max-min справедливая доля (называется также max-min гарантированной долей) агента является наиболее предпочтительным набором, который агент может гарантировать себе, если будет делящим лицом в протоколе Дели-и-выбирай. Распределение называется MFS-справедливым, если любой агент получает набор, который слегка предпочтительнее его MFS. MFS агента можно интерпретировать как максимальная полезность, которую агент может надеяться получить при распределении, когда все другие агенты имеют те же самые предпочтения, если агент всегда получает наихудшую долю. Это можно рассматривать как минимальное количество полезности, которое на которое агент может рассчитывать, основываясь на следующих доводах: если все другие агенты имеют те же предпочтения, что и я, имеется по меньшей мере одно распределение, которое даёт мне эту полезность и делает всех других агентов (слегка) богаче. Следовательно, нет никаких причин дать мне меньше. Это также максимальная полезность, которую агент может получить наверняка в игре распределения «Я режу, я выбираю последним» — агент предлагает лучшее распределение и оставляет остальным участникам выбрать свои доли, а сам получает оставшуюся долю. MFS-справедливость можно также описать как результат следующего процесса переговоров. Предлагается некоторое распределение. Каждый агент может возразить путём предложения другого разбиения предметов. Однако, делая это, он должен позволить всем другим агентам выбрать их доли перед тем как забрать свою. Следовательно, агент будет возражать на распределение только если он может предложить разбиение на наборы, которые все лучше текущего набора. Распределение MFS-справедливо тогда и только тогда, когда ни один из агентов не возражает, то есть для любого агент в любом разбиении существует набор, который слегка хуже, чем его текущая доля.

2. Пропорциональная справедливая доля (, PFS): Пропорциональная справедливая доля агента равна 1/n полезности от всего набора предметов. Распределение называется пропорциональным, если все агенты получают наборы, которые агенты оценивают по меньшей мере в справедливую пропорциональную долю.

3. Справедливая Min-max-доля (, mFS): Справедливая Min-max-доля агента равна минимальной полезности, которую агент надеется получить из распределения, если другие агенты имеют те же предпочтения, что и этот агент, и если агент получает всегда лучшую долю. Эта доля равна также минимальной полезности, которую агент может получить в игре распределения «Кто-то другой режет, я выбираю первым». Распределение является mFS-справедливым, если все агенты получают набор объектов, который для них слегка предпочтительнее их mFS. mFS-справедливость можно описать как результат следующего процесса переговоров. Предлагается некоторое распределение. Каждый агент может требовать, чтобы было сделано другое распределение другим агентом при разрешении, чтобы возражающий агент выбирал первым. Следовательно, агент возражал бы на имеющееся распределение только в случае, если во всех разбиениях существует набор, который он строго предпочитает текущему набору. Распределение mFS-справедливо тогда и только тогда, когда ни один из агентов не возражает против него, то есть для любого агента существует разбиение, в котором все наборы слегка хуже, чем его текущая доля.

Для любого агента с mFS стоит по меньшей мере . Следовательно, любое mFS-справедливое распределение пропорционально. Для любого агента с MFS стоит в лучшем случае . Следовательно, любое пропорциональное распределение является MFS-справедливым. Обе импликации строгие, даже когда любой агент имеет аддитивную полезность. Это иллюстрируется в следующем примере: Имеется 3 агента и 3 предмета: Алиса оценивает предметы как 2, 2, 2. Для неё MFS=PFS=mFS=2. Боб оценивает предметы как 3, 2, 1. Для него MFS=1, PFS=2 и mFS=3. Карл оценивает предметы как 3, 2, 1. Для него MFS=1, PFS=2 и mFS=3. Возможное распределение следующее: Любое распределение, которое даёт по предмету каждому участнику, является MFS-справедливость. Любое распределение, которое даёт первый и второй предметы Бобу и Карлу, а третий предмет — Алисе, является пропорциональным. Никакое распределение не будет mFS-справедливым.

Приведённые выше выводы не верны, если оценки агентов не под/супераддитивны.

4. Отсутствие зависти (, EF): любой агент предпочитает свой собственный набор любому другому набору. Любое свободное от зависти распределение всех предметов является mFS-справедливым. Это следует прямо из порядковых определений и не зависит от аддитивности. Если оценки аддитивны, то EF распределение также пропорционально и MFS-справедливо. В противном случае EF распределение может быть не пропорциональным и даже не MFS. См. Завистливое распределение предметов для детального рассмотрения.