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. обгоняя по обочине, не факт что в итоге он не увеличит пропускную способность..

    ОтветитьУдалить
  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. Имхо, вероятность, что все найдут свой номер = 0.5^2N.

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

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

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

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

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

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

    ОтветитьУдалить
  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, 9: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.

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