Алгоритм для соединения людей с помощью сообщений

Представьте, что у вас есть куча людей, которые все хотят найти партнера из этой группы людей. Каждый человек может сделать объявление для всей группы или любому конкретному человеку. Цель состоит в том, чтобы все они попадали в пары, где это возможно.

Новые пользователи могут войти в группу, пока процесс сопряжения продолжается. Как только два человека спариваются максимально оптимально, они выпадают из группы.

У каждого человека есть "оценка" для каждого другого человека. По возможности, люди должны быть вместе с партнерами с более высокими показателями. Тем не менее, более важно, чтобы люди находили пары вообще, чем эти пары были строго оптимальными. Таким образом, разумно, например, иметь двух человек "условно спаренных", а затем немного подождать, чтобы увидеть, подходит ли лучший партнер для обоих; если этого не делать, тогда правильно соедините два и они выпадают из группы.

Нет центрального элемента управления: вся работа должна выполняться путем передачи сообщений между людьми (или трансляции для всей группы).

Какой лучший алгоритм для этого?

Очевидно, проблема, которую я пытаюсь избежать, заключается в том, что A случайно выбирает B и говорит "эй, будь моим партнером", и в то же время B говорит C "эй, будь моим партнером". Кроме того, A не может просто объявить, что "кто-то будет моим партнером!" потому что A получит ответы от всех, и если B также объявил, что "кто-то будет моим партнером", B должен ответить на объявление или нет?

Это похоже на isa http://en.wikipedia.org/wiki/Stable_roommates_problem, но (а), что о поиске "стабильного" (строго оптимального) решения, которое полезно, но не требуется в моей проблеме, и (б) он предполагает, что группа фиксирована по размеру и не изменяется, тогда как моя проблема позволяет новым участникам группы участвовать в "выборах в парные".

Ответ 1

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

Также чрезвычайно важно знать, является ли эта мера доброты симметричной. Является ли оценка (A, B) = оценка (B, A)? Транзитивность также полезна, если ее можно установить. Но это кажется маловероятным.

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

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

Это интересная проблема, но я не уверен, что она очень хорошо определена.

Ответ 2

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

Каждый человек начинает с некоторого фактора липкости = 0. Начните с выбора временного партнера (через некоторый разумный эвристический/случайный хеш/что-то еще)

Затем перебираем что-то вроде этого:

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

Ответ 3

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

сейчас только 3 человека A B C

A трансляции

B сохраняет, {A, msg: xxx}

B широкие нажатия {A, msg: xxx} {me (B), msg: yyy}

A, {B, msg: yyy}

Хранилища

C, {A, msg: xxx}, {B, msg: yyy}

D присоединяется, широко применяется с запросом всех людей

A отправляет обратно {B, msg: yyy} {me (A), msg: xxx}

B отправляет обратно {A, msg: xxx} {me (B), msg: yyy}

C не является широким литьем, поэтому ничего не отправляйте

D обрабатывает все входящие запросы и делает некоторый анализ для определения возможных людей в области

A и B соответствуют

A, B трансляции удаляют A, B

C, {}

D, {}