Ответ в задачке про пиратов

[scholar_vit]

Пожалуй, мне следовало заскринить комментарии в задаче про пиратов: bazar_wokzal и rioman почти мгновенно её решили. Ответ такой: пираты делятся на две партии, с четным раногом и с нечетным. Капитан дает по одной монете своим однопартийцам, а остальные берет себе. Этот вариант для них выгоден, так как в противном случае первый помощник сделает то же самое со своими однопартийцами. Доказательство - несложная индукция по n.

Comments

[vap.livejournal.com]

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

Так что какая-то нехорошая мораль за этой задачкой стоит.

[vap.livejournal.com]

fix: в полном соответствиИ

[p_govorun.livejournal.com]

А по-моему мораль вполне годная. Никого ведь не убили, а деньги -- дело наживное. При других способах дележа, вполне возможно, они бы перебили друг друга. (Смайлик.)

(Помните конец "Острова сокровищ"? Там оставалось ещё два клада, но кладоискатели решили, что им хватит приключений.)

[meshko.livejournal.com]

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

[scholar-vit.livejournal.com]

Старший помощник, если он проголосует против, получит гораздо больше, чем одну монету, верно?

[meshko.livejournal.com]

Ну его пропустить. Остальным-то всё равно?

пираты делятся на две партии, с четным раногом и с нече

[sceptic-rus.livejournal.com]

"пираты делятся на две партии, с четным раногом и с нечетным"

Не предумотрена возможность кооперации низших по рангу против более высших.

[spartach.livejournal.com]

Меня смущает один момент в этом решении. Возможно, кто-нибудь пояснит, где я неправ?

Пусть пиратов трое. Первый что-то предлагает, второй заведомо будет против (ведь если первого скинут, то второй получит вообще всё), а третий колеблется - но знает, что если первого скинут, то ему не достанется вообще ничего.

И допустим, первый предложит забрать все деньги себе. Зачем в таком случае третьему голосовать "против" - ведь от смерти первого лучше ему не станет?

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

[scholar-vit.livejournal.com]

http://scholar-vit.livejournal.com/202425.html?thread=7122105#t7122105

[mccme.livejournal.com]

Вопрос по условию: как поступает пират, если при обоих вариантах его голосованиях ему достается одинаковое число монет?

[scholar-vit.livejournal.com]

Тогда его голос неопределен (он подбрасывает монетку). Поэтому в рациональной стратегии ему надо дать заведомо БОЛЬШЕ, чем в альтернативе.

[aikr.livejournal.com]

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

Доказательство:

Начнём с ситуации, когда пиратов ровно два. Капитан берёт все деньги себе и голосует за это: 50% голосов (из имеющихся двух) ему обеспечено. Отсюда видно, что при n=2 последний пират гарантированно ничего не получает.

Переходим к ситуации, когда пиратов трое. Капитан предлагает все деньги отдать ему. Второй пират, естественно, возражает. А третий пират, последний по рангу? Он знает, что если поддержать старпома, то капитан будет «списан за борт», и ситуация будет сведена к предыдущей. Но ведь мы уже выяснили, что при n=2 последний пират ничего не получает! То есть кого бы он ни поддержал, он остаётся без денег. Поэтому он голосует за предложение капитана: по деньгам ничего не изменится, зато на одного боевого товарища останется больше. Отсюда видно, что при n=3 два последних пирата гарантированно ничего не получают.

Переходим к n=4. Ну, вы поняли, да? Второй по рангу и хотел бы свести ситуацию к n=3, но два последних пирата знают, что денег им так и так не обломится, так хоть капитана бы сохранить, дело-то не последнее. И опять все деньги без остатка достаются капитану.

Дальнейшее очевидно: при любом n сводить ситуацию к n-1 невыгодно последним n-2 пиратам и тем более невыгодно первому. Только бедный старпом хотел бы избавиться от капитана, но кто ж ему даст...

[scholar-vit.livejournal.com]

http://scholar-vit.livejournal.com/202425.html?thread=7122105#t7122105

[aikr.livejournal.com]

Ага, понятно. Просто в том варианте, в котором я встречал эту задачу раньше, есть дополнительное условие: если по деньгам нет разницы, пират голосует за тот вариант, который позволяет оставить максимальное количество пиратов в живых. Надо мне было обратить внимание, что здесь этого условия нет.

[insead-hec.livejournal.com]

Я читал, что очень похожую задачу в Google дают на интервью по приему на работу

неясно с "однопартийцами"

[(Anonymous)]

Почему "первый помощник сделает то же самое", да еще обязательно "со своими однопартийцами"?

Вот я "нечетный" пират. Капитан предлагает мне монету. Брать? Если брать - получу 1 монету. Если не брать - капитан летит за борт, а первый помощник, очевидно, предложит ДРУГУЮ стратегию, дабы не полететь вслед за капитаном. Т.е. в любом случае первый помощник НЕ "сделает то же самое".

Re: неясно с "однопартийцами"

[p_govorun.livejournal.com]

Применим индукцию. Первый помощник предложит другую стратегию и тоже полетит за борт (мне и одной монеты -- мало, и много монет тоже -- мало). Потом туда последует второй помощник и т.д. А потом очередь дойдёт и до меня, и я тоже окажусь за бортом. Так что надо голосовать "за", пока не поздно.

(Иллюстрация :-)