Поиск выигрышной стратегии (если существует)

[Ort]

Ребята, нужны ваши мозги, своих не хватает. Задача практическая и весьма актуальная.

Имеются две планеты М и А. Жители планеты М хотят попать на планету А. Для переходя существует 8 разных портов, через которые можно официально пройти. На каждом из 8 портов есть своя собственная пропускная способность, варирующаяся от 200 (мах) до 25 (мин). Однако точного знания распределения квот по портам у жителей планеты М не имеется. Но зато известно общее количество квот по всем портам - 1000.

Житель планеты М может сделать 1 запрос на проход один раз в сутки. При этом имеет право выбрать любой из портов по своему желанию. По окончанию суток он либо получает разрешение на проход, либо может повториь попытку и сделать новый запрос на следующие сутки. И так до бесконечности.

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

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

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

[Ende]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Ende]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

[mihaild]

Ничего не понятно. Можете точно написать, по какому алгоритму выдается решение? Как растут шансы, что такое пропускная способность и т.д.?

[svv]

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

А если я после второго порта опять вернусь к первому порту, повышенные шансы быть выбранным в первый порт ещё сохранятся, или аннулируются?

И как именно повышаются шансы? Как повышение шансов зависит от числа предыдущих запросов? от порта?

Зависит ли от порта вероятность быть выбранным сразу?

В общем, куча вопросов. Достаточным описанием была бы программа, моделирующая ситуацию.

[ipgmvq]

Если упростить ситуцию, считая, что шансы быть выбранными не возрастают (из-за предыдущих обращений) и не уменьшаются (из-за нарастания количества желающих мигрировать), т.е. исходить из того, что каждый день вероятность пройти любой конкретный порт не меняется, и Вы не знаете, в каком порту какая вероятность, но точно знаете, что все они разные $\left( p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8 \right)$, то выбирая из двух (не единственных) вариантов: (1) выбрать с равной вероятностью один порт и всегда ходить в него, (2) случайно упорядочить порты и каждый раз (при неудаче) их ротировать именно в этом случайно выбранном в самом начале порядке, то я думаю, что второй вариант даст большее мат. ожидание успеха (кроме возможно нескольких первых дней, число которых будет зависеть от величины $p$).

[Ort]

Пропускная способность - это зафиксированное за каждым портом количество жителей, которые он пропускает на планету А за одни сутки. Например, если порт 1 имеет число 200, то этот порт пропускает на планету А 200 жителей в сутки. Характеристки портов могут выглядеть, например, так: порт 1 - 200 человек/сутки, порт 2 - 100 человек/сутки, порт 3- 25 человек/сутки, и т.д. Суммарно по 8 портам - 1000 человек/сутки. Важно, что зафиксированное за каждым портом количество разрешений остается всегда постоянным.

Как растут шансы? Точные детали распределения не известны. Но я покажу на примере.

Пусть у нас есть 20 000 жителей, которые хотят пройти через порты, они все участвуют в лотерее. Но эти 20 000 жителей начали играть не одновременно!
Пусть первые 2000 жителей (10%) уже участвовали 10 раз и выигрыш еще не получили, следующие 2000 участвовали 9 раз и тоже не получили выигрыш. Последние 2000 (самые молодые), участвовали только 1 раз и тоже не получили выигрыш. Все эти 20 000 жителей подают свои заявки на проход при наступлении новых суток.
Так вот, точно не известно как работает система, но мы знаем, что система учитывает как долго вы играли и отдает приоритет тем, кто играет дольше. Иными словами, "старые" 2000, которые уже играли 10 раз имеют шансов больше, чем 2000 "молодых", которые сыграли только 1 раз.
Но помимо приоритета для "старых", система также раздает какое-то количество выигрыщных проходов случайным образом. Иными словами, молодые тоже могут выиграть. К сожалению, не известна пропорция, т.е. сколько разрешений из имеющейся 1000 отдается тем кто дольше играет, а сколько на случайное распределение.

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

-- 18.05.2023, 15:12 --

-- 18.05.2023, 15:15 --

> Вопрос: быть выбранным в первый порт, или в любой?
В любой. По мере роста числа попыток шансы увеличиваются вне зависимости от порта. Система просто выберет вас если ви играете долго, и скажет идти в тот порт, который вы сами выбрали в последний раз.

> Т.е. если я теперь запрошу второй порт (впервые), шансы быть выбранным будут выше, чем если бы я не подавал запросы в первый порт?
Нет, ваши шансы в целом вырастут, но для обоих портов. Но штука в том, что квоты у портов разные и вы их не знаете. Более того, вы не знаете как много других жителей запросило конкретный порт в данные сутки.

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

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

> Зависит ли от порта вероятность быть выбранным сразу?
А вот это точно не известно, и очень хороший вопрос поскольку он заставляет подумать КАК система ДОЛЖНА была быть устроена (предполагая, что наша задача заключается в нахождении выиграшной стратегии). Поясню.

Пусть у нас есть порт 8 с малой пропускной способностью - 25 человек/сутки. Представим, что система никак не смотрит на порты (моя рабочая гипотеза) и она просто выбирает выигрышных участников, а потом они уже сами отправляются в выбранные ими портаы. Это будет работать если участников очень много, скажем, 70 000. В этом случае, даже при маленькой пропускной способности порта (скажем 25 человек/сутки) среди 70 000 всегда найдутся те, кто выберет порт 8. По сути системе не о чем беспокоиться, порта 8 гарантированно будет загружен. Но что если представить, что никто не выбрал порт 8. В этом случае он будет простаивать и система перестанет работать корректно. Таким образом, запуск алгоритма выиграша БЕЗ учета выбранных жителями портов может привести к нарушению работы всей программы!! Ведь можно представить гипотетическую ситуацию, когда ВСЕ выбрали только один порт.

Таким образом, можно построить предположение, что система ДОЛЖНА работать по другому. Она должна сначала сформировать очереди из жителей к КАЖДОМУ порту, а уже потом прогонят алогритмы выбора победителей. И если исходить, что это предположение верно, то можно попытаться построить стратегию на нем.

[svv]

Ort в сообщении #1594397 писал(а):

Но что если представить, что никто не выбрал порт 8. В этом случае он будет простаивать и система перестанет работать корректно. Таким образом, запуск алгоритма выиграша БЕЗ учета выбранных жителями портов может привести к нарушению работы всей программы!! Ведь можно представить гипотетическую ситуацию, когда ВСЕ выбрали только один порт.

Как я понял, любой выигравший, хоть "старый", хоть "молодой", проходит только через последний выбранный им порт. Так что в ситуации, когда никто не выбрал порт 8, этот порт всё равно будет простаивать. Да и что фатального в простое?

[Ort]

Да, вы правы. Что так, что так порт будет простаивать. Фатального в принципе ничего нет.
В целом хочется понять, как подобная система выбирала бы выигравших.

Пример.

Пусть есть 5 самых старых участников: A>B>C>D>E, где А самый старый, а E самый молодой.

Вариант 1 работы системы. Система скаждые сутки выстраивает отдельные очереди на каждый порт. У портов выстраиваются разные по длине очереди и порты имеют разную пропускную способность (квоты), поэтому вероятности у участников разных очередей разные. В каждой очереди имеется самый старый и самый новый участники, а по каждой из очередей запускатеся одинаковый алгоритм выигрыша. Если A,B,C,D идут на один порт, а E на другой, то тогда D оказывается в самой проигрышной ситуации, а E гарантированно выигрывает.

Вариант 2. Система не строит очереди, а запускает алгоритм по всем участникам и ищет 1000 выигравших. Иными словами здесь квота порта вообще не учитывается. Система находит выигравшего, смотрит порт, наращивает счетчик по данному порту, повторят процедуру. Настанет момент, когда найдется выигрывший, но у него окажется порт, который уже заполнен, т.е. его туда оправить нельзя. Тогда просто его пропускаем, ищем другого и так до тех пор пока квоты на всех портах не выберутся. Как то криво это выглядит, но может работать в принципе.

Первый вариант мне нравится больше и в нем как раз можно как то строить стратегию вроде.

-- 18.05.2023, 18:52 --

ipgmvq в сообщении #1594396 писал(а):

Если упростить ситуцию, считая, что шансы быть выбранными не возрастают (из-за предыдущих обращений) и не уменьшаются (из-за нарастания количества желающих мигрировать), т.е. исходить из того, что каждый день вероятность пройти любой конкретный порт не меняется, и Вы не знаете, в каком порту какая вероятность, но точно знаете, что все они разные $\left( p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8 \right)$, то выбирая из двух (не единственных) вариантов: (1) выбрать с равной вероятностью один порт и всегда ходить в него, (2) случайно упорядочить порты и каждый раз (при неудаче) их ротировать именно в этом случайно выбранном в самом начале порядке, то я думаю, что второй вариант даст большее мат. ожидание успеха (кроме возможно нескольких первых дней, число которых будет зависеть от величины $p$).

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

[Geen]

Ort в сообщении #1594378 писал(а):

Однако точного знания распределения квот по портам у жителей планеты М не имеется.

Жители обмениваются между собой информацией?

Допустим в какой-то день только один житель подал заявку, каковы его (и всех остальных) шансы пройти?

-- 19.05.2023, 11:33 --

Ort в сообщении #1594397 писал(а):

очень хороший вопрос поскольку он заставляет подумать КАК система ДОЛЖНА была быть устроена

Простите, Вы какую именно задачу решаете?

[EUgeneUS]

"Товарищи учёные, у меня в подвале раздаётся стук. Помогите разобраться".

При всех этих сложностях, выигрышных стратегий видится две:

1. Если у игроков нет информации, по которой можно установить\оценить пропускную способность портов.
Каждый день случайным образом выбирать порт. Вероятность выбрать каждый порт одинакова.
Если все будут придерживаться этой стратегии, то это придет к следующему:
а) составы и размеры когорт в каждом порту (в данный день) будут одинаковыми.
б) вероятность пройти в какой-то определенный день будет пропорциональна пропускной способности выбранного в этот день порта.
Но так как порты меняются, в "плохом" порту на залипаем.

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

[Ort]

Спасибо всем ответившим. Извиняюсь за оформление своих ответов, я пока не совсем разобрался как правильно делать ответы, поэтому отвечаю по старинке с использованием ">"

>Жители обмениваются между собой информацией?
В реальности, да. Некоторые жители сообщают о своем выигрыше и даже указывают порт. Но не понятно как эту информацию можно так уж сильно использовать.

>Допустим в какой-то день только один житель подал заявку, каковы его (и всех остальных) шансы пройти?
В этом случае он 100% проходит, так как доступно 1000 проходов, а он только один. Остальные гарантировано не проходят. Отсутствие заявки на проход равнозначно не участию в лотерее.

>Простите, Вы какую именно задачу решаете?
Я, как смог, описал акутальную задачу из реального мира на язык математической задачи. В принципе, я могу раскрыть карты о чем идет речь, если есть интерес. Но это форум математиков, при решение конкретной задачи из реального мира можно погрязуть в куче нюансов и деталей, а это делать не хочется. Важно то, что никто в деталях не знает как работает алгоритм выбора 1000 победителей. Это черный ящик. Известно только то, о чем я написал ранее. Сами жители наблюдают за работой системы извне и строят свои догадки. Если кто-то догадается об устройстве, он получит некоторые премущества. Например, он сможет хоть приблизительно рассчитать сколько суток надо голосовать, чтобы выиграть с вероятностью в 50%. Это дает ему возможность рассчитать свои ресурсы. Действительно, если это 2 месяца, то ресурсы одни, если 12 месяцев, то ресурсы нужны другие.

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

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

[Geen]

Ort в сообщении #1594458 писал(а):

В реальности, да. Некоторые жители сообщают о своем выигрыше и даже указывают порт. Но не понятно как эту информацию можно так уж сильно использовать.

Собрать статистику и вычислить пропускную способность каждого порта....

[Ort]

Geen в сообщении #1594462 писал(а):

Собрать статистику и вычислить пропускную способность каждого порта....

Известно, что один порт (самый большой) пропускает 200 человек. По остальным ничего не известно пока.
Штука в том, что жители разобщены, небольшие группы могут действовать совместно, но в целом нет кооперации, все конкурируют друг с другом, как и в реальном мире.

-- 19.05.2023, 07:47 --

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

[Geen]

Ort в сообщении #1594463 писал(а):

но в целом нет кооперации, все конкурируют друг с другом

Конкурировать или кооперировать определяется в оптимальной стратегии...

Сколько претендентов в сутки? меньше 1000, порядка 1000, много больше 1000?