Общая цель

Добрый день!

В задачах о взаимодействии игроков бывают разные цели:
1) индивидуалистическая (максимизировать вероятность собственной победы),
2) бухгалтерская (максимизировать суммарный выигрыш всех игроков),
3) бескомпромиссная (максимизировать вероятность того, что все победят),
4) конкурентная (максимизировать количество тех, у кого результат будет хуже собственного),
5) ...

Классификаций, конечно, бывает много, но они нам сейчас и не нужны. Впрочем, для ясности приведу примеры (возможно, не самые удачные, но короткие, что важнее):
1) шахматная партия — индивидуалистическая игра,
2) задача о составлении расписания или настройке светофоров — бухгалтерская игра (максимизируем комфорт для всех участников),
3) взаимное кредитование стран — бескомпромиссная игра (если один «проиграет», то и остальные полетят вниз),
4) шахматный турнир — конкурентная игра (стараемся подняться как можно выше).

Какое это имеет отношение к жизни? Многие игры возникли не просто так, а являются отражением реальности. Например, когда автомобилист обгоняет пробку по обочине, то он выигрывает в своей индивидуалистической игре (приезжает быстрее), но все остальные проигрывают в бухгалтерской игре (пропускная способность дороги уменьшается из-за того, что эти автомобили потом с обочины лезут обратно на автодорогу). А бывают ситуации, когда даже индивидуального выигрыша человек не получает, но всё равно поступает так, чтобы другим не было удобно (например, когда ставит свою машину так, что она занимает два-три парковочных места).

Предлагаю одну из задачек о бескомпромиссной игре, в которой участники обязаны думать друг о друге (т.е. у них есть общая цель, а индивидуальная победа невозможна по условию):
Бесчеловечный тиран пронумеровал 2N человек числами от 1 до 2N, заготовил 2N коробочек, пронумерованных от 1 до 2N, произвольным образом поместил в каждую коробочку ровно одну табличку с числом от 1 до 2N. Другой бы на этом остановился, но этот был очень бесчеловечным! Он запер всех людей в одной комнате, а все коробочки с бумажками в другой. Но не просто так запер, а объявил, что все люди будут заходить по одному в комнату с коробочками, чтобы заглянуть ровно в N штук, ничего не перекладывая. Естественно, состояние комнаты перед входом каждого участника делают исходным (все коробочки закрыты, ничего не сдвинуто и так далее), а игроки никак не могут общаться после того, как первый зашёл в комнату.

Цель людей — договориться действовать таким образом, чтобы максимизировать вероятность того, что каждый человек откроет коробочку, в которой лежит табличка с его номером. Другими словами, выигрыш каждого возможен только тогда, когда выигрывают все. А если хоть один участник свой номер не найдёт, то их всех заберёт паром из задачки про остров без зеркал. Этого никто не хочет, поэтому все будут стараться :)

Второй вопрос: с какой вероятностью умные люди будут выигрывать в этой игре?

Для начала давайте рассмотрим крайний случай — N=1. У нас есть два участника и две коробочки. В одной коробочке номер одного, в другой — номер второго. Каждый из них может открыть только одну коробочку, поэтому они должны договориться о том, что откроют разные (так как выиграть могут только при условии, что оба увидят свои номера в коробочках). Сначала заходит первый — он может открыть любую коробку (с вероятностью 1/2 в ней он увидит свой номер). Если игроки хорошо договорились, то второй участник вскроет вторую коробку с вероятностью 100%. Соответственно, для N=1 ответ такой:
1) игроки должны договориться, что первый открывает первую коробочку, а второй — вторую (или наоборот),
2) если они так поступят, то выиграют с вероятностью 50%.

Это был простой случай, чтобы лучше понять условие. А теперь приглашаю решить задачу для N>1.

Хорошего дня!

P.S.
Поздравляю всех с победой мужской волейбольной команды России в Мировой лиге 2011! Кстати, наша сборная показала высокий уровень командной игры, что прямо относится к теме этой заметки. Было видно, что каждый игрок понимал, что важно максимизировать не количество мячей, эффектно забитых своими руками, а вероятность победы команды в матче/партии.