2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 
Сообщение09.06.2006, 17:05 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Кажется, я понял постановку задачи Руста. Поправьте, если не прав.

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

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

 Профиль  
                  
 
 
Сообщение09.06.2006, 18:10 
Заслуженный участник


09/02/06
4382
Москва
Да. Есть неделимая часть (типа штучного товара) и делимая часть например деньги с точностью до копеек (дальше никто не мельчает) или бочка вина, которую можно разделить с помощью ензурки в необходимой пропорции. Если делимого товара достаточно и неделимый товар можно так сгруппировать (при этом часть из групп может быть пустой), чтобы сумма стоимостей в каждой группе для каждого участника (кадый оценивает по своему) то имеется возможность справедливо разделить. На самом деле, если эти группы неделимых товаров состоят не более чем из одного элемента то полученный раздел оптимален по Парето, т.е. никакие два не смогут поменяться частью полученных товаров так, чтобы у каждого из меняющихся увеличилась оценка стоимости их доли.
О необходимости этого условия для n>3 я точно не могу сказать. Но оно достаточно.

 Профиль  
                  
 
 Справедливо поделить..
Сообщение17.05.2009, 08:03 


20/11/08
36
Барнаул
Есть такая задача: Есть два вора, украли золотого песка мешок. Как теперь им поделить золото справедливо.(Весов у них нет, они торопятся за ними погоня, есть только пару минут).
Решение: Пусть один из воров разделит на две равные кучи, а второй выберет себе свою половину золота. Так будет справедливо, ведь если первый получит меньше золота,то он сам виноват, т.к неправильно поделил, иначе будет виноват второй.

Вопрос: Какое будет решение если у нас n воров? Как тогда справедиливо поделить?

 Профиль  
                  
 
 Re: Справедливый делёж
Сообщение17.05.2009, 08:30 
Модератор
Аватара пользователя


11/01/06
5660
Fsb4000
уже обсуждалось - см. выше в этой теме

 Профиль  
                  
 
 Re: Справедливый делёж
Сообщение17.05.2009, 20:26 


20/11/08
36
Барнаул
maxal спасибо за поднятие этой темы. Все прочитал, вопросы решены.

 Профиль  
                  
 
 Re: Справедливый делёж
Сообщение07.09.2015, 20:37 
Модератор
Аватара пользователя


11/01/06
5660
См. также http://elementy.ru/problems/953/Piratskaya_dolya

 Профиль  
                  
 
 Re: Справедливый делёж
Сообщение26.03.2018, 17:43 
Модератор
Аватара пользователя


11/01/06
5660
Решение в Кванте:
http://kvant.mccme.ru/1985/05/golovolomki.htm

История вопроса в Википедии:
https://en.wikipedia.org/wiki/Proportional_division
https://en.wikipedia.org/wiki/Envy-free_cake-cutting

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group