?

Log in

No account? Create an account

Previous Entry | Next Entry

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

Comments

( 17 comments — Leave a comment )
vap
Jun. 14th, 2009 01:54 am (UTC)
Демонстрируется, что решение проблем голосованием может быть несправедливым.
Но для (любого?) либертарианца это и так очевидно :)))
Также демонстрируется, что в сословном обществе (а ранги можно считать некоторым подобием сословного деления, ибо, хотя ранг и зависит от "заслуг", но от ранга зависят формальные права и обязанности) стоящий наверху имеет возможность принуждать тех, кто ниже, в полном соответствием с основными принципами теории игр.
И вдобавок в формулировке задачи неявно закодировано, что ситуация - одна, повторения не будет, и после окончания дележа все разбегаются и больше никогда друг друга не увидят, и поэтому принимать решение при голосовании нужно без учета нынешней и будущей репутации, что, очевидно, противоречит направлению "эмоциональной нагрузки", позволяющей проводить аналогии с реальным миром.

Так что какая-то нехорошая мораль за этой задачкой стоит.
vap
Jun. 14th, 2009 02:03 am (UTC)
fix: в полном соответствиИ
p_govorun
Jun. 14th, 2009 10:32 am (UTC)
А по-моему мораль вполне годная. Никого ведь не убили, а деньги -- дело наживное. При других способах дележа, вполне возможно, они бы перебили друг друга. (Смайлик.)

(Помните конец "Острова сокровищ"? Там оставалось ещё два клада, но кладоискатели решили, что им хватит приключений.)
meshko
Jun. 14th, 2009 03:12 am (UTC)
Интересно (если, конечно, я прав): я поспешил и решил задачу неправильно, но ответ мой, по-моему, всё-таки правильный: капитан дает по одной монете старшим n/2 пиратам.
На самом деле просто произвольным n/2. Потому что больше одной монеты всё равно никому не получить, так что все получившие проголосуют за.
scholar_vit
Jun. 14th, 2009 04:28 am (UTC)
Старший помощник, если он проголосует против, получит гораздо больше, чем одну монету, верно?
meshko
Jun. 14th, 2009 04:53 pm (UTC)
Ну его пропустить. Остальным-то всё равно?
sceptic_rus
Jun. 14th, 2009 05:09 am (UTC)
пираты делятся на две партии, с четным раногом и с нече
"пираты делятся на две партии, с четным раногом и с нечетным"

Не предумотрена возможность кооперации низших по рангу против более высших.
spartach
Jun. 14th, 2009 08:00 am (UTC)
Меня смущает один момент в этом решении. Возможно, кто-нибудь пояснит, где я неправ?

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

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

Точно так же и в произвольном случае мне не очевидно, почему, если первый по рангу захочет забрать всё себе, то его обязательно скинут.
mccme
Jun. 14th, 2009 08:06 am (UTC)
Вопрос по условию: как поступает пират, если при обоих вариантах его голосованиях ему достается одинаковое число монет?
scholar_vit
Jun. 14th, 2009 07:12 pm (UTC)
Тогда его голос неопределен (он подбрасывает монетку). Поэтому в рациональной стратегии ему надо дать заведомо БОЛЬШЕ, чем в альтернативе.


Edited at 2009-06-14 07:13 pm (UTC)
aikr
Jun. 14th, 2009 08:16 am (UTC)
И между прочим, это неправильный ответ. Правильный такой: капитан берёт все деньги себе, и все (кроме старпома) за это голосуют.

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

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

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

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

Дальнейшее очевидно: при любом n сводить ситуацию к n-1 невыгодно последним n-2 пиратам и тем более невыгодно первому. Только бедный старпом хотел бы избавиться от капитана, но кто ж ему даст...
aikr
Jun. 14th, 2009 07:56 pm (UTC)
Ага, понятно. Просто в том варианте, в котором я встречал эту задачу раньше, есть дополнительное условие: если по деньгам нет разницы, пират голосует за тот вариант, который позволяет оставить максимальное количество пиратов в живых. Надо мне было обратить внимание, что здесь этого условия нет.
insead_hec
Jun. 14th, 2009 05:40 pm (UTC)
Я читал, что очень похожую задачу в Google дают на интервью по приему на работу
(Anonymous)
Jun. 15th, 2009 08:14 am (UTC)
неясно с "однопартийцами"
Почему "первый помощник сделает то же самое", да еще обязательно "со своими однопартийцами"?

Вот я "нечетный" пират. Капитан предлагает мне монету. Брать? Если брать - получу 1 монету. Если не брать - капитан летит за борт, а первый помощник, очевидно, предложит ДРУГУЮ стратегию, дабы не полететь вслед за капитаном. Т.е. в любом случае первый помощник НЕ "сделает то же самое".
p_govorun
Jun. 15th, 2009 07:43 pm (UTC)
Re: неясно с "однопартийцами"
Применим индукцию. Первый помощник предложит другую стратегию и тоже полетит за борт (мне и одной монеты -- мало, и много монет тоже -- мало). Потом туда последует второй помощник и т.д. А потом очередь дойдёт и до меня, и я тоже окажусь за бортом. Так что надо голосовать "за", пока не поздно.

(Иллюстрация :-)
( 17 comments — Leave a comment )

Profile

knot
scholar_vit
scholar_vit

Latest Month

September 2017
S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Tags

Powered by LiveJournal.com
Designed by Paulina Bozek