Главная
Строительство
Ремонт
Дизайн и интерьер




27.02.2021


27.02.2021


27.02.2021


27.02.2021


27.02.2021











         » » Эффективное разрезание торта

Эффективное разрезание торта

09.02.2021

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

Наиболее часто эффективность изучалась в связи со справедливостью, а целью является поиск разбиения, которое удовлетворяет обоим критериям, эффективности и справедливости.

Предположения

Есть торт C {displaystyle C} . Обычно предполагается либо конечный одномерный отрезок, либо двумерный многоугольник, либо конечное подмножество многомерного евклидова пространства R d {displaystyle mathbb {R} ^{d}} .

Есть n {displaystyle n} участников. Каждый участник i {displaystyle i} имеет субъективную функцию оценки V i {displaystyle V_{i}} , которая отображает подмножества C {displaystyle C} в числа.

C {displaystyle C} нужно разбить на n {displaystyle n} непересекающихся подмножеств, таких что каждый участник получает отдельный кусок. Кусок, передаваемый участнику i {displaystyle i} обозначим X i {displaystyle X_{i}} , так что C = X 1 ⊔ . . . ⊔ X n {displaystyle C=X_{1}sqcup ...sqcup X_{n}} .

Пример торта

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

Эффективность

Разбиение Y {displaystyle Y} доминирует по Парето X {displaystyle X} , если по меньшей мере одно лицо чувствует, что Y {displaystyle Y} лучше, чем X {displaystyle X} , и никто не чувствует, что Y {displaystyle Y} хуже, чем X {displaystyle X} . Символически:

∀ i :   V i ( Y i ) ⩾ V i ( X i ) {displaystyle forall {i}: V_{i}(Y_{i})geqslant V_{i}(X_{i})} и ∃ i : V i ( Y i ) > V i ( X i ) {displaystyle exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})}

Эффективное по Парето (ЭП, англ. Pareto-efficient, PE) распределение — это распределение, которое не доминируется по Парето каким-либо другим распределением, то есть его нельзя улучшить без возражений. В примере торта возможно несколько ЭП распределений. Например, любое разбиение, которое даёт весь торт одному лицу, является ЭП, поскольку любое изменение в распределении приведёт к возражению этого одного лица. Естественно, ЭП распределение не обязательно справедливо.

Разбиение, которое и эффективно по Парето, и пропорционально, называется ЭППР (англ. Pareto-efficient and proportional, PEPR), а разбиение, которое и ЭП, и свободно от зависти, называется ЭПСЗ (англ. Pareto-efficient and envy-free , PEEF) для краткости.


Комбинация эффективности и справедливости

Делёж ЭППР

ЭП делёж можно получить тривиально путём передачи всего торта одному участнику. Но ЭП распределение, которое также и пропорционально, нельзя найти конечным алгоритмом. Доказательство, по существу, то же самое, что и для разрезания торта согласно полезности.

Делёж ЭПСЗ

Для n участников с аддитивными функциями оценок, когда куски могут быть несвязными, ЭПСЗ разбиение всегда существует. Это теорема Веллера.

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

Если торт является одномерной окружностью (то есть отрезком, два конца которого топологически отождествлены), а каждый участник должен получить связные дуги, то вышеприведённые результаты не выполняются — СЗ распределения не обязательно ЭП. Кроме того, существуют пары (неаддитивных) функций оценок, для которых никакого ЭПСЗ распределения не существует. Однако, если есть 2 агента и по меньшей мере один из них имеет аддитивную функцию оценок, то ЭПСЗ существует.