Строго пропорциональное деление

деление Сильно пропорциональное ^[1] (иногда называемое сверхпропорциональным делением ) — это разновидность справедливого дележа . Это разделение ресурсов между n партнерами, при котором стоимость, полученная каждым партнером, строго превышает причитающуюся ему долю в 1/ n от общей стоимости. при строго пропорциональном разделении ресурса C между n партнерами каждый партнер i с мерой стоимости Vi _{Формально} получает долю X _i такую, что

$V_{i}(X_{i})>V_{i}(C)/n$ .

Очевидно, что строго пропорционального разделения не существует, когда все партнеры имеют одинаковую меру стоимости. Наилучшее состояние, которое всегда можно гарантировать, — это $V_{i}(X_{i})\geq V_{i}(C)/n$ , что является условием простого пропорционального деления . Однако можно надеяться, что, когда разные агенты имеют разные оценки, можно будет использовать этот факт на благо всех игроков и дать каждому из них строго больше, чем причитается ему.

Существование

В 1948 году Хьюго Штайнхаус предположил существование сверхпропорционального деления торта : ^[2]

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

В 1961 году Дубинс и Спэньер доказали, что необходимое условие существования также является достаточным. То есть всякий раз, когда оценки партнеров аддитивны и неатомарны и есть хотя бы два партнера, функция ценности которых хоть немного различается, то имеет место сверхпропорциональное разделение, при котором все партнеры получают более 1/ n .

Доказательство было следствием теоремы Дубинса-Спанье о выпуклости . Это было чисто экзистенциальное доказательство, основанное на аргументах выпуклости.

Алгоритмы

В 1986 году Дуглас Р. Вудалл опубликовал первый протокол для нахождения сверхпропорционального деления. ^[3]

Пусть C — весь торт. Если оценки агентов различны, то для этого должен быть свидетель : свидетель — это конкретный кусок пирога, скажем, X ⊆ C , который какими-то двумя партнерами, скажем, Алисой и Бобом, оценивается по-разному. Пусть Y := C \ X. Пусть a _x =V _Alice (X) и b _x =V _Bob (X) и a _y =V _Alice (Y) и b _y =V _Bob (Y) и предположим, что wlog что:

b _x > a _x , что подразумевает: by _y < a _y .

Идея состоит в том, чтобы разделить X и Y отдельно: при разделении X мы дадим немного больше Бобу и немного меньше Алисе; при разделении Y мы дадим немного больше Алисе и немного меньше Бобу.

Протокол Вудалла для двух агентов

Найдите рациональное число между b _x и a _x , скажем p/q такое, что b _x > p/q > a _x . Отсюда следует, что _y < (qp)/q < a _y . Попросите Боба разделить X на p равных частей, а Y — на qp равных частей.

Согласно нашим предположениям, Боб оценивает каждую часть X в точке b _x /p > 1/ q , а каждую часть Y в точке b _y /(qp) < 1/ q . Но для Алисы хотя бы одна часть X (скажем, X ₀ ) должна иметь стоимость меньше 1/ q и хотя бы одна часть Y (скажем, Y ₀ ) должна иметь стоимость больше 1/ q .

Итак, теперь у нас есть две части, X ₀ и Y ₀ , такие, что:

В _Боб (X ₀ )>В _Алиса (X ₀ )

V _Боб (Y ₀ )<V _Алиса (Y ₀ )

Пусть Алиса и Боб разделят остаток C \ X ₀ \ Y ₀ между собой пропорциональным образом (например, с помощью разделяем и выбираем ). Добавьте Y ₀ к куску Алисы и добавьте X ₀ к куску Боба.

Теперь каждый партнер считает, что его/ее распределение строго лучше, чем у другого, поэтому его значение строго больше 1/2.

Протокол Вудалла для n партнеров

Распространение этого протокола на n партнеров основано на протоколе Fink «Lone Chooser» .

Предположим, у нас уже есть строго пропорциональное разделение на i -1 партнеров (при i≥3 ). партнёр #i Теперь в партию вступает и нам надо отдать ему по небольшому куску от каждого из первых i -1 партнёров, так чтобы новое деление по-прежнему было строго пропорциональным.

Рассмотрим, например, партнера №1. Пусть d будет разницей между текущей стоимостью партнера № 1 и (1/( i -1)). Поскольку текущее деление строго пропорционально, мы знаем, что d>0 .

Выберите целое положительное число q такое, что: $d>{\frac {1}{(i-1)i(q(i-1)-1)}}$

Попросите партнера №1 разделить свою долю на $qi-1$ части, которые он считает равноценными, и пусть новый партнер выбирает $q$ предметы, которые он считает наиболее ценными.

Партнер №1 остается со стоимостью ${\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}$ его предыдущей стоимости, которая была ${\frac {1}{i-1}}+d$ (по определению d ). Первый элемент становится ${\frac {q(i-1)-1}{(i-1)(qi-1)}}$ и d становится ${\frac {1}{i(i-1)(qi-1)}}$ ; их суммирование дает, что новое значение больше: ${\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}$ от всего торта.

Что касается нового партнера, то после того, как он заберет q фигур у каждого из первых i -1 партнеров, его общая стоимость составит не менее: ${\frac {q}{qi-1}}>{\frac {1}{i}}$ от всего торта.

Это доказывает, что новое разделение также является строго пропорциональным.

Протокол Барбанеля

Юлиус Барбанель ^[1] распространил алгоритм Вудалла на агентов с различными правами , включая иррациональные права. В этом случае права каждого агента i представлены весом $w_{i}$ , с $W:=\sum _{i}w_{i}$ . Сильно пропорциональное распределение — это распределение, при котором для каждого агента i :

$V_{i}(X_{i})>w_{i}\cdot V_{i}(C)/W$ .

Протокол Янко-Джу

Янко и Джу ^[4] представил более простой алгоритм для агентов с разными правами. Фактически, они показали, как свести проблему строго пропорционального деления (с равными или разными правами) на две проблемы пропорционального деления с разными правами :

Для фрагмента X измените право Алисы на $w_{A}-1/a_{x}$ и право Боба на $w_{B}+1/b_{x}$ . Поскольку b _x > a _x_, сумма новых пособий строго меньше, чем $w_{A}+w_{B}$ , поэтому сумма всех n прав (обозначаемых W _X ) строго меньше W.
Для фрагмента Y измените право Алисы на $w_{A}+1/a_{y}$ и право Боба на $w_{B}-1/b_{y}$ . , поскольку y _{Здесь также} < _ay_, новая сумма всех прав (обозначаемая W _Y ) строго меньше W .
Ценность Алисы как минимум ${\begin{aligned}&(w_{A}-1/a_{x})\cdot a_{x}/W_{X}+(w_{A}+1/b_{y})\cdot b_{x}/W_{Y}=\\=&(w_{A}a_{x}-1)/W_{X}+(w_{A}a_{y}+1)/W_{Y}\\>&(w_{A}a_{x}-1)/W+(w_{A}a_{y}+1)/W\\=&w_{A}V_{A}(C)/W\end{aligned}}$
Аналогично, значение Боба не менее ${\begin{aligned}&(w_{B}+1/b_{x})\cdot b_{x}/W_{X}+(w_{B}-1/b_{y})\cdot b_{y}/W_{Y}=\\=&(w_{B}b_{x}+1)/W_{X}+(w_{B}b_{y}-1)/W_{Y}\\>&(w_{B}b_{x}-1)/W+(w_{B}b_{y}+1)/W\\=&w_{B}V_{B}(C)/W\end{aligned}}$
Ценность любого другого агента i не менее ${\begin{aligned}&w_{i}\cdot V_{i}(X)/W_{X}+w_{i}\cdot V_{i}(Y)/W_{Y}\\>&w_{i}\cdot V_{i}(X)/W+w_{i}\cdot V_{i}(Y)/W\\=&w_{i}V_{i}(C)/W\end{aligned}}$ Таким образом, разделение строго пропорционально.