Дележь сокровищ
Добавлено: 26 авг 2023, 23:29
Собственно по мотивам задачи. Пусть есть некое сокровище, состоящее из многих дискретных частей, и [math] разбойников. Каждый разбойник дает свою ценность каждой части от [math] до [math] так, чтобы в сумме все части давали единицу. Надо разделить сокровище между разбойниками так, чтобы каждый получил не менее [math] своей ценности.
Я предложил вероятностный алгоритм
Для каждой части проделываем следующую процедуру - берем все оценки разбойников для это части [math],[math] и т.д. и отдаем ее i-ому разбойнику с вероятностью [math]. В итоге имеем максимальное приближенное к тому, что каждый получил не менее [math] всех частей (а при очень большом числе частей можно так утверждать почти наверное, что приемлемо для практических целей)
Отсюда вылезло еще одно предположение. Если в исходном решении, предложенном на канале, наименьшая ценность, которую мог получить разбойник, равна [math], то в моем решении матожидание наименьшей ценности должно быть не меньше наибольшей наименьшей ценности, которую вообще можно получить путем справедливого дележа (при котором каждый получает не менее [math]).
Если немного вернуть задачу к исходной, предложенной на канале, то если разделить все сокровище на очень большое число частей [math] и устремить это [math] к бесконечности, то фактически полученные части будут равны почти наверное своим матожиданиям, и эта стратегия обеспечивает наибольшее значение наименьшей ценности, которую может получить разбойник.
Это верно или нет, как доказать?
Я предложил вероятностный алгоритм
Для каждой части проделываем следующую процедуру - берем все оценки разбойников для это части [math],[math] и т.д. и отдаем ее i-ому разбойнику с вероятностью [math]. В итоге имеем максимальное приближенное к тому, что каждый получил не менее [math] всех частей (а при очень большом числе частей можно так утверждать почти наверное, что приемлемо для практических целей)
Отсюда вылезло еще одно предположение. Если в исходном решении, предложенном на канале, наименьшая ценность, которую мог получить разбойник, равна [math], то в моем решении матожидание наименьшей ценности должно быть не меньше наибольшей наименьшей ценности, которую вообще можно получить путем справедливого дележа (при котором каждый получает не менее [math]).
Если немного вернуть задачу к исходной, предложенной на канале, то если разделить все сокровище на очень большое число частей [math] и устремить это [math] к бесконечности, то фактически полученные части будут равны почти наверное своим матожиданиям, и эта стратегия обеспечивает наибольшее значение наименьшей ценности, которую может получить разбойник.
Это верно или нет, как доказать?