12 июл. 2011 г.

Общая цель

Добрый день!

В задачах о взаимодействии игроков бывают разные цели:
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! Кстати, наша сборная показала высокий уровень командной игры, что прямо относится к теме этой заметки. Было видно, что каждый игрок понимал, что важно максимизировать не количество мячей, эффектно забитых своими руками, а вероятность победы команды в матче/партии.

29 комментариев:

  1. Ключ, по видимому, в том, что участники перекладывают таблички между коробочками. Задача - чтобы номера коробочек соответствовал номерам табличек в ней.
    Считать, к сожалению, сейчас лень. Извините :/

    ОтветитьУдалить
  2. Очень просто добиться вероятности (N!)^2/(2N)! - для этого первые N человек открывают коробочки от 1 до N, а остальные - от N+1 до 2N

    Для N=2 этот вариант действительно наилучший (довольно простой перебор), а для больших N - не знаю.

    ОтветитьУдалить
  3. Анонимный12.07.2011, 18:03

    Интуитивно кажется, что выгоднее всего i-му чуваку посмотреть в коробочки i, i+1, ..., i+N (при циклической нумерации, то есть под коробочкой с номером k>2N подразумевается коробочка номер ((k-1) mod 2N)+1). Но ни найти вероятность победы при такой стратегии, ни доказать ее оптимальность сходу не получилось.

    ОтветитьУдалить
  4. Интуитивный ответ - 50%
    Стратегия: входящий (номер Х) открывает коробочку с со своим номером (Х). Если внутри карточка с другим номером (У) - открывает коробочку с этим номером (У) и кладет эту карточку в неё. Карточку из новой коробочки (З) перекладывает по той-же логике. Когда находит свою карточку (Х), кладет её в свою коробку. Если осталось более одной коробочки для открытия - открывает пусть 2N-Х коробочку

    ОтветитьУдалить
  5. Анонимный12.07.2011, 19:11

    обгоняя по обочине, не факт что в итоге он не увеличит пропускную способность..

    ОтветитьУдалить
  6. 1/2^N
    Ящики и людей нужно разделить пополам. первая половина населения заглядывает в первую половину ящиков, вторая - во вторую. Или наоборот. Для каждого из первой половины шанс найти свой номер 1/2, для всех из первой половины 1/2^N. если они все найдут свои номера, то вторая половина людей найдут свой номер с вероятностью 100%.

    ОтветитьУдалить
  7. Denter, Вы предложили интересное решение, хоть и решали другую задачу. По условию состояние комнаты перед входом каждого участника делают исходным (т.е. они не могут что-то менять в комнате, а могут только заглядывать в N коробочек).

    zmior, действительно, вскрыв N коробочек из 2N, игрок найдёт свою карточку с вероятностью 1/2. А вот продолжение Вашего решения я не понимаю. Можете пояснить?

    ОтветитьУдалить
  8. Илья, я оставался в рамках формулировки "коробочки закрыты, ничего не сдвинуто". Про содержимое коробочек в условии ничего не было :)

    Ход мыслей zmior: если все первые N нашли свои карточки, значит в первых N коробочках находятся карточки с 1 до N. И в коробочках с N+1 до 2N будут и соответствующие карточки.
    Ошибка в рассуждении - только у первого шанс будет 1/2. У второго уже - (N-1)/(2N-1).

    При рассуждении, возможно, стоит поставить себя на место коробочки, а не участника. Если я коробочка и меня открывало Х участников, то шансов что меня открыл участник с номером, совпадающим с номером на моей карточке, Х/2N. Теперь сравним вероятность для 2-х коробочек, когда X равно N и когда одну проверили на 1 раз больше, а другую - на 1 раз меньше.
    Или ((N-1)/2N)*((N+1)/2N) сравнить с (N/2N)*(N/2N). Получаем (N^2-1)/4N^2=1/4-(1/4N^2), что определенно меньше чем просто 1/4.
    Итого максимизация шансов достигается тогда, когда каждую коробочку проверили одинаковое количество раз.
    А вот что за цифра получается - пока не готов ответить.

    ОтветитьУдалить
  9. Анонимный13.07.2011, 12:07

    Имхо, вероятность, что все найдут свой номер = 0.5^2N.

    Или я непонимаю, если они не могут общаться, и между ними не происходит никакого обмена, и свой номер с коробкой не забирается — тогда каждый просто заходит и смотрит любой набор из половины коробок.

    Какой смысл второму открывать вторую коробку, если его номер — в первой? И первый участник видел это.

    ОтветитьУдалить
  10. > Или я непонимаю, если они не могут общаться, и между ними не происходит никакого обмена, и свой номер с коробкой не забирается
    Они могут договориться заранее, кто какие коробки откроет, чтобы максимизировать вероятность того, что все они найдут свой номер.

    > Какой смысл второму открывать вторую коробку, если его номер — в первой?
    Никакого! В этом и идея решения.

    > И первый участник видел это.
    Не важно, что видел первый, если он ничего не может сообщить второму, так ведь?

    ОтветитьУдалить
  11. Анонимный13.07.2011, 12:57

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

    ОтветитьУдалить
  12. Поддержу zmior:

    Коробочки делятся на две части. Первая половина людей открывает эти коробочки, а вторая половина - остальные.

    В этом случае вероятность того что все найдут свои коробочки

    N!*N!/2N!

    Если открывать циклически (1,2,..; 2,3..; 3,4..), то вероятность снижается. Какая именно не считал. Проверил эмпирически в Екселе :)

    ОтветитьУдалить
  13. Анонимный14.07.2011, 10:11

    Задача известная, и довольно аддиктивная. )

    По сути, раскладка 2N карточек в 2N занумерованных коробочек являкется перестановкой из 2N элементов.

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

    Илья.

    ОтветитьУдалить
  14. Анонимный16.07.2011, 10:44

    Все люди смотрят одну половину коробочек.
    вероятность жестко 50%. Ни меньше, ни больше =)

    Тио.

    ОтветитьУдалить
  15. Анонимный16.07.2011, 11:41

    >>Все люди смотрят одну половину коробочек.
    Вероятность ровно 0, поскольку люди, у которых карточки лежат в коробочках N+1...2N никогда не найдут свою карточку.

    Относительно перестановок - да, решение довольно неплохо увеличивает шансы на победу. В случаях, когда нет циклов из N+1...2N элементов - будет победа. Всего обратных случаев
    сумма по i от N+1 до 2N C^{i}_{2N}*(2N-i)! = сумма по i от N+1 до 2N ((2N)!/i!). Т.к. это надо поделить на (2N)! - число случаев вообще, то получим, что вероятность победы равна
    \sum_{i=1}^N 1/i!

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

    ОтветитьУдалить
  16. Анонимный16.07.2011, 11:43

    *Предыдущий анонимный комментатор.
    Поправка, вероятность победы равна
    (1 - \sum_{i=N+1}^{2N} 1/i!)

    ОтветитьУдалить
  17. Анонимный16.07.2011, 11:50

    *Предыдущий анонимный комментатор
    Извиняюсь за разведённый флуд. Я не учёл, что порядок элементов в "длинном" цикле так же имеет значение. Если не ошибаюсь, то для каждого i будет (i-1)! различных циклов. Таким образом вероятность получается
    (1 - \sum_{i=N+1}^{2N} 1/i)
    С другой стороны это решение тоже не очень похоже на правду, поскольку при больших N оно, кажется, будет меньше нуля.

    ОтветитьУдалить
  18. Анонимный16.07.2011, 12:26

    *предыдущий анонимный комментатор.

    Нет, оно не будет меньше нуля, поскольку \sum_{i=N+1}^{2N} 1/i
    сводится к последовательности
    a(1) = 1/2
    a(n) = a(n-1) - 1/(n) + 1/(2n) + 1/(2n-1) = a(n-1) - 1/(2n) + 1/(2n-1) = a(n-1) - 1/(2n) + 1/(2n-1)
    Таким образом итоговая вероятность 1-a(n) представляет собой сумму знакопеременного гармонического ряда. И стремится при n -> inf к log(2).

    ОтветитьУдалить
  19. Илья К.16.07.2011, 12:34

    Тио, увы, в таком случае вероятность жестко 0%. Ни меньше, ни больше =)

    ОтветитьУдалить
  20. Анонимный19.07.2011, 14:16

    В лоб:
    Четные номера открывают четные коробочки, нечетные- нечетные
    Итоговая вероятность успеха (1/2)^2n

    ОтветитьУдалить
  21. Уважаемый аноним, а Вы можете доказать, что более эффективного подхода не существует?

    ОтветитьУдалить
  22. Анонимный20.07.2011, 09:55

    Насколько мне известно, этого пока никто не может доказать. )

    Илья.

    ОтветитьУдалить
  23. Анонимный20.07.2011, 10:31

    Думаю что оценка в (1/2)^2n
    можно улучшить если как-то использовать знание о том, что раз испытание продолжается, то это значит что предыдущие попытки закончились успешно. В этом смысле использование статичной стратегии (чет/нечет например) приводит к тому, что у последующих попыток вероятность успеха будет на самом деле не равно 1/2. Из-за то что например в пуле четных коробочек _точно_ есть k номеров предыдущих попыток.
    Стало быль вероятность успеха попытки k (для четного случая на пример): p(k) = (n-k)/(2n)

    ОтветитьУдалить
  24. Анонимный20.07.2011, 11:51

    Уточнение: (1/2)^(2n-1)
    Ибо последний человек уже точно найдет свой номер.

    ОтветитьУдалить
  25. Анонимный20.07.2011, 16:35

    А могут ли люди которые еще не заходили в комнату учитывать как быстро вызывают следующего?
    Олег

    ОтветитьУдалить
  26. Анонимный20.07.2011, 19:12

    Все-таки нечетные фишки окажутся в нечетных коробках с вероятностью (N!)^2/(2N)!

    Дмитрий

    ОтветитьУдалить
  27. > Уточнение: (1/2)^(2n-1)
    Ибо последний человек уже точно найдет свой номер.

    А какие у нас есть основания надеяться, что последний точно найдёт?

    > А могут ли люди которые еще не заходили в комнату учитывать как быстро вызывают следующего?
    Нет, бесчеловечный диктатор так всё устроил, что время всегда получается одинаковое, поэтому этот аспект учитывать никак нельзя.

    ОтветитьУдалить
  28. Анонимный21.07.2011, 11:09

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

    ОтветитьУдалить
  29. Олег, таким образом Вы делаете лишь оценку вероятности, а не вычисляете честную вероятность (так как проводите это уточнение только для последнего игрока, хотя и у предшествующих игроков иногда вероятность была не ровно 1/2, а чуть лучше).

    Предлагаю продолжить обсуждение в следующей заметке.

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний