О справедливом дележе

sevabashirov — 17.08.2025 Многие наверняка слышали про алгоритм "справедливого дележа" - распределения какого-то блага (часто говорят об условном торте) между несколькими людьми, у каждого из которых собственное представление о ценности того или иного кусочка (т.н. функция полезности).

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

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

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

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

Помимо беспристрастности, от дележа можно добиться и оптимальности по Парето - найти максимальную "удовлетворенность" среди всех возможных: т.е. если мы каким-то образом нашли точку (0,51; 0,51), еще не значит, что не найдется точка (0,52; 0,52). В общем случае это сложная задача, требующая полного описания всех субъективных функций полезности.

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

1. Оба участника, "не подглядывая", указывают на медианные по их мнению точки. В общем случае они не совпадают, и тогда они встают к тому концу, к которому их медиана оказалось ближе - выходит, что у каждого уже есть своя несгораемая субъективная половина.
2. Далее участники борются за остаточный центральный отрезок: каждый намечает медиану (со своей точки зрения) у противоположной половины (т.е. пытается нарастить свой потенциальный кусок с 50% до 75%). Далее два варианта: если относительное расположение точек не изменилось, они просто сблизились - новые куски прибавляются к несгораемым "хвостам" и процедура продолжается; если же возникло наложение претензий, это означает, что 75% (в данном случае) недостижимо, надо урезать осетра и теперь искать точку 62,5% (т.е. медиану от отрезка, который только что попытались заполучить).
3. Повторять процедуру, фактически спускаясь от разряда к разряду в двоичной записи дроби, означающей полученную долю.
...
N. Максимально возможный PROFIT.
___

P.S. Кто-то спросит, а нет ли в посте политической подоплеки? А это уж сами решайте - как известно, любой читатель гораздо лучше автора знает, что автор имел в виду.

Оставить комментарий

Популярные посты:

• Ранее
• Архив