Справедливый дележ нечеткого множества

[Nadir Zaitov]

Вы знаете, что в былые времена пираты, награбленное золото делили между собой. В допустим группе пиратов, больше рядовых пиратов в 5 раз получает капитан, в 3 раза - боцман, старшие мотросы получить должны по 2 единицы добычи, а рядовые пираты по 1 единице. Этот дележ всеми принимается и считается справедливым. Проблема в том, что добыча - золотые и серебрянные украшения с камнями ювелирной работы, мечи кованные с золотой рукояткой с рубинами, золотые и серебрянные монеты разного достоинства из разных стран - короче нечто, что оценить в числовом виде невозможно или очень субъективно. Да и менял в море нет, чтоб курс валют указать.

Задача. Вы капитан. В вашей команде 1 боцман, 5 старших пиратов, 17 рядовых пиратов.

Разделить нужно справедливо между ними достаточно большую (чтобы считать, что особенно крупных предметов в куче нет) разношерстную кучу золота и серебра. При этом, каждый пират должен быть доволен и/или уверен, что он получил не меньше, чем остальные.

Как это сделать? Ведь вкусы у всех разные. Каждый пират думает сам и другим не верит.

[insider]

может по очереди раздавать

Я капитан мне 5 штук
боцману 3 штуки
1 ст. пирату 2 шт
2 ст. пирату 2 шт
...

17 ряд пирату 1 шт

и так по кругу

[Nadir Zaitov]

может по очереди раздавать

Я капитан мне 5 штук
боцману 3 штуки
1 ст. пирату 2 шт
2 ст. пирату 2 шт
...

17 ряд пирату 1 шт

и так по кругу
5 "шт" чего?

Например, мне досталась сабля императора с брилиантами, а Вам серебрянная монета. Это же не "шт". Я буду реально доволен, а Вы скорее всего поднимите бунт.

Да и кто эти "шт." выбирает? Может боцман специально мне (или скорее себе, так как мне он тоже не верит по условию) передает самое дорогое, а другим подешевле? Стало быть недовольные найдутся и тут.

[insider]

сначало разделить монеты
а оставшиеся (не монеты) на аукцион
деньги с аукциона опять разделить между всеми

и т.д. :)

[Nadir Zaitov]

на аукционЭто вариант, но долгий, если аукцион вне группы пиратов. А вот аукцион среди пиратов нужно еще как-то провести - как я не знаю, но может быть тут есть также решение.сначало разделить монеты а оставшиеся (не монеты) на аукцион деньги с аукциона опять разделить между всемиМонеты тоже разного достоинста в разных металлах (золото, серебро), разных государств и что самое главное - каждая монета со своим весом: истерлась в процессе эксплуатации. Просто делить нельзя.

[insider]

научить пиратов закону Архимеда

[Nadir Zaitov]

АрхимедаА брилики в украшениях? А работа ювелира? А железо от шпаги? А серебро как сопоставить с золотом - курса то нет? Короче нужно понимать, что однозначной численной величины ни один предмет вам дать не может. :)

[German Stimban]

Отделить золотые монеты от серебряных по внешнему виду. Поделить отдельно золотые и серебряные между пиратами по весу. А потом устроить аукцион среди пиратов, лучше по "голландской" системе - озвучивается максимальная цена за каждый лот, а потом постепенно снижается до тех пор, пока кто-либо не захочет купить. После продажи каждого лота по возможности распределять деньги, полученные от его продажи. Если какой-либо лот не будет востребован (не продан за какой-то, заранее оговоренный минимум), он отдаётся наиболее храброму в последнем бою. Как вариант, невостребованные лоты после аукциона распределить между пиратами или оставить до берега, там продать и заново поделить деньги.

[Nadir Zaitov]

Отделить золотые монеты от серебряных по внешнему виду. Поделить отдельно золотые и серебряные между пиратами по весу. А потом устроить аукцион среди пиратов, лучше по "голландской" системе - озвучивается максимальная цена за каждый лот, а потом постепенно снижается до тех пор, пока кто-либо не захочет купить. После продажи каждого лота по возможности распределять деньги, полученные от его продажи. Если какой-либо лот не будет востребован (не продан за какой-то, заранее оговоренный минимум), он отдаётся наиболее храброму в последнем бою. Как вариант, невостребованные лоты после аукциона распределить между пиратами или оставить до берега, там продать и заново поделить деньги. Герман. Задача в том, что и внешне золотые монеты не одинаковые. Ценности каждая монета не несет. Взвешивать каждую сделку смысла нет.

[Shuhrat Ismailov]

Сложная ситуация, однако. Есть идея.
Думаю, что нужно как-то голосованием дело обустроить. Возможно, что в голосовании будут участвовать не все пираты, а специально отобранные представители каждой группы.
О деталях еще не подумал.

научить пиратов закону Архимеда
То есть недовольных за борт акул кормить?

[Химера]

Подсказка. Как поделить кучку риса, не пересчитывая рисинки, между двумя людьми, чтобы никто не считал себя обманутым? Без весов и мерных емкостей.

[Renat Akhtyamov]

произвести оценку имущества в условных/виртуальных единицах. Что-то вроде выставления баллов каждой вещичке. Соответсвенно надо разработать систему оценки товара. Например, каждый предлагает свою оценку по оговоренной шкале, затем берутся усреднённые оценки каждой вещи. И всё делят, как полагается по закону пиратов.
Но это долго и скучно. Интереснее сокровища закопать таким образом, чтобы каждый член команды знал только 1 участок пути следования к месту "захоронения" клада (капитан возможно должен знать 5 участков, боцман 3 и т.д.). Каждый рисует карту местности своего участка(ов). Всё это перемешиваем, и уплываем подальше от этих мест. На очередном PiratParty случайным образом распределяем карты между участниками, капитану 5, боцману 3 и т.д.
А дальше они начинают вести торги или бойни, как уж им будет удобнее, за кусочки карт. Самый шустрый найдёт заветное местечко !

[Shuhrat Ismailov]

Подсказка. Как поделить кучку риса, не пересчитывая рисинки, между двумя людьми, чтобы никто не считал себя обманутым? Без весов и мерных емкостей.
Здесь легко. Нужно чтобы один делил на две части, а второй выбирал

[Evgeniy Sklyarevskiy]

Подсказка. Как поделить кучку риса, не пересчитывая рисинки, между двумя людьми, чтобы никто не считал себя обманутым? Без весов и мерных емкостей. Потом эта задача экстраполируется на 3, 4.... n участников.

[Shuhrat Ismailov]

произвести оценку имущества в условных/виртуальных единицах. Что-то вроде выставления баллов каждой вещичке. Соответсвенно надо разработать систему оценки товара. Например, каждый предлагает свою оценку по оговоренной шкале, затем берутся усреднённые оценки каждой вещи. И всё делят, как полагается по закону пиратов.
Верно, напоминает раздел имущества при бракоразводном процессе.
Вообще говоря есть фирма Fair Outcomes, Inc. которая вопросами разделения имущества занимается. http://www.fairoutcomes.com/
А здесь онлайн процедура дележки (но я не разобрался....)
http://www.nyu.edu/projects/adjustedwinner/

[Камолиддин Зайнутдинов]

теперь надо подумать как эти ссылки дать пиратам.

[Shuhrat Ismailov]

Потом эта задача экстраполируется на 3, 4.... n участников.
Экстраполяцию будем проводить по индукции.
База индукции:
n=2. Oдин делит добычу на две равные с его точки зрения доли, а другой выбирает из них ту долю, которая кажется ему большей (я об этом писал выше).
n=3. Пусть три пирата А,В,С теперь.
А разделил на три равные с его точки зрения доли а1,а2,а3,
В разделил на три равные с его точки зрения доли b1,b2,b3.
Пират C выбрал на свое шкурное усмотрение ak+bm, где 1<=k,m<=3 (например, a1+b3) и довольный ушел пить ром .
Остались 2 пирата, и они заново стали делить оставшуюся добычу, как я сказал выше.
Предположение индукции: Пусть n пиратов уже умеют разделить добычу справедливо.
Шаг индукции: Для n+1 пиратов:
Сначала разделим справедливо всю добычу между n пиратами (по предположению индукции они это умеют) и затем каждый из них разделит свою долю на n+1 равных , на его взгляд, частей.
Оставшийся (n+1)-й пират возьмет по своему шкурному усмотрению по одной из этих частей у каждого из n разбойников.
И будет всем счастье.

[Renat Akhtyamov]

Потом эта задача экстраполируется на 3, 4.... n участников.
Экстраполяцию будем проводить по индукции.
База индукции:
n=2. Oдин делит добычу на две равные с его точки зрения доли, а другой выбирает из них ту долю, которая кажется ему большей (я об этом писал выше).
n=3. Пусть три пирата А,В,С теперь.
А разделил на три равные с его точки зрения доли а1,а2,а3,
В разделил на три равные с его точки зрения доли b1,b2,b3.
Пират C выбрал на свое шкурное усмотрение ak+bm, где 1<=k,m<=3 (например, a1+b3) и довольный ушел пить ром .
Остались 2 пирата, и они заново стали делить оставшуюся добычу, как я сказал выше.
Предположение индукции: Пусть n пиратов уже умеют разделить добычу справедливо.
Шаг индукции: Для n+1 пиратов:
Сначала разделим справедливо всю добычу между n пиратами (по предположению индукции они это умеют) и затем каждый из них разделит свою долю на n+1 равных , на его взгляд, частей.
Оставшийся (n+1)-й пират возьмет по своему шкурному усмотрению по одной из этих частей у каждого из n разбойников.
И будет всем счастье.
А как учесть что капитан будет получать в 5 раз больше, боцман в 3 раза больше?

[Evgeniy Sklyarevskiy]

Еще красивая задача из Сети:

Пять пиратов на острове должны разделить между собой сотню золотых монет. Они делят свою добычу так: старший пират предлагает, как делить добычу, а потом каждый голосует, соглашаясь с его предложением или нет. Если по меньшей мере половина пиратов проголосует «за», они поделят монеты так, как предложил старший пират, если же нет — они убивают старшего пирата и начинают все сначала. Самый старший пират (из тех, кто выжил) предлагает новый план, за него голосуют по тем же правилам, а потом или делят добычу, или убивают старшего пирата. Процесс продолжается до тех пор, пока какой-то план не будет принят. Допустим, вы — старший пират. Как вы предложите разделить добычу? (Все другие пираты — жадные, мыслят очень логично, и все они хотят жить.)

[Evgeniy Sklyarevskiy]

А как учесть что капитан будет получать в 5 раз больше, боцман в 3 раза больше? Это уже другая задача, тут критерий чтобы все были довольны.

[Shuhrat Ismailov]

А как учесть что капитан будет получать в 5 раз больше, боцман в 3 раза больше?
Будем и их делить. Капитана - на пять частей, боцмана - на три, старшего матроса на две. Шутка..
Я дал решение для n равнозначных пиратов.
В нашем случае, естестественно предположить, что капитан будет участвовать пять раз в дележке (т.е. иметь пять подходов), остальные соответственно 3, 2 и 1 раз.

[Evgeniy Sklyarevskiy]

Пусть три пирата А,В,С теперь.
А разделил на три равные с его точки зрения доли а1,а2,а3,
В разделил на три равные с его точки зрения доли b1,b2,b3.
Пират C выбрал на свое шкурное усмотрение ak+bm, где 1<=k,m<=3 (например, a1+b3) и довольный ушел пить ром .
Это же теория. А как на практике разделить добычу одновременно на три кучи двумя разными способами? Ведь если пират С заберет а1, то уже не получится разделить также как и в начале на b1,b2,b3 так как процессы влияют друг на друга.

[Shuhrat Ismailov]

Пусть три пирата А,В,С теперь.
А разделил на три равные с его точки зрения доли а1,а2,а3,
В разделил на три равные с его точки зрения доли b1,b2,b3.
Пират C выбрал на свое шкурное усмотрение ak+bm, где 1<=k,m<=3 (например, a1+b3) и довольный ушел пить ром .
Это же теория. А как на практике разделить добычу одновременно на три кучи двумя разными способами? Ведь если пират С заберет а1, то уже не получится разделить также как и в начале на b1,b2,b3 так как процессы влияют друг на друга.
Не подумал, что ak и bm могут иметь общие предметы. Экстраполяция не получается....

[Химера]

Shuhrat Ismailov,
Ваши рассуждения в целом правильные, просто итерации должны быть последовательными.
Поделили 2.
Каждый разделил свою часть на 3 кучки.
Третий выбрал себе по 1 части.
Далее каждый поделил свою часть на 4. Пришел четвертый и взял себе по 1 части у каждого
И так до охвата всех участников дележа.

[Химера]

Пять пиратов на острове должны разделить между собой сотню золотых монет. Они делят свою добычу так: старший пират предлагает, как делить добычу, а потом каждый голосует, соглашаясь с его предложением или нет. Если по меньшей мере половина пиратов проголосует «за», они поделят монеты так, как предложил старший пират, если же нет — они убивают старшего пирата и начинают все сначала. Самый старший пират (из тех, кто выжил) предлагает новый план, за него голосуют по тем же правилам, а потом или делят добычу, или убивают старшего пирата. Процесс продолжается до тех пор, пока какой-то план не будет принят. Допустим, вы — старший пират. Как вы предложите разделить добычу? (Все другие пираты — жадные, мыслят очень логично, и все они хотят жить.)
98 0 0 1 1

[Shuhrat Ismailov]

И так до охвата всех участников дележа.
А как учесть что капитан будет получать в 5 раз больше, боцман в 3 раза больше?

[Химера]

А как учесть что капитан будет получать в 5 раз больше, боцман в 3 раза больше?
Ничего сложного.
Допустим в дележе уже участвуют 2 матроса, надо включить капитана.
2 матроса делят свои части на 1+1+5 частей, капитан забирает 5.
Немного сложнее когда забирают часть у капитана. Так как у него кучка "упятеренная", то он должен делить свою часть на в 5 раз больше частей чем матрос. Богатство - тяжелая ноша.
С боцманами аналогично. Просто количество кучек должно учитывать "вес" всех участвующих в данной итерации участников.

[Nadir Zaitov]

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

[Nadir Zaitov]

то он должен делить свою часть на в 5 раз больше частей чем матрос.Допустим делить нужно между капитаном и 2 матросами. Делить капитану кучку нужно на 7 частей - пусть мотрос забирает свою часть, на 35 частей делить не обязательно, так как матрос должен забрать 5 маленьких частей, что эквивалентно 1-й большой. Наверное так.

[iDead]

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

[Химера]

Делить капитану кучку нужно на 7 частей - пусть мотрос забирает свою часть, на 35 частей делить не обязательно, так как матрос должен забрать 5 маленьких частей, что эквивалентно 1-й большой. Наверное так.
Действительно. Достаточно просто учитывать на сколько частей делить.