{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Брошюра первая — субоптимальные стратегии знакомств через бота" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть первая — общие положения" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Эта брошюра не про чуства и эмоции, а про логику\n", "\n", "В случае если нужна не логика, всё вроде бы просто — либо торкает, либо нет\n", "\n", "Но в реальности Вам почти никогда не скажут, что торкает\n", "\n", "И возникнет вопрос: переходить к следующему варианту или продолжать с текущим?\n", "\n", "Более глобально это вопрос о том: что лучше, создавать что-то новое или развивать уже существующее?\n", "\n", "Мой лучший ответ: не важно, важны действия" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Эта брошюра про игру, а не про выживание\n", "\n", "Если вам нужно выживать, знакомьтесь оффлайн\n", "\n", "Более того, зачастую самые продвинутые выживальщики не знакомятся онлайн — их там просто нет\n", "\n", "Формально это означает, что локальный экстремум не всегда совпадает с глобальным\n", "\n", "Применительно к сервису: топ в боте может не быть топом в жизни, а также топ в боте может быть топом в жизни, но не быть топом во всем множестве людей, например, из МГУ — то есть не только в множестве пользователей бота " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть вторая — 3 стратегии" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Пусть у Вас есть выбор из двух альтернатив и нужно принять решение что-то делать\n", "\n", "Формально это означает, что новая информация появляется только в результате Ваших действий\n", "\n", "Возможны следующие стратегии" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Стратегия первая — два зайца" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Двукритериальная оптимизация\n", "\n", "Нужно строить Парето-фронт(https://ru.wikipedia.org/wiki/Многокритериальная_оптимизация)\n", "\n", "Очень сложно, не рекомендуются без глубокого понимания предметной области" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Стратегия вторая — один осёл" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Расстановка приоритетов\n", "\n", "Либо первая альтернатива важнее второй, либо наоборот\n", "\n", "Проблема классическая: невозможность выбора либо в силу недостатка информации, либо в силу несравнимости альтернатив\n", "\n", "Также возможна неловкая ситуация, связанная с тупиком: чтобы принять решение об одной альтернативе, нужно принять решение по другой и наоборот" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Стратегия третья — много оленей" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Общий зачёт\n", "\n", "Очень у нас любят эту стратегию\n", "\n", "Например при подготовке к Олимпиаде бюджет вкладывается в какой-то один вид спорт, по нему получается золотая медаль и затем делается отчёт о величии нашего спорта\n", "\n", "Но в общем зачете, по совокупному числу золотых медалей, результат плачевный\n", "\n", "Более близкий пример — рейтинг ВУЗов\n", "\n", "По какому-то одному направлению, например, числу Высших школ, мы в топе\n", "\n", "А по сумме мест не в топе" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Здесь опять же есть проблема неполноты\n", "\n", "Например, если это внутренние соревнования или рейтинг среди ВУЗов по стране\n", "\n", "В этом случае, поскольку все применяют одну и ту же стратегию, результаты даже получаются реалистичными — такое вот любопытное наложение ошибок, приводящее к реалистичной итоговой картине\n", "\n", "По факту это свидетельствует об отсутствии длинного горизонта планирования — то есть нет готовности инвестировать, отказавшись от мгновенных, но локальных результатов, ради глобальных, но отдалённых" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть третья — задача о разборчивой невесте" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Задача была придумана М. Гарднером в 60х и решена Е. Дынкиным в 1965 \n", "\n", "Брошюра С. Гусейна-Заде с решением — https://www.mccme.ru/free-books/mmmf-lectures/book.25.pdf\n", "\n", "В классической постановке к принцессе по одному приходят принцы\n", "\n", "Когда принц приходит, она общается с ним и говорит либо \"да\", либо \"следующий\"\n", "\n", "Если принц услышал \"следующий\" — он обижается, уходит и больше никогда не возвращается\n", "\n", "Если принц услышал \"да\" — он берёт принцессу в жены и они живут вместе всю жизнь\n", "\n", "Если принцы закончились — принцесса идёт в монастырь\n", "\n", "Задача принцессы — максимизировать свои шансы сказать \"да\" лучшему принцу\n", "\n", "Возникает вопрос: по какой стратегии действовать принцессе, чтобы минимизировать свои шансы уйти в монастырь или выбрать не лучшего принца?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В сухом остатке у средневековой принцессы нет ограничений по времени — удачно выйти замуж это цель её жизни\n", "\n", "Но у неё есть ограничения по качеству — она хочет выйти замуж за лучшего принца" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ограничения задачи:\n", "\n", "—известно число принцов\n", "\n", "—есть общий порядок: то есть любые два принца сравнимы( и все сравнения непротиворечивы)\n", "\n", "—\"да\" можно сказать только один раз\n", "\n", "—нельзя менять прошлые решения" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Решение:\n", "\n", "Средневековая принцесса вынуждена принимать решение в условиях недостатка информации, потому что у неё нет других источников сведений, кроме как беседы с принцами-кандидатами\n", "\n", "Содержательно решение состоит из двух частей — этап разведки(exploration) и применения(exploitation)\n", "\n", "По Гусейну-Заде нужно пропустить первых n/e принцев и затем сказать \"да\" первому, кто лучше всех предыдущих:\n", "\"При этом вероятность получить в конце концов самого лучшего жениха из всех n претендентов равна примерно 0,368.\"\n", "\n", "Это и есть знаменитое правило 37%\n", "\n", "Вроде бы существует ряд уточнений, чтобы принцесса не осталась одна — в любом случае всегда можно сказать \"да\" последнему:)\n", "\n", "Нам же будет интересно, что делать, если ограничение по качеству более слабое — то есть принцессу устроит не самый лучший, а любой из топ-t\n", "\n", "Также есть вариант, который выглядит более справедливым — это вариант, когда её устроит любой из топ-t, но она будет тем счастливее, чем ближе он к топ-1\n", "\n", "Для случая, когда принцесса будет одинаково счастлива с любым из топ-2 принцев решение следующее:\n", "\"Таким образом, при большом количестве претендентов n и при m=2 оптимальная стратегия принцессы состоит в следующем. Она должна пропустить приблизительно 34,7% претендентов, не давая согласия на брак, из следующих приблизительно 32% (вплоть до 66,7% всех претендентов) давать согласие на брак только тому, кто лучше всех предыдущих, а из оставшихся 33,3% претендентов соглашаться и на второго по качеству среди уже прошедших. При этом вероятность удачного выбора (опять-таки при большом n, т. е. при n→∞) оказывается равной приблизительно 0,574. Таким образом, в этом случае шансы принцессы на удачный выбор (при оптимальной стратегии) больше 50%.\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Далее мы наконец готовимся перейти к описанию своего сервиса\n", "\n", "Мы используем ограничение по качеству на топ-t, но с учетом места в этом топ-t\n", "\n", "Возникает интересный вопрос: как мы определяем счастье в своём сервисе?:)\n", "\n", "Также мы вводим ограничение по времени, то есть наша принцесса хочет получить наилучшего принца за наименьшее время" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть между третьей и четвертой — задача о марьяже" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Более сложной задачей является задача о марьяже — https://ru.wikipedia.org/wiki/Задача_о_марьяже\n", "\n", "За решение этой задаче в 2012 году была присвоена Нобелевская премия по экономике\n", "\n", "Отличие данной задачи от предыдущей в том, что кроме ответов \"да\" и \"следующий\" можно отвечать \"может быть\"\n", "\n", "Разница в ограничениях задачи в том, что прошлые решения можно менять — \"может быть\" может измениться как в сторону \"да\", так и в сторону \"следующий\". Судя по всему \"да\" и \"следующий\" меняться не могут, а игра заканчивается, когда все \"может быть\" разрешены \n", "\n", "Данная задача уже ближе к реальности, но к сожалению для её реализации нужно вводить понятия состояния, итерации, а также строить конечный автомат — пока мы до этого не дошли\n", "\n", "Мы решили пока остановиться на реализации задачи о разборчивой невесте, но несколько осовременить её, в частности за счёт некоторых свойств Тиндера \n", "\n", "Таким образом наш сервис пытается найти баланс между средневековыми принцессами и пользователями Тиндера\n", "\n", "В некотором смысле мы делаем Тиндер для умных современных принцесс:)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть четвёртая — о сервисе" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Мы используем комбинацию свайповой и анкетной моделей\n", "\n", "То есть пользователи региструются, отвечают на ряд вопросов и загружают своё фото\n", "\n", "После этого созданный профиль видят другие пользователи и ставят \"да\" или \"следующий\"\n", "\n", "Пользователю также становятся доступны профили других пользователей\n", "\n", "Если два пользователя поставили друг другу \"да\" — возникает матч\n", "\n", "В результате матча пользователи получают доступ к контактам друг друга\n", "\n", "Сервис реализован в виде Телеграм бота\n", "\n", "Регистрация производится через приложение ВК" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Отличия от канонической принцессы**\n", "\n", "В случае средневековой принцессы считается, что все принцы по умолчанию поставили ей лайк\n", "\n", "В современном мире данное допущение неверно(*первое отличие*)\n", "\n", "Также каноническая принцесса из задачи готова принимать решения в условиях недостатка информации\n", "\n", "Однако если оставить ограничения на число лайков(один в базовом варианте) и запретить менять прошлые решения, то современные принцессы могут проявить изобретательность и сказать всем принцам \"следующий\", а затем найти понравившихся через сторонние сервисы\n", "\n", "Нам известно о таких сервисах, мы готовим одному из них предложение о партнёрстве\n", "\n", "Также мы в дальнейшем хотим коммерциализовать наши будущие сервисы или ввести внутренние покупки в существующие\n", "\n", "Но мы хотим сохранить своих пользователей, чтобы они возвращались к нам и пользовались нашими сервисами, поэтому ограничений на число лайков нет(*второе отличие*) и прошлые решения менять можно(*третье отличие*)\n", "\n", "Итого три отличия" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Отличия от Тиндера**\n", "\n", "—нет придурков\n", "\n", "Извращенцы и содержанки это настоящий бич сервисов знакомств\n", "\n", ">Дополнение: однако извращенцы находят друг друга и никому не мешают, а содержанки привлекают пользователей, которые являются их ЦА. Таким образом, ограничивать регистрацию для данных категорий пользователей смысла нет. Однако некоторые ограничения всё же должны быть — о них в следующей брошюре!\n", "\n", "—физическая локальность\n", "\n", "Наши пользователи находятся физически недалеко друг от друга\n", "\n", ">Дополнение: это тоже может быть не всегда полезно. Содержательным примером будет мужчина, который ищет любовницу вдали от дома. Предположительно люди также чаще пользуются сервисами знакомств за границей, а не у себя. Это говорит о том, что фактор локальности очень важен, но иногда в обратном смысле!\n", "\n", "Понять, насколько это существенно, можно на примере Pure — там удалённость является основой ранжирования поисковой выдачи\n", "\n", "Кстати, почитайте пользовательское соглашение Pure — это шедевр https://ru.pure.dating/terms\n", "\n", ">Эти два свойства достигаются за счет проверки принадлежности к сообществу МГУ при регистрации\n", "\n", "—количество конкурентов\n", "\n", "Когда пользователь ставит кому-то лайк, ему может быть интересно, а сколько ещё лайков получил этот кто-то — в нашем сервисе это называется конкуренцией первого рода\n", "\n", "После этого пользователь может от этого кого-то получить взаимный лайк и ему может стать интересно, а сколько ещё взаимных лайков у этого кого-то — это конкуренция второго рода\n", "\n", ">Мы показываем только количество конкурентов второго рода\n", "\n", "—уведомление о разрыве матча\n", "\n", "Пользователь получает уведомление не только о появлении матча, но и о пропадании матча\n", "\n", "Итого четыре отличия" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**О лайках и матчах**\n", "\n", "Важными представляются следующие моменты:\n", "\n", "—Пользователю не стоит знать, сколько лайков ему поставили\n", "\n", "Если много — можно зазнаться\n", "\n", "Если мало — расстроиться\n", "\n", "Поэтому мы не показываем число лайков в явном виде\n", "\n", "Также мы не показываем их и в неявном виде — через конкурентов первого рода\n", "\n", "Так, находчивая девушка может попросить поставить ей лайк лучшего друга детства и затем спросить, сколько у него конкурентов первого рода\n", "\n", "Поэтому мы показываем только количество конкурентов второго рода\n", "\n", "—Только пользователю стоит знать, сколько лайков он поставил\n", "\n", "Из информации о конкурентах любого рода не следует сколько лайков поставил пользователь \n", "\n", "Например, девушка может поставить лайк тому, кто ей лайк не поставил:(\n", "\n", "Таким образом только сам пользователь знает количество своих лайков\n", "\n", ">Стоит понимать, что матч это не лайк\n", "\n", "Есть такая проблема, когда у одного пользователя несколько диалогов в один момент времени и это неприятно другому пользователю, который видит число матчей\n", "\n", "Рассматривалась возможность ввести ограничение на число доступных матчей — раз уж нет ограничения на число доступных лайков\n", "\n", "Например, при ограничении на один матч, матчи показываются по одному и новый матч становится доступен только при разрыве предыдущего\n", "\n", "Но было решено не вводить данное ограничение из-за интересного следствия" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Интересное следствие**\n", "\n", "Возможность поставить более одного лайка, изменять прошлые решения и уведомления о разрыве матча порождают интересную дилемму\n", "\n", "Пусть есть два очень популярных человека\n", "\n", "Они поставили друг другу лайк и увидели, что у каждого из них по 20 матчей\n", "\n", "Им не хочется ставить друг друга в неудобное положение и они начинают снимать матчи с других пользователей\n", "\n", "В итоге 40 пользователей получают уведомления о разрыве матчей, а эти двое видят, на что они пошли ради общения друг с другом\n", "\n", "Дилемма в том, сколькими матчами пользователи готовы пожертвовать ради одного, но перспективного матча" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть между четвёртой и пятой — следующая брошюра" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В Тиндер люди идут ради общения в чатах\n", "\n", "Если бы это было не так, Pure бы не появился:)\n", "\n", "О том, зачем пользоваться нашим сервисом, в следующей брошюре:\n", "\"О воронке знакомств\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Часть пятая — современная принцесса" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Итак, мы подошли к самой важной части\n", "\n", "Задача похожа на задачу о разборчивой невесте\n", "\n", "Но нужно не просто максимизировать шансы получить одного из топ-t принцев с учетом его места в топе\n", "\n", "Нужно сделать это за наименьшее время\n", "\n", ">мы будем использовать комбинаторный, а не вероятностный подход" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В нашем сервисе время меряется как количество просмотренных анкет\n", "\n", "Временем на изменение предыдущих решений мы прененебрегаем\n", "\n", "Представляется, что время на первое решение >> времени на любое последующее решение" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Пусть у нас 1000 пользователей\n", "\n", "Пусть из них в топе находятся 10% — то есть 100\n", "\n", "Таким образом" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "n = 1000\n", "\n", "t = 100" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Вероятность того, что среди первых k элементов перестановки из [1, n] есть числа из [n - t, n] это" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from math import factorial\n", "\n", "def prob(n, k, t):\n", " #return 1 - factorial(n-k)*factorial(n-t)/(factorial(n)*factorial(n-t-k))\n", "\n", " i = n-t-k\n", " num = 1\n", " while(i != n - t):\n", " i = i + 1\n", " num = num * i\n", " #print(num)\n", " \n", " i = n-k\n", " den = 1\n", " while(i != n):\n", " i = i + 1\n", " den = den * i\n", " #print(den)\n", " \n", " return 1 - num/den\n", " \n", "#change n-t-k by n-k-t\n", "#if will swap t and k\n", "#now solute not to swap" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.09999999999999998" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prob(100, 1, 10)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.19090909090909092" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prob(100, 2, 10)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prob(99, 0, 10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Определим функцию P_1 для этапа разведки — exploration" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "k1 = tr\n", "\n", "P_1 = prob(n, k1, t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Определим функцию P_2 для этапа применения — exploitation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "k2 = k - tr\n", "\n", "P_2 = prob(n - tr, k2, t)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Теперь определим функцию, которую мы максимизируем" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "P_12 = P_1 * P_2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Важно понимать, что максимизируется именно произведение P_1 и P_2, а не, например, P_2 при условии достижения P_1 некоторого порога" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Итого для каждого заданного k мы можем найти такое tr, при котором P_12 максимально" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "max_P_12 = -1\n", "max_tr = -1\n", "k_with_max_tr=[-1]*(n + 1)\n", "k_P_12_with_max_tr = [-1]*(n + 1)\n", "\n", "for k in range(1, n + 1):\n", " #if k % 100 == 0:\n", " # print(k)\n", " for tr in range(1, k + 1):\n", " k1 = tr\n", " P_1 = prob(n, k1, t)\n", " k2 = k - tr\n", " P_2 = prob(n - tr, k2, t)\n", " P_12 = P_1 * P_2\n", " if P_12 > max_P_12:\n", " max_P_12 = P_12\n", " max_tr = tr\n", " k_with_max_tr[k] = max_tr\n", " k_P_12_with_max_tr[k] = max_P_12\n", " #print(k, max_tr, max_P_12)\n", " #uncomment line above to see the results" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Далее нам остался всего один шаг: найти такое k, для которого следующая величина будет максимальна — это наше счастье — оно зависит от времени, которое мы потратили на просмотр анкет — мы пытаемся минимизировать это время" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "820.3283794374119 73\n" ] } ], "source": [ "max_pleasure = -1\n", "max_pleasure_k = -1\n", "\n", "for k in range(1, n + 1 - t):\n", " pleasure = k_P_12_with_max_tr[k] * (n - k) - k\n", " if pleasure > max_pleasure:\n", " max_pleasure = pleasure\n", " max_pleasure_k = k\n", "\n", "print(max_pleasure, max_pleasure_k)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**О более простых стратегиях**\n", "\n", "Предложенная стратегия может быть интуитивно не очевидна\n", "\n", "Кроме того похоже на правду, что сложные модели не работают никогда, а простые работают в лучшем случае в среднем — шансы на развод положительно коррелирует со знаком разности количества ссор и секса — если знак положительный шансов на развод больше чем если знак отрицательный\n", "\n", "**Более простая стратегия**\n", "\n", "Задача та жа — за минимальное время получить максимально топового кандидата\n", "\n", "Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе\n", "\n", "Для применении этой стратегии нужно определить место кандидата в топе\n", "\n", "О том как это сделать — в следующей брошюре:)\n", "\n", "**Менее простая стратегия**\n", "\n", "Минимизируется произведение места в топе на количество конкурентов\n", "\n", "О том, в каких случаях уместно использовать данную стратегию, также в следующей брошюре;)\n", "\n", "Можно связать предыдущую стратегию с данной:\n", "\n", "Минимизируется произведение числа шагов(количество просмотренных анкет) на место в топе на количество конкурентов" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Итоги" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "В тексте данной брошюры можно встретить вопросы и отсылки к следующей брошюре: \"О воронке знакомств\"\n", "\n", "Ниже они собраны вместе в виде тем, которые в ней затронуты:\n", "\n", "\n", "* О балансе между средневековыми принцессами и пользователями Тиндера\n", "\n", "* Об ограничениях для некоторых категорий пользователей нашего сервиса\n", "\n", "* О проверки принадлежности к сообществу МГУ при регистрации в нашем сервисе\n", "\n", "* О том, зачем пользоваться нашим сервисом\n", "\n", "* Об определении места кандидата в топе\n", "\n", "* О контексте применения стратегий" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Напоследок небольшой спойлер — кажется, что нужно искать не тех, кто есть в нашем сервисе, а тех, кого в нём нет" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }