#!/usr/bin/env python
# coding: utf-8

# # Брошюра первая — субоптимальные стратегии знакомств через бота

# ##  Часть первая —  общие положения

# Эта брошюра не про чуства и эмоции, а про логику
# 
# В случае если нужна не логика, всё вроде бы просто — либо торкает, либо нет
# 
# Но в реальности Вам почти никогда не скажут, что торкает
# 
# И возникнет вопрос: переходить к следующему варианту или продолжать с текущим?
# 
# Более глобально это вопрос о том: что лучше, создавать что-то новое или развивать уже существующее?
# 
# Мой лучший ответ: не важно, важны действия

# Эта брошюра про игру, а не про выживание
# 
# Если вам нужно выживать, знакомьтесь оффлайн
# 
# Более того, зачастую самые продвинутые выживальщики не знакомятся онлайн — их там просто нет
# 
# Формально это означает, что локальный экстремум не всегда совпадает с глобальным
# 
# Применительно к сервису: топ в боте может не быть топом в жизни, а также топ в боте может быть топом в жизни, но не быть топом во всем множестве людей, например, из МГУ — то есть не только в множестве пользователей бота 

# ## Часть вторая — 3 стратегии

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

# ### Стратегия первая — два зайца

# Двукритериальная оптимизация
# 
# Нужно строить Парето-фронт(https://ru.wikipedia.org/wiki/Многокритериальная_оптимизация)
# 
# Очень сложно, не рекомендуются без глубокого понимания предметной области

# ### Стратегия вторая — один осёл

# Расстановка приоритетов
# 
# Либо первая альтернатива важнее второй, либо наоборот
# 
# Проблема классическая: невозможность выбора либо в силу недостатка информации, либо в силу несравнимости альтернатив
# 
# Также возможна неловкая ситуация, связанная с тупиком: чтобы принять решение об одной альтернативе, нужно принять решение по другой и наоборот

# ### Стратегия третья — много оленей

# Общий зачёт
# 
# Очень у нас любят эту стратегию
# 
# Например при подготовке к Олимпиаде бюджет вкладывается в какой-то один вид спорт, по нему получается золотая медаль и затем делается отчёт о величии нашего спорта
# 
# Но в общем зачете, по совокупному числу золотых медалей, результат плачевный
# 
# Более близкий пример — рейтинг ВУЗов
# 
# По какому-то одному направлению, например, числу Высших школ, мы в топе
# 
# А по сумме мест не в топе

# Здесь опять же есть проблема неполноты
# 
# Например, если это внутренние соревнования или рейтинг среди ВУЗов по стране
# 
# В этом случае, поскольку все применяют одну и ту же стратегию, результаты даже получаются реалистичными — такое вот любопытное наложение ошибок, приводящее к реалистичной итоговой картине
# 
# По факту это свидетельствует об отсутствии длинного горизонта планирования — то есть нет готовности инвестировать, отказавшись от мгновенных, но локальных результатов, ради глобальных, но отдалённых

# ## Часть третья — задача о разборчивой невесте

# Задача была придумана М. Гарднером в 60х и решена Е. Дынкиным в 1965 
# 
# Брошюра С. Гусейна-Заде с решением — https://www.mccme.ru/free-books/mmmf-lectures/book.25.pdf
# 
# В классической постановке к принцессе по одному приходят принцы
# 
# Когда принц приходит, она общается с ним и говорит либо "да", либо "следующий"
# 
# Если принц услышал "следующий" — он обижается, уходит и больше никогда не возвращается
# 
# Если принц услышал "да" — он берёт принцессу в жены и они живут вместе всю жизнь
# 
# Если принцы закончились — принцесса идёт в монастырь
# 
# Задача принцессы — максимизировать свои шансы сказать "да" лучшему принцу
# 
# Возникает вопрос: по какой стратегии действовать принцессе, чтобы минимизировать свои шансы уйти в монастырь или выбрать не лучшего принца?

# В сухом остатке у средневековой принцессы нет ограничений по времени — удачно выйти замуж это цель её жизни
# 
# Но у неё есть ограничения по качеству — она хочет выйти замуж за лучшего принца

# Ограничения задачи:
# 
# —известно число принцов
# 
# —есть общий порядок: то есть любые два принца сравнимы( и все сравнения непротиворечивы)
# 
# —"да" можно сказать только один раз
# 
# —нельзя менять прошлые решения

# Решение:
# 
# Средневековая принцесса вынуждена принимать решение в условиях недостатка информации, потому что у неё нет других источников сведений, кроме как беседы с принцами-кандидатами
# 
# Содержательно решение состоит из двух частей — этап разведки(exploration) и применения(exploitation)
# 
# По Гусейну-Заде нужно пропустить первых n/e принцев и затем сказать "да" первому, кто лучше всех предыдущих:
# "При этом вероятность получить в конце концов самого лучшего жениха из всех n претендентов равна примерно 0,368."
# 
# Это и есть знаменитое правило 37%
# 
# Вроде бы существует ряд уточнений, чтобы принцесса не осталась одна — в любом случае всегда можно сказать "да" последнему:)
# 
# Нам же будет интересно, что делать, если ограничение по качеству более слабое — то есть принцессу устроит не самый лучший, а любой из топ-t
# 
# Также есть вариант, который выглядит более справедливым — это вариант, когда её устроит любой из топ-t, но она будет тем счастливее, чем ближе он к топ-1
# 
# Для случая, когда принцесса будет одинаково счастлива с любым из топ-2 принцев решение следующее:
# "Таким образом, при большом количестве претендентов n и при m=2 оптимальная стратегия принцессы состоит в следующем. Она должна пропустить приблизительно 34,7% претендентов, не давая согласия на брак, из следующих приблизительно 32% (вплоть до 66,7% всех претендентов) давать согласие на брак только тому, кто лучше всех предыдущих, а из оставшихся 33,3% претендентов соглашаться и на второго по качеству среди уже прошедших. При этом вероятность удачного выбора (опять-таки при большом n, т. е. при n→∞) оказывается равной приблизительно 0,574. Таким образом, в этом случае шансы принцессы на удачный выбор (при оптимальной стратегии) больше 50%."

# Далее мы наконец готовимся перейти к описанию своего сервиса
# 
# Мы используем ограничение по качеству на топ-t, но с учетом места в этом топ-t
# 
# Возникает интересный вопрос: как мы определяем счастье в своём сервисе?:)
# 
# Также мы вводим ограничение по времени, то есть наша принцесса хочет получить наилучшего принца за наименьшее время

# ##  Часть между третьей и четвертой — задача о марьяже

# Более сложной задачей является задача о марьяже — https://ru.wikipedia.org/wiki/Задача_о_марьяже
# 
# За решение этой задаче в 2012 году была присвоена Нобелевская премия по экономике
# 
# Отличие данной задачи от предыдущей в том, что кроме ответов "да" и "следующий" можно отвечать "может быть"
# 
# Разница в ограничениях задачи в том, что прошлые решения можно менять — "может быть" может измениться как в сторону "да", так и в сторону "следующий". Судя по всему "да" и "следующий" меняться не могут, а игра заканчивается, когда все "может быть" разрешены 
# 
# Данная задача уже ближе к реальности, но к сожалению для её реализации нужно вводить понятия состояния, итерации, а также строить конечный автомат — пока мы до этого не дошли
# 
# Мы решили пока остановиться на реализации задачи о разборчивой невесте, но несколько осовременить её, в частности за счёт некоторых свойств Тиндера 
# 
# Таким образом наш сервис пытается найти баланс между средневековыми принцессами и пользователями Тиндера
# 
# В некотором смысле мы делаем Тиндер для умных современных принцесс:)

# ## Часть четвёртая — о сервисе

# Мы используем комбинацию свайповой и анкетной моделей
# 
# То есть пользователи региструются, отвечают на ряд вопросов и загружают своё фото
# 
# После этого созданный профиль видят другие пользователи и ставят "да" или "следующий"
# 
# Пользователю также становятся доступны профили других пользователей
# 
# Если два пользователя поставили друг другу "да" — возникает матч
# 
# В результате матча пользователи получают доступ к контактам друг друга
# 
# Сервис реализован в виде Телеграм бота
# 
# Регистрация производится через приложение ВК

# **Отличия от канонической принцессы**
# 
# В случае средневековой принцессы считается, что все принцы по умолчанию поставили ей лайк
# 
# В современном мире данное допущение неверно(*первое отличие*)
# 
# Также каноническая принцесса из задачи готова принимать решения в условиях недостатка информации
# 
# Однако если оставить ограничения на число лайков(один в базовом варианте) и запретить менять прошлые решения, то современные принцессы могут проявить изобретательность и сказать всем принцам "следующий", а затем найти понравившихся через сторонние сервисы
# 
# Нам известно о таких сервисах, мы готовим одному из них предложение о партнёрстве
# 
# Также мы в дальнейшем хотим коммерциализовать наши будущие сервисы или ввести внутренние покупки в существующие
# 
# Но мы хотим сохранить своих пользователей, чтобы они возвращались к нам и пользовались нашими сервисами, поэтому  ограничений на число лайков нет(*второе отличие*) и прошлые решения менять можно(*третье отличие*)
# 
# Итого три отличия

# **Отличия от Тиндера**
# 
# —нет придурков
# 
# Извращенцы и содержанки это настоящий бич сервисов знакомств
# 
# >Дополнение: однако извращенцы находят друг друга и никому не мешают, а содержанки привлекают пользователей, которые являются их ЦА. Таким образом, ограничивать регистрацию для данных категорий пользователей смысла нет. Однако некоторые ограничения всё же должны быть — о них в следующей брошюре!
# 
# —физическая локальность
# 
# Наши пользователи находятся физически недалеко друг от друга
# 
# >Дополнение: это тоже может быть не всегда полезно. Содержательным примером будет мужчина, который ищет любовницу вдали от дома. Предположительно люди также чаще пользуются сервисами знакомств за границей, а не у себя. Это говорит о том, что фактор локальности очень важен, но иногда в обратном смысле!
# 
# Понять, насколько это существенно, можно на примере Pure — там удалённость является основой ранжирования поисковой выдачи
# 
# Кстати, почитайте пользовательское соглашение Pure — это шедевр https://ru.pure.dating/terms
# 
# >Эти два свойства достигаются за счет проверки принадлежности к сообществу МГУ при регистрации
# 
# —количество конкурентов
# 
# Когда пользователь ставит кому-то лайк, ему может быть интересно, а сколько ещё лайков получил этот кто-то — в нашем сервисе это называется конкуренцией первого рода
# 
# После этого пользователь может от этого кого-то получить взаимный лайк и ему может стать интересно, а сколько ещё взаимных лайков у этого кого-то — это конкуренция второго рода
# 
# >Мы показываем только количество конкурентов второго рода
# 
# —уведомление о разрыве матча
# 
# Пользователь получает уведомление не только о появлении матча, но и о пропадании матча
# 
# Итого четыре отличия

# **О лайках и матчах**
# 
# Важными представляются следующие моменты:
# 
# —Пользователю не стоит знать, сколько лайков ему поставили
# 
# Если много — можно зазнаться
# 
# Если мало — расстроиться
# 
# Поэтому мы не показываем число лайков в явном виде
# 
# Также мы не показываем их и в неявном виде — через конкурентов первого рода
# 
# Так, находчивая девушка может попросить поставить ей лайк лучшего друга детства и затем спросить, сколько у него конкурентов первого рода
# 
# Поэтому мы показываем только количество конкурентов второго рода
# 
# —Только пользователю стоит знать, сколько лайков он поставил
# 
# Из информации о конкурентах любого рода не следует сколько лайков поставил пользователь 
# 
# Например, девушка может поставить лайк тому, кто ей лайк не поставил:(
# 
# Таким образом только сам пользователь знает количество своих лайков
# 
# >Стоит понимать, что матч это не лайк
# 
# Есть такая проблема, когда у одного пользователя несколько диалогов в один момент времени и это неприятно другому пользователю, который видит число матчей
# 
# Рассматривалась возможность ввести ограничение на число доступных матчей — раз уж нет ограничения на число доступных лайков
# 
# Например, при ограничении на один матч, матчи показываются по одному и новый матч становится доступен только при разрыве предыдущего
# 
# Но было решено не вводить данное ограничение из-за интересного следствия

# **Интересное следствие**
# 
# Возможность поставить более одного лайка, изменять прошлые решения и уведомления о разрыве матча порождают интересную дилемму
# 
# Пусть есть два очень популярных человека
# 
# Они поставили друг другу лайк и увидели, что у каждого из них по 20 матчей
# 
# Им не хочется ставить друг друга в неудобное положение и они начинают снимать матчи с других пользователей
# 
# В итоге 40 пользователей получают уведомления о разрыве матчей, а эти двое видят, на что они пошли ради общения друг с другом
# 
# Дилемма в том, сколькими матчами пользователи готовы пожертвовать ради одного, но перспективного матча

# ## Часть между четвёртой и пятой — следующая брошюра

# В Тиндер люди идут ради общения в чатах
# 
# Если бы это было не так, Pure бы не появился:)
# 
# О том, зачем пользоваться нашим сервисом, в следующей брошюре:
# "О воронке знакомств"

# ## Часть пятая — современная принцесса

# Итак, мы подошли к самой важной части
# 
# Задача похожа на задачу о разборчивой невесте
# 
# Но нужно не просто максимизировать шансы получить одного из топ-t принцев с учетом его места в  топе
# 
# Нужно сделать это за наименьшее время
# 
# >мы будем использовать комбинаторный, а не вероятностный подход

# В нашем сервисе время меряется как количество просмотренных анкет
# 
# Временем на изменение предыдущих решений мы прененебрегаем
# 
# Представляется, что время на первое решение >> времени на любое последующее решение

# Пусть у нас 1000 пользователей
# 
# Пусть из них в топе находятся 10% — то есть 100
# 
# Таким образом

# In[6]:


n = 1000

t = 100


# Вероятность того, что среди первых k элементов перестановки из [1, n] есть числа из [n - t, n] это

# In[1]:


from math import factorial

def prob(n, k, t):
    #return 1 - factorial(n-k)*factorial(n-t)/(factorial(n)*factorial(n-t-k))

    i = n-t-k
    num = 1
    while(i != n - t):
        i = i + 1
        num = num * i
    #print(num)
    
    i = n-k
    den = 1
    while(i != n):
        i = i + 1
        den = den * i
    #print(den)
    
    return 1 - num/den
    
#change n-t-k by n-k-t
#if will swap t and k
#now solute not to swap


# In[2]:


prob(100, 1, 10)


# In[3]:


prob(100, 2, 10)


# In[4]:


prob(99, 0, 10)


# Определим функцию P_1 для этапа разведки — exploration

# k1 = tr
# 
# P_1 = prob(n, k1, t)

# Определим функцию P_2 для этапа применения — exploitation

# k2 = k - tr
# 
# P_2 = prob(n - tr, k2, t)

# Теперь определим функцию, которую мы максимизируем

# P_12 = P_1 * P_2

# Важно понимать, что максимизируется именно произведение P_1 и P_2, а не, например, P_2 при условии достижения P_1 некоторого порога

# Итого для каждого заданного k мы можем найти такое tr, при котором P_12 максимально

# In[8]:


max_P_12 = -1
max_tr = -1
k_with_max_tr=[-1]*(n + 1)
k_P_12_with_max_tr = [-1]*(n + 1)

for k in range(1, n + 1):
    #if k % 100 == 0:
    #    print(k)
    for tr in range(1, k + 1):
        k1 = tr
        P_1 = prob(n, k1, t)
        k2 = k - tr
        P_2 = prob(n - tr, k2, t)
        P_12 = P_1 * P_2
        if P_12 > max_P_12:
            max_P_12 = P_12
            max_tr = tr
    k_with_max_tr[k] = max_tr
    k_P_12_with_max_tr[k] = max_P_12
    #print(k, max_tr, max_P_12)
    #uncomment line above to see the results


# Далее нам остался всего один шаг: найти такое k, для которого следующая величина будет максимальна — это наше счастье — оно зависит от времени, которое мы потратили на просмотр анкет — мы пытаемся минимизировать это время

# In[9]:


max_pleasure = -1
max_pleasure_k = -1

for k in range(1, n + 1 - t):
    pleasure = k_P_12_with_max_tr[k] * (n - k) - k
    if pleasure > max_pleasure:
        max_pleasure = pleasure
        max_pleasure_k = k

print(max_pleasure, max_pleasure_k)


# **О более простых стратегиях**
# 
# Предложенная стратегия может быть интуитивно не очевидна
# 
# Кроме того похоже на правду, что сложные модели не работают никогда, а простые работают в лучшем случае в среднем — шансы на развод положительно коррелирует со знаком разности количества ссор и секса — если знак положительный шансов на развод больше чем если знак отрицательный
# 
# **Более простая стратегия**
# 
# Задача та жа — за минимальное время получить максимально топового кандидата
# 
# Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе
# 
# Для применении этой стратегии нужно определить место кандидата в топе
# 
# О том как это сделать — в следующей брошюре:)
# 
# **Менее простая стратегия**
# 
# Минимизируется произведение места в топе на количество конкурентов
# 
# О том, в каких случаях уместно использовать данную стратегию, также в следующей брошюре;)
# 
# Можно связать предыдущую стратегию с данной:
# 
# Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе на количество конкурентов

# ## Итоги

# В тексте данной брошюры можно встретить вопросы и отсылки к следующей брошюре: "О воронке знакомств"
# 
# Ниже они собраны вместе в виде тем, которые в ней затронуты:
# 
# 
# * О балансе между средневековыми принцессами и пользователями Тиндера
# 
# * Об ограничениях для некоторых категорий пользователей нашего сервиса
# 
# * О проверки принадлежности к сообществу МГУ при регистрации в нашем сервисе
# 
# * О том, зачем пользоваться нашим сервисом
# 
# * Об определении места кандидата в топе
# 
# * О контексте применения стратегий

# Напоследок небольшой спойлер — кажется, что нужно искать не тех, кто есть в нашем сервисе, а тех, кого в нём нет