Эта брошюра не про чуства и эмоции, а про логику
В случае если нужна не логика, всё вроде бы просто — либо торкает, либо нет
Но в реальности Вам почти никогда не скажут, что торкает
И возникнет вопрос: переходить к следующему варианту или продолжать с текущим?
Более глобально это вопрос о том: что лучше, создавать что-то новое или развивать уже существующее?
Мой лучший ответ: не важно, важны действия
Эта брошюра про игру, а не про выживание
Если вам нужно выживать, знакомьтесь оффлайн
Более того, зачастую самые продвинутые выживальщики не знакомятся онлайн — их там просто нет
Формально это означает, что локальный экстремум не всегда совпадает с глобальным
Применительно к сервису: топ в боте может не быть топом в жизни, а также топ в боте может быть топом в жизни, но не быть топом во всем множестве людей, например, из МГУ — то есть не только в множестве пользователей бота
Пусть у Вас есть выбор из двух альтернатив и нужно принять решение что-то делать
Формально это означает, что новая информация появляется только в результате Ваших действий
Возможны следующие стратегии
Двукритериальная оптимизация
Нужно строить Парето-фронт(https://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BA%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F)
Очень сложно, не рекомендуются без глубокого понимания предметной области
Расстановка приоритетов
Либо первая альтернатива важнее второй, либо наоборот
Проблема классическая: невозможность выбора либо в силу недостатка информации, либо в силу несравнимости альтернатив
Также возможна неловкая ситуация, связанная с тупиком: чтобы принять решение об одной альтернативе, нужно принять решение по другой и наоборот
Общий зачёт
Очень у нас любят эту стратегию
Например при подготовке к Олимпиаде бюджет вкладывается в какой-то один вид спорт, по нему получается золотая медаль и затем делается отчёт о величии нашего спорта
Но в общем зачете, по совокупному числу золотых медалей, результат плачевный
Более близкий пример — рейтинг ВУЗов
По какому-то одному направлению, например, числу Высших школ, мы в топе
А по сумме мест не в топе
Здесь опять же есть проблема неполноты
Например, если это внутренние соревнования или рейтинг среди ВУЗов по стране
В этом случае, поскольку все применяют одну и ту же стратегию, результаты даже получаются реалистичными — такое вот любопытное наложение ошибок, приводящее к реалистичной итоговой картине
По факту это свидетельствует об отсутствии длинного горизонта планирования — то есть нет готовности инвестировать, отказавшись от мгновенных, но локальных результатов, ради глобальных, но отдалённых
Задача была придумана М. Гарднером в 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/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BC%D0%B0%D1%80%D1%8C%D1%8F%D0%B6%D0%B5
За решение этой задаче в 2012 году была присвоена Нобелевская премия по экономике
Отличие данной задачи от предыдущей в том, что кроме ответов "да" и "следующий" можно отвечать "может быть"
Разница в ограничениях задачи в том, что прошлые решения можно менять — "может быть" может измениться как в сторону "да", так и в сторону "следующий". Судя по всему "да" и "следующий" меняться не могут, а игра заканчивается, когда все "может быть" разрешены
Данная задача уже ближе к реальности, но к сожалению для её реализации нужно вводить понятия состояния, итерации, а также строить конечный автомат — пока мы до этого не дошли
Мы решили пока остановиться на реализации задачи о разборчивой невесте, но несколько осовременить её, в частности за счёт некоторых свойств Тиндера
Таким образом наш сервис пытается найти баланс между средневековыми принцессами и пользователями Тиндера
В некотором смысле мы делаем Тиндер для умных современных принцесс:)
Мы используем комбинацию свайповой и анкетной моделей
То есть пользователи региструются, отвечают на ряд вопросов и загружают своё фото
После этого созданный профиль видят другие пользователи и ставят "да" или "следующий"
Пользователю также становятся доступны профили других пользователей
Если два пользователя поставили друг другу "да" — возникает матч
В результате матча пользователи получают доступ к контактам друг друга
Сервис реализован в виде Телеграм бота
Регистрация производится через приложение ВК
Отличия от канонической принцессы
В случае средневековой принцессы считается, что все принцы по умолчанию поставили ей лайк
В современном мире данное допущение неверно(первое отличие)
Также каноническая принцесса из задачи готова принимать решения в условиях недостатка информации
Однако если оставить ограничения на число лайков(один в базовом варианте) и запретить менять прошлые решения, то современные принцессы могут проявить изобретательность и сказать всем принцам "следующий", а затем найти понравившихся через сторонние сервисы
Нам известно о таких сервисах, мы готовим одному из них предложение о партнёрстве
Также мы в дальнейшем хотим коммерциализовать наши будущие сервисы или ввести внутренние покупки в существующие
Но мы хотим сохранить своих пользователей, чтобы они возвращались к нам и пользовались нашими сервисами, поэтому ограничений на число лайков нет(второе отличие) и прошлые решения менять можно(третье отличие)
Итого три отличия
Отличия от Тиндера
—нет придурков
Извращенцы и содержанки это настоящий бич сервисов знакомств
Дополнение: однако извращенцы находят друг друга и никому не мешают, а содержанки привлекают пользователей, которые являются их ЦА. Таким образом, ограничивать регистрацию для данных категорий пользователей смысла нет. Однако некоторые ограничения всё же должны быть — о них в следующей брошюре!
—физическая локальность
Наши пользователи находятся физически недалеко друг от друга
Дополнение: это тоже может быть не всегда полезно. Содержательным примером будет мужчина, который ищет любовницу вдали от дома. Предположительно люди также чаще пользуются сервисами знакомств за границей, а не у себя. Это говорит о том, что фактор локальности очень важен, но иногда в обратном смысле!
Понять, насколько это существенно, можно на примере Pure — там удалённость является основой ранжирования поисковой выдачи
Кстати, почитайте пользовательское соглашение Pure — это шедевр https://ru.pure.dating/terms
Эти два свойства достигаются за счет проверки принадлежности к сообществу МГУ при регистрации
—количество конкурентов
Когда пользователь ставит кому-то лайк, ему может быть интересно, а сколько ещё лайков получил этот кто-то — в нашем сервисе это называется конкуренцией первого рода
После этого пользователь может от этого кого-то получить взаимный лайк и ему может стать интересно, а сколько ещё взаимных лайков у этого кого-то — это конкуренция второго рода
Мы показываем только количество конкурентов второго рода
—уведомление о разрыве матча
Пользователь получает уведомление не только о появлении матча, но и о пропадании матча
Итого четыре отличия
О лайках и матчах
Важными представляются следующие моменты:
—Пользователю не стоит знать, сколько лайков ему поставили
Если много — можно зазнаться
Если мало — расстроиться
Поэтому мы не показываем число лайков в явном виде
Также мы не показываем их и в неявном виде — через конкурентов первого рода
Так, находчивая девушка может попросить поставить ей лайк лучшего друга детства и затем спросить, сколько у него конкурентов первого рода
Поэтому мы показываем только количество конкурентов второго рода
—Только пользователю стоит знать, сколько лайков он поставил
Из информации о конкурентах любого рода не следует сколько лайков поставил пользователь
Например, девушка может поставить лайк тому, кто ей лайк не поставил:(
Таким образом только сам пользователь знает количество своих лайков
Стоит понимать, что матч это не лайк
Есть такая проблема, когда у одного пользователя несколько диалогов в один момент времени и это неприятно другому пользователю, который видит число матчей
Рассматривалась возможность ввести ограничение на число доступных матчей — раз уж нет ограничения на число доступных лайков
Например, при ограничении на один матч, матчи показываются по одному и новый матч становится доступен только при разрыве предыдущего
Но было решено не вводить данное ограничение из-за интересного следствия
Интересное следствие
Возможность поставить более одного лайка, изменять прошлые решения и уведомления о разрыве матча порождают интересную дилемму
Пусть есть два очень популярных человека
Они поставили друг другу лайк и увидели, что у каждого из них по 20 матчей
Им не хочется ставить друг друга в неудобное положение и они начинают снимать матчи с других пользователей
В итоге 40 пользователей получают уведомления о разрыве матчей, а эти двое видят, на что они пошли ради общения друг с другом
Дилемма в том, сколькими матчами пользователи готовы пожертвовать ради одного, но перспективного матча
В Тиндер люди идут ради общения в чатах
Если бы это было не так, Pure бы не появился:)
О том, зачем пользоваться нашим сервисом, в следующей брошюре: "О воронке знакомств"
Итак, мы подошли к самой важной части
Задача похожа на задачу о разборчивой невесте
Но нужно не просто максимизировать шансы получить одного из топ-t принцев с учетом его места в топе
Нужно сделать это за наименьшее время
мы будем использовать комбинаторный, а не вероятностный подход
В нашем сервисе время меряется как количество просмотренных анкет
Временем на изменение предыдущих решений мы прененебрегаем
Представляется, что время на первое решение >> времени на любое последующее решение
Пусть у нас 1000 пользователей
Пусть из них в топе находятся 10% — то есть 100
Таким образом
n = 1000
t = 100
Вероятность того, что среди первых k элементов перестановки из [1, n] есть числа из [n - t, n] это
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
prob(100, 1, 10)
0.09999999999999998
prob(100, 2, 10)
0.19090909090909092
prob(99, 0, 10)
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 максимально
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, для которого следующая величина будет максимальна — это наше счастье — оно зависит от времени, которое мы потратили на просмотр анкет — мы пытаемся минимизировать это время
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
О более простых стратегиях
Предложенная стратегия может быть интуитивно не очевидна
Кроме того похоже на правду, что сложные модели не работают никогда, а простые работают в лучшем случае в среднем — шансы на развод положительно коррелирует со знаком разности количества ссор и секса — если знак положительный шансов на развод больше чем если знак отрицательный
Более простая стратегия
Задача та жа — за минимальное время получить максимально топового кандидата
Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе
Для применении этой стратегии нужно определить место кандидата в топе
О том как это сделать — в следующей брошюре:)
Менее простая стратегия
Минимизируется произведение места в топе на количество конкурентов
О том, в каких случаях уместно использовать данную стратегию, также в следующей брошюре;)
Можно связать предыдущую стратегию с данной:
Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе на количество конкурентов
В тексте данной брошюры можно встретить вопросы и отсылки к следующей брошюре: "О воронке знакомств"
Ниже они собраны вместе в виде тем, которые в ней затронуты:
О балансе между средневековыми принцессами и пользователями Тиндера
Об ограничениях для некоторых категорий пользователей нашего сервиса
О проверки принадлежности к сообществу МГУ при регистрации в нашем сервисе
О том, зачем пользоваться нашим сервисом
Об определении места кандидата в топе
О контексте применения стратегий
Напоследок небольшой спойлер — кажется, что нужно искать не тех, кто есть в нашем сервисе, а тех, кого в нём нет