Страницы: Пред. 1 ... 7 8 9 10 11 ... 15 След.
RSS
Как разделить пирог?, Старая задача с новым решением?
Цитата
Техник пишет:
в данной задаче возможна ситуация с абсолютно проигрышной стратегией, которую я и продемонстрировал
Да какой тут абсолютный проигрыш? Нет разницы с делением пирога.
Ну, хорошо, ещё подробней:
Старшенький: Ну ничего так себе картинка, я бы купил на развалах за 101 рупь, это если вместе с рамкой.
Младшенький: Ну, ты даёшь, ни хрена в живописи. Это-ж иллюстрация к Бокаччо. Там в правом нижнем углу баба красивая. Никак не меньше 102.
Старшенький: (почесав затылок) Ну может ты и прав в чём-то. В общем, давай по чесноку. Сбросимся по сотне и разделим, как Нэш завещал.
Сбросившись поровну братья набрали 200 рублей и картину в придачу. Эту совокупность надо разделить пополам и чтоб никому не обидно.
Старшенький стал делить и положил на одну тарелку картину и 25 рублёв, а на другую тарелку 175 рублёв.
Оказывается старшенький немного лукавил при обсуждении или рассмотрел правый угол или у него были какие-то другие соображения. Во всяком случае, чтобы не прогадать, ему пришлось сделать тарелки равноценными.
Младшенький выбирает и, думается, выберет не в ущерб себе. И значит также не прогадает. В принципе, технология такая-же, как при делении пирога.
Что в итоге.
Старшенький, очевидно, оценивает картину в 150 рублей.
Предположим, младшенький оценивает также и выбирает тарелку с 175 рублями.
Старший получил картину стоящую 150 р. + 25 р. в тарелке. (Минус вложенные 100 и получается, что получил картину и заплатил 75 р. за долю брата в этой картине)
Младший получил 175 р. (минус вложенные 100 и получается, что получил от брата 75 р. за свою долю в картине).
Если-же младшенький оценивает картину в 160 р., то
1- Старший никак не пострадает от того, что младший после него как-то по-другому оценивает картину. Ему в любом случае достаётся одна из равноценных, по его мнению, тарелок.
2- Младший выбирает тарелку с картиной +25 р. (т.е. на общую сумму 185, по его мнению) и также не может пожаловаться на свою горькую участь.
Цитата
Вот если оценить пирог в деньгах, то и проблемы деления пирога бы не было - отслюнявил каждому его долю, и... нафиг пирог вообще?
А за вишенку?
Как у вас просто получается. И нет никакой задачи деления пирога. Отрезал "каждому его долю"...
Цитата
А Нэш здесь каким боком? Я вроде про "неудовлетворительность решения Нэша" ничего не говорил.
Вы не говорили, а я уже устал повторять. Современные математики говорят о суперсложном решении. Значит есть какие-то соображения о неудовлетворительности решения Нэша. Собственно, этому и посвящена тема. Ну для меня, по крайней мере.
В споре не рождается истина, но убивается время.
...
Изменено: Техник - 11.12.2016 17:04:55
Ясность - одна из форм полного тумана
Цитата
eLectric пишет:
Да какой тут абсолютный проигрыш?
Я вам уже показывал, какой. Не, я конечно, не утверждаю, что такая ситуация неизбежна, я лишь говорю, что она возможна. Чисто гипотетически.
Цитата
eLectric пишет:
Ну, хорошо, ещё подробней:
Ну, если не хотите смотреть на наши цифры, будем смотреть на ваши.
Цитата
eLectric пишет:
Если-же младшенький оценивает картину в 160 р., то
1- Старший никак не пострадает от того, что младший после него как-то по-другому оценивает картину. Ему в любом случае достаётся одна из равноценных, по его мнению, тарелок.
То есть в этом случае старший получает 175 - 100 =75р и картина делится 75р/85р. А мог бы получить 180 - 100 = 80р при делении картины ровно пополам, 80/80, если бы позволил делить брату. Ну, это если без зависти (по справедливости). Не, я конечно понимаю, типа "так получилось" и "сам виноват", но мы же всё-таки ищем оптимальное решение, не? То есть такое, когда каждый, сравнив свой кусок со всеми другими, приходит к выводу, что его кусок не хуже любого другого. А тут у брата явно кусок лучше :)
Цитата
eLectric пишет:
Цитата
Техник пишет:
Вот если оценить пирог в деньгах, то и проблемы деления пирога бы не было - отслюнявил каждому его долю, и... нафиг пирог вообще?
А за вишенку?
Как у вас просто получается. И нет никакой задачи деления пирога. Отрезал "каждому его долю"...
Так не у меня, а у вас. Вы же вместо деления картины делите деньги и говорите что это одно и то же с пирогом. А деньги делить конечно проще.
Цитата
eLectric пишет:
Современные математики говорят о суперсложном решении. Значит есть какие-то соображения о неудовлетворительности решения Нэша.
Ничего это не значит. Наоборот - говорят, доказано, что деление пирога относится к классу задач PPAD, в этом же классе находится и задача поиска равновесия Нэша. Это, насколько я помню, было в вашей же ссылке???
Изменено: Техник - 11.12.2016 17:25:06
Ясность - одна из форм полного тумана
Цитата
Да какой тут абсолютный проигрыш?
Техник пишет:  Я вам уже показывал, какой. Не, я конечно, не утверждаю, что такая ситуация неизбежна, я лишь говорю, что она возможна. Чисто гипотетически.
Тогда вернёмся к тому, что я говорил: Да, ассиметрия есть.
Но нельзя же это назвать абсолютным проигрышем, ведь никто не получает меньше половины.
Цитата
То есть в этом случае старший получает 175 - 100 =75р и картина делится 75р/85р.
про 85 я чего-то не понял.
Цитата
А мог бы получить 180 - 100 = 80р при делении картины ровно пополам, 80/80, если бы позволил делить брату. Ну, это если без зависти (по справедливости). Не, я конечно понимаю, типа "так получилось" и "сам виноват", но мы же всё-таки ищем оптимальное решение, не? То есть такое, когда каждый, сравнив свой кусок со всеми другими, приходит к выводу, что его кусок не хуже любого другого. А тут у брата явно кусок лучше
Ну так здесь и есть та самая ситуация, когда каждый видит свой кусок ничем не хуже другого. Кто-бы не делил, каждый видит свою тарелку не хуже, чем другая. Почему это у брата тарелка лучше? Это вовсе не явно.
По вашему рассуждать, то и деление пирога абсолютно несправедливо. В самом деле, Делитель не обращает внимания на какие-то вишенки, они ему по-фигу, а Выбирателю вишенка может быть важна и он по разному оценивает предлагаемые ему на выбор куски.
Ну, примем, якобы "А тут у брата явно кусок лучше". Скажем, такое развитие - Младшенький увидел, как старший расстроился и от щедрости душевной предложил: "Ну на, сам выбирай." Ну и что для старшенького? Он опять видит перед собой две равноценные тарелки. Какой у него выбор: выбрать из равноценных по-лучше или сделать их ещё более равноценными?
В общем ситуация такая: Делитель получает один из равноценных кусков/тарелок и они оба именно равноценны, а Выбиратель получает кусок, который получше другого, в том возможном случае, если они для него неравноценны. Причём, неизвестно, этот лучший кусок стоит ли больше, чем один из равноценных по мнению Делителя.
Но, давайте всё-таки, определимся с условиями. Вернее уточним. Никакой объективной, независимой от мнения братьев, цены не существует. Например, возможно такое развитие событий: картина в действительности оказалась ранним Брейгелем старшим и стоит в Кристи мильон. Или внутри куска пирога оказалась золотая монета. Но всё это потом, и заранее неизвестно, как скажется на цене делимого. Это, равно как и любая инсайдерская информация, находится вне условий задачи.
Тогда какая оценка является реальной? Только та, что в момент действия с пирогом или картиной, причем с точки зрения того, кто это действие производит. Когда старший брат уравновешивает тарелки, картина стоит столько, сколько считает старший брат. А потом уже она будет стоить по-другому: на аукционе или, когда младший будет выбирать тарелки.
Цитата
Ничего это не значит. Наоборот - говорят, доказано, что деление пирога относится к классу задач PPAD
Вот буквально, что говорится в последней ссылке про сентябрьское, кажется, решение 2016 года:
Цитата
Двое молодых учёных, специалистов в области информатики, придумали, как честно поделить торт между любым количеством людей, решив задачу, над которой математики бились десятилетиями. Их работа удивила многих исследователей, считавших такое разделение невозможным в принципе.
Делёж пирога – это метафора для широкого круга реальных задач, включающих деление некоего непрерывного объекта, будь это торт или надел земли, между людьми, по-разному оценивающими его свойства.
В споре не рождается истина, но убивается время.
Цитата
eLectric пишет:
Тогда вернёмся к тому, что я говорил: Да, ассиметрия есть.
Но нельзя же это назвать абсолютным проигрышем, ведь никто не получает меньше половины.
http://www.nkj.ru/forum/forum26/topic19657/messages/message344273/#message344273
Цитата
eLectric пишет:
про 85 я чего-то не понял.
если один получает 75, то другой - 85, итого 160. А 160 - это в данном случае оптимальная стоимость картины, т.е. такая, что её можно разделить фифти-фифти.
Цитата
eLectric пишет:
Ну так здесь и есть та самая ситуация, когда каждый видит свой кусок ничем не хуже другого. Кто-бы не делил, каждый видит свою тарелку не хуже, чем другая. Почему это у брата тарелка лучше? Это вовсе не явно.
Если играть "в тёмную", не зная оценок друг друга, то вы правы - всё определяет случай. Т.е. одному может повезти, а другой об этом и знать не будет. Поэтому, если братья не дураки, они вполне в состоянии просчитать всю арифметику не хуже нас с вами и прийти к выводу, что для обоих лучше сыграть "в открытую" и получить свои законные 50% от оптимальной цены, которая и максимальная. Тогда каждый честно получит максимум возможного. Чего тут ещё?
Цитата
eLectric пишет:
По вашему рассуждать, то и деление пирога абсолютно несправедливо. В самом деле, Делитель не обращает внимания на какие-то вишенки, они ему по-фигу, а Выбирателю вишенка может быть важна и он по разному оценивает предлагаемые ему на выбор куски.
Так я и не считаю, что это идентичные задачи. Картина делится по одному параметру (по стоимости), а пирог с вишенкой - по многим. N участников (и наборов критериев), N кусков, N параметров... Это разные задачи.
Если брать в самой простой формулировке, у куска пирога тоже один параметр - размер. В этом случае задачи схожи  - у пирога размер, у картины стоимость.
Цитата
eLectric пишет:
Ну, примем, якобы "А тут у брата явно кусок лучше". Скажем, такое развитие - Младшенький увидел, как старший расстроился и от щедрости душевной предложил: "Ну на, сам выбирай." Ну и что для старшенького? Он опять видит перед собой две равноценные тарелки. Какой у него выбор: выбрать из равноценных по-лучше или сделать их ещё более равноценными?
Тогда старший выбирает картину и младшенький улетает в минус 5р :)
Цитата
eLectric пишет:
Тогда какая оценка является реальной? Только та, что в момент действия с пирогом или картиной, причем с точки зрения того, кто это действие производит. Когда старший брат уравновешивает тарелки, картина стоит столько, сколько считает старший брат.
Реальная - да, а оптимальная?
Предлагаю на этом закончить с картиной, уже всё вроде разобрали дальше некуда :)
Цитата
eLectric пишет:
Вот буквально, что говорится в последней ссылке про сентябрьское, кажется, решение 2016 года:
...Их работа удивила многих исследователей, считавших такое разделение невозможным в принципе.
ну и что? Класс PPAD, насколько я понимаю, это когда известно, что решение существует, но найти его трудно в связи с большой вычислительной сложностью. Ну, одни считали, что невозможно найти, а другие взяли и нашли. Говорят, что нашли. Что тут такого?
Ясность - одна из форм полного тумана
Цитата
Olginoz пишет:
Тесто готовится дрожжевое, мягкое, сдобное, но не сильно сладкое. На слой теста выкладывается слой вареного рассыпчатого риса. На рис кладутся небольшие кусочки сливочного масла и посыпается нарезанным луком. На лук выкладываются куски кеты или горбуши (кета вкуснее) толщиной около 1-1.5 см. Рыбу не надо резать мелко, она порежется при разрезании пирога, но нужно очистить от костей и посолить. Закрыть всю поверхность рыбой, чтобы в начинке не было просветов без рыбы, и рыба должна контактировать с луком, а снизу рис. Закрыть слоем теста,  можно слепить сверху украшения. Некоторое время дать отстояться, чтобы тесто поднялось (полчаса). Помазать пирог яйцом и выпекать в духовке.
Olginoz, спасибо. :)

Буду импровизировать. 8)
Вместе мы выстоим, а порознь --- падём.
Цитата
Тогда вернёмся к тому, что я говорил: Да, ассиметрия есть.
Но нельзя же это назвать абсолютным проигрышем, ведь никто не получает меньше половины.
Техник пишет:  http://www.nkj.ru/forum/forum26/topic19657/messages/message344273/#message344273
Не. Мы же говорили - складываются поровну.
Цитата
А 160 - это в данном случае оптимальная стоимость картины, т.е. такая, что её можно разделить фифти-фифти.
Что такое "оптимальная стоимость" и откуда она взялась?
Цитата
Так я и не считаю, что это идентичные задачи. Картина делится по одному параметру (по стоимости), а пирог с вишенкой - по многим. N участников (и наборов критериев), N кусков, N параметров... Это разные задачи.
Это разные задачи, а принцип решения один и тот-же. Разные, потому что пирог делимый, а картина нет. Чтобы разделить картину, к ней пристёгивают кучу денег и после этого задача становится совершенно такой-же. Деление пирога с вишенкой ничем не отличается от деления кучи денег с картинкой.
И картину с кучей денег также можно разделить на N участников.
Цитата
Реальная - да, а оптимальная?
Предлагаю на этом закончить с картиной, уже всё вроде разобрали дальше некуда
Не, ну никто-ж не заставляет. Но для меня полной загадкой осталась некая оптимальная цена. Что-то сродни оптимального размера куска. Стоимость не есть единый параметр, как и размер куска. Стоимость лишь выражает совокупность разных параметров. У каждого эти параметры разные, поэтому и оценка картины субъективна, у каждого своя.
Цитата
Ну, одни считали, что невозможно найти, а другие взяли и нашли. Говорят, что нашли. Что тут такого?
Не-е, не так.
Одни считали, что давно уже нашли и довольно просто.
Другие позже сказали, что невозможно найти.
А третьи потом взяли и нашли, но очень сложно.
Где правда?
Изменено: eLectric - 12.12.2016 23:04:25
В споре не рождается истина, но убивается время.
Цитата
eLectric пишет:
Не. Мы же говорили - складываются поровну.
Есть такие слова - "если" и "допустим". Слыхали?
Цитата
eLectric пишет:
Что такое "оптимальная стоимость" и откуда она взялась?
Еще раз. Оптимальная - это такая, которая позволяет разделить по-честному объективно. В данном случае - наибольшая цена картины.
Цитата
eLectric пишет:
Деление пирога с вишенкой
В самой простой формулировке нет там никакой вишенки, сколько можно говорить-то? Точно так же вместо пирога можно делить бутылку водки.
Цитата
eLectric пишет:
Стоимость лишь выражает совокупность разных параметров. У каждого эти параметры разные, поэтому и оценка картины субъективна, у каждого своя.
Разумеется, однако одна цена позволяет разделить поровну, а другая - нет. Какая лучше?
Если один брат внезапно узнаёт, что другой оценивает картину дороже, изменит он своё мнение, как вы думаете? Хотя бы ради того, чтобы слупить с другого компенсацию побольше? Это считается рациональным поведением? А если останется при своей, меньшей оценке, значит себе во вред. Не так?
Цитата
eLectric пишет:
Не-е, не так.
Одни считали, что давно уже нашли и довольно просто.
Другие позже сказали, что невозможно найти.
А третьи потом взяли и нашли, но очень сложно.
Где правда?
Правда в том, что решают разные задачи. В самой простой формулировке решили давно и просто, А в другой формулировке (с вишенкой) оказалось сложно.

Однако, мы пошли уже на третий круг, лично я заканчиваю - сил больше нет :)
Изменено: Техник - 13.12.2016 10:14:42
Ясность - одна из форм полного тумана
Цитата
Техник пишет:
Правда в том, что решают разные задачи. В самой простой формулировке решили давно и просто, А в другой формулировке (с вишенкой) оказалось сложно.
А я вам с самого начала говорю, что вишенка не причём.
Цитата
Техник пишет:
Однако, мы пошли уже на третий круг, лично я заканчиваю - сил больше нет
Ок. Остальное, уважаемый Техник, я пишу не вам, а тем, у кого могло-бы сложиться превратное представление о задаче деления пирога.
.
Про простые формулировки. Математики ставят и решают обобщённые задачи. В которых отвлекаются от конкретных физических или химических подробностей. Обобщение, это методический принцип математики. Упрощение, это совсем даже наоборот. Это дополнительная деталь или условие, конкретизация, которая позволяет решить задачу легко и просто.
Например, деление любого угла на три равные части. В общем случае - деление любого угла на 3, это трудная, настолько трудная, что и вообще неразрешимая задача. А вот упрощённая задача, конкретная: разделить не любой угол, а, скажем, 180 градусов. Такую задачу решить, легко и просто.
.
Задача о делении пирога, это математическая задача. Слово "пирог" используется только для примера и названия задачи. Требуется решение применимое не только к пирогам и тортам, но любым объектам, которые могут делиться: запасы на складе или надел земли или имущество при разводе... Делимое может быть самой разнообразной формы и содержания. Кроме того, участники делёжки, среди которых и делится "пирог" имеют самое разное представление о ценности делимого и его отдельных частей. Вот в таком общем виде задача и имеет математический интерес.
Если вводить в условия какие-то конкретные частности, например, что "пирог" однороден (и никаких "вишенок"), что делить надо по объективному параметру - весу, то задача упрощается до примитивного физического взвешивания.
.
Один из конкретных видов задачи, это деление на двоих. Эта конкретизация, конечно, является упрощением и решение известно с доисторических времён: один разрезает, другой выбирает.
Математический интерес представляет более общая задача - деление на N участников. Такое решение приписывают Банаху, но я его статью не видел, врать не буду. Другие пишут о Г. Штейнгаузе.
В интернете встречаются разные текстовые варианты задачи. Делится то пирог, то тортик, то мешки с зерном, то пираты делят сокровища. Неизменными остаются общие условия: порции можно делить, делимое может быть однородным или неоднородным и любой формы, а также, участники могут иметь разное мнение о ценности порций.
При таких общих условиях находятся, всё-таки, некоторые детали, позволяющие конкретизировать задачу и разбить её на несколько частных. Это потому, что требование справедливого или честного раздела может толковаться по-разному. Например, на Элементах приводится 2 варианта задачи раздела сокровищ пиратами:
1- Разделить надо так, чтобы ни один из N пиратов не мог пожаловаться, что ему досталось менее, чем 1/N часть
2- Разделить надо так, чтобы ни один из N пиратов не мог пожаловаться, что ему досталось менее, чем любому другому пирату.
Формулы задачи очень похожи, но тем не менее различаются по-существу. Тут дело в том, что никакой объективной оценки порций нет. Если делить сокровища классически, по Банаху, то каждый отрезает себе долю не менее, чем 1/N. Однако, порции не равноценны с т.з. участника, и он может заметить, что другие порции больше или меньше, чем 1/N (хотя, каждый из владельцев своей порции считает её не меньшей, чем 1/N). Тогда он может счесть делёж несправедливым. На Элементах это называется задачей завистливых пиратов.
.
В теории игр есть и другая похожая задача. Когда требуется разделить неделимый предмет. И также, участники деления могут иметь разные представления о ценности предмета. Популярно задача описывается в таком виде: два брата (или N братьев) получили в наследство картину, которую и требуется разделить по справедливости.
Решается так: оба брата скидываются поровну на сумму заведомо большую, чем стоимость картины и получается куча: деньги вместе с картиной. А вот эту кучу уже можно разделить точно также, как и пирог.
В споре не рождается истина, но убивается время.
Цитата
eLectric пишет:
А я вам с самого начала говорю, что вишенка не причём.
То есть как это?! Если мне не изменяет память, вы эту вишенку с самого начала пытались мне впихнуть, а теперь выясняется, что ни при чём... Замечательно.
Цитата
eLectric пишет:
Остальное, уважаемый Техник, я пишу не вам
А я всё-таки скажу, дабы не создалось превратного впечатления, ибо не могу молчать :)
В принципе, со всем согласен, но имею одно существенное, на мой взгляд, замечание.
Цитата
eLectric пишет:
Если вводить в условия какие-то конкретные частности, например, что "пирог" однороден (и никаких "вишенок"), что делить надо по объективному параметру - весу, то задача упрощается до примитивного физического взвешивания.
Вот тут категорически не могу согласиться. Предполагается, что никаких весов, линеек и циркулей нет, пирог режется "на глаз", а глазомер, понятно, у каждого свой. Поэтому задача с пирогом "без вишенки", даже однородным и правильной формы, никоим образом не теряет в общности. Упрощается - да, но исключительно за счёт уменьшение числа параметров/критериев (до одного-единственного), по которым производится сравнение частей.
Изменено: Техник - 14.12.2016 12:43:53
Ясность - одна из форм полного тумана
Страницы: Пред. 1 ... 7 8 9 10 11 ... 15 След.

Как разделить пирог?


Портал журнала «Наука и жизнь» использует файлы cookie и рекомендательные технологии. Продолжая пользоваться порталом, вы соглашаетесь с хранением и использованием порталом и партнёрскими сайтами файлов cookie и рекомендательных технологий на вашем устройстве. Подробнее