Дележь сокровищ

[Albus]

Собственно по мотивам задачи. Пусть есть некое сокровище, состоящее из многих дискретных частей, и [math]N разбойников. Каждый разбойник дает свою ценность каждой части от [math]0 до [math]1 так, чтобы в сумме все части давали единицу. Надо разделить сокровище между разбойниками так, чтобы каждый получил не менее [math]\frac{1}{N} своей ценности.
Я предложил вероятностный алгоритм
Для каждой части проделываем следующую процедуру - берем все оценки разбойников для это части [math]a_1,[math]a_2 и т.д. и отдаем ее i-ому разбойнику с вероятностью [math]a_i/(a_1+a_2+...). В итоге имеем максимальное приближенное к тому, что каждый получил не менее [math]\frac{1}{N} всех частей (а при очень большом числе частей можно так утверждать почти наверное, что приемлемо для практических целей)
Отсюда вылезло еще одно предположение. Если в исходном решении, предложенном на канале, наименьшая ценность, которую мог получить разбойник, равна [math]\frac{1}{N}, то в моем решении матожидание наименьшей ценности должно быть не меньше наибольшей наименьшей ценности, которую вообще можно получить путем справедливого дележа (при котором каждый получает не менее [math]\frac{1}{N}).
Если немного вернуть задачу к исходной, предложенной на канале, то если разделить все сокровище на очень большое число частей [math]M и устремить это [math]M к бесконечности, то фактически полученные части будут равны почти наверное своим матожиданиям, и эта стратегия обеспечивает наибольшее значение наименьшей ценности, которую может получить разбойник.
Это верно или нет, как доказать?

[Ian]

Для каждой части проделываем следующую процедуру - берем все оценки разбойников для это части [math]a_1,[math]a_2 и т.д. и отдаем ее i-ому разбойнику с вероятностью [math]a_i/(a_1+a_2+...).

Ну хорошо, 1я часть кому-то досталась. Этот кто-то далее исключается из дележа или продолжает участвовать? Это же важно

[Albus]

Ну хорошо, 1я часть кому-то досталась. Этот кто-то далее исключается из дележа или продолжает участвовать? Это же важно

Конечно участвует, а как же тогда? Всем по крошечной части бы досталось и все

[Ian]

Пусть ценность j-й части (j=1,...M) для i- го разбойника (i=1,...N) [math]a_{ij} , условие нормировки
[math]\forall i\;\sum_{j}a_{ij}=1
Обозначим
[math]b_{j}=\sum_{i}a_{ij},\;\sum_{j}b_{j}=\sum_{i}1=N

Далее все для конкретного i-го: Вероятность получения им j-й части ценностью [math]a_{ij}
[math]\frac{a_{ij}}{b_{j}}
, значит матожидание ценности для него
[math]E_{i}=\sum_{j}\frac{a_{ij}^{2}}{b_{j}}
Неравенство Коши-Буняковского:
[math]1=\left(\sum_{j}a_{ij}\right)^{2}=\left(\sum_{j}\frac{a_{ij}}{\sqrt{b_{j}}}\sqrt{b_{j}}\right)^{2}\leq E_{i}\sum_{j}b_{j}=NE_{i}
[math]E_{i}\geq\frac{1}{N}гарантированно.

Так что в смысле матожиданий -лотерея честная.

Но почти наверное -найдется такой которого не удовлетворит розыгрыш)

[Albus]

Но почти наверное -найдется такой которого не удовлетворит розыгрыш)

Это да Но если число частей будет стремиться к бесконечности, то дисперсия к нулю
И да, вы доказали, что

В итоге имеем максимальное приближенное к тому, что каждый получил не менее 1N
всех частей (а при очень большом числе частей можно так утверждать почти наверное, что приемлемо для практических целей)

А что насчет

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

?

[Ian]

Видимо в ролике вас не устроило то, что нет симметрии по людям, одного назначают первым другого вторым, и тд., в итоге кто-то имеет ценность для себя ровно 1/N, а у кого-то есть шанс преуспеть больше.

[Albus]

Ian
Да, ну так что с задачкой?

[Ian]

Так Вы ее нестрого поставили

Если немного вернуть задачу к исходной, предложенной на канале, то если разделить все сокровище на очень большое число частей [math]M и устремить это [math]M к бесконечности, то фактически полученные части будут равны почти наверное своим матожиданиям, и эта стратегия обеспечивает наибольшее значение наименьшей ценности, которую может получить разбойник.
Это верно или нет, как доказать?

"наибольшее значение наименьшей ценности, которую может получить разбойник" Наименьшей по чему? по разбойникам? по всем случайностям которые могли бы произойти в этой лотерее при фиксированном М? Во втором случае это 0, имеется ненулевая вероятность что 1й разбойник не получит ничего.
А наибольшее по чему? по всем стратегиям? а какие вообще допустимы стратегии?
Как минимум Вам надо поправить текст на "наибольшее значение наименьшего по разбойникам матожидания ценности, которую он может получить ." Мы доказали что оно не меньше 1/N, а вообще-то оно определяется структурой добычи. Например разбойников двое : голодная собака и сорока, один ценит только съедобное, другой только блестящее, а так как съедобное блестящим не бывает, то каждый получит 1, (к сожалению в пределе и почти наверное -если дробить на части достаточно мелко, и если повезет с дроблением)

Между тем и в данном частном случае и в общем есть идеальное решение задачи для двух, без всяких лотерей, непохожее ни на ваше ни на ютуб. Добыча раскладывается по отрезку [0,1] так что для первого, которому досталась добыча из множества Е отрезка, ценность равна мере этого множества [math]c_1=\int_Edt(для любого измеримого множества E), а для второго удельная ценность убывает, так что если ему достанется добыча из [0,t], то функция ценности для него [math]c_2=F(t) вогнута. Остается решить уравнение [math]F(t)=1-t (=c_1=c_2) и ценности будут равные и как правило больше 1/2 -соблюдена и симметрия. По лемме Неймана-Пирсона, решение типа "отношение ценностей не ниже некоторой константы" дает максимум ценности для одного при условии ценности не ниже заданной для другого -так подберем константу так что они равны. Или например, задача о рюкзаке. Каждый кто над ней подумает, приходит к идее "веса деленного на объем" присвоенной каждому предмету, но неделимость предметов мешала дать точное универсальное решение.
В частном случае когда 1)собака и 2)сорока, все блестящее ляжет в точку 0, точка 0 достанется сороке, а остальной отрезок собаке.

[Albus]

"наибольшее значение наименьшей ценности, которую может получить разбойник" Наименьшей по чему? по разбойникам?

Ага

А наибольшее по чему? по всем стратегиям?

Да

а какие вообще допустимы стратегии?

Любые

Как минимум Вам надо поправить текст на "наибольшее значение наименьшего по разбойникам матожидания ценности, которую он может получить ."

Матожидания можно убрать. В случае мелкого дробления оно почти в точности совпадет с тем, что мы по факту получим, из-за околонулевой дисперсии

Например разбойников двое : голодная собака и сорока, один ценит только съедобное, другой только блестящее, а так как съедобное блестящим не бывает, то каждый получит 1, (к сожалению в пределе и почти наверное -если дробить на части достаточно мелко, и если повезет с дроблением)

А зачем тут мелко дробить и брать пределы? Все точно получается и с двумя частями - блястящим и сьедобным

Между тем и в данном частном случае и в общем есть идеальное решение задачи для двух, без всяких лотерей, непохожее ни на ваше ни на ютуб

.
Да, это оптимальное решение А если для многих участников?
Кстати, я тут решил сравнить результаты вашего решения с моим в случае, если у нас сокровище разбито на две части. У первой части ценность для вороны , а для собаки , у второй части ценность для вороны , а для собаки .
Ваш подход дает ценность для обоих участников, а мой дает для собаки , а для вороны .
Я думаю, что немного ошибся Мой подход дает не максимум минимальной части, а минимум максимальной (при условии, что каждая часть ограничена снизу ). Чтоб все получили как можно ближе к , дешево и сердито
Надо теперь доказать это)

[Albus]

Надо теперь доказать это

Ой, это легко опровергнуть, для двух игроков легко показать, что можно дать его половину каждому