5.4: Самотній дільник

Метод одинокого дільника працює для будь-якої кількості сторін - ми будемо використовувати N для кількості партій. Один учасник випадковим чином позначається дільником, а решта учасників позначаються як обранці.

Метод одиночного дільника

Метод Lone Divider протікає наступним чином:

1) Дільник ділить деталь на$N$ частини, які ми будемо маркувати$S_{1}, S_{2}, \ldots, S_{N}$.

2) Кожен з обранців окремо перерахує, які твори вони вважають справедливою часткою. Це називається їх декларацією, або ставкою.

3) Переліки розглядаються. Є дві можливості:

а Якщо можна дати кожній партії шматок, який вони оголосили, то зробіть це, і дільник отримує решту шматок.

б Якщо дві або більше сторін обидві хочуть однакових частин і немає інших, то дайте неоскаржуваний шматок роздільнику. Решта шматочки з'єднуємо і повторюємо всю процедуру з іншими сторонами. Якщо залишилося тільки дві сторони, вони можуть використовувати роздільник-селектор.

Приклад 5

Розглянемо приклад з раніше, в якому шматки цінувалися як:

\ (\ почати {масив} {|l|l|l|}
\ hline &\ textbf {Шматок 1} &\ textbf {Шматок 2} &\ textbf {Шматок 3}\\ hline\ textbf {Вибір 1} & 40\% & 30\%\\
\ hline\ textbf {Вибір 2} & 45\% & 30\%\% & 25\%\\
\
hline\ textbf {дільник} & 33.3\% & 33.3\% & 33.3\%\\
\ hline
\ end {масив}\)

Рішення

Кожен вибирач робить декларацію про те, які шматки вони цінують як справедливу частку. У цьому випадку

Вибір 1 зробить декларацію: Шматок 1

Вибір 2 зробить декларацію: Шматок 1

Оскільки обидва вибирають один і той же шматок, ми не можемо відразу виділити шматки. Метод одинокого дільника вказує, що ми даємо неоскаржуваний шматок дільнику. Обидва шматки 2 і 3 є беззаперечними, тому ми перевертаємо монету і даємо шматок 2 на роздільник. Шматок 1 і 3 потім рекомбінують, щоб зробити шматок вартістю 70% до Chooser 1, і 70% до Chooser 2. Оскільки залишилося лише два гравці, вони можуть розділити рекомбіновані фігури за допомогою дільника-вибору. Кожному гарантується шматок, який вони оцінюють як мінімум 35%, що є справедливою часткою.

Спробуйте зараз 3

Використовуйте метод Lone Divider, щоб завершити справедливий поділ за вказаними нижче значеннями.

\ (\ почати {масив} {|l|l|l|}
\ hline &\ textbf {Шматок 1} &\ textbf {Шматок 2} &\ textbf {Шматок 3}\\ hline
\ textbf {Вибір 1} & 40\% & 30\%\\\ hline\ textbf {Вибір 2} & 40
\% & 30\%\\ hline\ textbf {Вибір 2} & 40\%\% & 25\%\\
\ hline\ textbf {дільник} & 33.3\% & 33.3\% & 33.3\%\\
\ hline
\ end {масив}\)

Відповідь

Вибір 1 зробить декларацію: Шматок 1

Вибір 2 зробить декларацію: шматок 1, шматок 2

Ми можемо негайно виділити шматки, даючи шматок 2 для вибору 2, шматок 1 для вибору 1 та шматок 3 до роздільника. Усі гравці отримують шматок, який вони цінують як справедливу частку.

Приклад 6

Припустимо, що Еббі, Брайан, Кріс і Доріан ділять ділянку землі. Доріан був обраний роздільником через кидок монети. Оцінка кожної людини кожного шматка показана нижче.

\ (\ почати {масив} {|l|l|l|l|l|}
\ hline &\ textbf {Шматок 1} &\ textbf {Шматок 2} &\ textbf {Шматок 3} &\ textbf {Шматок 4}
\\ hline\ textbf {Еббі} & 15\% & 30\% & 20\% & 35\\
\\ hline\ textbf {Брайан} & 30\% & 35\% & підсилювач; 10\% & 25\%
\\ hline\ textbf {Кріс} & 20\% & 45\% & 20\% & 15\%
\\ hline\\ textbf {Доріан} & 25\% & 25\% & 25\%\\
\ hline
\ кінець {масив}\)

Рішення

Виходячи з цього, їх декларації повинні бути:

Еббі: Шматок 2, шматок 4

Брайан: Шматок 1, шматок 2, шматок 4

Кріс: Шматок 2

Цей випадок можна вирішити просто - присудивши шматок 2 Крісу, шматок 4 Еббі, шматок 1 Брайану та шматок 3 Доріану. Кожна людина отримує шматок, який вони цінують як мінімум справедливу частку (25% вартості).

Приклад 7

Припустимо, що оцінки в попередній задачі були:

\ (\ почати {масив} {|l|l|l|l|l|}
\ hline &\ textbf {Шматок 1} &\ textbf {Шматок 2} &\ textbf {Шматок 3} &\ textbf {Шматок 4}
\\ hline\ textbf {Еббі} & 15\% & 30\% & 20\% & 35\\
\\ hline\ textbf {Брайан} & 20\% & 35\% & підсилювач; 10\% & 35\%
\\ hline\ textbf {Кріс} & 20\% & 45\% & 20\% & 15\%
\\ hline\\ textbf {Доріан} & 25\% & 25\% & 25\%\\
\ hline
\ кінець {масив}\)

Рішення

Декларації будуть такими:

Еббі: Шматок 2, шматок 4

Брайан: Шматок 2, шматок 4

Кріс: Шматок 2

Зверніть увагу в цьому випадку, що простого врегулювання немає. Отже, шматок, який ніхто більше не оголосив, Piece 3, присуджується оригінальному дільнику Доріана, і процедура повторюється з рештою трьома гравцями.

Припустимо, що на другому раунді цього методу Брайан вибирається дільник, три нові шматки вирізаються, а оцінки такі:

\ (\ почати {масив} {|l|l|l|l|}
\ hline &\ textbf {Шматок 1} &\ textbf {Шматок 2} &\ textbf {Шматок 3}
\\ hline\ textbf {Еббі} & 40\% & 30\\\%\
\ hline\ textbf {Брайан} & 33.3\% & 33.3\% & 33.3\%\\
\ hline \ textbf {Кріс} & 50\% & 20\% & 30\%\\
\ hline
\ end {масив}\)

Декларації тут були б:

Еббі: Шматок 1

Кріс: Шматок 1

Ще раз маємо протистояння. Брайан може бути нагороджений або шматок 2 або шматок 3, а решта частин можна рекомбінувати. Оскільки залишилося лише два гравці, вони можуть розділити решту землі, використовуючи основний метод вибору дільника-вибору.

Спробуйте зараз 4

Чотири інвестори ділять ділянку землі вартістю 320 000 доларів. Один був обраний як дільник, а їх значення ділення (в тисячах) наведені нижче. Хто був дільником? Опишіть результат поділу.

\ (\ почати {масив} {|l|l|l|l|l|}
\ hline &\ textbf {Шматок 1} &\ textbf {Шматок 2} &\ textbf {Шматок 3} &
\ textbf {Шматок 4}\\ hline\\ $90 &\ $70 & $\ 80\ $\\
\ hline\ textbf {Сезар} &\ $80 &\ $80 & підсилювач;\ $80 &\ $80\
\\ hline\ textbf {Адріанна} &\ $60 &\ $70 &\ $100 &\ $90\\
\ hline\ textbf {Ракель} &\ $70 &\ $50 &\ $90 &\ $110\\
\ hline
\ кінець {масив}\)

Відповідь

Справедлива частка становила б 80 000 доларів. Сезар був дільником.

Їхні декларації були б:

Соня: Пірс 1, шматок 3, шматок 4.

Адріанна: Шматок 3, шматок 4.

Ракель: Шматок 3, шматок 4.