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

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

Эта брошюра не про чуства и эмоции, а про логику

В случае если нужна не логика, всё вроде бы просто — либо торкает, либо нет

Но в реальности Вам почти никогда не скажут, что торкает

И возникнет вопрос: переходить к следующему варианту или продолжать с текущим?

Более глобально это вопрос о том: что лучше, создавать что-то новое или развивать уже существующее?

Мой лучший ответ: не важно, важны действия

Эта брошюра про игру, а не про выживание

Если вам нужно выживать, знакомьтесь оффлайн

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

Формально это означает, что локальный экстремум не всегда совпадает с глобальным

Применительно к сервису: топ в боте может не быть топом в жизни, а также топ в боте может быть топом в жизни, но не быть топом во всем множестве людей, например, из МГУ — то есть не только в множестве пользователей бота

Часть вторая — 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)
Out[2]:
0.09999999999999998
In [3]:
prob(100, 2, 10)
Out[3]:
0.19090909090909092
In [4]:
prob(99, 0, 10)
Out[4]:
0.0

Определим функцию 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)
820.3283794374119 73

О более простых стратегиях

Предложенная стратегия может быть интуитивно не очевидна

Кроме того похоже на правду, что сложные модели не работают никогда, а простые работают в лучшем случае в среднем — шансы на развод положительно коррелирует со знаком разности количества ссор и секса — если знак положительный шансов на развод больше чем если знак отрицательный

Более простая стратегия

Задача та жа — за минимальное время получить максимально топового кандидата

Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе

Для применении этой стратегии нужно определить место кандидата в топе

О том как это сделать — в следующей брошюре:)

Менее простая стратегия

Минимизируется произведение места в топе на количество конкурентов

О том, в каких случаях уместно использовать данную стратегию, также в следующей брошюре;)

Можно связать предыдущую стратегию с данной:

Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе на количество конкурентов

Итоги

В тексте данной брошюры можно встретить вопросы и отсылки к следующей брошюре: "О воронке знакомств"

Ниже они собраны вместе в виде тем, которые в ней затронуты:

  • О балансе между средневековыми принцессами и пользователями Тиндера

  • Об ограничениях для некоторых категорий пользователей нашего сервиса

  • О проверки принадлежности к сообществу МГУ при регистрации в нашем сервисе

  • О том, зачем пользоваться нашим сервисом

  • Об определении места кандидата в топе

  • О контексте применения стратегий

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