16 дек. 2010 г.

Обобщение задачи Монти-Холла

Добрый день!

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

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

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

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

Итак, задача:
0) игрок и ведущий умные (то есть они оба могут догадаться до всего, до чего можно догадаться, как и в задаче про голубоглазых на острове),
1) игрок хочет с максимальной вероятностью выбирать призы, а ведущий хочет минимизировать эту вероятность,
2) перед игроком два подноса, на каждом из которых по три шкатулки, причём на каждом подносе есть ровно одна шкатулка с призом,
3) ведущий обязан ровно один раз открыть пустую шкатулку.

Игра проходит следующим образом:
а) игрок показывает на одну из шкатулок,
б) ведущий открывает или не открывает одну из оставшихся двух шкатулок на этом подносе (естественно, пустую),
в) ведущий предлагает игроку изменить свой выбор (указать на оставшуюся пустую шкатулку или ничего не менять для данного подноса),
г) пункты а), б) и в) повторяются для второго подноса (но ведущий обязан открыть пустую шкатулку ровно один раз).
После игры становится ясно, сколько (0, 1 или 2) призов добыл игрок/проиграл ведущий.

Что дальше? А получается довольно забавная ситуация:
- игрок знает, что если ведущий не открыл шкатулку на первом подносе, то он заведомо сделает это на втором, что позволит игроку хотя бы тут получить приз с вероятностью 2/3,
- ведущий знает, что игрок настроен поменять свою шкатулку на другую, если ведущий воспользуется своей возможностью вскрыть пустую, поэтому будет открывать её именно тогда, когда игрок выбрал шкатулку с призом,
- игрок понимает это, поэтому будет настаивать на своём выборе, даже если ведущий открыл пустую шкатулку,
- ведущий, догадавшись до такой хитрости игрока, будет вскрывать пустую шкатулку тогда, когда игрок не попал в приз,
...

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

Соответственно, вопрос задачи: как должны действовать игрок и ведущий, чтобы достичь своих целей?

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

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

23 комментария:

  1. Анонимный17.12.2010, 13:57

    Наконец-то! Я уже волноваться начал, почему нет новых постов. Сейчас про задачку подумаю :-)

    ОтветитьУдалить
  2. В задаче не увидел одной важной детали - вопроса.
    Что определить-то требуется?

    ОтветитьУдалить
  3. Lisandrel, оптимальные стратегии игрока и ведущего, наверное.

    ОтветитьУдалить
  4. Уважаемый аноним, спасибо, что ждали :) Не волнуйтесь, всё хорошо! Было совсем мало времени, поэтому долго не писал.

    LisandreL, спасибо за замечание, я поправил текст заметки. Basilevs, благодарю за верное пояснение.

    ОтветитьУдалить
  5. Анонимный17.12.2010, 22:06

    0. Игрок делает первый выбор.
    1. Указал на приз. (вероятность 1\3)
    1.1. Ведущий открывает пустую.
    1.1.1.1. Игрок меняет первый выбор. | проигрывает (шанс 2\3)
    1.1.1.2. Игрок не меняет первый выбор. | выигрывает (шанс 1\3)
    1.1.2. Игрок делает второй выбор. | Ведущий не может ничего открыть.
    1.1.4.1. Игрок заново делает второй выбор. | ни на что не влияет (выигрыш 1\3)
    1.1.5. Конец.

    1.2. Ведущий не открывает пустую.
    1.2.1.1. Игрок заново делает первый выбор. | ни на что не влияет (выигрыш 1\3)
    1.2.2. Игрок делает второй выбор.
    1.2.3. Ведущий открывает пустую.
    1.2.4.1. Игрок меняет второй выбор. | проигрывает (шанс 1\3) выигрывает (шанс 2\3)
    1.2.4.2. Игрок не меняет второй выбор. | проигрывает (шанс 2\3) выигрывает (шанс 1\3)
    1.2.5. Конец.

    2. Указал на пустую. (вероятность 2\3)
    2.1. Ведущий открывает пустую.
    2.1.1.1. Игрок меняет первый выбор. | выигрывает (шанс 2\3)
    2.1.1.2. Игрок не меняет первый выбор. | проигрывает (шанс 1\3)
    2.1.2. Игрок делает второй выбор. | Ведущий не может ничего открыть.
    2.1.4. Игрок заново делает второй выбор. | ни на что не влияет (выигрыш 1\3)
    2.1.5. Конец.

    2.2. Ведущий не открывает пустую.
    2.2.1. Игрок заново делает первый выбор. | ни на что не влияет (выигрыш 1\3)
    2.2.2. Игрок делает второй выбор.
    2.2.3. Ведущий открывает пустую.
    2.2.4.1 Игрок меняет второй выбор. | проигрывает (шанс 1\3) выигрывает (шанс 2\3)
    2.2.4.2 Игрок не меняет второй выбор. | проигрывает (шанс 2\3) выигрывает (шанс 1\3)
    2.2.5. Конец.


    Что заметно?
    На второй поднос все сводится к двум ситуациям: либо базовая задача, либо повтор выбора без последствий:
    *Если ведущий открыл пустую на первом подносе, то на втором подносе игроку останется лишь шанс 1\3. Выгодно ведущему.
    *Если ведущий не открыл пустую на первом подносе, то на втором по базовой задаче игрок 100% поменяет выбор, обеспечив шанс 2\3. Выгодно игроку.

    Если ведущий откроет пустую на первом подносе, он повысит шанс выиграть на нем до 2\3. Выгодно Игроку.
    Если ведущий не откроет пустую на первом подносе, он оставит игрока с шансом выиграть 1\3. Выгодно ведущему.

    И главное: от игрока ситуация на втором подносе не зависит.

    Далее:
    т.к. пункты 1.2.x и 2.2.x соответствуют полностью, и они полностью описывают ситуацию с открытием шкатулки на втором подносе, то перепишем вариант с открытием шкатулки на первом подносе глазами игрока, для лучшего подсчета шанса выиграть.

    1. Делаем выбор на первом подносе. (Шанс угадать 1\3)
    2. Ведущий открыл шкутулку. | Все, на втором подносе шанс 1\3...
    3.1 Если...
    А что продолжать? Это опять базовая задача. Замена увеличит шанс до 2\3 независимо от целей ведущего.

    Итог?
    Независимо от действий ведущего, у игрока будет на одном из подносов базовая задача, а на другом - выбор 1 из 3 без всяких заморочек.
    Конечный результат зависит только от везения игрока.



    P.S.
    Если тут опять начнется спор, что можно считать понятным для всех кареголубоглазых началом отсчета дней переглядываний...
    Игрок изначально не может точно знать, поступает ли ведущий так от того, что он выбрал верную шкатулку, или же от того, что не верную. Потому все его теории о стократных вложениях мыслей изначально будут биться на две направления: с шансами 1\3 и 2\3. Результат не изментися.

    ОтветитьУдалить
  6. Анонимный18.12.2010, 1:12

    Если нет точки равновесия в классе чистых стратегий, нужно их рандомизировать. Теория игр рулит. :)

    ОтветитьУдалить
  7. Один подумал, что второй подумал:
    http://en.wikipedia.org/wiki/Traveler%27s_dilemma

    Честнее надо быть. :)

    ОтветитьУдалить
  8. Нету тут парадокса узника... обычная задачка из теории игр.

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

    ОтветитьУдалить
  9. Пусть p_1 - вероятность, с которой ведущий открывает коробку если игрок угадал. p_2 - если не угадал. p_3 - вероятность, с которой игрок меняет коробку в первом раунде если ведущий открыл коробку, p_4 - если не открыл. Тогда мат ожидание призов равняется
    1/3*(p_1*(1-p_3+1/3)+(1-p_1)*(1-p_4+2/3))+
    2/3*(p_2*(p_3+1/3)+(1-p_2)*(p_4/2+2/3)).
    Легко проверить что при p_1=1, p_2=1/2, p_3=5/6, p_4=1 обеим сторонам не имеет смысла менять стратегию. Мат. ожидание количества призов при этих параметрах равно 17/18.

    ОтветитьУдалить
  10. Анонимный24.12.2010, 16:32

    жаль, что в этом году вы не так активно пишете :)

    ОтветитьУдалить
  11. Предлагаю свое решение. (Мне не дали сюда вставить картинки с формулами, поэтому я расписал у себя: http://janatem.livejournal.com/69301.html )

    Задача, как оказалось, с неожиданным поворотом. ;)

    ОтветитьУдалить
  12. Вы решили другую задачу - игрок в вашем случае не имеет права сменить коробку, если Якубович не откроет шкатулку. Но в условии задачи это не так (хотя возможно автор имел в виду как раз ваш вариант). В конце концов Якубович должен предложить сменить выбор просто из вежливости ;).

    ОтветитьУдалить
  13. Что-то не понял. Если ведущий не открывает шкатулку, то предложение перевыбрать бесполезно для игрока (он всё равно имеет свою 1/3 приза). Поэтому считаем, что либо ведущий «открывает шкатулку и предлагает перевыбрать», либо «не открывает и не предлагает». Вариант «не открывает и предлагает» считаем бессмысленным.

    ОтветитьУдалить
  14. Не бесполезно ибо это дает новую информацию игроку. В моем случае Якубович не открывает шкатулку только если игрок не угадал. Значит смена позволит выиграть 1/2 приза вместо 0. Учитывая, что это происходит с вероятностью 2/3*1/2=1/3 мы и получаем 1/6 на которую мой ответ больше.

    ОтветитьУдалить
  15. Andrey, совершенно верно!
    Игрок, видя, что ведущий не стал открывать шкатулку, получает новые данные о данном наборе шкатулок и своём выборе. В этот момент ему вполне осмысленно предложить выбор. Иначе, зачем ему эту информацию давали?

    ОтветитьУдалить
  16. Всё равно не понял. Пусть ведущий решил не открывать шкатулку и размышляет над тем, предложить ли выбор. Тогда ему нет никакого резона связывать свое решение (предлагать ли выбор) с текущим раскладом (угадал ли игрок). Поскольку иначе он совершенно зазря выдаст игроку информацию о раскладе.

    Если эти простые соображения неубедительны, то их легко проверить вычислениями. А именно, добавить еще три параметра: (1), (2) предлагать ли выбор в случае если игрок указал на пустую/приз и (3) как действовать игроку, если ему предложили сменить выбор. (Все три применимы только если ведущий не открыл ничего.)

    ОтветитьУдалить
  17. Якубовичу запрещено не предлагать выбор. Работа такая, не эффективная.

    ОтветитьУдалить
  18. Andrey, пусть тогда всегда предлагает, но это всё равно дает ноль бит информации игроку.

    Илья, нельзя ли комментировать без капчи (кажется, ее размер монотонно зависит от размера комментария)? Я всё-таки не совсем анонимус, меня авторизует довольно известный сайт. ;)

    ОтветитьУдалить
  19. А, кажется, наконец, понял: ведущий _вначале_ решает открывать или не открывать шкатулку, а потом _всегда_ предлагает перевыбрать. Тогда действительно будет не три (как в моем решении), и не 6, а четыре параметра, как их описал Andrey. (Т.е. теперь мне остается убедится, что его решение верное. Кстати, там тоже минимакс совпал с максимином?)

    ОтветитьУдалить
  20. В играх с нулевой суммой по другому и не бывает.

    ОтветитьУдалить
  21. janatem, я пробовал убирать капчу. Увы, роботы сразу заваливают своей рекламой :(
    Похоже, мой блог попал в какие-то списки "популярных блогов, авторы которых не замечают рекламных сообщений" (хотя я всегда оперативно удалял такие комментарии). А может и всем это достаётся...

    Спасибо, что находите в себе силы прорываться через капчу. Я всё надеюсь, что у blogger.com со временем появится опция "капча только для комментов со ссылкой" (livejournal же научился специально обрабатывать такие случаи). А пока, увы, приходится терпеть капчу.

    ОтветитьУдалить
  22. Анонимный04.01.2011, 7:19

    Очень интересное обобщение задачи Монти-Холла, Илья.

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

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

    Задача игрока: Выяснить как ему действовать на первом этапе игры, чтобы максимально повысить математическое ожидание выигриша призов с учетом обеих этапов игры. Можно сказать, что свобода действий игрока тоже полностью сосредоточена на первом этапе, ибо оптимальные действия игрока на втором этапе предопределены - ему надо менять шкатулку в любом случае ибо обмен улучшает его шансы выиграть приз, если Якубович открыл пустую шкатулку (оригинальная задача Монти-Холла), или шансы просто не меняются, если Якубович не открыл никакую шкатулку.

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

    Из всего сказанного должно быть очевидно, что самая общая стратегия Якубовича может быть сведена к паре чисел (x, y): x - вероятность с которой Якубовичу следует открыть пустую шкатулку на первом этапе, если игрок держит шкатулку с призом; y - вероятность с которой Якубовичу следует открыть пустую шкатулку на первом этапе, если игрок держит пустую шкатулку.

    Подобным же образом, самая общая стратегия игрока тоже может быть сведена к паре чисел (a, b): a - вероятность с которой игроку следует менять шкатулку на первом этапе, если Якубович открыл пустую шкатулку; b - вероятность с которой игроку следует менять шкатулку на первом этапе, если Якубович решил не открывать шкатулку.

    Остальное, как говориться, дело техники.

    Вероятность проигрыша f и выигриша g приза игроком на первом этапе:

    f=(1/3)xa+(1/3)(1-x)b+(2/3)y(1-a)+(2/3)(1/2)(1-y)b+(2/3)(1-y)(1-b);

    g=1-f.

    Вероятность проигрыша F и выигриша G приза игроком на втором этапе:

    F=(1/3)[(1/3)(1-x)+(2/3)(1-y)]+(2/3)[(1/3)x+(2/3)y];

    G=1-F.

    Вероятность ниодного приза по результатам обеих этапов игры, P0:

    P0=fF

    Вероятность выигриша одного приза, P1:

    P1=fG+gF

    Вероятность выигриша двух призов, P2:

    P2=gG

    Математическое ожидание выигриша в обобщеной игре Монти-Холла:

    M(x,y;a,b)=0*P0+1*P1+2*P2=f(1-F)+(1-f)F+2(1-f)(1-F)=2-f-F=1-[(3a-3b+1)x-(6a-3b-2)y]/9.

    M(x,y;a,b) имеет только одну стационарную точку: (x,y;a,b)=(1,1/2;5/6,1), где minmax(M)=maxmin(M)=17/18.

    Иными словами, окончательный, пожалуй чуточку противоинтуитивный, ответ таков. Оптимальная стратегия для Якубовича: Если игрок держит шкатулку с призом на первом этапе - всегда открывай пустую шкатулку, в противном случае - открывай пустую шкатулку случайным образом с вероятностью 1/2.

    Оптимальная стратегия для игрока: Если Якубович открыл пустую шкатулку на первом этапе - поменяй шкатулку случайным образом с вероятностью 5/6, в противном случае - всегда меняй шкатулку.


    Артур Бараов, Хьюстон

    ОтветитьУдалить
  23. Артур, я рад вновь видеть Ваши комментарии :)
    С Наступившим!

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

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

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



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

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