Разбойники не поделили добычу и умерли)

Ian · Сообщение **Ian** » 29 окт 2014, 08:29

ARRY писал(а):Source of the post

Ian писал(а):Source of the post
$\max\{a_i\}<\frac{D}{N},\;\max\{b_i\}<\frac{D}{N};\;\max\{c_i\}<\frac{D}{N}$ Наверное, точнее везде нестрогое неравенство, нет?-А это пофиг, "существует D такое, что...", в общем удельная ценность песка не выше удельной ценности самого золота.

Ian писал(а):Source of the post
$$Ñ\bar{\lim_{N\to\infty}}\max_{a_i,b_i,c_i}\left [\max\{\sum_{i\in B}a_i,\;\sum_{i\in C}a_i \}-\sum_{i\in A}a_i\right ]\geqslant 0$$Наверное, имелось в виду:
$\bar{\lim_{N\to\infty}}\max_{a_i,b_i,c_i}\left [\max\{\sum_{i\in B}a_i,\;\sum_{i\in C}a_i \}-\sum_{i\in A}a_i\right ]= 0$
Нет?
А вообще-то непрерывная модель более понятна, даже на интуитивном уровне.

Имелось в виду $\leqslant 0$ .извините запутался с исправлением. Интуитивно 1я модель -чтобы доля каждого игрока была максимумом как предел интегральных сумм Римана, а 2я -максимум как интеграл Лебега-Стилтьеса. И во 2й я постарался избежать вопроса об измеримости множеств, на которые они делят добычу.А то ведь разбить отрезок на три неизмеримых - и каждый будет думать, что ему досталось вся добыча)

Таланов

Таланов писал(а):Source of the post Будем делить поровну или по справедливости?
Один из разбойников делит кучу золотого песка на три равные на его взгляд кучи, следовательно его устраивает любая их 3-х. Следующий разбойник выбирает одну из трёх кучек и делит её на его взгляд ровно пополам, следовательно его устраивает любая из 2-х. Оставшийся разбойник из этих половинок выбирает одну себе, вторая достаётся делившему. Далее он делит одну из оставшихся двух кучек попалам, а другой забирает понравившуюся ему половину. У каждого по 1/3 и оставшая кучка достаётся первому делившему. Как тут можно быть кому-то недовольным?

Я понял в чём дело. Нужно придумать такой алгоритм раздела что-бы двое договорившись против третьего не получили в сумме больше 2/3. Мой вариант не проходит.
1-ый договорился со 2-ым против 3-го. 1 делит на 50%+50%+0%. Второй делит 0% и 50% с третьим. Третьему достаётся 25%.

Ian · Сообщение **Ian** » 30 окт 2014, 07:08

Да, интересный поворот.Поднимаются вопросы "криминоустойчивости" искомого алгоритма, а также "антикоалиционной устойчивости".
Первое совершенно необходимо, раз участники дележа- криминальные элементы. Но имхо у алгоритма Брамса-Тейлора она есть. В задаче - возникновение зависти у любого к любому ведет к поножовщине, вероятна смерть любого, его долю забирает победитель, тогда опять, возможно, зависть и, короче, ни один из троих не может быть уверенным что выживет, если алгоритм негодный, либо кем-то не соблюдается. Присвоим "выигрыш" участника в случае смерти "минус бесконечность". Предположим, на одном из этапов кто-то должен был делить поровну, но умышленно делит не поровну, в расчете получить больше. Но так как он не знает в точности оценок других участников, может допустить вероятность, что после такого дележа возникнет зависть, а тогда у него самого матожидание выигрыша минус бесконечность и он на такой мухлеж не пойдет.
Подчеркиваю, что в искомом алгоритме, если прямо не предусмотрено выяснение кем-то оценок другого, то он этих оценок и не знает. Иначе у нас корректной задачи не получится.
Почему я повторяю "искомый алгоритм", хотя он уже есть, и (как я проверял) криминоустойчив. А рассмотрим пример: добыча состоит из 20 песчинок тип1 и 20 тип2. Оценки тип1 от А: 1, от В и С: 2. Оценки тип2 наоборот, от А; 2 от В и С: 1.Общая ценность добычи, по мнению каждого, 60 ден.единиц. По алгоритму Брамса-Тейлора А делит на кучи 20*тип1, 10*тип2,10*тип2 (он хитрый, ему именно так выгодно) В и С указывают на кучу 1, проводится 2й этап, в результате, как можете проверить, В и С остаются с ценностью 20, а А с ценностью (для него) 25, но зависти не будет. А плохо то, что они могли бы поделить по-другому, с ценностью 24 (из 60) для каждого - одинаковой. Вот это и хотелось бы в искомом алгоритме, причем с криминоустойчивостью и даже антикоалиционной устойчивостью (компоненты https://ru.wikipedia.org/wiki/Вектор_Шепли равны между собой)

Anik · Сообщение **Anik** » 07 окт 2015, 08:07

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

Таланов

Обозначим участвующих в разделе сокровища А, Б и В. А делит сокровище пополам и дает Б выбрать одну из частей. После этого А и Б делят свои доли на три части, и В выбирает одну треть из каждой доли. Сговор между А и Б ничего не даст, поскольку В выберет из обеих половин не меньше трети по его мнению. Сговор между А и В нисколько не влияет на Б, поскольку тот выбирает не меньше половины и может честно поделить ее на три части. Сговор между Б и В также не влияет на А, поскольку А может честно поделить пополам и потом честно поделить свою половину на трети. Это решение легко обобщается на любое число участников.

Ian · Сообщение **Ian** » 09 окт 2015, 07:11

to Таланов:
Кто контролирует, какую треть доли А выбирает В? Если только А, то Б на это просто смотрит. Что может получиться: доля В в доле Б х меньше половины того, что осталось у Б. А вот доля В в доле А, по мнению Б, может оказаться почти троекратно больше, почти 3х, Б не может на это повлиять, и потом Б будет завидовать В

Таланов

Пусть Б завидует В и сочувствует А. Главное что он понимает что ему досталось не меньше 1/3.

yourdomain.com