Hacker News new | past | comments | ask | show | jobs | submit login
Solving the Dating Problem with the SENPAI Protocol [pdf] (csail.mit.edu)
305 points by obi1kenobi on July 27, 2016 | hide | past | favorite | 108 comments



This already exists, it is called flirting.

Given two socially well adjusted participants it allows either party to back down without hurting the other parties feelings and allows everyone to save face. The person escalating the flirtation doesn't feel bad because they aren't outright denied and the respondee isn't put in the awkward situation of having to deny someone.

It also has the added benefit of allowing each person to get to know each other better and figure out if they actually have real 'chemistry' to begin with. Furthermore, attraction isn't binary, you might initially start chatting with someone with the intention of escalating the flirting process but figure out, hey, I just want to be friends with this person! With the SENPAI protocol you might just end up in an ill fated relationship with your would be friend


This technique is described in the paper:

2.4 The Start Out As Friends Protocol The Start Out As Friends Protocol (SOAP), as presented by [9], is summarized in Figure 1. In this protocol, Alice and Bob participate in many exchanges over a long period, transferring pieces of information that provide only incremental evidence of their responses. Over time, each party can become more and more confident in the other’s answer, until the probability of a mismatch is low enough that a JMAP exchange becomes feasible. Unfortunately, the runtime of this protocol may be inordinately long in some cases, and deriving evidence from the individual transmissions can be difficult. There are also highly complex failure modes when dealing with a malicious adversary, as Munroe illustrates in his paper.

[9] R. Munroe. Friends. May 2008. https://xkcd.com/513/


That's not the same thing.

Flirting does not require that you first be friends with someone and certainly doesn't require a runtime of many months. A successful flirtation can happen within a few minutes.


Flirting doesn't require a runtime of months, but then nor does SOAP. SOAP only specifies a "long period", but as they say, a minute can seem like hours.


Flirting has a high signal to noise ratio.

There are also many issues with unintentional signalling.


Seems like the sort of problem a deep neural network would be great for. I've already got some good hardware for it, but I'm a little apprehensive about acquiring enough training examples.


Just put together a research pool so you can generate a solid baseline. I'm sure you could use Amazon Mechanical Turk to get a large number of able participants at minimal cost to your wallet and pride.


It is for people that aren't socially adept (which one can learn btw) and this is of course also one important criteria for sexual selection.

My view is that it is not in the interest of women (who mostly do the selecting while men do the approaching) to use a process for selection that obfuscates if the approaching person is socially adept or not.

It is maybe just my experience, but generally women do know which men are interested and which are not, even if the male didn't make an approach yet.


Do you have a set of suggested resources for learning to be social adept. Its too late for me, but I am hoping to teach it on to my version 2.0 systems.



Long story short: use their names and feed their egos. Ignore all the stuff about sincerity and real connection, since the author does.


I called it a 'good start' for a reason. Obviously there is a lot more to social success than charm and flattery, but they are important regardless.


You could say that if you've made it to v2.0, you have already been evolutionarily selected in your favor.


If you have version 2.0 systems, how'd you do that without being socially adept? Did you adopt them as a single person or something?

If you've managed to convince someone to procreate with you (and multiple times at that, apparently), then you're by definition socially adept.


Try practice?


That's the whole point. The noise provides plausible deniability.


> Given two socially well adjusted participants

But socially poorly-adjusted folks want love too!


> Given two socially well adjusted participants

So non-socially-well-adjusted, raised-on-the-internet types shouldn't get to date? Your comment is tautological and merely says that people who are good at dating are good at dating.


You might as well argue that the SENPAI paper implies that people who aren't comfortable with homomorphic encryption shouldn't get to date.


>who aren't comfortable with homomorphic encryption shouldn't get to date.

It's 2016, homophobia should be shunned anyway.


It would have been funny, had you written Homomorphobia.


Rather, the SENPAI protocol makes dating available to people who aren't socially adept but are comfortable with homomorphic encryption. Socially adept people can continue to flirt.


I'm not sure what your point is?

"So people who never play football shouldn't get to score goals?"


I think it's closer to the other way around. People who can't score goals can still contribute in a football game, for example as goalkeepers. But if you select your team based on who's the best at scoring goals, they're not going to get a chance to demonstrate their goalkeeping ability.

Similarly, I think there are a lot of people who are bad at flirting but would make good romantic partners for the people they're interested in. But being bad at flirting means they often don't get a chance to demonstrate the other qualities they could bring to a relationship.


No one said that, but these people need to either work on improving themselves (which most people definitely can) or they have to deal with the fact that a vast majority of women will never be interested in them.

There is no IT solution that we could come up with to change this and it wouldn't even be desirable in the first place.

Sexual selection has the purpose to ensure that only people with desirable traits get to breed and while it isn't perfect it is my opinion that it still is the best process known to us.


Yet how would I be viewed if I applied the same logic to acquiring goods and services? If you aren't able to earn a living then you should focus on improving yourself. If you can't then you are SOL.

It's funny how high production skills are forcefully shared but there is little effort to even try to share social skills. If anything, being socially awkward is met with scorn. Maybe we should swap the name to socially poor and people would have some pity


> If you aren't able to earn a living then you should focus on improving yourself.

Of course everyone should try hard to do this.

> It's funny how high production skills are forcefully shared but there is little effort to even try to share social skills.

What skills are forcefully shared? And how can you possibly share social skills? Or are you suggesting that government should allocate sexual partners to everyone? I don't understand what point you are trying to make here.

The bottom line is that most could significantly improve their social skills and confidence but many chose to live in denial because the first step is frightening and actually the hardest part. You just have to practice this skill like everything else in life and learn to not take judgement of others too serious.


If social skills can be learned by practice, then we can share by teaching. Maybe force 15% of one's time socializing is done so with those considered socially awkward. Socializing, not sex.

My actual point is that society says we should help those who wasted an education by giving up part of our lives (income tax is a time tax on the average worker), but society says that someone who wasted their teen years not developing social skills is just a loser. This is a troubling view.

If one considers a concept of social wealth then there seems to be a resource transfer from the financially well off to the socially well off without a response in kind.

In the worst case consider a child who was bullied and turned to tech, who gained financially useful tech skills but missed out on social skills. Once they grow into an adult they are then taxed to support those who picked on the 'geeks and nerds' and who scorned education in favor of social standing among their peers. So the bullies get to enjoy financial support and the dividends of their social skills while the 'geeks and nerds' get only the dividends of their financial skills. Seems we should either provide relevant welfare for both or neither... but if one side is going to be better at pushing a position that is to their advancement I can guess which.

And of course this doesn't account for millions of nuances in each individual life that are exceptions, like the child who couldn't learn because they were too focused on their hunger.

Maybe we can start by considering those without social skills as socially poor instead of just losers.


> There is no IT solution that we could come up with to change this and it wouldn't even be desirable in the first place.

Tinder has worked well for some people I know


Ding ding ding. The whole point of flirting is that it's a gradual (potentially) escalation path with a built in escape route / plausible deniability (for having a romantic interest in someone). It's like tossing across a thin fishing line and then the other person attaching a length of cord to while you pull it back and then attach a rope to, and so on. At any point any party can back down or back out without feeling hugely awkward or embarrassed, and to proceed it requires the cooperative participation of both people. It's quite an elegant system, in fact, it's a shame to many people are baffled by it.


The success of Tinder demonstrates demand for a faster and less ambiguous protocol. SENPAI is basically Tinder without a trusted third party.


Tinder would be MFP, which is quite effective with sufficient trust in the "F" (Tinder).


i wonder where harassment fits into flirting given that the second party can have a completely negative response to flirtatious advances. also flirting can create an immediate awkward moment as it is very similar to the "just man up and ask" protocol.


While JMAP doesn't work particularly well in a one-to-many relational structure it can be made decidedly less awkward in a one-to-one relational structure if you are willing to invest some social cycles up front.


> In his presentation of the original protocol, Aaronson suggests that zero-knowledge proofs can be used to prevent cheating. However, we find this approach unsatisfying, partly because zero-knowledge proofs would make the protocol much more unwieldy and time-consuming, and partly because we have no clue how to actually implement ZKP in this context

I am in love with the honesty in this.


> An unavoidable issue with group SENPAI exchanges is the problem of love triangles [...] The authors’ recom- mended solution is polyamory [...] We remark that this situation is just generally shitty, and seri- ously, what do you expect us to even do here?

I love this


ZKP is also useless in this case because there's no way to enforce dating if the ZKP finds a match. Anybody who wants to detect a crush can simply lie about having one themself.


Except the presented protocol already does not prevent this attack (which they acknowledge in the paper).

ZKP still provides the property that cheating will be detected, which is all that is required to satisfy the papers security definition.


Garbled circuits can be used for the ZKP protocol, and in this case the circuit would just be a single AND gate. https://www.math.ucla.edu/~tdokos/notes_files/garbledCircuit...


For those not getting the reference, "senpai" is a Japanese honorific used to address one's upper classman in school.

A common trope in Japanese medium is that a character will have a crush on a senpai (equivalent to a prefect or hall monitor in that context), only for them to be utterly oblivious to it.

http://tvtropes.org/pmwiki/pmwiki.php/Main/SempaiKohai

This is a witty paper, as other commenters are noting.


> For those not getting the reference, "senpai" is a Japanese honorific used to address one's upper classman in school.

Not just in school. In work situations as well. Note that this is no real equivalent for the opposite (there is Kouhai but it's not used at all in the same way).


How is "kouhai" used? Is it not the same as hoobae (Korean)?


Kouhai is not used behind a person's name. And you can usually refer to a senpai just by calling them "senpai" and whoever you are talking to would understand who are refering to. But "kouhai" is never used like what I described above - it's purely an adjective to describe the position of a junior student.


I don't know any Korean, but the difference in Japanese is that you (generally) don't address people with kōhai. The younger one usually says '<name>-senpai' or 'senpai', the elder just '<name>'.

They're really not that different.


> The younger one usually says '<name>-senpai' or 'senpai', the elder just '<name>'.

Really? I thought use of a bare name was only for intimate relationships.


<name> here is the family name, which in a language without idiomatic spoken pronouns, is how you talk about people.


> Really? I thought use of a bare name was only for intimate relationships.

Not only. Even at work you can refer to your colleagues without the honorific -san in some specific contexts.


Including vocative address?


It could also be <name>-san, <name>-kun, or <name>-chan.


> A common trope in Japanese medium is that a character will have a crush on a senpai

There is the whole "Notice me senpai" meme that is making the rounds among the trendy youths, I hear.

1. http://knowyourmeme.com/memes/i-hope-senpai-will-notice-me


I think you see that trope mainly in hentais and very rarely in regular romcoms, as far as animes go.


That's not true. I've stopped watching seasonal anime but the last time I did (2014), every single comedy/romance anime had that trope. Sometimes it's just admiration and not romance but it seems to always be there.


It's most of the times admiration and not romance, and is most of the times a comedy element and not part of the main plot. That's very different from what OP stated.


Very common in Slice of Life/Highschool Life shows. It is essentially the Japanese equivalent of the Football Star/Quarterback dating the Head Cheerleader trope.


I strongly disagree. The typical trope in SoL highschool romcom animes is the love triangle featuring a rather "dense" MC, a tsundere and a childhood friend, the three members of the triangle being classmates (so no "senpai"/underclass-mate relationships).

Examples: Toradora!, Golden time, Kokoro connect, White Album 2, ... to name the most popular ones.

Those that don't feature a love triangle (Ore Monogatori!, Lovely Complex, Kimi ni Todoke,... ) don't have sempais either.

I simply can't remember a romcom anime in which the sempai relationship plays a significant role, if present at all. In any case, that's not a dominant trope in the genre.


Yotsugi from Monogatari series, Kuriyama from Kyoukai no Kanata, Azusa from K-On (more-so admiration of Mio than romantic), Free!, Gochuumon wa Usagi desu ka? just to name a few.

If MAL wasn't for whatever reason blocked by my work's filter I'm sure I could come up with 10+ more from relatively popular shows (Monogatari, Beyond the Boundary, and K-On! being the most popular)


I still don't agree. Love triangles are very common. Tsunderes are very common. Sempais are less common.

"In terms of pop culture however, senpai is a word that has taken on a life of its own. Now it seems that everyone and their uncle on both sides of the Pacific are throwing the word around like it's nothing at all. Anyone who is slightly older than you might or might not have a crush on is now being referred to as senpai. Will it become yet another buzz word that invades popular culture in the west? It's certainly possible." [0]

Anyway. Calling it the "BAKA protocol" would have fit more in more than one way.

[0] http://myanimelist.net/featured/645/Senpai_and_Kouhai_Relati...


> Unfortunately, this protocol is completely dependent on the trustworthiness of Trent, as they receive all of Alice and Bob’s information and are entirely free to manipulate the results of the protocol. If Trent has been compromised, perhaps by a nation-state adversary, Alice and Bob’s love life will be completely in the hands of a malicious attacker

Beautifully done.


"nation-state adversary" and "logical AND" both cracked me up. It is surprising to see common themes with my own research on this topic: "thinking too much".


This whole paper was great. It starts heavy on the humor but then also delivers just enough actual cryptographic protocol to make the lead-up worth it. This bit at the end was my favorite:

  As is noted in [1], if Alice simply suggests to Bob that
  they carry out a SENPAI exchange, this in and of itself is
  indicative of interest on Alice’s part. Thus, the only nonawkward
  way to actually use the SENPAI protocol is to
  assemble large groups of people, and have every pair of
  people carry out the protocol.


I'm interested in the consequences of, instead of "everyone" carrying out SENPAI, having a more efficient STB Matching System (Spin The Bottle).

Sure, it could backfire: interested parties may fall victims of the universe's Random Number Generator, but it makes for some interesting Game Theory dynamics, which I call the Tinder Card Stack Dilemma.

Any one party could be more willing to express interest in any of the other parties (assigned by STB), if they believe there is a low chance of them being matched with someone else they are more interested in.

On the other hand, they could become more picky, and only express interest in parties they are very interested in, rejecting others because they believe there is a high chance of them being matched with greater interests.

There is a definite trade off between efficiency and overall population happiness when choosing between STB and the solution described in the paper. Because STB is more efficient, it ends up being way more scale-able. But bigger populations greatly intensify the TCSD.


TLDR; (fta)

    Alice and Bob should each
    learn the logical AND of their
    responses, and nobody should
    learn any other information
The SENPAI protocol is proposing a way to do this with cryptography. There's a historical review of other proposed protocols (AMP, JMAP, MFP, SOAP, YGMP, SLP) along with their deficiencies. A SENPAI-MTT protocol is also considered that allows for non-binary interest (MTT=More Than Two). They propose foiling protocol cracking by quantum factoring by basing future SENPAI protocols on lattice based cryptographic methods.


The entire site hosting this is hilarious - it appears to be an April Fools parody of an academic tech conference and it's very well executed.

"Submissions are double blind and author names must be removed. On the published copy, authors must be ordered by descending number of vowels."


Thanks- I initially thought this was hosted on arxiv (it's on a MIT server).

This paper from the same conference also looks good:

http://sigtbd.csail.mit.edu/pubs/veryconference-paper5.pdf

"Locally Bijective, Non-Noetherian, Ultra-Liouville Random Variables and Parabolic Lie Theory"

"Good" as in "it was probably generated by an LSTM RNN".

Full papers listing here:

http://sigtbd.csail.mit.edu/pubs/

And main conference page:

http://sigtbd.csail.mit.edu/

For the benefit of other July fools like me :0

P.S.

This one is of special interest to me: Evident Logic, a logic programming language based on a new logic, made special by "not the rules that it has, but the rules it lacks, so we wish the reader good luck in figuring that out":

http://sigtbd.csail.mit.edu/pubs/veryconference-paper8.pdf


Any interpersonal conflicts of interest must be declared in the form of a passive aggressive email sent to the PC chair. In the event an interpersonal conflict of interest is declared, the validity of the interpersonal conflict of interest will be determined by the PC. The best conflict of interest emails will be anonymized and includeed in the conference proceedings.

If you are using LaTeX to typeset your paper, then we strongly suggest that you use this LaTeX class file (with the ‘sigtbd’ class option) and template. If you are using Microsoft Word, we recommend you give up on following any of the formatting requirements and submit in whatever format you please.


Tangential: can somebody explain to me how same-sex speed-dating is sequenced? Two-sex is easy as one sex remains static while the other rotates around, but I can't figure out a solution for single-sex.

Update: a solution that satisfies being practical to organise and that lets you talk to all participants

Update2: http://math.stackexchange.com/questions/55439/gay-speed-dati...


I don't know how they actually do it, but this would work: https://en.wikipedia.org/wiki/Graph_factorization#Complete_g...


This way you see everyone, but have a logistical nightmare.


All you need to do is set it to music, so that at the end of the set each 1-factor of the factorization has been represented for a verse. You'd probably need a distinct song and pattern for each group size.

If your dancers are some mixture of male/female/het/homo/bi such that you don't have a complete graph or other easy problem then you may need to have a computer-augmented dance caller.


A solution: everyone is sequentially numbered. Evens rotate left one round, odds rotate right the next round. That way everyone has to move the same amount (assuming an even number of participants).


If I understand you correctly, not everyone then sees everyone else, which is likely to breed customer dissatisfaction


That's a pre-existing problem.


You divide the people into two groups arbitrarily.


While I suspect that this is true in practice, this is the disadvantage that you don't talk to everyone, even though you can see them.


I have a solution: divide everyone into two groups arbitrarily. Then, tell everyone to look at everyone in their group, and inform them they won't be able to talk to any of those people. Then offer anyone who's unhappy with this (because they see someone in their group they'd like to chat with) the option of switching sides. Do it one at a time, until everyone's happy with the arrangement (however long this takes), then if one group is too large, arbitrarily move some people to the smaller group and repeat. When time runs out (because you've booked the venue for X hours), then send everyone home even though they never actually got to do the speed-dating at all.


> The Just Man Up And Ask Protocol (JMAP) is often proposed as a naive solution to the Dating Problem...

Man, this paper is golden!


Super fun paper.

It seems like their modification to Aaronson's algorithm would also work for Yao's garbled circuits, i.e.

1. Alice generates a long random bitstring s, and publishes hash(s)

2. Alice crafts a garbled circuit with just one AND gate, where the false output is 0+s, and the true output is 1. Alice sends the circuit and her input to Bob.

3. Bob gets his input from Alice using oblivious transfer. He evaluates the circuit, publishing the result.

4. If the result starts with 0, Bob verifies that hash of the rest of the string matches the hash published by Alice. Alice also checks to make sure the rest of the string matches her original s.


If you want to use heavy handed crypto you can utilise multiparty computation protocols that are secure against malicious parties.

For the 2PC case this problem was solved way back in the 1980s Andrew Yao.


The paper is very helpful for the arbitration of a "simple, binary phenomenon". Section 4.1 correctly investigates ternary responses.

However, logic may only be used if a common GND is accepted. If Alice does not believe in absolute truth, there is no way that trust can be established. Analogue systems may not approach 1, only digital logic can provide "TRUE" love.

Moral relativism is commonly professed. However, I theorise that an absolute 0 point can be readily established.

"Is cheating in relationships always wrong?"

If a common GND cannot be established this way, then the crush may be ended without wasting more time running the simulation.


This has already existed for ages using trusted third parties. A while ago on Facebook there were things were you could say which of your friends you fancy, and if you match it sends you both a message.

The problem is there's no real disincentive just to say 'yes' to everyone, just to see who said yes back. Kind of like always swiping right on Tinder (although I'm sure they punish you for that in some way).


While reading i had to scratch my head and ask myself, is this serious or is someone pulling my leg.


The paper was submitted to SIGTBD 2016. From the website (http://sigtbd.csail.mit.edu/):

SIGTBD's emphases includes innovative, elegant (to the point of simplicity) and creative approaches for solving problems that are not traditionally served by the academic community. These problem spaces may be obsolete or unrealistic even by academic standards and are often of debatable research taste.


dlgeek 7 hours ago [-]

The entire site hosting this is hilarious - it appears to be an April Fools parody of an academic tech conference and it's very well executed. "Submissions are double blind and author names must be removed. On the published copy, authors must be ordered by descending number of vowels." reply


Uhm, how do one compute the cubic root of x^3 modulo N?


Is the protocol described in Aaronson's algorithm actually sound? I can't seem to make sense of it myself. An example sequence would help.


I'm curious what happened to paper number 6


"There is no paper number six!"


Who is the Author of the paper? Usually people put that at the top.


This is a preprint from a conference with a double blind submission process, which is why the author names are not present. According to the agenda the authors are S. Dukhovni, J. Weisblat, and I. Chung.


I can't find these people using google.


They are undergraduates at the EECS department.


First the underwear sorting hat, and now this.

MIT, never change.


[10] is the best


先輩のが多きくて硬い。 カッコいい!


Use 大きくて, not 多きくて

the former is 'big', the latter is 'many'


You have to watch that Windows IME like a hawk.


"Notice me SENPAI!"


There is a dating problem?


> The problem concerns two agents Alice and Bob (or Alex and Bob, or Alice and Beatrice), each of whom may or may not have a crush on the other. Each is initially unaware of the other’s feelings, and if they have a crush, they would like to know whether the other does as well; however, each would like to reveal their crush only if the other shares the interest.


This does not just apply to crushes but also more specific sexual interests. Unfortunately, the fact that you want your partner to use a service such as this already leaks that your interest is unusual or socially frowned upon.


That is not necessarily a problem. I would not mind leaking the fact that there exists a sexual interest I have that is embarrassing, as long as I do not leak what that interest is. In fact, I have publicly said that I have sexual preferences that I do not want to be known on multiple occasions.

Incidently, an MFP like service already exists for this usecase [0].

[0] http://mojoupgrade.com/


What percentage of people have an interest like that though? If I had to pull a number from nowhere I would say at least 50%, so using the service shouldn't be particularly damning.


I thought Tinder had it solved...


Tinder is Trent in this protocol. As long as both Alice and Bob trust Trent, that works. But Trent can cheat.


See Ashley Madison?


And then the Russians might control our love lives!


I'm prepared to give them a go at this point, they can't do a worse job of it than me.


What is this dating thing everyone seems to be talking about?




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: