flaass: игры втроем

игры втроем
Допустим, конечная игра без случайностей и с полной информацией, но играют трое. Ходят по очереди, по кругу. Проигрывает тот, кто не может сделать ход; он получает -1. Последний сходивший получает +1, а остальной - 0.

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

Это известно? Или это неверно? Если неверно, то я вывешу доказательство, очень простое. Ошибок в нем не вижу, но интуиция сопротивляется. Может, все же ошибся? :)

UPD Ура, нашли ошибку!

(Добавить комментарий)

irishoak@lj
2008-12-11 12:10 (ссылка)

Гений нечетких формулировок.

Если мне все равно, получу я 0 или -1 (скажем, я сговорился с другим делить выигрыш пополам), то это неверно. Вот граф: d<-c<-<-b<-a->e->f. Начинаем из a, ходим по стрелкам. Тогда первый может обеспечить выигрыш любому из двух остальных.

Если же я хочу получить КАК МОЖНО БОЛЬШЕ ПРИ ОПТИМАЛЬНОЙ (???) ИГРЕ ОСТАЛЬНЫХ - то что это такое - оптимальная игра остальных?

(Ответить) (Ветвь дискуссии)

	buddha239@lj 2008-12-11 12:30 (ссылка)
	Да, я тоже подумал о похожем примере.:) Но Ваш проще. (Ответить) (Уровень выше)

	flaass@lj 2008-12-11 14:10 (ссылка)
	Уф, ну слава богу :) Видимо, было помутнение рассудка. Доказательство вывешивать уже не надо, ибо на этом примере видно, где в нем ошибка. Но зато интуиция не пострадала, а это главное :) (Ответить) (Уровень выше)

ipain@lj
2008-12-11 12:57 (ссылка)

игры втроем редкий зверь, пару лет назад беседовал с одним из авторов этой статьи (http://necsi.org/events/iccs6/viewpaper.php?id=43) про свою старую игрушку (трое одновременно называют число, выигрывает среднее) и во время разговора всплыла еще одна статья (http://arxiv.org/PS_cache/quant-ph/pdf/0007/0007038v2.pdf) на ту же тему, в которой что то похожее вашему рассуждению обсуждается.

(Ответить)

ahaxopet@lj
2008-12-11 13:14 (ссылка)

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

(Ответить) (Ветвь дискуссии)

	flaass@lj 2008-12-11 14:03 (ссылка)
	Как раз в такой и сопротивлялась: неужто нельзя придумать такую игру, чтоб при любом раскладе 2:1 побеждали бы 2, а не 1? И не зря сопротивлялась, см. выше :) (Ответить) (Уровень выше)

	ilya_dogolazky@lj 2008-12-11 16:40 (ссылка)
	Простой пример: на столе 4 монеты, за один ход можно брать 1 или 2 штуки. Тут не выиграть никак, или таки можно? (Ответить) (Ветвь дискуссии)

urod@lj
2008-12-11 20:16 (ссылка)

Сажаем первого: первый берёт 1 или 2, второй оставшееся до 3, третий последнюю монету - первый проиграл.

Сажаем второго: первый берёт 1, второй берёт 1 или 2, третий оставшееся - второй получил 0.

Сажаем третьего: первый и второй берут по 2 - третий проиграл.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	flaass@lj 2008-12-12 07:05 (ссылка)
	Здесь второй отделывается нулем. Но есть простой пример, где еще круче: любые двое, сговорившись, могут оставить третьего с -1. (Ответить) (Уровень выше)