задачка (математическое)

[avva]

Поздравляю, вы - один из 13 директоров большой и очень богатой компании!

Вам приналежит ровно 1/13 компании, как и каждому из остальных директоров. Вместе с 12 вашими коллегами, каждую неделю вы участвуете в заседании совета директоров, во время которого вы рассаживаетесь по кругу. Любой директор имеет право выдвинуть предложение, и как только он его выдвигает, все голосуют следующим образом: предложивший автоматически считается "за", после него голосует следующий за ним по часовой стрелке, потом следующий и так далее до конца круга. Голосование открытое, так что каждый знает голоса предыдущих. Голосовать можно только "за" или "против". Предложение принимается только если оно получает большинство (больше 50%) голосов.

Для того, чтобы уменьшить число махинаций и стабилизировать работу совета, существует также следующее правило. Любое предложение, которое включает в себя перераспределение имущества компании, изменение состава совета директоров, или изменение правил голосования, называется "опасным". В случае, если "опасное" предложение не принимается, его автор и все другие директора, проголосовавшие "за" автоматически теряют свои места в совете директоров и теряют свои доли в компании, которые перераспределяются равным образом среди оставшихся. Это правило делает выдвижение "опасных" предложений таким рискованным делом, что их практически никогда не выдвигают.
Ведь если задуматься, даже если предложение кажется разумным и выгодным многим в совете, ничто не мешает им всем проголосовать против, обогатиться на долю предложившего, а потом подумать о нем снова.

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

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

P.S. Я не буду пытаться скрывать правильные решения, потому что это сложно - основная идея "витает в воздухе", но трудность в том, чтобы ее правильно использовать, и в том, чтобы строго доказать. Так что не заглядывайте в комментарии, если хотите решить сами - "витающих в воздухе" приблизительных идей уже сейчас там несколько, а скоро наверняка и точные решения появятся.

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

Comments

[asiafilm-tv.livejournal.com]

А давайте выгоним того, кто первый проголосует "против"?

[angerona.livejournal.com]

не пойдет. С чего бы им это предложение принимать? Если они все проголосуют против, то выгонится предложивший, так что они получат такую же долю, как если б проголосовали "за". Плюс это никак не убирает всех остальных с совета директоров.

[rezoner.livejournal.com]

Не обязательно "первый". Просто всех кто против.

[mkal.livejournal.com]

Что-то вроде исключить и расстрелять первого, кто проголосует против или отдать компанию мне, если такого не найдётся.

[asiafilm-tv.livejournal.com]

О, еще идея: изменение правил голосования. Можно предложить "а давайте отныне "за" будет означать "против", а "против" - "за"

На вопрос не отвечает, но забавно подумать, к чему приведет. Если большинство проглосует "за", это будет значить, что они проголосовали "против".

[mkal.livejournal.com]

Или так. Отдать имущество всех, проголосовавших против, всем остальным кроме меня. Если против никто не проголосовал, то отдать компанию мне, раздав всем по доллару в виде компенсации.

Если 6 человек уже проголосовало против, то остальным выгоднее голосовать за, т.к. тогда они получают по целой доле, а при голосовании против - не больше 6/7 долей. Поэтому при 5и против следующий будет за, а значит при четырёх против следующий будет за и т.д. Т.ч. решение будет принято.

Почему после 7 голосов за остальные, поняв, что решение будет принято, будут всё равно голосовать "за"? Голос против означает потерю всего, голос за - в худшем случае останется 1 доллар.

[imfromjasenevo.livejournal.com]

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

[imfromjasenevo.livejournal.com]

при этом, если кто-то голосует против, остальные уже голосуют за, так как ничего не теряют в таком случае.

вот такое какое-то условие должно быть

[dimrub.livejournal.com]

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

[avva.livejournal.com]

Доказательство не очень убедительное. "Второй по кругу ничем не рискует, голосуя за, и рискует всем, голосуя против" - почему же не рискует, а вдруг предложение не пройдет?

[dibr.livejournal.com]

Предлагаю. [Отдать всё мне, остальным раздать доллар на всех], но если будет хотя бы один голос против - оставить всё как есть, но первого проголосовавшего против - расстрелять исключить из совета.

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

[vnesov.livejournal.com]

Тут видимо необходимо законом природы делать causal decision theory (http://en.wikipedia.org/wiki/Causal_decision_theory) или что-то вроде того, т.к. очевидно, что если все проголосуют против - это будет Парето-улучшение (http://en.wikipedia.org/wiki/Pareto_improvement), хотя может быть и не равновесие, личное или коалиционное.

Т.е. например если бы все 12 остальных директоров были бит-в-бит идентичными компьютерными программами, выбиравшими стратегию [Номер-места -> решение], то стратегию они бы выбрали одну и ту же, и эта стратегия не была бы такой плохой, т.к. всем дружно отказаться - лучше.

"Уволим первого, кто проголосует против" - форма парадокса неожиданной казни (http://en.wikipedia.org/wiki/Unexpected_hanging_paradox), с теми же проблемами, которых тьма тьмущая (http://dedekind.mit.edu/~tchow/surprise.pdf), так что действительно будут большие проблемы с удовлетворительным доказательством, даже при введении необходимых допущений об алгоритмах мышления, используемых директорами.

[(Anonymous)]

предложение из двух пунктов:
1. автор опасного предложения, принятого единогласно, имеет право всех выгнать за компенсацию в один доллар.
2. кто против этого предложения, того выгоняем без компенсации.

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

примерно в таком ключе, наверное.

[igor734.livejournal.com]

Что-то вроде: "Кто за то, чтобы каждый проголосовавший "за" смог выкупить все акции пролосовавшего следом за ним за 1 доллар?" :)

[max-i-m.livejournal.com]

Строго больше 50%?

[avva.livejournal.com]

Да.

[ahaxopet.livejournal.com]

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

[ahaxopet.livejournal.com]

А, извиняюсь, невнимательно условие прочитал. Оказывается, ровно 50% голосов недостаточно. Пойду еще подумаю.

[alexeybobkov]

Непонятно, как можно "доказать, что оно действительно пройдет единогласно". Для этого в условии должно быть сказано, как именно участники принимают решение голосовать за то или иное предложение.

[avva.livejournal.com]

Строго денежные соображения.

[avva.livejournal.com]

Да, я это не написал, т.к. привык, что это предполагается в задачах такого типа.

[spamrobot3.livejournal.com]

Неприятная задача. Решение подразумевает необычную вещь: что свежепринятый закон может задним числом "наказать" за действия, совершенные до момента принятия этого закона.

[spamrobot3.livejournal.com]

т.е голос "против" будет нагружен дополнительным значением задним числом

[alexeybobkov]

Мда, немножко не сообразил. Жаль.

А что будет, интересно, если сделать то же предложение, но голосование будет одновременное.

[rakshas.livejournal.com]

Показательно, что очень мало полных правильных ответов, хотя задача довольно тривиальная.

Интересно, есть ли разница между вариантом "поделить имущество проголосовавших против на всех, кроме меня" и "поделить имущество проголосовавших против на всех ровно + с меня один бакс"

Мне кажется второе решение более соответствует духу задачи, хотя формально они эквивалентны :)

[avva.livejournal.com]

Первый вариант всего равно требует один бакс (для того, чтобы убедить последних шестерых).

[(Anonymous)]

Бородатый боян. Задача про 5 пиратов и 100 золотых монет. Дальше надеюсь можно не продолжать.

[alexeybobkov]

Слегка похожие условия задачи и абсолютно другое решение.

[proninc.livejournal.com]

Уважаемые господа!
С прискорбием сообщаю, что наша компания попала под судебное преследование, полностью поглотившее активы. Более того, аналитики предсказывают, что уже в краткосрочной перспективе у собственников компании возникнут все увеличивающиеся долги, связанные с бременем обладания компанией. Возможны и тюремные сроки.
Поскольку данная ситуация случилась по моей вине, предлагаю не делить ответсвенность на всех. Вы передаете мне свои доли в компании за символическую плату в 1 доллар на всех и тем самым избегаете дальнейшего перследования.

имхо- это лучший вариант;)

[utirki.livejournal.com]

Классный журнал, подписался на ленту!